Алгоритм преобразования целого числа (представленного в виде массива) с основанием n в целое число с основанием m - PullRequest
Новая
       22

Алгоритм преобразования целого числа (представленного в виде массива) с основанием n в целое число с основанием m

1 голос
/ 02 января 2012

У меня очень длинное целое число. Целое число представлено массивом беззнаковых символов.

Пример: целое число 1234 с основанием 10 представлено в массиве как [4,3,2,1], [2,2,3,2] (основание 8) и [2, 13,4] (база 16)

Теперь я хочу преобразовать мое целое число с основанием n в другое целое число с основанием m. В моем убеждении за ответ я наткнулся на алгоритм Уоллара , первоначально из здесь 

from math import *
def baseExpansion(n,c,b):
    j = 0
    base10 = sum([pow(c,len(n)-k-1)*n[k] for k in range(0,len(n))])
    while floor(base10/pow(b,j)) != 0: j = j+1
    return [floor(base10/pow(b,j-p)) % b for p in range(1,j+1)]

Сначала я подумал, что это мой ответ, но, к сожалению, это не так. У меня проблема в том, что алгоритм вычисляет сумму. В моем случае это проблема, потому что переменная base10 имеет тип целое число без знака из 32 бит. Поэтому, когда мое целое число, представленное в виде массива, имеет более 10 цифр, оно больше не может преобразовать число. У кого-нибудь есть решение?

1 Ответ

1 голос
/ 04 января 2012

Вот алгоритм учебника для того, чтобы делать то, что вы пытаетесь. Вы начинаете с представления для нуля и называете его промежуточной суммой. Затем для каждой цифры числа, которое необходимо преобразовать, начиная с самого старшего и заканчивая наименее значимым, 1) умножьте промежуточную сумму на базу исходного числа и 2) добавьте цифру к промежуточной сумме. Теперь все, что вам нужно, это алгоритмы для умножения и сложения (и вы можете сделать оба сразу). Вот как это сделать: 1) установить текущую цифру в переменную, назовите ее «переносить», 2) для каждой цифры в вашем новом номере, начиная с наименее значимой и переходя к самой значимой: 2а) установить перенос в текущая цифра в новом числе, умноженная на выходную базу плюс перенос, 2b) устанавливает текущую цифру для переноса в выходную базу, 2c) устанавливает перенос в перенос, деленную на выходную базу. И это должно сделать это. Здесь есть реализация того, что вы пытаетесь сделать: http://www.cis.ksu.edu/~howell/calculator/comparison.html

...