ща постараюсь не так закрученно...
пускай у нас имеется 230(5) и надо перевести в, скажем ?(10)
преобразование можно сделать так:
2∙5^2 + 3∙5^1 + 0
но выражение можно свернуть:
5∙(2∙5 + 3) - и нам уже прийдётся умножать на 5 не каждое из двух чисел(2∙5 и 3), а их сумму.
Если число будет больше, то:
1342(5) = 1∙5^3 + 3∙5^2 + 4∙5^1 + 2∙5^0 = 5∙(5∙(5∙1 + 3) + 4) + 2
В чём мы выигрываем? В действиях. В их количестве. Где? Когда нам надо было найти 5^4, мы находили 5∙5∙5∙5. Потомо нам надо было найти 5^2, и мы делали 5∙5, при том, что это число мы уже находили, когда искали 5^4, только оно было промежуточным этапом. А если идти последовательным умножением на пять, то этой "лишней работы" мы избегаем. Что осталось? Вести вычисления в той системе счисления, в которую надо перевести число.
Например, 123(4) === ?(3)
В десятиричной это выглядело бы так: 4*(4*1 + 2) + 3, но в 3 системе счисления нет цифры 4. Потому в 3 системе счисления это будет выглядеть так:
11 * (11 * 1 + 2) + 10 = 11 * 20 + 10 = 220 + 10 = 300(3)
Как несложно убедиться, 123(4) == 27(10) == 300(3)
Вобщем, весь фокус состоит в вычислениях в той системе счисления, в котороую надо перевести число.
А фокус со "свёртывнием" полинома от возведения в степень к каскадному умножению имеет название. Только я его забыл 
Полином ...(кого-то). |
