首页 > 代码库 > PID277 / 整数拆分 (递归)
PID277 / 整数拆分 (递归)
题目描述
任何一个正整数都可以用2的幂次方表示。例如: {40%}
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≤20000)
输出格式
输出:符合约定的n的0,2表示(在表示中不能有空格)
#include<iostream> #include<cstdio> #include<cmath> using namespace std; void solve(int n) { int i,b[50],p=0; for(i=0;n>0;i++,n>>=1) //二进制转换,应该是最快的方法吧。 b[i]=n&1; for(i--;i>1;i--) { if(b[i]&1) { if(p) printf("+"); printf("2("); solve(i); printf(")"); p=1; } } if(b[1]&1) //特例1 { if(p) printf("+"); printf("2"); p=1; } if(b[0]&1) //特例2 { if(p) printf("+"); printf("2(0)"); } } int main() { int n; while(scanf("%d",&n)!=EOF) { solve(n); printf("\n"); } return 0; }
PID277 / 整数拆分 (递归)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。