Skaitlis n un negatīva bāze negBase mums ir dots, mums ir jāattēlo n šajā negatīvajā bāzē. Negatīvā bāze darbojas līdzīgi pozitīvajai bāzei. Piemēram, 2. bāzē mēs reizinām bitus līdz 1 2 4 8 un tā tālāk, lai iegūtu faktisko skaitli decimāldaļās. Bāzes -2 gadījumā mums jāreizina biti ar 1 -2 4 -8 un tā tālāk, lai iegūtu skaitli aiz komata.
Piemēri:
galvenā metode java
Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
Ir iespējams attēlot skaitli jebkurā negatīvā bāzē, izmantojot to pašu procedūru (sk Nedēļa sīkākai informācijai). Vienkāršības labad (lai atbrīvotos no A B utt rakstzīmēm izvadē) mēs pieļaujam, ka mūsu bāze ir tikai no -2 līdz -10.
Mēs varam atrisināt šo problēmu līdzīgi kā problēmas risināšana ar pozitīvām bāzēm, taču viena svarīga lieta, kas jāatceras, ir tas, ka atlikums vienmēr būs pozitīvs neatkarīgi no tā, vai mēs strādājam ar pozitīvu bāzi vai negatīvu bāzi, taču lielākajā daļā kompilatoru rezultāts, dalot negatīvu skaitli ar negatīvu skaitli, tiek noapaļots uz 0, parasti atstājot negatīvu atlikumu.
Tātad, kad mēs iegūstam negatīvu atlikumu, mēs varam to pārvērst pozitīvā, kā norādīts tālāk
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.
Tātad, kad mēs iegūsim negatīvu atlikumu, mēs to padarīsim pozitīvu, pievienojot tam bāzes absolūto vērtību un pievienojot mūsu koeficientam 1.
Iepriekš izskaidrotā pieeja ir ieviesta zemāk esošajā kodā
python rstripC++
// 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>
Izvade:
11101
Laika sarežģītība: O(N)
Palīgtelpa: O(1)
Atsauce:
https://en.wikipedia.org/wiki/Negative_base