難度：普及-（普及/提高-）

題目類型：分治

提交次數(shù)：1

涉及知識：分治

題目描述

任何一個正整數(shù)都可以用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)

輸入輸出格式

輸入格式：

一個正整數(shù)n(n≤20000)。

?

輸出格式：

符合約定的n的0，2表示(在表示中不能有空格)

?

代碼：

1 #include<iostream> 2 using namespace std; 3 int n; 4 int a[16]; 5 void solve(int x){ 6 int i = 0; 7 if(x){ 8 cout<<"2"; 9 while(x>=a[i]) 10 i++; 11 i--; 12 x-=a[i]; 13 if(i!=1) cout<<"("; 14 if(i == 0||i == 2) cout<<i<<")"; 15 if(i >= 3){ 16 solve(i); cout<<")"; 17 } 18 if(x!=0) { 19 cout<<"+"; solve(x); 20 } 21 } 22 return; 23 } 24 int main(){ 25 cin>>n; 26 int i; 27 a[0] = 1; 28 for(i = 1; i <= 15; i++) 29 a[i] = a[i-1]*2; 30 solve(n); 31 return 0; 32 }

備注：

to be honest。。這道題呢，就是我看了一遍某題解，又照著抄了一遍，并告訴自己只是通過這種方式熟悉一下分治思想……分析一下這道題的思路吧：大家都說題目已經(jīng)把遞歸過程說的很清楚了。然而我……

比較巧妙的一點就是，因為給了n<=20000，所以就打表把2的1——15次方都存在數(shù)組a里了。思路是，只要待處理的數(shù)字不是0，就先把2打上，找出這個數(shù)字的最大冪（就是2的i次方），把最大冪減掉，然后下面就處理減掉的這部分，即最大冪。

只要不是1（是1就不用打了），二話不說先把“（”打上，如果是0或2，直接輸出就行了，如果不是，就solve（i），然后最大冪這部分就finish了。

此時如果x還剩下，就先連接一個“+”，然后繼續(xù)處理x。

思路似乎是挺清晰的。但遞歸特別讓我頭疼……可能多練練就好了吧

轉(zhuǎn)載于:https://www.cnblogs.com/fangziyuan/p/5935936.html

總結(jié)

以上是生活随笔為你收集整理的1010 幂次方的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。