Uva 11384 - Help is needed for Dexter（） - c++编程基础

题目大意：

有一个从1、2、3、.......n的正整数数列，现在要通过若干次操作将这个数列全部变为0，操作的方法是每次选取任意1个或多个任意位置的数，然后将这几个数同时减去一个一个数。问至少要经过多少次操作才能让数列全部变为0

题目分析：

将[1， n]从中间分成[1, n/2] 和[n/2+1, n]两个部分，分别包含n/2和（n+1)/2个数，将第二部分的数分别减去n/2+1, 第二部分变为[0, (n-1)/2], 第一部分包括第二部分，可得递推公式为：f(n) = f(n/2) + 1;

代码：

#include   
  
int f(int n)  
{  
    return n == 1   1 : f(n/2)+1;  
}  
  
int main()  
{  
    int n;  
    while(scanf("%d", &n) != EOF)  
        printf("%d\n", f(n));  
    return 0;  
}

第二种解法：

把那些1到16的答案全都列举出来，很快就发现了一个规律，即答案是1的有1个（2^0),答案是2的有2个(2^1)，答案是3的有4个(2^2)，诶，有了这个规律，那我们只需要打一个从1到31的表了，内容是dp[i] = 1<

代码：

#include  
int dp[40];  
void dabiao() {  
    int c=1;  
    for(int i=0;i<=31;++i)  
    dp[i] = c<=dp[i]&&n<=dp[i+1]-1)  
    printf("%d\n",i+1);  
    return 0;  
}