递归解决2的幂次方

2019-11-11 03:46:46

字体：大中小

来源：转载

供稿：网友

总时间限制: 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)

来源 NOip1998复赛普及组第一题

每一个数都可以分解为2的x次幂加上另外一个数然后依次递归将x和另外的一个数分解最后的结果都可以归结为1，2，3三种情况将这三种情况作为程序的结束点#include <iostream>#include <cmath>using namespace std;int maxNum=142; //2^142>20000void micifang(int n);int main(){ int n; cin >> n; micifang(n); return 0;}void micifang(int n){ if(n==1){ cout << "2(0)"; return; } if(n==2){ cout << "2"; return; } if(n==3){ cout << "2+2(0)"; return; } for(int i=0;i<maxNum;i++){ if( n>=pow(2,i) && n<pow(2,i+1)){ cout << "2("; micifang(i); cout << ")"; if(n-pow(2,i)>0){ cout << '+'; micifang(n-pow(2,i)); } } }}

上一篇：laravel5.1 源码阅读

下一篇：一文读懂机器学习，大数据/自然语言处理/算法