1443. 遞迴問題

連結：https://tioj.ck.tp.edu.tw/problems/1443

題目大意

$$F(n)=\{\begin{array}{ll}0& \text{if }n=0\\ F([\frac{n}{2}])+n-2[\frac{n}{2}]& \text{otherwise}\end{array}$$

給定 $n$，問 $F(0),F(1)\dots ,F(n)$ 中的最大值為何。

題解

如果仔細觀察一下，$F(n)$ 的結果是 $n$ 寫成二進位時有多少 $1$，因此這題要問的答案就很明顯了，就是到數字 $n$ 進位最多有幾個 $1$。答案等於 $\lfloor {\log }_2(N+1)\rfloor$

這裡做法有點懶惰，直接用 python 大數算，速度跟自己開大數模板差不多。

AC Code

import math
print(math.floor(math.log(int(input())+1,2)))