人工智能(梵塔问题)

梵塔问题实验报告梵塔问题实验报告 实验目的实验目的 1 熟悉和掌握问题规约法的原理 实质和规约过程 2 理解规约图的表示方法 3 熟悉并掌握递归解决问题的思想 实验原理实验原理 1 利用问题规约法的原理进行问题的分析与描述 2 利用递归思想进行问题的解决 实验条件实验条件 1 Window NT xp 7 及以上的操作系统 2 内存在 512M 以上 3 CPU 在奔腾 II 以上 实验内容实验内容 梵塔问题源于印度古老的一个传说 相传开天辟地的神勃拉玛创造世界时 在印度北部的佛教圣地的圣庙里 安放了三根金刚石的棒 第一根上面套着 64 个圆的金片 最大的一个在底下 其余一个比一个小 依次叠上去 庙里的众 僧不倦地把它们一个个地从这根棒搬到另一根棒上 规定可利用中间的一根棒 作为帮助 但每次只能搬一个 而且大的不能放在小的上面 值班僧侣按照法 则日夜不停地搬运 当搬运完成时世界将在一声霹雳中毁灭 实验分析实验分析 我们假设把该任务交给一个僧人 为了方便叙述 将他编号为 64 僧人自 2 然会这样想 假如有另外一个僧人能有办法将 63 个盘子从一个座移到另一个座 那么问题就解决了 此时僧人 64 只需这样做 1 命令僧人 63 将 63 个盘子从 A 座移到 C 座 2 自己将最底下的最大的一个盘子从 A 座移到 C 座 3 再命令僧人 63 将 63 个盘子从 B 座移到 C 座 为了解决将 63 个盘子从 A 座移到 B 座的问题 僧人 63 又想 如果能再有 一个僧人 62 能将 62 个盘子移动到另一座 我就能将 63 个盘子从 A 座移动到 B 座 他是这样做的 1 命令僧人 62 将 62 个盘子从 A 移动到 C 2 自己将一个盘子从 A 座移动到 B 座 3 再命令僧人 62 将 62 个盘子移到 B 座 再进行一次递归 如此 层层下放 直到后来找到第 2 个僧人 让他完成 将 2 个盘子从一个座移到另一个座 进行到此 问题就解决了 最后找到第 1 个僧人 让他完成将一个盘子从一个座移动到另一个座 至此 全部工作已经 完成 该烦他问题得到解决 实验步骤实验步骤 1 1主程序流程图主程序流程图 2 2梵塔求解流程图梵塔求解流程图 初始化过程 绘制初始图形 汉诺塔求解 开始 输入盘子数 结束 主程序流程图 3 开始 将盘子从 A 座移到 C 座 n 为 1 是否 递归调用 初始 n n 1 盘子数为 n 结束 梵塔问题递归过程流程图 退出一级调用 n n 1 程序代码程序代码 include include include include include define PAOGAO 190 动画抛高 数值越小越高 define PANHOU 10 define PANAMOUNT 19 盘子数 int PANAMOUNT typedef int pans typedef struct s pillar int amount int x y pans pan 20 存放每个盘的代号 pillars pillars pillar 4 三个台柱 int movecount 0 移动计数 void drawpillar pillars p void init 初始化函数 void drawmat char mat int matsize int x int y int color 点陈汉字 void drawpan pans p int x int y void zimu 显示字幕 4 void drawpps 画装盘的台柱 void hanoi 主算法 void hanoi int n char one char two char three void sdelay int delay t 函数申明 void finish 完成 void main void 主函数 printf n tplease input n n 19 输入要演示的盘子数 scanf d if PANAMOUNT19 越界的话 n 当 19 处理 PANAMOUNT 19 init drawpps hanoi PANAMOUNT a b c finish void init 初始化函数 int gd DETECT gm int i n color clrscr initgraph cleardevice pillar 1 amount PANAMOUNT pillar 1 x 105 pillar 1 y 405 for i 1 i pillar 1 amount i pillar 1 pan i pillar 1 amount i 1 pillar 2 amount 0 pillar 2 x 320 pillar 2 y 405 pillar 3 amount 0 pillar 3 x 527 pillar 3 y 405 setcolor YELLOW 柱座标记 settextstyle 0 0 2 outtextxy 105 418 A 5 outtextxy 320 418 B outtextxy 527 418 C setcolor YELLOW 画框 setlinestyle SOLID LINE 0 NORM WIDTH line 0 0 0 479 line 0 0 639 0 line 639 0 639 479 line 0 479 639 479 line 0 PAOGAO PANHOU 40 450 PAOGAO PANHOU 40 黄金线 settextstyle 0 0 1 outtextxy 250 PAOGAO PANHOU 50 Press ANY Key to EXIT 线上字 zimu void drawpillar pillars p 画柱 int x y mount x p x y p y mount p amount setfillstyle SOLID FILL BROWN bar x y mount PANHOU 20 x 5 y bar x 45 y x 55 y 5 void drawmat char mat int matsize int x int y int color 依次 字模指针 点阵大小 起始坐标 x y 颜色 int i j k n n matsize 1 8 1 for j 0 j matsize j for i 0 i n i for k 0 k k 测试为 1 的位则显示 putpixel x i 8 k y j color void drawpan pans p int x int y setfillstyle SOLID FILL LIGHTGRAY bar x 5 5 p y PANHOU 1 x 5 5 p y setlinestyle SOLID LINE 0 NORM WIDTH setcolor BLACK line x 5 5 p y x 5 5 p y line x 5 5 p y 1 x 5 5 p y 1 6 void clearpan pans p int x int y setfillstyle SOLID FILL BLACK bar x 5 5 p y PANHOU x 5 5 p y void drawpps 画装盘的台柱 pillars p int i j int x y mount for i 1 i 3 i p pillar i x p x y p y mount p amount drawpillar p 画台柱 for j 1 j 15 clearprocess 清除步骤提示 movecount movecount 15 1 模 20 1 setcolor RED 输出移动过程 settextstyle TRIPLEX FONT HORIZ DIR 1 outtextxy 560 30 movecount 10 a outtextxy 580 30 movecount 10 outtextxy 620 30 movecount 10 b setfillstyle SOLID FILL BLACK 涂黑 重画 bar 3 pillar 1 y PANHOU 19 20 584 412 drawpps 重画 action data pillar ifrom pillar ito 此处添加动画函数 pillar ito amount 入栈 mountt pillar ito amount 刷新数量 pillar ito pan mountt data drawpps 重画 void clearprocess int i setfillstyle SOLID FILL BLACK for i 0 i 16 i 8 bar 545 30 i 10 638 40 i 10 sdelay 1 动画延迟 n 个 1 18 2 秒 整数 1 代表 1 18 2 秒 void sdelay int delay t clock t start time start time clock while clock start time delay t 循环空语句 void action pans pan pillars fromp pillars top 移动动画 float x1 y1 x2 y2 float p q a int x y temp 整形变量用与当前帧 x1 float fromp x y1 float fromp y fromp amount PANHOU 20 PANHOU 为盘厚常数 减 20 处理 以便避开柱子 x2 float top x y2 float top y top amount PANHOU q sqrt y1 PAOGAO y2 PAOGAO 此处注意产生增根 if 1 q 除数不为 0 a x1 x2 q 1 q else a x1 x2 2 0 p y2 PAOGAO x2 a x2 a 除以平方 if x1 x2 for x floor x1 0 5 xfloor x2 0 5 x x 7 if kbhit exit 用户按 ESC 则退出 y floor p x a x a PAOG