Číslo n a negativní základ negBase je nám dáno, musíme reprezentovat n v tomto záporném základu. Negativní báze funguje podobně jako kladná báze. Například v základu 2 násobíme bity na 1 2 4 8 a tak dále, abychom dostali skutečné číslo v desítkové soustavě. V případě základu -2 potřebujeme vynásobit bity 1 -2 4 -8 a tak dále, abychom dostali číslo v desítkové soustavě.
Příklady:
java pár
Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
Stejným postupem je možné reprezentovat číslo do libovolného záporného základu (viz Týden pro podrobnosti). Pro jednoduchost (abychom se zbavili znaků A B atd. ve výstupu) umožňujeme, aby naše základna byla pouze mezi -2 a -10.
Tento problém můžeme vyřešit podobně jako řešení problému s kladnými základy, ale jednu důležitou věc, kterou je třeba si zapamatovat, je, že zbytek bude vždy kladný, ať už pracujeme s kladným nebo záporným základem, ale ve většině kompilátorů je výsledek dělení záporného čísla záporným číslem zaokrouhlen směrem k 0, přičemž obvykle zůstává záporný zbytek.
Takže kdykoli dostaneme záporný zbytek, můžeme jej převést na kladný, jak je uvedeno níže
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.
Takže když dostaneme záporný zbytek, učiníme ho kladným tím, že k němu přičteme absolutní hodnotu báze a přičteme 1 k našemu kvocientu.
Výše popsaný přístup je implementován v níže uvedeném kódu
logika prvního řáduC++
// 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>
výstup:
11101
Časová náročnost: NA)
Pomocný prostor: O(1)
Reference:
https://cs.wikipedia.org/wiki/Negative_base