Bir sayı N ve negatif bir baz NegBase Bize verilen n'yi bu negatif tabanda temsil etmemiz gerekiyor. Negatif taban, pozitif tabana benzer şekilde çalışır. Örneğin, 2 tabanında, gerçek sayıyı ondalık sayı olarak elde etmek için bitleri 1 2 4 8 ile çarparız. -2 tabanı durumunda, ondalık sayıyı elde etmek için bitleri 1 -2 4 -8 vb. ile çarpmamız gerekir.
Örnekler:
chown komutu
Input : n = 13 negBase = -2 Output : 11101 1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1) = 13
Aynı prosedürle bir sayıyı herhangi bir negatif tabanda temsil etmek mümkündür (Bkz. Bir hafta ayrıntılar için). Basitlik açısından (çıktıdaki A B vb. karakterlerden kurtulmak için) tabanımızın yalnızca -2 ile -10 arasında olmasına izin veriyoruz.
Bu problemi pozitif tabanlarla problemi çözmeye benzer şekilde çözebiliriz, ancak hatırlanması gereken önemli bir nokta, pozitif tabanla veya negatif tabanla çalışsak da kalanın her zaman pozitif olacağıdır, ancak çoğu derleyicide negatif bir sayıyı negatif bir sayıya bölmenin sonucu genellikle negatif bir kalan bırakarak 0'a yuvarlanır.
Negatif bir kalan aldığımızda bunu aşağıdaki gibi pozitife dönüştürebiliriz.
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.
Yani negatif kalan elde ettiğimizde buna tabanın mutlak değerini ve bölümümüze 1 ekleyerek pozitif hale getireceğiz.
Yukarıda açıklanan yaklaşım aşağıdaki kodda uygulanmıştır.
uri vs urlC++
// 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>
Çıkış:
11101
Zaman Karmaşıklığı: AÇIK)
Yardımcı Alan: Ç(1)
Referans:
https://en.wikipedia.org/wiki/Negative_base