热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

汉诺塔算法:动态可视化实现与解析

本研究基于状态空间方法,通过动态可视化技术实现了汉诺塔问题的求解过程,即将n个盘子从A柱移动到C柱。本文提供了一个使用C语言在控制台进行动画绘制的示例,并详细注释了程序逻辑,以帮助读者更好地理解和学习该算法。

  人工智能实验要求:利用状态空间法,实现汉诺塔求解过程的动画(将n个盘子,从A柱移到C柱上)。

  这里是一个C语言实现控制台绘制的实例,笔者将程序的思想写了个详细的注释,方便大家学习。

  同时利用这种方法,笔者改写了一个Java的用户界面效果演示程序,在Java相关文章中,大家可以看看。


程序效果图及思路:

                                

这里的思路是:以三进制数据表示3个盘子的状态:比如0,1,2分别表示在A,B,C柱子上,一种状态值为220,就表示:最小盘在A柱,其他在C柱上

                                                                                   

这里如果是n个盘子,还是用0,1,2三进制数表示盘子所在柱子,数字的组合就是一个整体的状态,就是三进制数序列,转化为10进制,就是一个整型值

这个数值就是整个盘子摆放的一种状态,状态的取值有3^n种这里显示的是最短可行的状态路径(状态之间是相关联的,0.....0是起点,2.....2是要到达的状态),算法就是要在这些状态中选择一条最佳路径,到达目的地!


详细解答请看程序注释:

#include
#include
#include
#include
#include


#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{
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 (from1for(k=from1; k<=to1; k++)//右移
{
for(m=k-size; 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  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
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 //计算总状态数
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 {
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 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;
}

这个程序的关键是:从所有的状态值中,筛选出需要的状态值,并确定他们之间的先后关系,以便能正确按序挪动盘子,完成任务

  


推荐阅读
  • 在幼儿园中,有 \( n \) 个小朋友需要通过投票来决定是否午睡。尽管这个问题对每个孩子来说并不是特别重要,但他们仍然希望通过谦让的方式达成一致。每个人都有自己的偏好,但为了集体和谐,他们决定采用一种最小割的方法来解决这一问题。这种方法不仅能够确保每个人的意愿得到尽可能多的尊重,还能找到一个最优的解决方案,使整体满意度最大化。 ... [详细]
  • 题目旨在解决树上的路径最优化问题,具体为在给定的树中寻找一条长度介于L到R之间的路径,使该路径上的边权平均值最大化。通过点分治策略,可以有效地处理此类问题。若无长度限制,可采用01分数规划模型,将所有边权减去一个常数m,从而简化计算过程。此外,利用单调队列优化动态规划过程,进一步提高算法效率。 ... [详细]
  • 如何利用C语言进行高效的商品管理程序设计与开发
    本文详细探讨了使用C语言高效开发商品管理系统的技巧与方法。通过简洁明了的代码示例,文章逐步引导读者掌握商品管理程序的设计与实现,适合初学者及有一定基础的开发者参考学习。 ... [详细]
  • 题目描述:小K不幸被LL邪教洗脑,洗脑程度之深使他决定彻底脱离这个邪教。在最终离开前,他计划再进行一次亚瑟王游戏。作为最后一战,他希望这次游戏能够尽善尽美。众所周知,亚瑟王游戏的结果很大程度上取决于运气,但通过合理的策略和算法优化,可以提高获胜的概率。本文将详细解析洛谷P3239 [HNOI2015] 亚瑟王问题,并提供具体的算法实现方法,帮助读者更好地理解和应用相关技术。 ... [详细]
  • 本文介绍了C语言中指针的基础知识及其初步应用。首先,文章详细解释了如何定义变量和指针,例如通过 `int i, j, k;` 定义整型变量,以及使用 `int *pi, *pj, *pk;` 来声明指向整型数据的指针。接着,探讨了变量和指针的初始化方法,强调了正确的初始化对于避免程序错误的重要性。此外,还简要介绍了指针在数组、函数参数传递等场景中的基本应用,为初学者提供了全面的入门指导。 ... [详细]
  • 题目《UVa 11978 福岛核爆问题》涉及圆与多边形交集面积的计算及二分法的应用。该问题的核心在于通过精确的几何运算与高效的算法实现来解决复杂图形的面积计算。在实现过程中,特别需要注意的是对多边形顶点的平移处理,确保所有顶点包括最后一个顶点 \( p[n] \) 都经过正确的位移,以避免因细节疏忽导致的错误。此外,使用循环次数为50次的二分法能够有效提高算法的精度和稳定性。 ... [详细]
  • 考研数据结构复习:链式栈深入解析与应用
    在考研数据结构复习中,链式栈的深入解析与应用是一个重要环节。本文详细探讨了链式栈的实现方法,特别是栈底和栈顶指针的使用。通过对比常见的单链表实现方式,本文整理了一份代码示例,与王道复习指导中的链式存储类型高度一致。此外,本文还提供了详细的注释和解释,帮助读者更好地理解和掌握链式栈的原理与应用。 ... [详细]
  • 在2015年世界总决赛的Tours问题中,参赛者面临一个包含n个节点和m条边的无向图挑战。任务是选定一种颜色数量k,并使用这些颜色为每条边着色。核心要求是在图中的任何简单循环中,每种颜色的边数必须相等。该研究对竞赛路线进行了全面分析,探讨了满足条件的所有可能的着色方案。 ... [详细]
  • Codeforces 1065D 解题心得与代码实现分析 ... [详细]
  • 24点纸牌智力挑战:经典数学益智游戏
    24点纸牌智力挑战是一款广受欢迎的经典数学益智游戏。玩家需要从一副扑克牌中随机抽取四张牌,通过加、减、乘、除等运算,在最短时间内计算出结果为24,最先达成目标的玩家获胜。游戏中,J、Q、K分别代表11、12、13,增加了游戏的复杂性和趣味性。 ... [详细]
  • `ArrayDeque` 类中的 `removeLast()` 方法用于移除并返回双端队列中的最后一个元素。该方法在处理数据结构时非常有用,特别是在需要高效地从队列末尾移除元素的场景中。本文将详细介绍 `removeLast()` 方法的工作原理,并通过具体的应用实例展示其使用方法和优势。 ... [详细]
  • C语言实现:深入解析希尔排序算法
    C语言实现:深入解析希尔排序算法 ... [详细]
  • 掌握DSP必备的56个核心问题,我已经将其收藏以备不时之需! ... [详细]
  • 本文深入探讨了C语言中函数指针作为参数传递的应用及其优势。通过具体示例,详细解析了如何将函数指针作为参数传递给其他函数,展示了其在代码灵活性和可维护性方面的显著提升。 ... [详细]
  • 深入解析Spring框架中的双亲委派机制突破方法
    在探讨Spring框架中突破双亲委派机制的方法之前,首先需要了解类加载器的基本概念。类加载器负责将类的全限定名转换为对应的二进制字节流。每个类在被特定的类加载器加载后,其唯一性得到保证。然而,这种机制在某些场景下可能会限制灵活性,因此Spring框架提供了一些策略来突破这一限制,以实现更加动态和灵活的类加载。这些策略不仅能够提升系统的可扩展性,还能在复杂的运行环境中确保类的正确加载和管理。 ... [详细]
author-avatar
好天气
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有