任何一个正整数都可以用2的幂次方表示:137=2^7+2^3+2^0

一、题目描述

例如: 137=2⁷⁺²3+2^{0,同时约定几次方用括号来表示，即a}b可表示为a(b),由此可知,137可表示为: 2(7)+2(3)+2(0)，进一步: 7=2²⁺²⁺²0 (2^1用2表示) 3=2+2^0.所以最后137可表示为:
2(2(2)+2+2(0))+2(2+2(0))+2(0).
又如: 1315=2^ 10+2⁸⁺²5+2+1.所以1315最后可表示为:
2(2(2+2(0))+ 2)+2(2(2+ 2(0)))+2(2(2)+2(0))+ 2+2(0)。
输入:正整数(n<= 20 00)。
输出:符合约定的n的0,2表示(在表示中不能有空格)。

二、算法的设计思路

1.算法设计一

(1)对复杂问题的操作不要希望一蹴而就，不妨先实现137=2⁷⁺²3+2^0的表示，然后再讨论更复杂的表现形式。
(2)由于不知道数据的位数，加上对数据还是从低位到高位的操作比较简单，而输出显然是由高位到低位进行的，这时就要考虑用递归机制实现算法了。

2. 算法设计二

处理指数r的“2的幂次方”表示，函数try(n,0)就是求n的“2的幂次方”表示，所以，递归调用try(n,0)就可以解决问题。当然，当n<=2的时候，直接按格式输出就可以。

三、算法实现的要点

(1)输出操作应该在递归之后。
(2)为了记录递归的深度，也就是2的指数,递归函数的参数应该是两个，一个是当前操作数n,另一个用来记录递归的深度。
(3)递归的停止条件本来可以是0;当n==0时,不做任何操作。但由于第-个输出项没有“+”号,其余输出项都有“+”号，所以将递归的停止条件定为1.

四、伪码描述

1.算法一

main()
{
    int n;
    input(n);
    if(n>=1) {
        try(n,0);
    }else{
        print("data error!");
    }
}
try(int n,int r)
{
    if(n=1) {
        print("2(",r,")");
    }else{
        try(n/2,r+1);
        if(n%2==1) {
            print("+2(",r,")");
        }
    }
}

2.算法二

main()
{
    int n;
    input(n);
    if(n>=1) {
        try(n,0);
    }else{
        print("data error!");
    }
}
try(int n,int r)
{
    if(n==1) {
        switch(r)
        {
            case 0: prnt(2(0);) break;
            case 1: print("2"); break;
            case 2: pint(2(2);) break;
            default:("2("); try(r,0); print(")");
        }
    }else{
        try(n/2,r+1);
        if(n%2==1) {
            case 0: print("+2(0)"); break;
            case 1: print("+2"); break;
            case 2: print("+2(2)"); break;
            default: print("+2("); try(r,0); print(")");
        }
    }
}

五、编程体会

由于递归算法的实现包括递归和回湖两步，当问题需要“后进先出”的操作时，还是用递归算法更有效。如数据结构课程中树的前、中、后序遍历、图的深度优先等算法都是如此。所以不能仅仅从效率上评价两种控制重复操作机制的好坏。