PDA

Просмотр полной версии : Перевод из одной системы исчисления в другую. Как оказалось вопрос не тривиальный



Zilon
22.11.2009, 23:22
Стоит задача перевода значения из 2-ной системы исчисления в 4094-ичную (то есть (2^12 - 2) - ичную). То есть не кратную степени двойки. Существующие выкладки на эту тему предлагают значение числа в исходной сист. счисл. делить на основание. Проблема в том что исходное число в 2-ной системе может (и будет) n-битныйм. То есть произвольно большим.
Подскажите алгоритм решения этой задачи.
К стати эта задача возикла не из головы сумашедшего препода... мне ее завтра имплиментить)))

Хыиуду
23.11.2009, 09:37
http://www.uroki.net/docinf/docinf28.htm
В самом низу - деление в двоичной системе счисления.

chur
23.11.2009, 13:38
Для работы с большими числами надо использовать массивы. Этот вопрос регулярно появляется, на этом форуме тоже был. Попробуй поискать.

В твоей задаче лучше сначала создать массив массивов представляющий степени двойки в новой системе исчисления. Ну, конечно, надо ограничиться какой-то максимальной разрядностью входного двоичного числа



// пример создаваемого массива массивов
// bits[0] = [1];
// bits[1] = [2];
// bits[2] = [4];
// ....
// bits[12] = [2, 1];
// bits[13] = [4, 2];
// ...
newbase = 4094;
maxsize = 1024;
bits[] = [];

bits[0] = [1];
for i=1; i<maxsize; i++
L = lenght(bits[i-1]);
overflow = 0;
for k=0; k<L; k++
bits[i][k] = bits[i-1][k] * 2 + overflow;
if bits[i][k] >= newbase
bits[i][k] -= newbase; overflow = 1;
else
overflow = 0;
end if
end for
if overflow then bits[i][L] = 1;
end for


Будем считать, что входное число представлено массивом "0" и "1". Если очередной разряд содержит "1", то просто по-разрядно прибавляем к результату соответствующий массив (из первого куска кода)


in = [];
out = [];
for i=0; i<length(in); i++
next unless in[i]
for L=0; L<length(bits[i]); L++
out[L] += bits[i][L];
end for
end for


Вот и все. Возможно, надо еще будет полученный массив out привести в нормальный вид (всмысле, чтобы значение конкретного разряда не превышало основание системы)