数値を負の基数表現に変換する

数字 n そしてマイナスベース ネグベース が与えられているので、n をその負の基数で表す必要があります。負の塩基は正の塩基と同様に機能します。たとえば、基数 2 では、ビットを 1 2 4 8 などに乗算して、10 進数で実際の数値を取得します。基数 -2 の場合、10 進数の数値を取得するには、ビットに 1 -2、4 -8 などを乗算する必要があります。
例:

リッスンポート

Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13

同じ手順で数値を任意の負の基数で表すことができます (参照一週間詳細については)。簡素化のため (出力で A B などの文字を取り除くため)、基数を -2 から -10 までの間のみにします。

この問題は、正の基数を使用した問題の解決と同様に解決できますが、覚えておくべき重要な点は、正の基数を使用するか負の基数を使用するかにかかわらず、剰余は常に正になるということです。ただし、ほとんどのコンパイラでは、負の数を負の数で除算した結果は 0 に向かって丸められ、通常は負の剰余が残ります。
したがって、負の剰余を取得するたびに、以下のように正に変換できます。

Let n = (?negBase) * quotient + remainder = (?negBase) * quotient + negBase ? negBase + negBase = (?negBase) * (quotient + 1) + (remainder + negBase). So if after doing 'remainder = n % negBase' and 'n = n/negBase' we get negative remainder we do following. remainder = remainder + (-negBase) n = n + 1   Example :   n = -4 negBase = -3 In C++ we get remainder = n % negBase = -4/-3 = -1 n = n/negBase [Next step for base conversion] = -4/-3 = 1 To avoid negative remainder we do remainder = -1 + (-negBase) = -1 - (-3) = 2 n = n + 1 = 1 + 1 = 2.

したがって、負の剰余が得られる場合は、基数の絶対値を加算し、商に 1 を加算することで、剰余を正にします。
上記で説明したアプローチは以下のコードで実装されます

Javaバイナリツリー

C++

// C/C++ program to convert n into negative base form #include    using namespace std; // Utility method to convert integer into string string toString(int n) {  string str;  stringstream ss;  ss << n;  ss >> str;  return str; } // Method to convert n to base negBase string toNegativeBase(int n int negBase) {  // If n is zero then in any base it will be 0 only  if (n == 0)  return '0';  string converted = '';  while (n != 0)  {  // Get remainder by negative base it can be  // negative also  int remainder = n % negBase;  n /= negBase;  // if remainder is negative add abs(base) to  // it and add 1 to n  if (remainder < 0)  {  remainder += (-negBase);  n += 1;  }  // convert remainder to string add into the result  converted = toString(remainder) + converted;  }  return converted; } // Driver code to test above methods int main() {  int n = 13;  int negBase = -2;  cout << toNegativeBase(n negBase);  return 0; }

Java

// Java program to convert n into  // negative base form class GFG { // Method to convert n to base negBase static String toNegativeBase(int n int negBase) {  // If n is zero then in any base  // it will be 0 only  if (n == 0)  return '0';  String converted = '';  while (n != 0)  {  // Get remainder by negative base   // it can be negative also  int remainder = n % negBase;  n /= negBase;  // if remainder is negative   // add Math.abs(base) to it   // and add 1 to n  if (remainder < 0)  {  remainder += (-negBase);  n += 1;  }  // convert remainder to String add into the result  converted = String.valueOf(remainder) + converted;  }  return converted; } // Driver Code public static void main(String[] args) {  int n = 13;  int negBase = -2;  System.out.print(toNegativeBase(n negBase)); } } // This code is contributed by 29AjayKumar

Python3

# Python 3 program to convert n into  # negative base form # Method to convert n to base negBase def toNegativeBase(n negBase): # If n is zero then in any base it  # will be 0 only if (n == 0): return '0' converted = '01' while (n != 0): # Get remainder by negative base  # it can be negative also remainder = n % (negBase) n = int(n/negBase) # if remainder is negative add  # abs(base) to it and add 1 to n if (remainder < 0): remainder += ((-1) * negBase) n += 1 # convert remainder to string add # into the result converted = str(remainder) + converted return converted # Driver Code if __name__ == '__main__': n = 13 negBase = -2 print(toNegativeBase(n negBase)) # This code is contributed by # Surendra_Gangwar

// C# program to convert n into  // negative base form using System; class GFG { // Method to convert n to base negBase static String toNegativeBase(int n int negBase) {  // If n is zero then in any base  // it will be 0 only  if (n == 0)  return '0';  String converted = '';  while (n != 0)  {  // Get remainder by negative base   // it can be negative also  int remainder = n % negBase;  n /= negBase;  // if remainder is negative   // add Math.Abs(base) to it   // and add 1 to n  if (remainder < 0)  {  remainder += (-negBase);  n += 1;  }  // convert remainder to String add into the result  converted = String.Join('' remainder) + converted;  }  return converted; } // Driver Code public static void Main(String[] args) {  int n = 13;  int negBase = -2;  Console.Write(toNegativeBase(n negBase)); } } // This code is contributed by Rajput-Ji

JavaScript

<script> // JavaScript program to convert n into // negative base form // Method to convert n to base negBase function toNegativeBase(n negBase) {  // If n is zero then in any base  // it will be 0 only  if (n == 0)  return '0';  let converted = '01';  while (n != 0)  {  // Get remainder by negative base  // it can be negative also  let remainder = (-1)*(Math.abs(n) % Math.abs(negBase));  n = parseInt(n/negBase);  // if remainder is negative  // add Math.abs(base) to it  // and add 1 to n  if (remainder < 0)  {  remainder += ((-1)*negBase);  n += 1;  }  // convert remainder to String add into the result  converted = remainder.toString() + converted;  }  return converted; } // Driver Code let n = 13; let negBase = -2; document.write(toNegativeBase(n negBase)'
'); // This code is contributed by shinjanpatra </script>

出力：

時間計算量: の上）
補助スペース: ○(1)
参照：
https://en.wikipedia.org/wiki/Negative_base

クイズの作成