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

Опубликовано: 20 Января, 2022

Нам дано число 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

Выход:

Ссылка :
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.

Алгоритмы

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

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C++

Java

Python3

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ