【日常学习】【搜索/递归】codevs2802 二的幂次方题解

雨点打透心脏的1/2处 2022-08-02 06:28 144阅读 0赞

题目描述 Description

任何一个正整数都可以用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)

输入描述 Input Description

正整数n

输出描述 Output Description

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

样例输入 Sample Input

【输入样例1】  
137  
【输入样例2】  
1315

样例输出 Sample Output

【输出样例1】  
2(2(2)+2+2(0))+2(2+2(0))+2(0)  
【输出样例2】  
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

数据范围及提示 Data Size & Hint

n为2的指数<=1100586419200

典型的递归题 很久没写搜索我都不会写了 感谢显摆点拨~

直接上代码一看就懂

关键是先输出左括号，递归，输出右括号 这种经典格局

还有其他方法 里奥的lowbit啊什么的= =慢慢学

注意要用long long 吐槽4.9.9.2悲了个剧的编译器 和codevs奇怪的编译原理= =

上代码

//整数的表示 number 递归 
    //copyright by ametake 
    #include
       
        
    #include
        
         
    #include
         
          
    using namespace std;
    
    long long duru;
    
    void digui(long long n)
    {
         if (n==1) {printf("2(0)");return;}
         long long x=1,count=0;
         while (x*2<=n)
         {
             x*=2;
             count++; 
         }
         long long left=n-x;//number left;
         if (count>=2)
         {
             printf("2(");
             digui(count);
             printf(")");//remember!
         }
         if (count==1) printf("2");
         if (left>0)
         {
             printf("+");
             digui(left);
         }
         return;
    }
    
    int main()
    {
        freopen("number.in","r",stdin);
        freopen("number.out","w",stdout);
        scanf("%lld",&duru);
        if (duru==0) {printf("0\n");return 0;}
        if (duru==1) {printf("2(0)\n");return 0;}
        digui(duru);
        return 0;
    }

——旧赏轻抛，到此成游宦