欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P1010 幂次方

程序员文章站 2022-05-08 22:12:44
...

题面
题目描述
任何一个正整数都可以用22的幂次方表示。例如

137=27+23+2^0

同时约定方次用括号来表示,即a^b
可表示为a(b)。

由此可知,137可表示为:2(7)+2(3)+2(0)

进一步:

7= 22+2+20 (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≤20000)

输出格式
符合约定的n的0,2表示(在表示中不能有空格)

输入输出样例
输入 #1 复制
1315
输出 #1 复制
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2

分析
根据题目可以得知,这一道题目的意思是将一个数拆分乘2的若干次方,之后再对其中的次方数进行拆分(再对拆分后的数进行拆分,直到不可以拆分为止)

很明显,这是一种递归的思想·(虽然我先看了题解)
这里给出笔者看过题解后恍然大悟的思路:
①找出与当前数最接近的二的平方数
②对这个平方数进行拆分(上一步同时记录下来这是2的多少次方,对指数进行判断,根据题意来)
③判断这里的数是否可以再拆分了(不能就直接GG退出)

这里我们要思考一下对指数的判断,根据题目可知以下的特殊情况:
指数为 0 :直接输出
指数为 1:不用管
指数为 2:直接输出
我们不妨可以发现,以上的几个都是无法再次进行拆分的了
但是对于上面第二个的处理,我们可以每次搜索前都直接输出一个2(在可取时)
之后的几个无非是if二等判断了

代码

#include <bits/stdc++.h>
using namespace std;

int n;

void search(int x) {
	if (n != 0) {
		int p = 0, q = 1;
		while (x >= q) p++, q*=2;  //找打最接近的2的平方数
		p--, q /= 2;
		//每一次拆分都是需要这样的,不仅是指数为1的情况,每一次拆分前根据题目所需要的格式也要输出出来
		cout<<2;
		
		if (p == 0 || p == 2) cout<<'('<<p<<')';    //特殊情况
		//一般情况
		if (p >= 3) {
			cout<<'('; search(p); cout<<')'; 
		}
		//看看能不能继续搜索
		if (x - q > 0) {
			x -= q; cout<<'+'; search(x);
		}
	}
}

int main() {
	cin>>n;
	
	search(n);
	
	return 0;
}