1501102328-藍橋杯-算法訓練 2的次冪表示

1501102328-藍橋杯-算法訓練 2的次冪表示

算法訓練 2的次冪表示 時間限制：1.0s 內存限制：512.0MB 問題描述 　　任何一個正整數都可以用2進制表示，例如：137的2進制表示為10001001。
　　將這種2進制表示寫成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） 輸入格式 　　正整數（1<=n<=20000） 輸出格式 　　符合約定的n的0，2表示（在表示中不能有空格） 樣例輸入 137 樣例輸出 2(2(2)+2+2(0))+2(2+2(0))+2(0) 樣例輸入 1315 樣例輸出 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

提示
用遞歸實現會比較簡單，可以一邊遞歸一邊輸出 解題思路 用遞歸來實現。將十進制數轉換成二進制，記錄轉換過程中為1的是第幾次循環，然後再判斷。遞歸的邊界就是當n==0,n==1n==2的時候。 但是應該注意的是，要判斷什麼時候輸出+號，什麼時候不輸出。當不是最後一個的時候就輸出 + 定義數組的時候要定義為局部變量，因為每一次數組存儲的都不同。 代碼

#include
int main()
{
	int n;
	void cimi(int n);
	while(scanf("%d",&n)!=EOF)
	{
		cimi(n);
		printf("\n");
	}
	return 0;
}
void cimi(int n)
{
	int num;
	int i,j,k;
	int a[32];//數組定義為局部變量 
	num=0;
	i=0;
	while(n)
	{
		j=n%2;
		if(j==1)
		    a[num++]=i;//存儲第幾次是1 
		i++;
		n/=2;
	}
	for(i=num-1;i>=0;i--)
	{
		if(a[i]==0)
			printf("2(0)");
		else if(a[i]==1)
			printf("2");
		else if(a[i]==2)
			printf("2(2)");
		else if(a[i]>2)
		{
			printf("2(");
			cimi(a[i]);
			printf(")");
		}
		if(i!=0)
		    printf("+");//如果不是最後一個就得輸出 +  
	}
}