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

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
Zilon
Сообщения: 1
Зарегистрирован: 22 ноя 2009, 23:12

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

Сообщение Zilon » 22 ноя 2009, 23:22

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

Хыиуду
Сообщения: 2388
Зарегистрирован: 06 мар 2005, 21:03
Откуда: Москва
Контактная информация:

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

Сообщение Хыиуду » 23 ноя 2009, 09:37

http://www.uroki.net/docinf/docinf28.htm
В самом низу - деление в двоичной системе счисления.
Искусство программирования - заставить компьютер делать все то, что вам делать лень.
Для "спасибо" есть кнопка "Спасибо" в виде звездочки внизу под ником автора поста.

chur
Сообщения: 195
Зарегистрирован: 17 фев 2004, 10:44
Откуда: Riga, Latvia

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

Сообщение chur » 23 ноя 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 привести в нормальный вид (всмысле, чтобы значение конкретного разряда не превышало основание системы)

Ответить