【题解】UVa P11384 【Help is needed for Dexter】

【题目大意】

给定一个正整数$n$,定义一次操作为:可从$1,2,…,n$的序列中选择一个或多个整数,同时减去同一个正整数,求变为全$0$的最少操作数。比如:$1,2,3$最少可以同时把$2,3$减小$2$,得到$1,0,1$,再把$1,0,1$变为$0,0,0$。

【题解】

其实很容易就可以得到一个递归式,模拟一下就好了。
$f(n)=f(n\div2)+1$,边界就是$f(1)=1$;神奇的解法。

##【代码】

#include<cstdio>

int f(int x){
    return x == 1 ? 1 : f(x / 2) + 1;
}

int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        printf("%d\n",f(n));
    }

    return 0;
}