1.实验目的：

通过本实验，掌握复杂性问题的分析方法，了解汉诺塔游戏的时间复杂性和空间复杂性。

2.问题描述：

      汉诺塔问题来自一个古老的传说：在世界刚被创建的时候有一座钻石宝塔（塔A),其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。

3.算法设计思想：

    对于汉诺塔问题的求解，可以通过以下三个步骤实现：
    (1)将塔A上的n-1个碟子借助塔C先移到塔B上。
    (2)把塔A上剩下的一个碟子移到塔C上。
    (3)将n-1个碟子从塔B借助于塔A移到塔C上。

4.实验步骤：

1.      用c++ 或c语言设计实现汉诺塔游戏；

2.      让盘子数从2 开始到7进行实验，记录程序运行时间和递归调用次数；

3.      画出盘子数n和运行时间t 、递归调用次数m的关系图，并进行分析。

5.代码设计：

Hanio.cpp

#include "stdafx.h"

#include <stdlib.h>

#include <stdio.h>

#include <iostream>

…… …… 余下全文

课 程 设 计 报 告

课程名称： 高级语言课程设计

课程代码： 07300561

设计内容： 汉诺塔演示系统

专 业： 计算机科学与技术

2012 年 12月 16日

- 1 -

目 录

1.课程设计目的............................................................ 3

1.1 内容简介............................................. 错误！未定义书签。

1.2 功能实现............................................. 错误！未定义书签。

2.课程设计题目描述和要求.................................................. 3

2.1 描述................................................. 错误！未定义书签。

2.2 要求................................................. 错误！未定义书签。

3.课程设计报告内容........................................................ 3

3.1 内容概要............................................. 错误！未定义书签。

3.2 功能实现............................................. 错误！未定义书签。

3.3 程序流程图........................................... 错误！未定义书签。

…… …… 余下全文

计算机学院

实验报告

课程名称：     数据结构 

实验名称：     汉诺塔   

学生姓名：朱孝彬            

学生学号： 20110511001   

实验日期： 2012           

一、实验目的

1．理解数据结构中汉诺塔

2．掌握汉诺塔的C++描述。

二、实验内容

1． 编制汉诺塔的程序。

三、实验步骤

1．需求分析

本演示程序用C++6.0编写，完成汉诺塔的生成，

2．概要设计

1）为了实现上述程序功能，需要定义单链表的抽象数据类型：
　　 （1）insert

初始化状态：单链表可以不为空集；操作结果：插入一个空的单链表L。
　    （2）decelt
　　　　操作结果：删除已有的单链表的某些结点。

（3）display
　　　　操作结果：将上述输入的元素进行排列显示。
　　　（4）modify
　　　　操作结果：将上述输入的某些元素进行修改。
　　　（5）save
　　　  操作结果：对上述所有元素进行保存。
　　　（6）load
　　　　操作结果：对上述元素进行重新装载。

3．使用说明

程序执行后显示
　　======================

     1.单链表的创建

 2.单链表的显示

 3.单链表的长度

 4.取第i个位置的元素

…… …… 余下全文

一，算法程序

#include <iostream>

using namespace std; /*圆盘的个数最多为64*/

const int MAX = 64; /*用来表示每根柱子的信息*/

struct st{

int s[MAX]; /*柱子上的圆盘存储情况*/

int top; /*栈顶，用来最上面的圆盘*/

char name; /*柱子的名字，可以是A，B，C中的一个*/

int Top() /*取栈顶元素*/

{

return s[top];

}

int Pop()

{

return s[top--];

}

void Push(int x)

{

s[++top] = x;

}

} ;

long Pow(int x, int y); /*计算x^y */

void Creat(st ta[], int n); /*给结构数组设置初值*/

void Hannuota(st ta[], long max); /*移动汉诺塔的主要函数 */

int main(void)

{

int n;

cin >> n; /*输入圆盘的个数*/

st ta[3]; /*三根柱子的信息用结构数组存储*/

Creat(ta, n); /*给结构数组设置初值*/

long max = Pow(2, n) - 1; /*动的次数应等于2^n – 1*/

Hannuota(ta, max); /*移动汉诺塔的主要函数*/

system("pause");

return 0;

}

void Creat(st ta[], int n)

{

ta[0].name = 'A';

ta[0].top = n-1; /*把所有的圆盘按从大到小的顺序放在柱子A上*/ for (int i=0; i<n; i++)

…… …… 余下全文

JAVA第二次实训报告

     

       姓名：柳正利        

          学号：101530137

                班级：软件工程软工一班

                日期：20##年3月16日

目录

一．设计要求………………………………………………

二．总体设计………………………………………………

三．详细设计………………………………………………

四．代码调试………………………………………………

五．软件发布………………………………………………

  六．总结……………………………………………………

  七．参考文献…………………………………………….

一．  设计要求

1. 设计GUI界面的Hannoi塔。汉诺塔中有三个座，名字分别为A，B，C。初始状态时A塔上有3个大小不等的盘子，这些盘子从座底到座顶按着大小顺序依次摆放在A座上。用户可以用鼠标选中盘子，然后通过拖动鼠标来移动盘子。释放鼠标来放置该盘子。

2. 程序要求用户在移动盘子的过程中，不允许吧大盘子放置在小盘子的上面，用户最终要完成的是把A座上的全部盘子移动到B座或C座上。

…… …… 余下全文

< 人工智能 > 实 验 报 告 3

一、实验目的： 掌握汉诺塔的深度有界搜索求解算法的基本思想。

二、实验要求：

用C语言实现汉诺塔的深度有界搜索求解

三、实验语言环境：

C语言

四、设计思路：

含有深度界限的深度优先搜索算法如下：

(1) 把起始节点S放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。

(2) 如果OPEN为一空表，则失败退出。

(3) 把第一个节点(节点n)从OPEN表移到CLOSED表。

(4) 如果节点n的深度等于最大深度，则转向(2)。

(5) 扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。

(6) 如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。

五、实验代码：

#include <stdio.h>

#include <string.h>

typedef struct node {

long map;

long floor; //记录第几层

} node;

node queue[362880 / 2 + 1]; //奇偶各一半

long tail, head;

long hash[362880 / 32 + 1];

int main()

{

void Solve();

while (scanf("%ld", &queue[0].map) && queue[0].map) { memset(hash, 0, sizeof(hash));

queue[0].floor = 1; //(根节点)第一层

tail = head = 0;

Solve();

printf("max_floor == %d\n", queue[head].floor); printf("total node == %d\n", head + 1);

…… …… 余下全文