Egy szám n és negatív bázis negBase adott nekünk, n-t kell képviselnünk abban a negatív bázisban. A negatív bázis hasonlóan működik, mint a pozitív bázis. Például a 2. bázisban megszorozzuk a biteket 1 2 4 8-ra és így tovább, hogy a tényleges számot decimális formában kapjuk meg. Alap -2 esetén meg kell szoroznunk a biteket 1 -2 4 -8-cal és így tovább, hogy decimális számot kapjunk.
Példák:
mi az a számítógép
Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
Lehetőség van egy számot bármilyen negatív bázisba ábrázolni ugyanazzal az eljárással (lásd Egy hét részletekért). Az egyszerűség kedvéért (hogy megszabaduljunk az A B stb. karakterektől a kimenetben) csak -2 és -10 közé engedjük alapunkat.
Ezt a problémát ugyanúgy meg tudjuk oldani, mint pozitív bázisokkal, de fontos megjegyezni, hogy a maradék mindig pozitív lesz, akár pozitív, akár negatív bázissal dolgozunk, de a legtöbb fordítóprogramban a negatív szám negatív számmal való osztásának eredménye 0-ra kerekítve, általában negatív maradékot hagyva.
Tehát amikor negatív maradékot kapunk, az alábbiak szerint pozitívvá alakíthatjuk
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.
Tehát amikor negatív maradékot kapunk, akkor azt pozitívvá tesszük úgy, hogy hozzáadjuk a bázis abszolút értékét, és hozzáadunk 1-et a hányadosunkhoz.
A fent ismertetett megközelítés az alábbi kódban valósul meg
integer to string 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>
Kimenet:
11101
Időbeli összetettség: ON)
Kiegészítő tér: O(1)
Hivatkozás:
https://en.wikipedia.org/wiki/Negative_base