Преобразование числа в отрицательное базовое представление
Нам дано число n и отрицательная база negBase, нам нужно представить n в этой отрицательной базе. Отрицательная база работает аналогично положительной базе. Например, в базе 2 мы умножаем биты на 1, 2, 4, 8 и так далее, чтобы получить фактическое число в десятичном виде. В случае с основанием -2 нам нужно умножить биты на 1, -2, 4, -8 и так далее, чтобы получить число в десятичном виде.
Примеры:
Ввод: n = 13, negBase = -2. Выход: 11101 1 * (16) + 1 * (- 8) + 1 * (4) + 0 * (- 2) + 1 * (1) = 13
С помощью той же процедуры можно представить число в любой отрицательной базе (подробности см. В Wiki). Для простоты (чтобы избавиться от символов A, B и т. Д. В выводе) мы позволяем нашей базе находиться только в диапазоне от -2 до -10.
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Мы можем решить эту проблему аналогично решению проблемы с положительным основанием, но нужно помнить одну важную вещь: остаток всегда будет положительным независимо от того, работаем ли мы с положительным основанием или отрицательным основанием, но в большинстве компиляторов результат деления отрицательного числа на отрицательное число. округляется до 0, обычно оставляя отрицательный остаток.
Поэтому всякий раз, когда мы получаем отрицательный остаток, мы можем преобразовать его в положительный, как показано ниже:
Позволять n = (? negBase) * частное + остаток = (? negBase) * частное + negBase? negBase + negBase = (? negBase) * (частное + 1) + (остаток + negBase). Итак, если после выполнения «Остаточная = n% negBase» и «n = n / negBase», получаем отрицательный остаток, делаем следующий. остаток = остаток + (-negBase) п = п + 1 Пример: n = -4, negBase = -3 В C ++ мы получаем остаток = n% negBase = -4 / -3 = -1 n = n / negBase [следующий шаг для базового преобразования] = -4 / -3 = 1 Чтобы избежать отрицательного остатка, мы делаем, остаток = -1 + (-negBase) = -1 - (-3) = 2 п = п + 1 = 1 + 1 = 2.
Поэтому, когда мы получим отрицательный остаток, мы сделаем его положительным, добавив к нему абсолютное значение базы и добавив 1 к нашему частному.
Above explained approach is implemented in below code,
C++
// C/C++ program to convert n into negative base form #include <bits/stdc++.h> using namespace std; // Utility method to convert integer into string string toString( int n) { string str; stringstream ss; ss << n; ss >> str; return str; } // Method to convert n to base negBase 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 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 = toString(remainder) + converted; } return converted; } // Driver code to test above methods int main() { int n = 13; int negBase = -2; cout << toNegativeBase(n, negBase); return 0; } |
Java
// 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 |
Python3
# 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#
// 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 |
Выход:
11101
Ссылка :
https://en.wikipedia.org/wiki/Negative_base
Эта статья предоставлена Уткаршем Триведи . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.