开发者社区> 贺利坚> 正文

C++项目参考-用递归方法求解

简介: 【项目-用递归方法求解】(1)编写递归函数求出n的阶乘(自定义main函数,调用定义的递归函数) 参考解答: #include <iostream> using namespace std; long fact(int); //函数声明 int main( ) { int n;
+关注继续查看

【项目-用递归方法求解】
(1)编写递归函数求出n的阶乘(自定义main函数,调用定义的递归函数)

参考解答:

#include <iostream>
using namespace std;
long fact(int);                           //函数声明
int main( )
{
	int n;                                 //n为需要求阶乘的整数
	long y;                                //y为存放n!的变量
	cout<<"please input an integer :";     //输入的提示
	cin>>n;                                //输入n
	y=fact(n);                              //调用fac函数以求n!
	cout<<n<<"!="<<y<<endl;                //输出n!的值
	return 0;
 }

long fact(int n)                          //递归函数
{
	long f;
	if (n==0) f=1;				//0!和1!的值为1
	else f=fact(n-1)*n;                  //n>1时,进行递归调用
	return f;                           //将f的值作为函数值返回
}


(2)写出求1*3*...*n的递归式,并编写出递归函数求解。

参考解答:

#include <iostream>
using namespace std;
long f(int);
int main( )
{
    int n;
    long y;
    cout<<"请输入一个数 :";
    cin>>n;
    if(n%2) //若奇数
        y=f(n);
    else
        y=f(n-1);
    cout<<n<<"以内的奇数积是:"<<y<<endl;
    return 0;
}

long f(int n)
{
    long s;
    if (n==1)
        s=1;
    else
        s=f(n-2)*n;
    return s;
}

(3)编程序,用递归函数求出两个数的最大公约数。(包括编main函数,调用定义的递归函数)

参考解答:

//递归解法
#include "iostream"
using namespace std;
int gcd(int x, int y);
void main()
{
	int m,n;
	cout<<"输入两个数字:";
	cin>>m>>n;
	cout<<"最大公约数:";
	cout<<gcd(m,n)<<endl;
}


int gcd(int a, int b)
{
	int t,g;
	//if (a < b) t=a,a=b,b=t;   //无所谓大小
	if (b==0)
		g=a;
	else
		g=gcd(b,a%b);
	return g;
}


(4)编制递归函数fib(int n)返回第n个Fibnacci数,以此输出Fibnacci序列的第20个数。

参考解答:

//递归法
#include <iostream>
using namespace std;
int fib(int n);
int main()
{
   cout<<fib(20)<<endl;
   return 0;      
}
//返回Fibnacci序列中的第n个数
int fib(int n)
{ 
	if(n==1)
		return 0;
	else if(n==2)
		return 1;
	else
		return(fib(n-1)+fib(n-2));
}


(5)输入一个整数n,要求输出对应的二进制形式,请用递归函数实现。

参考解答:

#include <iostream>
using namespace std;
void dec2bin(int n);
int main()
{
	int n;
	cout<<"请输入一个整数:";
	cin>>n;
	cout<<n<<"对应的二进制形式为:";
	dec2bin(n);
	cout<<endl;
	return 0;
}
void dec2bin(int n)
{
	if(n==0)
		return;       //其实在此有个BUG,如果在main()中直接调用的是dec2bin(0),并不会输出其二进制形式0,请在评论中跟进如何处理
	else
	{
		dec2bin(n/2);
		cout<<n%2;
		return;
	}
}

提示:二进制整数n转换为二进制的方法是“除2取余法”,即将n除以2后得到的余数,由后到前“串”起来,得到对应的二进制数,如图。



(6)汉诺塔
汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。古代有一个梵塔,塔内有三个座A、B、C,A座上有64个盘子,盘子大小不等,大的在下,小的在上。有一个和尚想把这64个盘子从A座移到C座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。在移动过程中可以利用B座,下面左图给出了移动方法的提示。请编制递归函数输出盘子数为4时(程序调试后,试试15个、20个,直至64个,看看会如何),移动的方案。图为盘子数为3时的输出供参考。

参考解答:

#include <iostream>
using namespace std;
const int discCount=3;
void move(int, char, char,char);
int main()
{ 
	move(discCount,'A','B','C');
	return 0;
}


void move(int n, char A, char B,char C)
{
	if(n==1)
	{
		cout<<A<<"-->"<<C<<endl;
		return;
	}
	else
	{
		move(n-1,A,C,B);
		cout<<A<<"-->"<<C<<endl;
		move(n-1,B,A,C);
		return;
	}
}

下面的解答还可以输出移动的次数,当盘子数太多时,这是个温柔长的过程:

//输出且计数
#include <iostream>
using namespace std;
const int discCount=3;
long move(int, char, char,char);
int main()
{ 
	long count;
	count=move(discCount,'A','B','C');
	cout<<discCount<<"个盘子需要移动"<<count<<"次。"<<endl;
	return 0;
}


long move(int n, char A, char B,char C)
{
	long c1,c2;
	if(n==1)
	{
		cout<<A<<"-->"<<C<<endl;
		return 1;
	}
	else
	{
		c1=move(n-1,A,C,B);
		cout<<A<<"-->"<<C<<endl;
		c2=move(n-1,B,A,C);
		return c1+c2+1;
	}
}

下面的代码不去输出移动方案,仅输出需要移动的次数,免去了输出花费的时间:

//仅计数
#include <iostream>
using namespace std;
const int discCount=3;
long move(int, char, char,char);
int main()
{ 
	long count;
	count=move(discCount,'A','B','C');
	cout<<discCount<<"个盘子需要移动"<<count<<"次。"<<endl;
	return 0;
}


long move(int n, char A, char B,char C)
{
	long c1,c2;
	if(n==1)
	{
		return 1;
	}
	else
	{
		c1=move(n-1,A,C,B);
		c2=move(n-1,B,A,C);
		return c1+c2+1;
	}
}


有同学的输出中,加入了“几号盘子”字样,输出信息更明白:

#include <iostream>
using namespace std;
void move(int n, char A, char B,char C);//盘子数由序号数增大而依次增大
int main()
{
	move(4,'A','B','C');
	return 0;
}
//有n个盘子,
void move(int n, char A, char B,char C)
{
    if(n==1)
    {
        cout<<n<<"号盘子:"<<A<<"  to  "<<C<<endl;
    }
    else
        {
            move(n-1,A,C,B);
            cout<<n<<"号盘子:"<<A<<"  to  "<<C<<endl;
            move(n-1,B,A,C);
        }
}




版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
C++第16周项目4 -处理C++源代码 - (2)花括号单独占一行
课程首页地址:http://blog.csdn.net/sxhelijian/article/details/7910565,本周题目链接:http://blog.csdn.net/sxhelijian/article/details/9078413 【项目4】写处理C++源代码的程序    (2)读入一个C++程序,使程序中的所有左花括号“{”和右花括号“}”都单独占一行,新程序保存到另
1044 0
2014秋C++ 第13周项目 C++中的一维数组
课程主页在http://blog.csdn.net/sxhelijian/article/details/39152703,课程资源在云学堂“贺老师课堂”同步展示,使用的帐号请到课程主页中查看。  【项目1 - 数组大折腾】(1)创建一个有20个元素的整型数组,通过初始化,为数组中的前10个元素赋初值,然后通过键盘输入后10个元素的值,从前往后(从第0个到第19个)输出数组中元素的值,每5个
1093 0
关于React Native项目在android上UI性能调试实践
我们尽最大的努力来争取使UI组件的性能如丝般顺滑,但有的时候这根本不可能做到。要知道,Android有超过一万种不同型号的手机,而在框架底层进行软件渲染的时候是统一处理的,这意味着你没办法像iOS那样自由。不过有些时候,你还是可以想办法提升应用的性能(有的时候问题根本不是出在原生代码上!) 要想解决应用的性能问题,第一步就是搞明白在每个16毫秒的帧中,时间都去哪儿了。为此,我们会使用一个标准的
2706 0
C++第16周项目4 -处理C++源代码 - (1)有没有main函数?
课程首页地址:http://blog.csdn.net/sxhelijian/article/details/7910565,本周题目链接:http://blog.csdn.net/sxhelijian/article/details/9078413 【项目4】写处理C++源代码的程序   (1)读入一个C++程序,判断其中是否只有一个main()函数,输出“暂时没有发现问题”,或者“没有
964 0
2014秋C++ 第12周项目 C++函数新特征与递归函数
课程主页在http://blog.csdn.net/sxhelijian/article/details/39152703,课程资源在云学堂“贺老师课堂”同步展示,使用的帐号请到课程主页中查看。  【项目1- 阅读程序】阅读下列程序,写出程序的运行结果。上机时运行程序,与你的预期进行对照、理解。如果对运行结果和其背后的原理仍不理解,请通过单步执行的手段跟踪理解。(1)阅读下面两个有静态局部变量
1145 0
C++第16周项目3 -电子词典
课程首页地址:http://blog.csdn.net/sxhelijian/article/details/7910565,本周题目链接:http://blog.csdn.net/sxhelijian/article/details/9078413 【项目3】电子词典   做一个简单的电子词典。在文件dictionary.txt中,保存的是英汉对照的一个词典,词汇量近8000个,英文、中文释
914 0
2014秋C++ 第10周项目 控制结构综合、C程序结构及输入输出
课程主页在http://blog.csdn.net/sxhelijian/article/details/39152703,课程资源在云学堂“贺老师课堂”同步展示,使用的帐号请到课程主页中查看。 【项目1:程序填充与阅读】云学堂中有完整的代码,不必再费力亲自输入:1.阅读下面的程序,在____上填上合适的成份,使程序能够输入“1+2”形式的式子,并输出相应的结果。 #include &lt;
1160 0
C++项目参考-用递归方法求解
【项目-用递归方法求解】(1)编写递归函数求出n的阶乘(自定义main函数,调用定义的递归函数) 参考解答: #include &lt;iostream&gt; using namespace std; long fact(int); //函数声明 int main( ) { int n;
959 0
+关注
贺利坚
烟台大学计算机学院教师,建设系列学习资源,改革教学方法,为IT菜鸟建跑道,让大一的孩子会编程,为迷茫的大学生出主意,一起追求快乐的大学。 著书《逆袭大学:传给IT学子的正能量》,帮助处于迷茫中的大学
1965
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
OceanBase 入门到实战教程
立即下载
阿里云图数据库GDB,加速开启“图智”未来.ppt
立即下载
实时数仓Hologres技术实战一本通2.0版(下)
立即下载