Eine Zahl N und eine negative Basis negBase uns gegeben wird, müssen wir n in dieser negativen Basis darstellen. Die negative Basis funktioniert ähnlich wie die positive Basis. Zum Beispiel multiplizieren wir in der Basis 2 Bits mit 1 2 4 8 usw., um die tatsächliche Zahl im Dezimalformat zu erhalten. Im Fall der Basis -2 müssen wir die Bits mit 1 -2, 4 -8 usw. multiplizieren, um die Zahl im Dezimalformat zu erhalten.
Beispiele:
Zeichenfolge Java indexof
Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
Mit demselben Verfahren ist es möglich, eine Zahl in jede negative Basis darzustellen (siehe Eine Woche für Einzelheiten). Der Einfachheit halber (um die Zeichen A, B usw. in der Ausgabe zu entfernen) erlauben wir, dass unsere Basis nur zwischen -2 und -10 liegt.
Wir können dieses Problem ähnlich wie das Problem mit positiven Basen lösen, aber es ist wichtig, sich daran zu erinnern, dass der Rest immer positiv ist, egal ob wir mit positiver oder negativer Basis arbeiten, aber in den meisten Compilern wird das Ergebnis der Division einer negativen Zahl durch eine negative Zahl gegen 0 gerundet, wobei normalerweise ein negativer Rest verbleibt.
Wenn wir also einen negativen Rest erhalten, können wir ihn wie folgt in einen positiven Rest umwandeln
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.
Wenn wir also einen negativen Rest erhalten, machen wir ihn positiv, indem wir den absoluten Wert der Basis dazu addieren und 1 zu unserem Quotienten hinzufügen.
Der oben erläuterte Ansatz wird im folgenden Code implementiert
Karten JavaC++
// C/C++ program to convert n into negative base form #include
// 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
# 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
<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>
Ausgabe:
11101
Zeitkomplexität: AN)
Hilfsraum: O(1)
Referenz :
https://en.wikipedia.org/wiki/Negative_base