（一）枚舉 （二）遞歸 NOIP 2的幂次方

NOIP 2的幂次方

• ​​題目​​
• ​​AC代碼​​
• ​​解析​​

• ​​遞歸順序​​
• ​​遞歸及for循環是控制哪個變量​​
• ​​邊界條件​​

• ​​找變化的量​​
• ​​分析變量的變化​​

• ​​坑以及注意事項​​

• ​​+号如何輸出​​
• ​​（）如何輸出​​

• ​​新知識​​

• ​​和2進制有關的題目使用位處理​​
• ​​在遞歸函數前後進行符号的處理​​
• ​​第一次處理，第二次不處理，需要bool型标志位​​

題目

002:2的幂次方表示

檢視送出統計提問

總時間限制: 1000ms 記憶體限制: 65536kB

描述

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

137=27+23+20      

同時約定方次用括号來表示，即ab可表示為a(b)。由此可知，137可表示為：

2(7)+2(3)+2(0)      

進一步：7=22+2+20（21用2表示）

3=2+20      

是以最後137可表示為：

2(2(2)+2+2(0))+2(2+2(0))+2(0)      

又如：

1315=210+28+25+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表示（在表示中不能有空格）。

樣例輸入

137

樣例輸出

2(2(2)+2+2(0))+2(2+2(0))+2(0)

AC代碼

/**********************************************************************/
/*                     _   _   __  __    ____   _____                   */
/*                    | | | | |  \/  |  / ___| |  ___|                  */
/*                    | | | | | |\/| | | |     | |___                   */
/*                    | |_| | | |  | | | |___  | |___|                  */
/*                     \___/  |_|  |_|  \____| |_|                      */
/**********************************************************************/
# include<iostream>

using namespace std;
inline int GetBit(int n,int i)
{
  return (n >> i ) & 1;
}

void twoPower(int n)
{
  bool first = true; 
  for(int i=15 ; i>=0;i--)
  {
    if(GetBit(n,i))
    {
      if(!first)
      {
        cout << "+";
      }
      else
      {
        first = false;  
      }
     if(i == 1)
     {
      cout << "2";
      
     } 
     else if(i == 0)
     {
      cout << "2(0)";
     }
     else
     {
      cout << "2(";
       twoPower(i);
       cout << ")";
     }
     
    } 
  }
}

int main()
{
  int n =0 ; 
  cin >> n;
  twoPower(n);
}      

解析

​​參看中國大學慕課郭炜老師課程講解遞歸二​​​ 一個整數，可以用二進制表示，比如137(D)=1000 1001(B)

很明顯137 = 27+23+2(因為該數字用二進制表示，第0,3，7)位是1

遞歸順序

從小到大還是從大到小，根據輸出的要求決定。這道題，從左到右輸出，顯然是從大到小，從高位開始周遊輸出

遞歸及for循環是控制哪個變量

對于一個表達式，遞歸函數twopower()是将參數n分解為2的幂，

for循環對該數值二進制的每一位進行變周遊，以及對應處理，是處理這個最終輸出的表達式的項，是以"+"在for循環裡處理

邊界條件

分為兩步

找變化的量

n以及i

分析變量的變化

主要是i，i到0,1時需要輸出，不能進行函數遞歸

坑以及注意事項

+号如何輸出

（）如何輸出

新知識

和2進制有關的題目使用位處理

在遞歸函數前後進行符号的處理

第一次處理，第二次不處理，需要bool型标志位