Число п и отрицателна основа negBase ни е дадено, трябва да представим n в тази отрицателна основа. Отрицателната основа работи подобно на положителната основа. Например в основа 2 умножаваме битовете до 1 2 4 8 и така нататък, за да получим действителното число в десетична система. В случай на основа -2 трябва да умножим битовете с 1 -2 4 -8 и така нататък, за да получим число в десетична система.
Примери:
java двойка
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
// 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>
Изход:
11101
Времева сложност: O(N)
Помощно пространство: О(1)
Справка:
https://en.wikipedia.org/wiki/Negative_base