[C++知识库]幂方分解（c语言 内存超级小）

【问题描述】

????????任何一个正整数都可以用2的幂次方表示。例如：

????????137=2^7+2^3+2^0

????????同时约定方次用括号来表示，即a^b可表示为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<=20000），为要求分解的整数。

【输出格式】

? ? ? ? 程序输出包含一行字符串，为符合约定的n的0，2表示（在表示中不能有空格）

【分析】

? ? ? ? 该题使用递归做。

? ? ? ? 最大数为2^14<20000<2^15

? ? ? ? 2^3<14<2^4

? ? ? ? 2^1<3<2^2

? ? ? ? 可知最多需要三次递归。

【代码】

? ? ? ?

#include<stdio.h>
void digui2(int j){        //第三次递归，目的是分解二维幂次
		int i=0,n=1;
	for(;n<=j;i++){
		n*=2;
	}
	i--;        //标记三维幂次
	printf("2");
	if(i==0){
		printf("(%d)",i);
		}
	if((j-=(n/2))!=0){        //符合第三次递归，二维幂次没有完全被表示
		printf("+");
		digui2(j);
	}
}
void digui1(int j){        //第二次递归，递归的是一维幂次
	int i=0,n=1;
	for(;n<=j;i++){
		n*=2;
	}
	i--;        //标记二维幂次
	printf("2");
	if(i==0){
		printf("(%d)",i);
		}
		if(i>1){        //符合第三次递归
		printf("(");
		digui2(i);
		printf(")");
	}
	if((j-=(n/2))!=0){        //符合第二次递归，第一维幂次还没有被完全表示
		printf("+");
		digui1(j);
	}
}
void digui(int N){        //第一次递归，递归的是N=n1+n2+……
	int i=0,n=1;
	for(;n<=N;i++){
		n*=2;
	}
	i--;        //找出每个一维幂次
	printf("2");
	if(i==0){
		printf("(%d)",i);
		}
	if(i>1){        //符合第二次递归的条件，题目要求只能用0，2表示
		printf("(");
		digui1(i);
		printf(")");
	}
	if((N-=(n/2))!=0){        //符合第一次递归的条件，N没有被表示完全
		printf("+");
		digui(N);
	}
}
int main(){
	int N;
	scanf("%d",&N);
	digui(N);
	return 0;
} 

? ?【附语】

我也想过用一个递归函数把这所有次的递归全部包含，因为这三次递归算法都一样，但是我也试过，递归函数要几种递归就要给函数加几个参数，大概是表示递归的状态吧，根据状态来判断下次递归的类型，但是难度太大。希望读者可以尝试一下。

? ? ? ?