Ivan Krivyakov wrote:
> Там запостились какие-то промежуточные рассуждения в конце.
> После подписи "Иван" можно не читать :)
> Итак, исправленному верить:
>
> Запишем наше число в троичном виде.
> Будем идти по числу с конца.
Не понимаю цели всех этих переусложнений.
Идея составления записи числа в системе (-1, 0, 1) фактически ничем не
отличается от алогритма записи числа в система (0, 1, 2). В обоих
случаях используется "жадный" алгоритм, работающий от старших разрядов к
младшим. "Жадность" алогритма заключается в том, что мы бесусловно
включаем в результат самый старший разряд (в максимально возможном его
количестве), из котрого "достижим" остаток переводимого числа.
Как мы переводим число 100 в обыкновенную троичную систему счисления?
Очень просто:
- Из разрядов 243 и выше число 100 недостижимо. Пропускаем их (т.е.
берем их в количестве 0)
- Из разряда 81 чило 100 достижимо. Берем 81 в количестве 1. Остаток 19.
- Из разряда 27 число 19 недостижимо. Берем 27 в количестве 0.
- Из разряда 9 число 19 достижимо. Берем 9 в количестве 2. Остаток 1.
- Из разряда 3 число 1 недостижимо. Берем 3 в количестве 0.
- Из разряда 1 число 1 достижимо. Берем 1 в количестве 1.
Результат: 10201.
Для симметричной системы алгоритм аналогичен, в смысле своей "жадности".
Надо только заметить, что в такой системе из разряда с весом N достижимы
значения в диапазонах [N - floor(N/2), N + floor(N/2)] и [-N -
floor(N/2), -N + floor(N/2)]
Переводим число 100:
- Из разряда 243 достижимы числа в диапазонах [122, 364] и [-364, -122]
значит этот разряд (и выше) нам не нужен.
- Из разряда 81 достижимы числа в диапазоне [41, 121] и [-121, -41].
Значит берем этот разряд в количестве 1. Остаток 19.
- Из разряда 27 достижимы числа в диапазоне [14, 40] и [-40, -14].
Значит берем этот разряд в количестве 1. Остаток -8.
- Из разряда 9 достижимы числа в диапазоне [5, 13] и [-13, -5]. Значит
берем этот разряд в количестве -1. Остаток 1.
- Из разряда 3 достижимы числа в диапазоне [2, 4] и [-4, -2]. Значит
этот разряд нам не нужен.
- Из разряда 1 достижимы числа в диапазоне [1, 1] и [-1, -1]. Значит
берем этот разряд в количестве 1.
Результат: 1, 1, -1, 0, 1