Получить последовательность каждый член которой равен -1, 0, или 1
Есть некоторое число ?, его нужно разложить в последовательность ?0 , ..., ??, каждый член которой равен -1, 0, или 1, такую, что ?=??⋅3^?+...+?1⋅3+?0 ( ??≠0 )
Есть идеи как можно это реализовать?
Ответы (1 шт):
Короче, если это 3 в степени n - а я в этом уверен :) - то задача решается так: переводим число в троичную систему счисления. Получается число с цифрами 0, 1 и 2.
Идем от младшего разряда к старшему, если встречаем 2 - заменяем на -1 и прибавляем к разряду старше единицу (по сути заменяя 2 = 3 - 1). Рекурсивно повторяем...
Например, 743. В троичной системе - 1000112. Последнюю двойку заменяем на -1 (буду изображать как i - просто чтоб отличать...) Получаем 100012i. Переходим к двойке слева. Та же картина - 10002ii. И опять... 1001iii. Это и есть искомое представление:
1*3^6+1*3^2+3+2=729+9+3+2=743 (1000112)
1*3^6+1*3^3-3^2-3-1=729+27-9-1=743 (1001iii)