Рубрики

Преобразовать число в отрицательное базовое представление

Нам дано число n и отрицательная база negBase , нам нужно представить n в этой отрицательной базе. Отрицательная база работает аналогично положительной базе. Например, в базе 2 мы умножаем биты на 1, 2, 4, 8 и так далее, чтобы получить действительное число в десятичном виде. В случае основания -2 нам нужно умножить биты на 1, -2, 4, -8 и так далее, чтобы получить число в десятичном виде.

Примеры:

Input  : n = 13, negBase = -2
Output : 11101
1*(16) + 1*(-8) + 1*(4) + 0*(-2) + 1*(1)  = 13

Можно представить число в любую отрицательную базу с помощью той же процедуры (подробности см. В Wiki ). Для простоты (чтобы избавиться от символов A, B и т. Д. В выводе), мы разрешаем нашей базе быть только между -2 и -10.

Мы можем решить эту проблему аналогично решению проблемы с положительными основаниями, но следует помнить одну важную вещь: остаток всегда будет положительным независимо от того, работаем ли мы с положительным или отрицательным основанием, но в большинстве компиляторов результат деления отрицательного числа на отрицательное число округляется до 0, обычно оставляя отрицательный остаток.
Поэтому, когда мы получаем отрицательный остаток, мы можем преобразовать его в положительный, как показано ниже,

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.

Поэтому, когда мы получим отрицательный остаток, мы сделаем его положительным, добавив к нему абсолютное значение базы и добавив 1 к нашему частному.

Вышеописанный подход реализован в следующем коде,

C ++

// C / C ++ программа для преобразования n в отрицательную базовую форму
#include <bits/stdc++.h>

using namespace std;

  
// Утилита для преобразования целого числа в строку

string toString(int n)

{

    string str;

    stringstream ss;

    ss << n;

    ss >> str;

    return str;

}

  
// Метод для преобразования n в базовый negBase

string toNegativeBase(int n, int negBase)

{

    // Если n равно нулю, то в любой базе это будет только 0

    if (n == 0)

        return "0";

  

    string converted = "";

    while (n != 0)

    {

        // Получить остаток по отрицательной базе, это может быть

        // отрицательно также

        int remainder = n % negBase;

        n /= negBase;

  

        // если остаток отрицательный, добавьте abs (base) к

        // это и добавить 1 к n

        if (remainder < 0)

        {

            remainder += (-negBase);

            n += 1;

        }

  

        // преобразовать остаток в строку add в результат

        converted = toString(remainder) + converted;

    }

  

    return converted;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int n = 13;

    int negBase = -2;

  

    cout << toNegativeBase(n, negBase);

  

    return 0;

}

python3

# Python 3 программа для преобразования n в
# отрицательная базовая форма

  
# Способ преобразования n в базовый negBase

def toNegativeBase(n, negBase):

      

    # Если n равно нулю, то в любой базе это

    # будет только 0

    if (n == 0):

        return "0"

  

    converted = "01"

    while (n != 0):

          

        # Получить остаток по отрицательной базе,

        # также может быть отрицательным

        remainder = n % (negBase)

        n = int(n/negBase)

  

        # если остаток отрицательный, добавьте

        # abs (основа) к нему и добавить 1 к n

        if (remainder < 0):

            remainder += ((-1) * negBase)

            n += 1

  

        # преобразовать остаток в строку add

        # в результат

        converted = str(remainder) + converted

          

    return converted

  
Код водителя

if __name__ == '__main__':

    n = 13

    negBase = -2

  

    print(toNegativeBase(n, negBase))

  
# Этот код предоставлен
# Surendra_Gangwar

Выход:

11101

Ссылка :
https://en.wikipedia.org/wiki/Negative_base

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Преобразовать число в отрицательное базовое представление

0.00 (0%) 0 votes