История изменений

Логика простая - для 1 операция, очевидно, одна, для 2 — две, для 3 — три, любое число больше 3 в процессе обязательно сведётся либо к 2 либо к 3. Дальше рассмотрим двоичную запись числа, очевидно, что ни одна операция не способна сократить число более, чем на один разряд. Число, заканчивающееся на 0, сокращается на разряд делением на 2. Рассмотрим число, оканчивающееся на n≥2 единиц. Прибавив 1 мы получим число, оканчивающееся на n нулей, т.е. за n+1 операцию уменьшим число на n разрядов. Очевидно, что за n операций уменьшить нечётное число на n разрядов невозможно, т.е. добавление 1 в этом случае гарантированно приводит к быстрейшему уменьшению. Число, оканчивающееся на 01 путём вычитания и деления на два два раза сокращается на 2 разряда, очевидно, что добавлением 1 быстрее уменьшить не получится, для этого достаточно рассмотреть 1(×n)01 +1 => 1(×(n+1))0 /2 => 1(×(n+1)) = 2+n+2 = n+4 операции, 1(×n)01 -1 /2 /2 => 1(×n) = 3+n+1=n+4 операции. Так что алгоритм в псевдокоде:

count = 0 
while n > 3
  case n mod 4
    0: n >> 2, count+=2
    1: n--, count++
    2: n >> 1, count++
    3: n++, count++
  end 
end
count+=n

Логика простая - для 1 операция, очевидно, одна, для 2 — две, для 3 — три, любое число больше 3 в процессе обязательно сведётся либо к 2 либо к 3. Дальше рассмотрим двоичную запись числа, очевидно, что ни одна операция не способна сократить число более, чем на один разряд. Число, заканчивающееся на 0, сокращается на разряд делением на 2. Рассмотрим число, оканчивающееся на n≥2 единиц. Прибавив 1 мы получим число, оканчивающееся на n нулей, т.е. за n+1 операцию уменьшим число на n разрядов. Очевидно, что за n операций уменьшить нечётное число на n разрядов невозможно, т.е. добавление 1 в этом случае гарантированно приводит к быстрейшему уменьшению. Число, оканчивающееся на 01 путём вычитания и деления на два два раза сокращается на 2 разряда, очевидно, что добавлением 1 быстрее уменьшить не получится, для этого достаточно рассмотреть 1(×n)01 +1 => 1(×(n+1))0 /2 => 1(×(n+1)) = 2+n+2 = n+4 операции, 1(×n)01 -1 /2 /2 => 1(×n) = 3+n+1=n+4 операции. Так что алгоритм в псевдокоде:
case n mod 4
0: n >> 2, count+=2
1: n--, count++
2: n >> 1, count++
3: n++, count++