数据结构之汉诺塔 落日映苍穹つ 2022-05-06 16:28 169阅读 0赞 * 汉诺塔栈 #include <stdio.h> #include <stack> //递归实现 void hanoi_With_Recursion(int n, char x, char y, char z) { if (n == 1) { printf("%d from %c to %c\n", n,x,z); } else { /* 将x 上编号1 至n-1 的圆盘移到y，z 作辅助塔*/ hanoi_With_Recursion(n - 1, x, z, y); /* 将编号为n 的圆盘从x 移到z */ printf("%d from %c to %c\n", n, x, z); /* 将y 上编号1 至n-1 的圆盘移到z，x 作辅助塔*/ hanoi_With_Recursion(n - 1, y, x, z); } } int main() { int n; scanf("%d", &n); printf("%d\n", (1 << n) - 1); /* 总次数*/ hanoi_With_Recursion(n, 'A', 'B', 'C'); return 0; } * 汉诺塔队列 * #include <stdio.h> #include <math.h> #include <stdlib.h> #include <string.h> #include <windows.h> #define FALSE 0 #define TRUE 1 char graph[10][43]={ {" ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \n"}, {" ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? \n"}, {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"}, {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"}, {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"}, {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"}, {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"}, {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"}, {" ? ? ? | ? ? ? ? ? ?| ? ? ? ? ? ?| ? ? ? \n"}, {"-----------------------------------------\n"}, }; typedef struct QNode { int data; //存放数据 struct QNode *next;//存放直接后继的指针 } QNode, *QueuePtr; typedef struct { //辅助队列 ?广度优先扩展时用到 QueuePtr front; QueuePtr rear; } LinkQueue; /* 初始化队列 */ int InitQueue(LinkQueue *Q) { /* 申请头结点空间，赋值给头/尾指针 */ Q->rear = Q->front = (QueuePtr)malloc(sizeof(QNode)); if (Q->front == NULL) exit(-1); Q->front->next = NULL;//头结点的next域 return TRUE; } /* 销毁队列 */ int DestroyQueue(LinkQueue *Q) { /* 整个链表(含头结点)依次释放 没有像链表、栈等借助 QNode *p, *q; 而直接借用了front和rear */ while (Q->front) { //若链表为空，则循环不执行 Q->rear = Q->front->next; //抓住链表的下一个结点 free(Q->front); Q->front = Q->rear; } Q->rear = Q->front = NULL; return TRUE; } /* 判断是否为空队列 */ int QueueEmpty(LinkQueue Q) { /* 判断front和rear指针是否相等 */ if (Q.front == Q.rear) return TRUE; else return FALSE; } /* 元素入队列 */ int EnQueue(LinkQueue *Q, int e) { QueuePtr p; p = (QueuePtr)malloc(sizeof(QNode)); if (p == NULL) return FALSE; p->data = e; p->next = NULL;//新结点的next必为NULL Q->rear->next = p;//接在当前队尾的后面 Q->rear = p; //指向新的队尾 return TRUE; } /* 元素出队列 */ int DeQueue(LinkQueue *Q, int *e) { QueuePtr p; /* 空队列则返回 */ if (Q->front == Q->rear) //用Q->front->next==NULL也可以 return FALSE; p = Q->front->next;//指向首元 Q->front->next = p->next;//front指向新首元，可能为NULL /* 如果只有一个结点，则必须修改尾指针 */ if (Q->rear == p) Q->rear = Q->front; /* 返回数据并释放结点 */ *e = p->data; free(p); return TRUE; } void IsExist(int *state,int tnum,int num,LinkQueue &Q) { // 四个参数的意义: 状态记录数组，下一个状态值，当前状态值，状态值队列 if (state[tnum] == -1) // 如果下一个状态值未被分配:未取得(对应状态标记为-1:初始化标记),将该状态入队列 { state[tnum] = num; // 修改下一个状态值为下标对应状态值数组的值(从-1变为上一状态值) ?(这里就包含了所求可行状态值之间的关系) EnQueue(&Q, tnum); //元素入队列 } } /* --------- 图像输出函数集 ------------ */ void PrintGraph() { system("cls"); printf("过程演示：\n"); int i; printf("\n"); for (i=0; i<10; i++) printf("%s", graph[i]); } void InitGraph(int n) {// 形成n对应的盘子叠加图形 int i,j,k; for (i=0,j=8; i<n; i++,j--) { for(k=7-n+i; k<=7+n-i; k++) graph[j][k]='@'; } } void Moveto(int from, int to, int size)//from to 只有0,1,2 { //bool moved=false;//判断是否已移动 int i,j,k,m,slen; int from1=from*13+7; int to1=to*13+7; for (i=2; i<9; i++)//找到起始层 if (graph[i][from1+1]=='@')//层数记录 break; for (j=2; j<=9; j++)//找到目标层数 if (graph[j][to1+1]=='@'||graph[j][to1+1]=='-')//层数记录 { j--; break; } // i 为当前层, j 为目标层 for(k=i-1; k>=0; k--)//上移 { for (m=from1-size; m<=from1+size; m++){ graph[k][m]='@'; if (m==from1&&k>=1) graph[k+1][m]='|'; else graph[k+1][m]=' '; } PrintGraph(); } slen=size*2+1; if (from1<to1)//平移 for(k=from1; k<=to1; k++)//右移 { for(m=k-size; m<k-size+slen; m++) graph[0][m]='@'; graph[0][k-size-1]=' '; PrintGraph(); } else//左移 for(k=from1; k>=to1; k--) { for(m=k+size; m>k+size-slen; m--) graph[0][m]='@'; graph[0][k+size+1]=' '; PrintGraph(); } //平移结束 /* 下移 */ for(k=1; k<=j; k++) { for (m=to1-size; m<=to1+size; m++){ graph[k][m]='@'; if (m==to1&&k>2) graph[k-1][m]='|'; else graph[k-1][m]=' '; } PrintGraph(); } } void Display(int **recd, int num, int len)//演示函数 { int i,j,k=0; int tmp[100][3]; //analysize recd for(i=1; i<=num; i++)//compare with last one { for (j=0; j<len; j++) if (recd[i][j]!=recd[i-1][j]) { tmp[k][0]=len-j;//变化的盘号 tmp[k][1]=recd[i-1][j];//变化的起始位置 tmp[k][2]=recd[i][j];//变化的终止位置 k++; } } InitGraph(len);//根据层数进行初始化图像 PrintGraph(); i=0; do { Moveto(tmp[i][1], tmp[i][2], tmp[i][0]); i++; }while(i<k); printf("Over..."); getchar(); getchar(); } /* ------------------------------------- */ /* 起始状态为0.....0 终止状态为2......2 */ int main() { /* -------------- 变量定义 ------------ */ int BRICKNUM; //圆盘数 printf("请输入汉诺塔层数："); scanf("%d",&BRICKNUM); LinkQueue Q; int i, j, k; int n; int num; int temp_of_num; int temp_of_add; int num_of_state=1;//总状态数 for (int count=0; count<BRICKNUM; count++) //计算总状态数 num_of_state *= 3; // 每个盘子有3种状态(状态之间关联，有些没有用会被筛除掉) // 状态值数组表示了状态值之间的单向羁绊！状态值数组下标与状态值元素值是上下(前后)关系，当前状态值是以下一状态值为下标的状态元素的值 // 当前状态数组元素值是其上一个状态值 int *record_of_state = (int*)malloc(num_of_state*sizeof(int)); //每种状态的记录,-1代表未分配，否则为其父节点的下标 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(总状态数为:num_of_state,状态分配状态值在相应数组中记录) int *temp = (int*)malloc(BRICKNUM*sizeof(int)); // 定义存放n个盘子数，整型大小的存储空间 int *order_of_state = (int *)malloc(num_of_state*sizeof(int));//记录状态变化顺序 //此次汉诺塔问题借助三进制表示方法，0代表的是存在a柱子，1代表放在b柱子上，2代表放在c柱子上，位高的代表大盘，位低代表小盘，如? ? ? ? ?0000代表 ? ? ? ? ? ? ? 四个盘全部放在a柱子上 for (i = 0; i < num_of_state; i++)//初始化record_of_state { record_of_state[i] = -1; //-1状态表示未分配 } InitQueue(&Q); // 初始化队列 num = 0; // num记录的是所有盘子元素状态序列对应的整数，可转化为一串0,1,2数字序列。 EnQueue(&Q, num); //状态1入栈，即0000(此时所有的盘子的状态都是0) record_of_state[num] = -2; // 状态数的大小是根据n的取值来确定的(num代表一个状态的取值，num的最大值即为最大状态数) /* ? ? ? ?这里是在出队列状态值的基础上,获取每一个盘子的状态(由整数得到一个数字序列)，在逐位来判断，确定下一状态值 ? ? ? ?这里的规律:确定最底盘后(序列下标相对最小)，该位就一直不变 ? ?*/ /* ?这里会筛选所需的状态值，以及他们的先后关系(每个状态值都进入了队列，有些被排除了，最后得到? ? ? ? 关键的状态值路径) ?*/ while (QueueEmpty(Q) == FALSE) //状态空间的生成（如果队列不为空，扩展状态空间） { DeQueue(&Q, &num); // 元素出队列，出队元素的值记录到了num中 n = num; // n获得的是当前盘子对应的状态序列整数(将整数整除3(三种摆放方式)得到序列：状态序列) for (i = BRICKNUM - 1; i >= 0; i--) // 分解成三进制形式(从后往前存储，大盘子的状态再最前面=>整数的高位，对应数组下标越小) {// 这里n个盘片，进行n次循环，temp对应是n个整型数据大小区间 temp[i] = n % 3; // 对应temp区间存储的是：n个盘子的状态序列 n /= 3; } if (temp[BRICKNUM - 1] == 0) //最后一位是0=>最上层盘子状态(该状态下:最小的盘子在a柱子上) { // 一个状态可以有多个子状态(关系记录在状态值数组中) temp_of_num = num + 1; // 记录下一状态值(在当前出队列的状态值的基础上) IsExist(record_of_state, temp_of_num,num, Q); //若下一状态值未被分配,将其入队列 temp_of_num = num + 2; IsExist(record_of_state, temp_of_num,num, Q); for (i = BRICKNUM - 2, temp_of_add = 3; i >= 0; i--) { //扫描当前状态值后续对应3进制的每一位 if (temp[i] == 1) { temp_of_num = num + temp_of_add; IsExist(record_of_state, temp_of_num,num, Q); break; } else if (temp[i] == 2) { temp_of_num = num - temp_of_add; IsExist(record_of_state, temp_of_num,num, Q); break; } temp_of_add *= 3; } } else if (temp[BRICKNUM - 1] == 1) //最后一位是1(该种状态下:最小的盘子在b柱子上) { temp_of_num = num - 1; IsExist(record_of_state, temp_of_num,num, Q); temp_of_num = num + 1; IsExist(record_of_state, temp_of_num,num, Q); for (i = BRICKNUM - 2, temp_of_add = 3; i >= 0; i--) { if (temp[i] == 0) { temp_of_num = num + temp_of_add * 2; IsExist(record_of_state, temp_of_num,num, Q); break; } else if (temp[i] == 2) { temp_of_num = num - temp_of_add * 2; IsExist(record_of_state, temp_of_num,num, Q); break; } temp_of_add *= 3; } } else // 该状态下:最小的盘子在c柱子上 { temp_of_num = num - 2; IsExist(record_of_state, temp_of_num,num, Q); temp_of_num = num - 1; IsExist(record_of_state, temp_of_num,num, Q); for (i = BRICKNUM - 2, temp_of_add = 3; i >= 0; i--) { if (temp[i] == 0) { temp_of_num = num + temp_of_add; IsExist(record_of_state, temp_of_num,num, Q); break; } else if (temp[i] == 1) { temp_of_num = num - temp_of_add; IsExist(record_of_state, temp_of_num,num, Q); break; } temp_of_add *= 3; } } } /* 1: 如何完成的所有状态值无序入队列 2: 前后结点（状态值之间联系）查找，筛选的算法 */ /* ?order_of_state 数组装载的是筛选的路径中入队的状态值,虽然所有的状态值都入过对列，但从中选择出了最短需要路径*/ num = num_of_state - 1; // 状态值数组最大下标 // 初始record_of_state数组的值都被赋值为-1，如果要入队列就将其值赋值为上一状态值的大小 i = 0; // 从后往前遍历状态值数组:如果当前状态值入过队列,则其值为上一状态值 while (record_of_state[num] != -2) // 跳出口为第一个状态值0...0，其对应状态值数组值为-2.它是作为起点单独处理的 { order_of_state[i] = num; // 这里记录着入过队列:即为分配过的状态值元素下标? num = record_of_state[num]; // num记录上一状态值，也即上上状态值对应下标 (应该可以将值与下标转化为相差为1的关系) i++; } order_of_state[i] = num; // 在num=0时并没有装入order_of_state就跳出了循环 int mycount=0; int **recd = (int **)malloc((i+1)*sizeof(int *));//记录状态变化顺序 for (j=0; j<=i; j++) recd[j] = (int *)malloc(BRICKNUM*sizeof(int)); // int **recd= new int[i][BRICKNUM];//记录状态变化，以便图像演示使用 for (j=i; j>=0; j--) { n = order_of_state[j]; for (k = BRICKNUM - 1; k >= 0; k--) //分解成三进制形式 { temp[k] = n % 3; n /= 3; } memcpy(recd[mycount], temp, BRICKNUM*sizeof(int)); mycount++; for (k = 0; k < BRICKNUM; k++) printf("%d", temp[k]); printf("\n"); } getchar(); getchar(); //输出演示 if(BRICKNUM!=0) Display(recd, i, BRICKNUM); //释放变量 free(temp); free(record_of_state); free(order_of_state); for (k=0; k<=i; k++) free(recd[k]); free(recd); getchar(); return 0; }
相关 数据结构--汉诺塔问题 数据结构–汉诺塔问题 我列举了两种解法—递归和非递归 1、这是递归解法 include<iostream> using namespa 清疚/ 2023年07月03日 14:29/ 0 赞/ 122 阅读
相关 汉诺塔 package com.someusefuldesign.demo; /假设有A B C三个柱子移动的顺序为： / public class 妖狐艹你老母/ 2022年08月13日 15:54/ 0 赞/ 233 阅读
相关 汉诺塔 Problem Description 汉诺塔（又称河内塔）问题是印度的一个古老的传说。 开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒A、B和C，A上面套着 Dear 丶/ 2022年06月17日 05:28/ 0 赞/ 309 阅读
相关 汉诺塔 汉诺塔 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Prob 约定不等于承诺〃/ 2022年06月11日 03:24/ 0 赞/ 262 阅读
相关 汉诺塔 \include<stdio.h> void hanoi(int n,char A,char B,char C) \{ if(n==1) printf("Move s 逃离我推掉我的手/ 2022年06月10日 12:57/ 0 赞/ 308 阅读
相关 汉诺塔 include <stdio.h> void hannuota(int n,char A,char B,char C){ if(1 == n){ 川长思鸟来/ 2022年06月07日 13:06/ 0 赞/ 228 阅读
相关 汉诺塔 汉诺塔 Time Limit: 1000 ms Memory Limit: 65536 KiB [Submit][] [Statistic][] Problem D 怼烎@/ 2022年05月29日 05:58/ 0 赞/ 271 阅读
相关 汉诺塔 def move(n, a, b, c): if n == 1: \ 如果a只有1盘子 print(a, '-->', c); \ 直接把盘子从a移到c els 迷南。/ 2022年05月18日 22:25/ 0 赞/ 339 阅读
相关 数据结构之汉诺塔 汉诺塔栈 include <stdio.h> include <stack> //递归实现 void hanoi_W 落日映苍穹つ/ 2022年05月06日 16:28/ 0 赞/ 170 阅读
清疚
怼烎@
迷南。
还没有评论，来说两句吧...