首页 > 其他分享 >用C语言实现汉诺塔问题（第四天：函数递归）【每天进步一点点-小白学习笔记】

用C语言实现汉诺塔问题（第四天：函数递归）【每天进步一点点-小白学习笔记】

时间：2024-11-08 13:48:27浏览次数：3  
标签：SeqStack int printArr 第四天 C语言 汉诺塔 printf data size

0  前言

        最近比较忙，到现在才有时间更新博客，这两天刚好学到了函数递归，这是个很有趣的知识，为什么说有趣呢？因为递归这个东西吧，很多人都对它又爱又恨。爱在递归不仅可以轻松简化代码，增加可读性，还能将一些很难解决的算法问题轻松解决，但它又大大加大了程序复杂度，既浪费内存又运行慢，还容易出现各种类似于栈溢出之类的BUG，但这东西好用又是真的好用，因此让人又爱又恨。今天我也尝试着用递归来打打两个精英怪：汉诺塔问题 与 青蛙过河问题。

1  题目概述

        在经典汉诺塔问题中，有3根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
        (1) 每次只能移动一个盘子;

        (2) 盘子只能从柱子顶端滑出移到下一根柱子;
        (3) 盘子只能叠在比它大的盘子上。

        请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

>> 示例1：

输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]

>> 示例2:

输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]

>> 提示：

        1. 你需要原地修改栈。

        2. A中盘子的数目不大于14个。

2  题目分析

        汉诺塔问题文字叙述还是有点抽象，于是我画了个图进行模拟：

        根据演示很容易能看出，汉诺塔问题的解决就是在保证下面的盘子比上面大的情况下，最终实现将第一个柱子上所有圆盘转移到最后一个圆盘上。那么很容易发现一个规律：假如设第一个柱子为A、第二个为B、第三个为C，转移其他圆盘前要先把最大那个圆盘转移到目标柱上，也就是说将柱A上面的圆盘全部转移到柱B上后才能转移最大的圆盘到柱C，那么以此类推转移完最大的圆盘后，第二大的圆盘转移也是同理，那么就可以根据这一点写出递归算法：将最大的圆盘转移的算法。

        首先为了模拟柱子，先定义一个结构体类型来模拟顺序栈：

//定义简单栈
typedef struct MyStack {
	int size;  //栈长
	int* data;  //栈数组
}MyStack;

        然后针对我创建的顺序栈（柱子）和上述分析写一个移动圆盘的递归函数：

static int count = 0;  //移动次数

//移动操作（移动圆盘数，源栈，辅助栈，目标栈）
void Move_1(int num, MyStack *A, MyStack* B, MyStack* C) {
	//如果只要移动一个，则直接将A中盘挪到C中
	if (1 == num) {
		//C栈在尾部接收数据后栈长+1，A栈栈长-1并将尾部数据发送（size-1为栈中最后一个元素下标）
		C->data[C->size++] = A->data[--A->size];
		return;  //直接跳出循环
	}
    count++;
	//将除最大圆盘以外圆盘从栈A移动到栈B，C作为辅助栈
	Move_1(num - 1, A, C, B);  
	//将最大圆盘从栈A移动到栈C
	Move_1(1, A, B, C);  
	//将剩余圆盘从栈B移动到栈C，A作为辅助栈
	Move_1(num - 1, B, A, C); 
}

        最后填入汉诺塔函数中：

#define MAX_NUM 15  //取提示中最多不超过14块圆盘

void hanota_1(int* A, int* ASize, int* B, int BSize, int** C, int* CSize) {
	//创建并分配栈
	MyStack X, Y, Z;
	X.data = A;
	X.size = *ASize;
	//Y.data = B;
	Y.data = (int*)malloc(MAX_NUM * (sizeof(int)));  //要及时释放（辅助栈）
	Y.size = 0;
	//Z.data = C;
	Z.data = (int*)malloc(MAX_NUM * (sizeof(int)));  //由于要传回main故不能释放
	Z.size = 0;
	Move_1(*ASize, &X, &Y, &Z);
	*C = Z.data;
	*CSize = Z.size;
	*ASize = 0;
	free(Y.data);
}

        最后放入main函数中进行用例测试：

//数组打印函数（为了方便测试写的）
void printArr(int* Arr, int ArrSize) {
	int i = 0;
	printf(" = [");
	if (ArrSize > 0) {
		for (i = 0; i < ArrSize; i++) {
			printf("%d", Arr[i]);
			if (i < ArrSize - 1)
				printf(", ");
		}
	}
	printf("]\n");
}

//主函数入口
int main() {
	int A[] = { 2, 1, 0 };
	int ASize = sizeof(A) / sizeof(A[0]);
	int B[3];
	int BSize = 0;
	int* C = NULL;
	int CSize = 0;
	printf("交换前：\nA"); printArr(A, ASize);  //打印交换前数组
	printf("B"); printArr(B, BSize);
	printf("C"); printArr(&C, CSize);
	hanota_1(A, &ASize, B, BSize, &C, &CSize);  //汉诺塔替换
	printf("交换%d次后：\nA",count); printArr(A, ASize);  //打印交换后数组
	printf("B"); printArr(B, BSize);
	printf("C"); printArr(C, CSize);
	
	return 0;
}

        运行结果如下：

        运行结果也很成功。由此可见我前面的分析整体来看是正确的。但再一看后我发现其实该代码内的内聚度较低、耦合度较高，作为一名未来的程序员，我当然要尽可能实现高内聚低耦合的理想代码，于是我开始拆解我的代码并建立模块，进行模块化编程，把栈的操作直接细分为创建、数据入栈、数据出栈三个单一功能的函数：

#include <climits>
#define MAX_NUM 15  //取提示中最多不超过14块圆盘

//定义顺序栈
typedef struct SeqStack {
	int size;  //栈大小
	int* data;  //栈内数据
	int top;  //栈顶指针（用于尾插与尾删）
}SeqStack;

//创建栈操作
SeqStack* CreateSeqStack(int size, int* arr) {
	SeqStack* S = (SeqStack*)malloc(sizeof(SeqStack));
	S->size = size;
	S->top = size - 1;  //栈顶指针指向最后一个元素
	S->data = (int*)malloc(MAX_NUM * sizeof(int));
	for (int i = 0; i < size; i++) {
		S->data[i] = arr[i];
	}
	return S;
}

//入栈操作
void PushStack(SeqStack* S, int val) {
	//防止越界
	if (S->top == (MAX_NUM - 1)) {
		printf("已饱和，无法入栈");
		return;
	}
	S->top++;
	S->data[S->top] = val;
	S->size++;
}

//出栈操作
int PopStack(SeqStack* S) {
	if (S->top == -1) {
		printf("栈空，无法出栈");
		return INT_MIN;
	}
	int r = S->data[S->top];
	S->top--;
	S->size--;
	return r;
}

        因此咱们的汉诺塔操作也可以进一步简化为：

static int count2 = 0;  //移动次数

//移动操作（移动圆盘数，源栈，辅助栈，目标栈）
void Move_2(int num, SeqStack* A, SeqStack* B, SeqStack* C) {
	//如果只要移动一个，则直接将A中盘挪到C中
	if (1 == num) {
		int val = PopStack(A);
		PushStack(C, val);
		count2++;  //计数加一
		return;  //直接跳出循环
	}
	//将除最大圆盘以外圆盘从栈A移动到栈B，C作为辅助栈
	Move_2(num - 1, A, C, B);
	//将最大圆盘从栈A移动到栈C
	Move_2(1, A, B, C);
	//将剩余圆盘从栈B移动到栈C，A作为辅助栈
	Move_2(num - 1, B, A, C);
}

void hanota_2(int* A, int* ASize, int* B, int BSize, int** C, int* CSize) {
	//创建并分配栈
	SeqStack* X = CreateSeqStack(*ASize, A);
	SeqStack* Y = CreateSeqStack(BSize, B);
	SeqStack* Z = CreateSeqStack(*CSize, *C);
	Move_2(*ASize, X, Y, Z);
	*C = Z->data;
	*CSize = Z->size;
	*ASize = 0;
	free(Y);
}

        填入测试用例后运行结果：

        由此可见，依旧是可以顺利运行。那么让我们记录一下二者的运行时间，对比一下两者的运行速度：

#include <time.h>

//主函数入口
int main() {
	clock_t start_time_1 = clock();//记录方法一开始时间

	//测试用例1
	int A[] = { 2, 1, 0 };
	int ASize = sizeof(A) / sizeof(A[0]);
	int B[3];
	int BSize = 0;
	int* C = NULL;
	int CSize = 0;
	printf("交换前：\nA"); printArr(A, ASize);  //打印交换前数组
	printf("B"); printArr(B, BSize);
	printf("C"); printArr(&C, CSize);
	hanota_1(A, &ASize, B, BSize, &C, &CSize);  //汉诺塔替换
	printf("交换%d次后：\nA",count1); printArr(A, ASize);  //打印交换后数组
	printf("B"); printArr(B, BSize);
	printf("C"); printArr(C, CSize);
	
	clock_t end_time_1 = clock();  //记录方法一结束时间
	double elapsed_time_1 = (double)(end_time_1 - start_time_1) / CLOCKS_PER_SEC;  //计算运行秒数
	printf("方法1运行时间：%f秒\n", elapsed_time_1);
	printf("\n---------------分割线----------------\n\n");
	clock_t start_time_2 = clock();//记录方法二开始时间

	//测试用例2
	int AA[] = { 3, 2, 1, 0 };
	int AASize = sizeof(AA) / sizeof(AA[0]);
	int BB[4];
	int BBSize = 0;
	int* CC = NULL;
	int CCSize = 0;
	printf("交换前：\nAA"); printArr(AA, AASize);  //打印交换前数组
	printf("BB"); printArr(BB, BBSize);
	printf("CC"); printArr(&CC, CCSize);
	hanota_2(AA, &AASize, BB, BBSize, &CC, &CCSize);  //汉诺塔替换
	printf("交换%d次后：\nAA", count2); printArr(AA, AASize);  //打印交换后数组
	printf("BB"); printArr(BB, BSize);
	printf("CC"); printArr(CC, CCSize);

	clock_t end_time_2 = clock();  //记录方法二结束时间
	double elapsed_time_2 = (double)(end_time_2 - start_time_2) / CLOCKS_PER_SEC;  //计算运行秒数
	printf("方法二运行时间：%f秒\n", elapsed_time_2);

	return 0;
}

        根据上述结果可以见得，方法二哪怕是在进行过更多步的操作后，运行速度也是远超方法一的，由此也能看出代码模块化的牛逼之处。（注：不同电脑不同状态下运行时间是不同的，性能比较好的电脑这里的秒数可能会越界出现0.000000秒之类的数字）

3  完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <climits>
#include <time.h>


//*************① 汉诺塔问题**************
#define MAX_NUM 15  //取提示中最多不超过14块圆盘
static int count1 = 0;  //方法1移动次数
static int count2 = 0;  //方法2移动次数


//*****************方法一******************
//定义简单栈
typedef struct MyStack {
	int size;  //栈长
	int* data;  //栈数组
}MyStack;


//移动操作（移动圆盘数，源栈，辅助栈，目标栈）
void Move_1(int num, MyStack *A, MyStack* B, MyStack* C) {
	//如果只要移动一个，则直接将A中盘挪到C中
	if (1 == num) {
		//C栈在尾部接收数据后栈长+1，A栈栈长-1并将尾部数据发送（size-1为栈中最后一个元素下标）
		C->data[C->size++] = A->data[--A->size];
		count1++;  //计数加一
		return;  //直接跳出循环
	}
	//将除最大圆盘以外圆盘从栈A移动到栈B，C作为辅助栈
	Move_1(num - 1, A, C, B);  
	//将最大圆盘从栈A移动到栈C
	Move_1(1, A, B, C);  
	//将剩余圆盘从栈B移动到栈C，A作为辅助栈
	Move_1(num - 1, B, A, C); 
}


void hanota_1(int* A, int* ASize, int* B, int BSize, int** C, int* CSize) {
	//创建并分配栈
	MyStack X, Y, Z;
	X.data = A;
	X.size = *ASize;
	//Y.data = B;
	Y.data = (int*)malloc(MAX_NUM * (sizeof(int)));  //要及时释放（辅助栈）
	Y.size = 0;
	//Z.data = C;
	Z.data = (int*)malloc(MAX_NUM * (sizeof(int)));  //由于要传回main故不能释放
	Z.size = 0;
	Move_1(*ASize, &X, &Y, &Z);
	*C = Z.data;
	*CSize = Z.size;
	*ASize = 0;
	free(Y.data);
}


//*****************方法二******************
//定义顺序栈
typedef struct SeqStack {
	int size;  //栈大小
	int* data;  //栈内数据
	int top;  //栈顶指针（用于尾插与尾删）
}SeqStack;

//创建栈操作
SeqStack* CreateSeqStack(int size, int* arr) {
	SeqStack* S = (SeqStack*)malloc(sizeof(SeqStack));
	S->size = size;
	S->top = size - 1;  //栈顶指针指向最后一个元素
	S->data = (int*)malloc(MAX_NUM * sizeof(int));
	for (int i = 0; i < size; i++) {
		S->data[i] = arr[i];
	}
	return S;
}


//入栈操作
void PushStack(SeqStack* S, int val) {
	//防止越界
	if (S->top == (MAX_NUM - 1)) {
		printf("已饱和，无法入栈");
		return;
	}
	S->top++;
	S->data[S->top] = val;
	S->size++;
}


//出栈操作
int PopStack(SeqStack* S) {
	if (S->top == -1) {
		printf("栈空，无法出栈");
		return INT_MIN;
	}
	int r = S->data[S->top];
	S->top--;
	S->size--;
	return r;
}


//移动操作（移动圆盘数，源栈，辅助栈，目标栈）
void Move_2(int num, SeqStack* A, SeqStack* B, SeqStack* C) {
	//如果只要移动一个，则直接将A中盘挪到C中
	if (1 == num) {
		int val = PopStack(A);
		PushStack(C, val);
		count2++;  //计数加一
		return;  //直接跳出循环
	}
	//将除最大圆盘以外圆盘从栈A移动到栈B，C作为辅助栈
	Move_2(num - 1, A, C, B);
	//将最大圆盘从栈A移动到栈C
	Move_2(1, A, B, C);
	//将剩余圆盘从栈B移动到栈C，A作为辅助栈
	Move_2(num - 1, B, A, C);
}


void hanota_2(int* A, int* ASize, int* B, int BSize, int** C, int* CSize) {
	//创建并分配栈
	SeqStack* X = CreateSeqStack(*ASize, A);
	SeqStack* Y = CreateSeqStack(BSize, B);
	SeqStack* Z = CreateSeqStack(*CSize, *C);
	Move_2(*ASize, X, Y, Z);
	*C = Z->data;
	*CSize = Z->size;
	*ASize = 0;
	free(Y);
}


//数组打印函数
void printArr(int* Arr, int ArrSize) {
	int i = 0;
	printf(" = [");
	if (ArrSize > 0) {
		for (i = 0; i < ArrSize; i++) {
			printf("%d", Arr[i]);
			if (i < ArrSize - 1)
				printf(", ");
		}
	}
	printf("]\n");
}


//主函数入口
int main() {
	clock_t start_time_1 = clock();//记录方法一开始时间

	//测试用例1
	int A[] = { 2, 1, 0 };
	int ASize = sizeof(A) / sizeof(A[0]);
	int B[3];
	int BSize = 0;
	int* C = NULL;
	int CSize = 0;
	printf("交换前：\nA"); printArr(A, ASize);  //打印交换前数组
	printf("B"); printArr(B, BSize);
	printf("C"); printArr(&C, CSize);
	hanota_1(A, &ASize, B, BSize, &C, &CSize);  //汉诺塔替换
	printf("交换%d次后：\nA",count1); printArr(A, ASize);  //打印交换后数组
	printf("B"); printArr(B, BSize);
	printf("C"); printArr(C, CSize);
	
	clock_t end_time_1 = clock();  //记录方法一结束时间
	double elapsed_time_1 = (double)(end_time_1 - start_time_1) / CLOCKS_PER_SEC;  //计算运行秒数
	printf("方法1运行时间：%f秒\n", elapsed_time_1);
	printf("\n---------------分割线----------------\n\n");
	clock_t start_time_2 = clock();//记录方法二开始时间

	//测试用例2
	int AA[] = { 3, 2, 1, 0 };
	int AASize = sizeof(AA) / sizeof(AA[0]);
	int BB[4];
	int BBSize = 0;
	int* CC = NULL;
	int CCSize = 0;
	printf("交换前：\nAA"); printArr(AA, AASize);  //打印交换前数组
	printf("BB"); printArr(BB, BBSize);
	printf("CC"); printArr(&CC, CCSize);
	hanota_2(AA, &AASize, BB, BBSize, &CC, &CCSize);  //汉诺塔替换
	printf("交换%d次后：\nAA", count2); printArr(AA, AASize);  //打印交换后数组
	printf("BB"); printArr(BB, BSize);
	printf("CC"); printArr(CC, CCSize);

	clock_t end_time_2 = clock();  //记录方法二结束时间
	double elapsed_time_2 = (double)(end_time_2 - start_time_2) / CLOCKS_PER_SEC;  //计算运行秒数
	printf("方法二运行时间：%f秒\n", elapsed_time_2);

	return 0;
}

4  总结

        总的来说，汉诺塔问题还算一个比较简单的问题，本来我还想再写一个青蛙过河问题的，但看到题目我就发现涉及的太多我还未接触过的东西，还得慢慢继续学习下去！

标签：SeqStack,int,printArr,第四天,C语言,汉诺塔,printf,data,size
From： https://blog.csdn.net/2403_87130854/article/details/142761228

相关文章

  • 2个月搞定计算机二级C语言——真题（10）解析qg
    合集-3个月搞定计算机二级C语言(6)1.2个月搞定计算机二级C语言——真题（5）解析10-292.2个月搞定计算机二级C语言——真题（6）解析10-303.2个月搞定计算机二级C语言——真题（7）解析11-034.2个月搞定计算机二级C语言——真题（8）解析11-035.2个月搞定计算机二级C语言——真题（9）解析11-06:Flow......
  • c语言入门学习这一篇就够了-知识点总结(三万字二级必看)
    C语言   C语言是中高级语言的代表之一，它是所有现代编程语言的基石，包括C++、Java、C#、Python、JavaScript、Swift等。C语言是学习其他编程语言的基础，因为它提供了对系统底层的精确控制，这使得它在开发操作系统、驱动程序、嵌入式系统、高性能计算等领域中有着不可替代的......
  • 汉诺塔问题代码分享及思路分享(c基础)
    可以先自己尝试，只要看见过递归即可写。（我自己是）希望能自己尝试出来。两种方法迭代比递归快很多.(不发代码的原因是想让你自己动手)1递归2迭代猜数游戏是自己写的第一个有互动的程序。对我很有意义。我绑定资源了的，大家可以先玩一下。（电脑上才行哦，放心有外挂不会......
  • (C语言)内存函数
    目录1）memcpy 1）memcpy的模拟实现2）memmove2）memmove的模拟实现3）memset4）memcmp1）memcpymemcpy是内存拷贝函数，其不同于strncpy在于其能拷贝任意数组；形式：void*memcpy(void*destinatoin,char*source,size_t num)；destination是目标空间地址，source是源空间地址；num是拷贝......
  • 重温c语言之，7天开整，就是随便的写写，第八天
    一：函数1、递归题目：求n的阶乘（不考虑溢出）上代码1#include<stdio.h>2intfactorial(intn){3if(n>1){4returnn*(factorial(n-1));5}6else7{8return1;9}10}11#include<stdio.h>12in......
  • C语言入门第二天常量
    一：常量1:整形常量a:八进制开头是0开头例如06434b:十六进制开头是0x开头例如0xd1cc:代码展示其中%d表示十进制，%o表示八进制，%x表示十六进制。2：浮点类型a：浮点常量又被称为实数，一般含有小数部分。b:float类型小数点的精度为6位c:想printf输出为浮点类型用%f;d:代码展示......
  • 2个月搞定计算机二级C语言——真题（10）解析
    1.前言本篇我们讲解2个月搞定计算机二级C语言——真题102.程序填空题2.1题目要求2.2提供的代码#include<stdio.h>#pragmawarning(disable:4996)doublefun(doublex[],intn){ inti,k=0; doubleavg=0.0,sum=0.0; for(i=0;i<n;i++) avg......
  • c语言二维数组
    一、创建二维数组并初始化在c语言中二维数组可以在声明时直接初始化。#include<stdio.h>intmain(){//创建一个3x3的二维数组并初始化intmatrix[3][3]={{1,2,3},{4,5,6},{7,8,9}};return0;}二、访问二......
  • c语言一维数组
    一维数组数组的目的主要是为了解决在编程中需要存储和处理多个相同类型数据的问题。#include<stdio.h>intmain(){intarr[5]={1,2,3,4,5};//定义一个一维数组for(inti=0;i<5;i++){//使用for循环遍历数组printf("%d",arr[i]);//打......
  • 数据结构_链表_双向循环链表 & 栈 的初始化、插入、删除、修改、查询打印（基于C语言实
    一、双向循环链表的原理与应用双向循环链表与双向链表的区别：指的是双向循环链表的首结点中的prev指针成员指向链表的尾结点，并且双向循环链表的尾结点里的next指针成员指向链表的首结点，所以双向循环链表也属于环形结构。由于带头结点更加方便用户进行数据访问，所以本次创建一条带......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99