@dmasloff

Как решить данную задачу?

Добрый день. Помогите решить данную задачу, уже перебровал всё: при переводе в десятичную систему счисления ull переполняется, а своя структура работает довольно медленно,в силу реализации деления через разность. Можно алгоритм предложить или общую идею.
5fecd7df34b09798331010.png
  • Вопрос задан
  • 261 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Вспомните алгоритм преобразования числа из 10-чной системы в t-ичную - надо делить на t с остатком, пока есть что делить. Остатки - цифры в t-ичной системе счисления (от младших к старшим).

Так, 323 в десятичной системе, если перевести в 16-ричную будет:
323 = 16*20+3. Остаток 3, результат 20.
20 = 16*1+4. Остаток 4, результат 1
1 = 16*0+1. Остаток 1. результат 0.

Отсюда получается, что искомое число в 16-ричной системе 143. Проверка 16*16*1+16*4+3 = 256+64+3=323

Итак, вам надо сделать то же самое, но не в 10-чиной системе, а в k-ичной (ведь переводим не из 10-чной а из k-ичной). Число записано в виде k-ичных цифр в массиве. Это, фактически, длинная арифметика с базой k.

Для этого надо реализовать деление числа в виде массива цифр на короткое с остатком.
Это делается со старших разрядов к младшим. Тупо делите каждую цифру с остатком отдельно. Остаток переносите в младший разряд. Последний остаток - это остаток от всего деления. Результаты делений - новые цифры.

Удобнее хранить цифры от младших к старшим в массиве. Т.е. элемент массива 0 - это единицы. Элемент 1 - это первая степень k. Еще стоит хранить номер последней ненулевой цифры. Смотрите реализацию по ссылке выше.

Вот пример из условия. Пусть k=666, t=10, число - {2, 179, 113} (в условии цифры от старших к младшим, но мы храним наоборот).

Делим на 10.

113/10 = 11 + остаток 3. Переносим 3 в младший разряд (умножив на 666), получаем 3*666+179=2177.
2177 / 10 = 217 + остаток 7. 7*666+2 = 4664.
4664 /10 = 466 + остаток 4. Дальше разрядов нет, значит 4 и есть остаток от деления {2, 179, 113} на 10. Результат деления - {466, 217, 11}

Последний остаток - 4 - это и есть младшая цифра в ответе (он в условии написан - 50241044). Надо продолжать делить результат пока он не окажется 0.

Повторим для {466, 217, 11}:
11/10 = 1 + остаток 1. 1*666+217 = 883
883/10 = 88 + остаток 3. 3*666+446 = 2444
2444/10 = 244 + остаток 4.
Опять, последний остаток - это остаток всего деления и следующая цифра в ответе (опять 4).
Результаты деления - {244, 88, 1}

И так далее, пока все число не станет 0 (все цифры в массиве 0).
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы