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

洛谷——P1010幂次方

程序员文章站 2022-05-08 22:11:26
...

原题链接
仔细读题可以看出,这道题本质上是递归。比如对于8,8=2^3,而继续对3分析3又可拆解为2的一次幂和2的零次幂。因此,我们采用递归来解决这道题。

#include<iostream>
using namespace std;
int a[15];
//这个是让数组储存2的幂次方的结果
void POW() {
	a[0] = 1;
	for (int i = 1; i < 15; i++)
		a[i] = a[i - 1] * 2;
}
void print(int n) {
//无论如何,第一个输出的总会是2
	cout << 2;
	int j = 14;
//我们从最大的2的幂次开始,逐渐减少,找到最接近n但比n小的那个	
	while (n < a[j])
		j--;
//这里是特判,如果是零次幂或是二次幂,直接就输出(j)	
//ps:一次幂什么都不输
	if (j == 0 || j == 2)
		cout << "(" << j << ")";
//否则,先输出(,对j递归,在输出)		
	if (j >= 3) {
		cout << "(";
		print(j);
		cout << ")";
	}
	n -= a[j];
//接着要考虑n剩余的部分,如果还有就要输出+,并对剩余部分递归	
	if (n) {
		cout << "+";
		print(n);
	}

}
int main()
{
	POW();
	int n;
	cin >> n;
	print(n);
	return 0;
}
相关标签: C++ 洛谷 递归