Numero n ja negatiivinen perusta negBase on meille annettu, meidän täytyy edustaa n tuossa negatiivisessa kannassa. Negatiivinen kanta toimii samalla tavalla kuin positiivinen kanta. Esimerkiksi kannassa 2 kerromme bitit 1 2 4 8:ksi ja niin edelleen saadaksemme todellisen luvun desimaalilukuina. Kanta -2:n tapauksessa meidän täytyy kertoa bitit luvuilla 1 -2 4 -8 ja niin edelleen saadaksemme numeron desimaalimuodossa.
Esimerkkejä:
1 miljardista miljoonaan
Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
On mahdollista esittää luku mihin tahansa negatiiviseen kantaan samalla menettelyllä (katso Viikko lisätietoja). Yksinkertaisuuden vuoksi (jos haluat päästä eroon A B jne. -merkeistä lähdössä) annamme kantamme olla vain -2:n ja -10:n välillä.
Voimme ratkaista tämän ongelman samalla tavalla kuin ongelman ratkaiseminen positiivisilla kantaluvuilla, mutta yksi tärkeä asia on muistaa, että jäännös on aina positiivinen riippumatta siitä, työskentelemmekö positiivisella kantalla vai negatiivisella kantalla, mutta useimmissa kääntäjissä negatiivisen luvun jakaminen negatiivisella luvulla pyöristetään kohti nollaa, jolloin jää yleensä negatiivinen jäännös.
Joten aina kun saamme negatiivisen jäännöksen, voimme muuntaa sen positiiviseksi kuten alla
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.
Joten kun saamme negatiivisen jäännöksen, teemme siitä positiivisen lisäämällä siihen kantaarvon itseisarvon ja lisäämällä osamääräämme 1.
Yllä selitetty lähestymistapa on toteutettu alla olevassa koodissa
hakemiston uudelleennimeäminen linuxissaC++
// 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>
Lähtö:
11101
Aika monimutkaisuus: O(N)
Aputila: O(1)
Viite:
https://en.wikipedia.org/wiki/Negative_base