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

【项目-用递归方法求解】
(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);
        }
}

时间: 2024-09-16 09:35:28

C++项目参考-用递归方法求解的相关文章

C语言OJ项目参考(2968)递归方法实现逆序

2968: 递归方法实现逆序 Description 你知道递归么?简单来说,递归就是函数自身对自身的调用,直到遇到终止条件,再对数据做逆向处理,下面就有一个递归的简单例子等你来处理. #include <stdio.h> void inverted(int); /*函数声明*/ int main() { int n; /*需要逆序的整数*/ scanf("%d",&n); inverted(n); /*调用逆序函数*/ return 0; } void inver

java递归方法求解:2BCD+BCDE=DA01,将字母替换成不同的数字满足等式

问题描述 java递归方法求解:2BCD+BCDE=DA01,将字母替换成不同的数字满足等式 如题 public class Puzzle { private String add1; private String add2; private String result; private Puzzle nowPuzzle; /** * Constructs a puzzle. * * @param add1 a string containing digits 0 - 9 and letters

mvc4-MVC4 突然运行报错,其他类型项目不会,求解,急!

问题描述 MVC4 突然运行报错,其他类型项目不会,求解,急! 解决方案 解决了,还是补丁的问题...就这两个坑补丁. 解决方案二: 应该是外部环境的问题,重装系统看看.或者你的机器上有side by side配置问题,重新卸载安装下.net framework 解决方案三: 环境是Windows 8 + VS2012 前几天报这个错,是个补丁的原因,卸载了就好了,现在又报了这个错,求大神解啊,在线等~

C++程序设计实践学材系列(27)——1.8 实践“项目”参考解答

回到系列文章的目录--[系列文章目录] 回到本章目录--[第1章目录] 1.8 实践"项目"参考解答 本节与前面各节相关性极大,建议由前面各节看清项目要求,必要时再阅读本节. [项目1.1] #include <iostream> using namespace std; int main( ) { cout<<"C++,我会爱上你!"<<endl; return 0; } [项目1.2] #include <iostrea

2013-C++第11周项目参考解答链接集

课程首页在:http://blog.csdn.net/sxhelijian/article/details/11890759 完整题目见:http://blog.csdn.net/sxhelijian/article/details/14109337 [项目1-调用函数输出星号图] 参考解答见:http://blog.csdn.net/sxhelijian/article/details/14548417 [项目2-求最大公约数]输入两个数,并求出其最大公约数 [项目2扩展-求四数的最大公约数]

2013-C++第9周项目参考解答链接集

课程首页在:http://blog.csdn.net/sxhelijian/article/details/11890759 完整题目见:http://blog.csdn.net/sxhelijian/article/details/12911289 [项目1分段函数求值]从键盘输入x的值(整型),根据公式1计算并输出x和y的值.  要求用switch语句构造多分支结构完成求解. 参考解答见:http://blog.csdn.net/sxhelijian/article/details/1328

C++项目参考解答-太乐了

[项目-太乐了] (1)先听故事,再编程序.故事是这样的:话说sin和cos是一对夫妇.一天,sin去听相声了,cos在家.过了一会,有人敲门,cos开门一看,是一个不认识的多项式函数.cos问:你是谁啊?他说:我是你的老公sin啊.cos说:你不是去听相声了吗?怎么成这幅摸样了?sin说:是啊,太乐了!故事讲完了.下面是sin函数的泰勒展式:(注:x取弧度值,而非角度值)用sin泰勒展式编写程序,求出sin(π/2)和sin(56°)的值,精度要求达到小数点后6位(即当最后一项的绝对值小于0.

C++项目参考解答:小试循环

[项目-小试循环] 写出实现下面求解任务的程序[提示:m是一个变量,在程序中输入] (1)求1到m的平方和 (2)求1到m间所有奇数的和 (3)求1到m的倒数和,即 1+12+13+14+...+1m (4)求值:1−12+13−14+...+(−1)(m+1)×1m (5)求m!,即1×2×3×...×m [参考解答] 写出实现下面求解任务的程序[提示:m是一个变量,在程序中输入] (1)求1到m的平方和 #include <iostream> using namespace std; in

2013-C++第15周项目参考解答链接集

课程主页在:http://blog.csdn.net/sxhelijian/article/details/11890759 [项目1-折腾二维数组]创建一个长度为5行4列的二维整型数组,通过初始化,为数组中的前两列的10个元素赋初值,然后通过键盘输入,使后两列的10个元素获得值,将所有元素值乘以3后保存在数组中.输出数组时,按行序优先输出,再按列序优先输出(输出的第一行是数组中的第一列--,其实输出的就是"转置"),再将数组"倒"着输出(即最后一行最后一列的最先输