标签归档:递归

C++ primer plus 第7章 7.16程序修复版本

7.16程序修复版本

第五版原书的代码是无法显示如下图的所示的。

|                                                               |
|                                                               |
|                               |                               |
|               |               |               |               |
|       |       |       |       |       |       |       |       |
|   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

代码使用了递归。
经过测试,修复代码如下:

#include <iostream>
const int Len = 66;
const int Divs = 6;

void subdivide(char arr[], int low, int high, int level);

int main(void)
{
	char ruler[Len];

	int i;
	for (i = 1; i < Len - 2; i++)
		ruler[i] = ' ';
	ruler[Len - 1] = '\n';
	ruler[Len] = '\0';
	
	int max = Len - 2;
	int min = 0;

	ruler[min] = ruler[max] = '|';
	std::cout << ruler;

	for (i = 0; i <= Divs; i++) {
		subdivide(ruler, min, max, i);
		std::cout << ruler;
		for (int j = 1; j < Len - 2; j++)
			ruler[j] = ' ';			// reset to blank ruler
	}

	return 0;
}

void subdivide(char arr[], int low, int high, int level)
{
	if (level == 0)
		return;
	int mid = (high + low) / 2;
	arr[mid] = '|';

	subdivide(arr, low, mid, level - 1);
	subdivide(arr, mid, high, level - 1);

	return;
}

兔子问题

兔子问题来源:

根据高德纳(Donald Ervin Knuth)的《计算机程序设计艺术》(The Art of Computer Programming),1150年印度数学家Gopala和金月在研究箱子包装物件长阔刚好为1和2的可行方法数目时,首先描述这个数列。 在西方,最先研究这个数列的人是比萨的列奥那多(意大利人斐波那契 Leonardo Fibonacci),他描述兔子生长的数目时用上了这数列。

  • 第一个月初有一对刚诞生的兔子
  • 第二个月之后(第三个月初)它们可以生育
  • 每月每对可生育的兔子会诞生下一对新兔子
  • 兔子永不死去

假设在n月有可生育的兔子总共a对,n+1月就总共有b对。在n+2月必定总共有a+b对: 因为在n+2月的时候,前一月(n+1月)的b对兔子可以存留至第n+2月(在当月属于新诞生的兔子尚不能生育)。而新生育出的兔子对数等于所有在n月就已存在的a对

求第N个月兔子对数问题

就是一个斐波那契数列中的一个数
费波那契数列由0和1开始,之后的费波那契系数就由之前的两数相加。首几个费波那契系数是:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

使用递归方法实现(C++)

 

/*************************************************

 *	Name:  			求第N个月兔子对数
 *      Date:   		2014-11-4 23:34:45
 *      Author: 		lnesuper
 *      Version:    	V0.1
 *      Discription:    使用递归解决兔子问题
 *      In math:        F(0) = 0
 *                      F(1) = 1
 *                      F(n) = F(n-1) + F(n-2); (n>2)

**************************************************/

#include <iostream>
using namespace std;

int f(int n);

int main(void) {
	int n;
    cout << "请输入所求第n个月的数值: ";
    cin >> n;
    
	cout << "第" << n << "个月的兔子对数: " <<  f(n) << endl;
	
	return 0;
}

/*
	第一个月:  一对兔子
	第二个月:  二对兔子
  	第 N 个月: 第 N-1 个月的兔子数 + 第 N-2 个月兔子对数
*/
int f(int n) {
	if (1 == n)
		return 1;
	else if (2 == n)
		return 2;
	else
		return f(n - 1) + f(n - 2);
}

/*
Result:

请输入所求第n个月的数值: 40
第40个月的兔子对数: 165580141

--------------------------------
Process exited after 5.223 seconds with return value 0
请按任意键继续. . .

*/

继续阅读

二叉树C语言递归算法演示

二叉树的定义

在计算机科学中,二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

二叉树节点定义

struct BTNode {                    //定义二叉树节点名称, B表示二, T表示树, Node表示节点
char data;                    //定义二叉树数据域
struct BTNode * pLchild;    //定义二叉树左指针
struct BTNode * pRchild;    //定义二叉树右指针
};

继续阅读

汉诺塔C语言算法演示

汉诺塔简介:

有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:

  1. 每次只能移动一个圆盘;
  2. 大盘不能叠在小盘上面。

提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。

汉诺塔移动分析:

定义汉诺塔移动函数:

void hanoi(int n, char from, char buffer, char to);

1) 参数 n 表示要移动的盘子数

2) 参数 from 表示盘子所在的柱子

3) 参数 buffer 表示盘子移动过程中借助的柱子

4) 产生 to表示盘子最终要移到的柱子

初始状态:

将A柱子的N个圆盘移至C柱子上, 其中可以借助B柱子

汉诺塔移动初始状态

汉诺塔移动初始状态
移动n-1个盘子

汉诺塔的3个中间状态:

以下内容需要理解函数调用, 栈的知识

栈的知识: 先进后出, 后进先出

1): 汉诺塔移动n-1个盘子从A借助C移到B

hanoi-1

汉诺塔移动n-1个盘子从A借助C到B

移动代码: hanoi(n-1, from, to, buffer);

为何可以移动n-1个盘子, 这是初学者最难理解的部分. 要想理解, 必须理解栈的知识, 递归是一种反向思维.

2): 汉诺塔移动盘子n从A到C

汉诺塔移动盘子n从A到C

汉诺塔移动盘子n从A到C

移动代码: printf(“%d A->C\n”, n);

3): 汉诺塔移动n-1个盘子从B借助A移到B

汉诺塔移动n-1个盘子从B借助A移至C

汉诺塔移动n-1个盘子从B借助A移至C

移动代码: hanoi(n-1, buffer, from, to);

这是移动n-1个盘子的情况, 这和初始状态时一样的, 区别在于位于不同的柱子.

移动n-2个盘子并重复1-3步骤

接下来是移动n-2个盘子的情况. 因为 盘子n和n-1已经不要移动了(从递归的思想来看)

直到剩下一个盘子

这是就需要移动最后一个盘子到C, 实际的运算过程中程序会不断压栈(从n, n-1, 直到1), 然后执行此步操作, 注意之后的每一步都是每次移动一个盘子(之前只是压栈操作, 不要移动操作), 然后释放内存, 执行盘子2的操作, 直到最后移动盘子n-1, n的操作
继续阅读