Функция для возврата 3 ^ k в n + 1 вызовах

Question

Может кто-нибудь помочь мне найти алгоритм для рекурсивной функции func(int k) для возврата 3^k только в n+1 вызовах, где k находится в диапазоне [ 3^n, 3^(n+1) )

Например, функция должна возвращать 3^1 или 3^2 в 1 вызове, 3^3, 3^4, .., 3^8 в 2 вызовах, 3^9, 3^10 .. in 3 звонка и пр.

Answer 1

Вот алгоритм в непроверенный C / C ++:

int 3pow(x)
{
    switch(x)
    {
        case 1: return 3;
        case 2: return 9;
        case 3: return 27;
    }

    int remain  = x % 3,
        recur   = 3pow((x-remain)/3),
        combine = recur * recur * recur;

    switch (remain)
    {
        case 0:  return combine;
        case 1:  return combine * 3;
        default: return combine * 9;
    }
}

( Я не скомпилировал, не выполнил или иным образом не протестировал этот код. Могут быть синтаксические ошибки и другие ошибки. Но этого достаточно для выяснения. )

Отличительной особенностью этого алгоритма является то, что он рекурсивно делится на 3 вместо 2. Эта функция довольно уродлива по необходимости, поскольку абстрагирование некоторой части шаблона, вероятно, потребует больше рекурсии. Тем не менее, этот алгоритм теперь O (log ₃ n). Вот таблица с заданным x от 1 до 50 и требуемым количеством рекурсивных вызовов (в виде списка из двух элементов: lisp):

(1  1) (2  1) (3  1) (4  2) (5  2) (6  2) (7  2) (8  2) (9  2) (10 2)
(11 2) (12 3) (13 3) (14 3) (15 3) (16 3) (17 3) (18 3) (19 3) (20 3)
(21 3) (22 3) (23 3) (24 3) (25 3) (26 3) (27 3) (28 3) (29 3) (30 3)
(31 3) (32 3) (33 3) (34 3) (35 3) (36 4) (37 4) (38 4) (39 4) (40 4)
(41 4) (42 4) (43 4) (44 4) (45 4) (46 4) (47 4) (48 4) (49 4) (50 4)
(51 4) (52 4) (53 4) (54 4) (55 4) (56 4) (57 4) (58 4) (59 4) (60 4)
(61 4) (62 4) (63 4) (64 4) (65 4) (66 4) (67 4) (68 4) (69 4) (70 4)
(71 4) (72 4) (73 4) (74 4) (75 4) (76 4) (77 4) (78 4) (79 4) (80 4)
(81 4) (82 4) (83 4) (84 4) (85 4) (86 4) (87 4) (88 4) (89 4) (90 4)
(91 4) (92 4) (93 4) (94 4) (95 4) (96 4) (97 4) (98 4) (99 4) (100 4)

Вы можете видеть, что даже когда мы встаём более 100, это займет всего 4 рекурсивных вызова.