Skaičius n ir neigiama bazė negBase mums duota, mes turime atstovauti n toje neigiamoje bazėje. Neigiama bazė veikia panašiai kaip teigiama bazė. Pavyzdžiui, 2 bazėje mes padauginame bitus iki 1 2 4 8 ir tt, kad gautume tikrąjį skaičių po kablelio. Esant bazei -2, turime padauginti bitus iš 1 -2 4 -8 ir tt, kad gautume skaičių po kablelio.
Pavyzdžiai:
urfi javed
Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
Galima pateikti skaičių į bet kurią neigiamą bazę ta pačia procedūra (žr Savaitė Norėdami gauti daugiau informacijos). Paprastumo dėlei (siekdami atsikratyti A B ir tt simbolių išvestyje) leidžiame bazei būti tik nuo -2 iki -10.
Šią problemą galime išspręsti panašiai kaip sprendžiant problemą su teigiamomis bazėmis, tačiau svarbu atsiminti, kad liekana visada bus teigiama, nesvarbu, ar dirbame su teigiama baze, ar su neigiama baze, tačiau daugumoje kompiliatorių neigiamo skaičiaus padalijimo iš neigiamo skaičiaus rezultatas suapvalinamas iki 0, paprastai paliekant neigiamą likutį.
Taigi, kai tik gauname neigiamą likutį, galime jį konvertuoti į teigiamą, kaip nurodyta toliau
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.
Taigi, kai gausime neigiamą likutį, padarysime jį teigiamu, pridėdami absoliučią bazės vertę ir pridėdami 1 prie mūsų koeficiento.
Aukščiau paaiškintas metodas įgyvendinamas žemiau esančiame kode
skaitytuvas.next 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>
Išvestis:
11101
Laiko sudėtingumas: O(N)
Pagalbinė erdvė: O(1)
Nuoroda:
https://en.wikipedia.org/wiki/Negative_base