一道水题，求解

pjr

Description 对于一个整数，有如下操作规则：如果n为偶数，将其除以2；如果n为奇数，可以加1或减1；一直处理下去。那么，最终该数会变为1。 例如：当n为7时，可以证明最少需要4次运算 n = 7 n-1 6 n/2 3 n-1 2 n/2 1最终该数会变为1. 现在给出一个整数，求它变为1的最少运算次数。 Input 输出包括多组测试用例，通过EOF结束。 每组测试用例包括一行，为一个整数n(1<=n<=2000000000)。 Output 每组测试用例输出一行，为一个数，即n变为1的最少运算次数。 Sample Input                                         Copy sample input to clipboard                                     7 Sample Output 4 感觉这题可以用书中的深度优先算法来解，然而我失败了，求大神帮忙！

推荐人

不是可以用动态规划吗

jhx

这样好像可以
[mw_shl_code=c,true]#include <stdio.h>
int main()
{
        int i,n,o;S:
        scanf("%d",&n);o=n;
    if(n<=0){
                printf("请输入正整数!\n\n");
                goto S;
        }for(i=0;o!=1;i++){
                o/=2;}
        for(o=1;i;i--)
                o*=2;
        i=(o/2+o>=n);
        for(o=0;n!=1;o++)
                if(n%2)
                        printf("n%c1=%d\n",
                        i?'-':'+',n+= i?-1:1);
                else
                        printf("n/2=%d\n",n/=2);
        printf("\n需要%d步\n\n\n",o);
        goto S;
}
[/mw_shl_code]