Есть число неограниченной длинны т.е. в int не всегда можно запихнуть. Число представленно массивом int*. Каждый элемент в массиве определяет значение разрядя (в определенной системе счисления) соответствущего индексу этого элемента. Массив оканчивается элементом со значением -1. Например 7D009AF в 16-ой системе будет {15,10,9,0,0,14,7,-1}. Массив может быть любой длинны.
Нужно перевести это число в другую систему счисления и записать в такой же массив.
Основания систем счислений в исходном числе и ответе могут быть любые от 2 до 256.
Тут основная проблема в том что это число в int не всегда можно зписать т.к. оно очень большое. По той же пречине не всегда получается записать в int n-ный элемент массива умноженный на основание системы счисления в степени n (n теоретически может быть любая).
Тут нужен оригинальный алгоритм :-\ .
Я уже несколько дней голову над этой задачкой ломаю. Может быть тут есть кто нибудь умнее меня :) ?
Здравствуйте Dima_, Вы писали:
D>Здравствуйте, люди добрые!
D>У меня вот такая вот задачка.
D>Есть число неограниченной длинны т.е. в int не всегда можно запихнуть. Число представленно массивом int*. Каждый элемент в массиве определяет значение разрядя (в определенной системе счисления) соответствущего индексу этого элемента. Массив оканчивается элементом со значением -1. Например 7D009AF в 16-ой системе будет {15,10,9,0,0,14,7,-1}. Массив может быть любой длинны.
D>Нужно перевести это число в другую систему счисления и записать в такой же массив.
D>Основания систем счислений в исходном числе и ответе могут быть любые от 2 до 256.
D>Тут основная проблема в том что это число в int не всегда можно зписать т.к. оно очень большое. По той же пречине не всегда получается записать в int n-ный элемент массива умноженный на основание системы счисления в степени n (n теоретически может быть любая).
D>Тут нужен оригинальный алгоритм .
Вот тебе стандартный алгоритм перевода числа в другую систему счисления, в котором нет ничего оригинального:
1) Представляешь новое основание в текущей системе счисления (например, 10 в в 16-ричной — это 0A).
2) Делишь свое число на новое основание (например, в столбик). Остаток от деления — последняя цифра числа в новой СС.
3) Если частное не 0, то переход к 2 с частным в качестве нового делимого.
Все тупо для безобразия. Деление в столбик, надеюсь, написать сумеешь (есть вроде и более продвинутые алгоритмы деления, но я с ними не знаком)?
Здравствуйте Dima_, Вы писали:
D>Здравствуйте, люди добрые!
D>У меня вот такая вот задачка.
Что-то мне подсказывает, что надо почитать второй том Кнута. Там очень много чего есть про системы счисления, причем и про представление неограниченных целых тоже есть
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте Lexey, Вы писали:
L>Здравствуйте Dima_, Вы писали:
D>>Здравствуйте, люди добрые!
D>>У меня вот такая вот задачка.
D>>Есть число неограниченной длинны т.е. в int не всегда можно запихнуть. Число представленно массивом int*. Каждый элемент в массиве определяет значение разрядя (в определенной системе счисления) соответствущего индексу этого элемента. Массив оканчивается элементом со значением -1. Например 7D009AF в 16-ой системе будет {15,10,9,0,0,14,7,-1}. Массив может быть любой длинны.
D>>Нужно перевести это число в другую систему счисления и записать в такой же массив.
D>>Основания систем счислений в исходном числе и ответе могут быть любые от 2 до 256.
D>>Тут основная проблема в том что это число в int не всегда можно зписать т.к. оно очень большое. По той же пречине не всегда получается записать в int n-ный элемент массива умноженный на основание системы счисления в степени n (n теоретически может быть любая).
D>>Тут нужен оригинальный алгоритм :-\ .
L>Вот тебе стандартный алгоритм перевода числа в другую систему счисления, в котором нет ничего оригинального: L>1) Представляешь новое основание в текущей системе счисления (например, 10 в в 16-ричной — это 0A). L>2) Делишь свое число на новое основание (например, в столбик). Остаток от деления — последняя цифра числа в новой СС. L>3) Если частное не 0, то переход к 2 с частным в качестве нового делимого.
L>Все тупо для безобразия. Деление в столбик, надеюсь, написать сумеешь (есть вроде и более продвинутые алгоритмы деления, но я с ними не знаком)?
Да, ещё обрати внимание, что (если это имеет отношение к делу) если число не целое, а с плавающей точкой, число разделяется на целую и дробную часть. Целая преобразуется довольно интуитивно с помощью целочисленного деления и остатка как было описано выше, а дробная часть несколько иначе (на первый взгляд, с точностью до наоборот).
Значит так.
Имеется число (dn-1dn-2...d1d0d-1...) по основанию b.
Необходимо получить то же число, но по основанию с. Понятно, что
(dn-1dn-2...d1d0d-1...)b = (dn-1*b^(n-1) + dn-2*b^(n-2) + ... + d1*b + d0 + d-1*b^(-1), d = 0..b-1.
Таким образом, для целой части dk получается путём последовательного целочисленного деления по основанию b (от d1 до dn-1).
Для дробной же части выполняется:
(0. d-1d-2d-3d-4...)b = d-1*b^(-1) + d-2*b^(-2) + d-3*b^(-3) + d-4*b^(-4) + ...
Умножив левую часть на b, и взяв целую часть, получим d-1. Далее берём оставшуюся дробную часть и продолжаем...
fAX.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте Lexey, Вы писали:
L>Здравствуйте Dima_, Вы писали:
D>>Здравствуйте, люди добрые!
D>>У меня вот такая вот задачка.
D>>Есть число неограниченной длинны т.е. в int не всегда можно запихнуть. Число представленно массивом int*. Каждый элемент в массиве определяет значение разрядя (в определенной системе счисления) соответствущего индексу этого элемента. Массив оканчивается элементом со значением -1. Например 7D009AF в 16-ой системе будет {15,10,9,0,0,14,7,-1}. Массив может быть любой длинны.
D>>Нужно перевести это число в другую систему счисления и записать в такой же массив.
D>>Основания систем счислений в исходном числе и ответе могут быть любые от 2 до 256.
D>>Тут основная проблема в том что это число в int не всегда можно зписать т.к. оно очень большое. По той же пречине не всегда получается записать в int n-ный элемент массива умноженный на основание системы счисления в степени n (n теоретически может быть любая).
D>>Тут нужен оригинальный алгоритм .
L>Вот тебе стандартный алгоритм перевода числа в другую систему счисления, в котором нет ничего оригинального: L>1) Представляешь новое основание в текущей системе счисления (например, 10 в в 16-ричной — это 0A). L>2) Делишь свое число на новое основание (например, в столбик). Остаток от деления — последняя цифра числа в новой СС. L>3) Если частное не 0, то переход к 2 с частным в качестве нового делимого.
L>Все тупо для безобразия. Деление в столбик, надеюсь, написать сумеешь (есть вроде и более продвинутые алгоритмы деления, но я с ними не знаком)?
.
