洛谷 P1010 幂次方

原题链接

描述

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

?????137=\(2^{7}\)+\(2^{3}\)+\(2^{0}\)

??同时约定方次用括号来表示，即ab可表示为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)

输入

一个正整数n（n≤20000）。

输出

一个正整数n（n≤20000）。

样例输入

137

样例输出

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

分析

(未完待续...)

代码

#include<iostream>
#include<cmath>
using namespace std;
void dfs(int n){
    if(n==1){
        cout<<"2(0)";
        return ;
    }
    if(n==2){
        cout<<2;
        return ;
    }
    
    //求得商的指数 
    int k=0;//指数 
    while(pow(2,k)<=n)k++;
    k--;
    
    int temp=pow(2,k);
    if(temp==n){
        if(k==1){ cout<<2; }
        else { cout<<"2("; dfs(k); cout<<")"; }
        return;
    }
    else{
        //商的处理 
         cout<<"2"; if(k!=1){ cout<<"(";  dfs(k);  cout<<")"; } 
    
        cout<<"+";
        
        //余数处理
        dfs(n-temp);
        return ;
        
        
    }
}
int main(){
    int n;
    cin>>n;
    dfs(n);
    return 0;
}

小结

（未完待续...）

洛谷 P1010 幂次方

原文：https://www.cnblogs.com/yifeianyi/p/12409338.html