а), б) Задачу удобно решать с конца, т. е. искать кратчайший способ получения числа 0 из произвольного натурального $n$ с помощью двух операций — вычитания 1 (В) и деления пополам (Д). Пусть $r(n)$ — число операций В и Д в таком кратчайшем алгоритме. Если число $n$ нечётно, то к нему можно применить только операцию В, так что $$
r(2k+1)=1+r(2k).
$$
Покажем индукцией по $k$, что $r(2k)=1+r(k)$, т. е. чётное число в кратчайшем алгоритме надо делить пополам. Для $k=1$ это ясно. Пусть это доказано для всех чисел, меньших $k$. Если к числу $2k$ сначала применить операцию В (вычесть 1), то число операций до получения 0 будет не меньше, чем $$
1+r(2k-1)=2+r(2k-2)=3+r(k-1)
$$
(по предположению индукции). Если же сначала делить $2k$ пополам, а дальше идти по оптимальному пути, то число операций будет $1+r(k)\le2+r(k-1)$. Таким образом, второй способ заведомо быстрее.
$
\def\|{\downarrow}\def\d{\text{Д}}\def\v{\text{В}}
\begin{array}{ccc}
100&&1100100\\
\|&\d^2=\d\cdot\d&\|\\
25&&11001\\
\|&\v&\|\\
24&&11000\\
\|&\d^3&\|\\
3&&11\\
\|&\v&\|\\
2&&10\\
\|&\d&\|\\
1&&1\\
\|&\v&\|\\
0&&0
\end{array}$
Чтобы узнать, сколько операций потребуется в кратчайшем алгоритме для заданного числа $n$, представим $n$ в виде суммы степеней двойки:
$$n=2^{k_1}+2^{k_1+k_2}+\ldots+2^{k_1+k_2+\ldots+k_m},$$
где $k_1$ неотрицательное, а $k_2$, $\ldots$, $k_m$ — положительные целые числа ($k_1$, $k_1+k_2$, $\ldots$ — это номера разрядов двоичной записи $n$, в которых стоят единицы). Тогда
$$
\begin{gather*}
r(n)=k_1+r{\left(\dfrac n{2^{k_1}}\right)}=k_1+1+r(2^{k_2}+\ldots+2^{k_2+\ldots+k_m})=\ldots\\
\ldots=(k_1+1)+(k_2+1)+\ldots+(k_m+1)=\\
=(k_1+k_2+\ldots+k_m)+m=[\log_2n]+m
\end{gather*}
$$
($[x]$ — целая часть $x$), поскольку $k_1+k_2+\ldots+k_m$ — это показатель наибольшей степени двойки, не превосходящей $n$. Отметим, что $m$ равно количеству единиц в двоичной записи числа $n$. В частности, для $n=100$ получаем ответ к задаче а): $r(100)=9$
На полях показано превращение числа 100 в 0 в десятичной и двоичной записи. Поскольку $100=2^6+2^5+2^2$, получаем $r(100)=6+3=9$.
