递归

冷不防 2021-12-24 08:43 334阅读 0赞

问题描述

任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。

将这种2进制表示写成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）

输入格式

正整数（1<=n<=20000）

输出格式

符合约定的n的0，2表示（在表示中不能有空格）

样例输入

137

样例输出

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

样例输入

1315

样例输出

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

提示

用递归实现会比较简单，可以一边递归一边输出

![loading.gif][]

\#include<iostream>

using namespace std;

void fun(int n) \{

int a\[10\];

int num=0,i;

for(int i=0; n; i++,n/=2) \{

if(n%2==1) \{

a\[num++\]=i;

for(int i=num-1; i>=0; i--) \{

switch(a\[i\]) \{

case 0:

cout<<"2(0)";

break;

case 1:

cout<<"2";

break;

case 2:

cout<<"2(2)";

break;

default:

cout<<"2(";

fun(a\[i\]);

cout<<")";

break;

if(i!=0)

cout<<"+";

int main() \{

int n;

while(cin>>n) \{

fun(n);

cout<<endl;

return 0;

算法训练 未名湖边的烦恼

时间限制：1.0s   内存限制：256.0MB

问题描述

每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。

每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）

输入格式

两个整数，表示m和n

输出格式

一个整数，表示队伍的排法的方案数。

样例输入

3 2

样例输出

数据规模和约定

m,n∈［0,18］

\#include<iostream>

using namespace std;

int m,n;

int count=0;

void fun(int a,int b) \{

if(a<b)

return;

if(a==m&&n==b)

count++;

else \{

if(a<m) fun(a+1,b);

if(b<n) fun(a,b+1);

int main() \{

while(cin>>m>>n) \{

fun(1,0);

cout<<count<<endl;

return 0;

转载于:https://www.cnblogs.com/wtblogwt/p/10585092.html

[loading.gif]: /images/20211223/012ddefbe2774ed2af56aa430fed63f2.png

递归

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关递归---从台阶问题学习递归、递归优化和非递归

相关递归

相关递归

相关递归——线性递归与二分递归

相关递归

相关递归

相关递归

相关递归

相关递归

相关递归