洛谷OJ P1010 幂次方 解题报告

by MedalPluS

 题目描述

  任何一个正整数都可以用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   (21用2表示)
        3=2+20   
所以最后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表示(在表示中不能有空格)

 分析

  这题有点难度，其实是思维难度【毕竟是递归。。】

  脑补了10分钟才会做

  我们可以引入树结构来分析这题，递归都可以这么做

                                                                      【137】

                                         /                                 |                             \

                                    【2⁷】                        【2³】                        【2⁰】      //从这层起对指数分解

                               /         |         \                /         \

                         【2²】 【2¹】   【2⁰】  【2¹】  【2⁰】          

  那么递归方法就出来了， 在主函数分解原数，然后在子函数里分解指数，分解到一层就输出2(，分解到0,1,2各有各的输出，然后分解完一个就输出)

  分解的话利用倍增来解决

 代码

1 #include 
     
       2 #include 
      
        3 using namespace std; 4  5 int n; 6  7 void f(int n){ 8     if(n==0){ 9       printf("2(0)");10       return ;11     }12     if(n==1){13       printf("2");14       return ;15     }16     if(n==2){17       printf("2(2)");18       return ;19     }20     int up;21     printf("2(");22     while(n){23       for(up=0;(1<
       
        <=n;up++);24       up--;25       n-=(1<
        
         >n;35     int up;36     while(n){37       for(up=0;(1<
         
          <=n;up++);38       up--;39       n-=(1<