洛谷 P1010 幂次方

题目描述

任何一个正整数都可以用2的幂次方表示。例如137=2⁷⁺²3+2^0.
同时约定方次用括号来表示，即ab可表示为a(b)。
由此可知，137 可表示为2(7) + 2(3) + 2(0)
进一步:
7= 2^2 + 2 + 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^8 + 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。

输出格式

符合约定的n的0,2表示（在表示中不能有空格）。

思路

题不算难，可以用递归来做。
先将2的各个次方数都存下来，不断找次方数中小于目标数的最大的数（如果看不懂可以结合代码看）
把目标数减刚刚找到的数后，进行递归
减完的数就是下一次的目标数。

让我们边看代码边讲细讲思路：

#include<iostream>
using namespace std;

int cf[20] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768};
//将2的各个次方数都存下来，因为n最大是20000，所以存到2^14就够了（最后那个是以防万一）

void m(int x)
{
    int i = 0;
    bool z = 0;//用来标记前面是否有过输出（其实就是控制输出加号的，必须前面有数才能输出加号）
    for(i = 14; i >= 0; i--)
    {
        if(cf[i] <= x)//找到小于目标数中最大的2的次方数
        {
            if(i == 1)//2^1次方时要特殊输出
            {
                if(z)//如果前面有数就输出“+”号
                {
                	cout << '+';
		}
                z = 1;
                cout << 2;
                x = x - 2;
                continue;
            }
            if(z) 
	    {
	       	cout << '+';
	    }
            z = 1;
            cout << "2(";//这里把2^0也包含了
            if(i > 2)//非2^0、2^1和2^2的情况
	    {
	   	m(i);
	    }
	    else if(i == 2)//2^2次方，也是一种特殊情况，因为里面的2后面不会再带括号（其实再递归一次也行，但尽量避免）
	    {
		cout << 2;
	    }
            else//2^0次方，不说了 
	    {
		cout << "0";
	    }
            x = x - cf[i];//计算下一个加数
            cout << ")";//凑全括号
        }
    }
}

int main()
{
    int n = 0;
    
    cin >> n;
    
    m(n);//调用递归
    
    return 0;
}

成功AC