友情提示:同学您好,此页面仅供预览,在此页面学习不会被统计哦! 请进入学习空间后选择课程学习。
案例


案例一:

          使用Raptor工具调试计算n个自然数的累加和,要求n在程序运行时输入,并输出最终结果。


1.算法分析
2.建立问题的数学模型
3.在Raptor 中画出程序流程图
4.调试算法,观察输出结果。
5.提交程序设计报告,包括算法流程图及程序运行结果。

案例二:

          使用Raptor 工具调试百元买百鸡问题的算法。


题目:假定小鸡每只0.5元,公鸡每只2元,母鸡每只3元。现在有100元钱要求买100只鸡,问共有几种购鸡方案?
1.算法分析,建立问题的数学模型
根据题目,设母鸡、公鸡、小鸡各为x,y,z只,列出方程为:x+y+z=100,3x+2y+0.5z=100,使用穷举法,将各种可能的组合一一测试,输出符合条件的组合。即在各个变量的取值范围内不断变化x,y,z的值,穷举x,y,z全部可能的组合,若满足方程组则是一组解。
2.确定程序所采用的数据结构组织
3.在Raptor中画出程序流程图
4.调试算法,观察输出结果。
5.提交程序设计报告,包括算法流程图及程序运行结果。
流程图示例:

友情提示:同学您好,此页面仅供预览,在此页面学习不会被统计哦! 请进入学习空间后选择课程学习。
资源下载

资源下载

1.课件

程序与程序设计


算法基本概念




友情提示:同学您好,此页面仅供预览,在此页面学习不会被统计哦! 请进入学习空间后选择课程学习。
拓展学习

问题求解方法

 问题求解是人工智能中研究得较早而且比较成熟的一个领域,它涉及规约、推断、决策、规划、常识推理、定理证明等相关过程的核心概念。数学家G.Polya在1945年给出了非严格定义的问题求解阶段,即


    第一阶段:理解问题;
    第二阶段:设计解决问题的方案;
    第三阶段:实施方案;
    第四阶段:从准确度和是否具有潜力作为解决其他问题的工具等方面评估这个方案。


把上述阶段移植到程序设计中,问题求解应当包括从理解问题、分析问题开始,建立数学模型,设计数据结构,完成算法设计,求解问题,到最后通过计算机运行得到正确结果的全过程。

基于程序设计思想的问题求解的基本步骤是:
   (1)明确所需要解决的问题,即理解问题。如问题条件、输入和输出等要求。
   (2)分析问题,构造数学模型。如抽象和简化自然界和现实生活中的现象,建立描述问题的模型。
   (3)设计数据结构和算法。数据结构涉及线性表、栈、队列、树等,是合理安排数据的存储方式。算法是为了解决问题而采取的正确、有限的步骤,即如何让计算机理解和解决问题。由于理解问题的层次不一样,算法的抽象程度也不一样。
   (4)根据数据结构和算法,编写源程序。即高级程序设计语言把算法准确、等价地描述出来,以便在计算机上运行。
   (5)调试程序,获得问题求解结果。


这里,我们以汉诺塔(Hannio)问题为例,来讲述问题求解的方法。 问题描述:汉诺塔问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。如图6.4.1所示。让我们来考虑一下64个圆盘重新摆好,需要移动多少次呢?


1.建立问题的数学模型

建立数学模型解决现实问题要经过模型准备、模型假设、模型构成、模型求解和模型分析这五个步骤。


(1)模型准备是了解问题的实际背景,明确建模目的,搜集必需的各种信息,尽量弄清对象的特征;
(2)模型假设是根据对象的特征和建模目的,对问题进行必要的、合理的简化,用精确的语言做出假设;
(3)模型构成是根据所作的假设分析对象的因果关系,利用对象的内在规律和适当的数学工具,构造各个量间的等式关系或其它数学结构;
(4)模型求解是采用各种已有的数学方法或计算机技术进行求解;
(5)模型分析是将求解结果进行误差或稳定性等数学分析,并解释为对现实问题的解答。


由此可见,建立问题的数学模型就是将数学的理论知识应用于解决实际问题,培养数学建模思想就是锻炼思维能力。
汉诺塔问题分析:完成汉诺塔问题的任务有下列限制条件:

(1)每次移动只能移动一个盘;
(2)每次移动都不允许大盘移到小盘之上;
(3)B塔作为辅助的、中间过渡的塔。

这个移动过程复杂与繁琐,但规律性却很强。解决这个问题的关键是判断盘数n。如果n = 1,则直接把1号盘从A塔移动到C塔就可以了。如果n > 1,则把待解决的问题分解为:
第一步:将A塔上的n-1个盘子借助C塔先移到B塔上,如图6.4.2-②所示;

第二步:把A塔上的第n号盘子移到C塔上,如图6.4.2-③所示;

第三步:将n-1个盘子从B塔借助于A塔移到C塔上,如图6.4.2-④所示。  


由此可见,汉诺塔问题的数学模型,即为典型的函数递归调用模型。


2.设计数据结构

    问题求解过程中,需要有效地组织操作对象以及它们之间存储关系,包括输入、输出和中间结果等,这就是我们所说的数据结构。通俗地说,数据结构是数据/变量的集合,并在数据/变量之间赋予了关系和操作。因此,关于数据结构不仅要考虑数据的数学性质,还必须考虑它的实现机制(存储和运行机制)。典型的数据结构包括变量、向量、列表、数组、树和图等。其中,变量是最基本、最重要的数据结构。
    汉诺塔问题数据结构分析:A塔、B塔、C塔可以看成三个栈,移动一个盘子相当于从一个栈弹出并压进另一个栈,该程序可设计成一个递归过程。
    因此,求解汉诺塔问题,设计数据结构为:

输入数据:要移动的盘子数n(定义为整型int),源塔A(定义为字符型Char),辅助塔B(定义为字符型Char),目的塔C(定义为字符型Char)。

输出数据:为将A塔上的盘子按规定全部移到C塔上所需要移动的最少次数H(n) (定义为整型int)。故:H(1)=1,H(2)=3,H(3)=7。 当n=3,即A塔上有3个盘子时,为了能将A塔上的最下面一个大盘子能移到C塔上,应先将A塔上的前2个盘子移到B塔上。根据n=2时的结论,这样要先移3次,第4次就可将A塔上的最下面的大盘子移到C塔上,然后再将B塔上的2个盘子移到C塔上,借助A塔,利用n=2时的结论,又需移动3次,这样一共移了7次,即H(3)=7。 以此类推,若当A塔上有n个盘子时,共需要移动H(n)次才能将盘子全部移到C塔上,则当A塔上有n+1个盘子时,为了将A塔上面的n个盘子先移到B塔上,根据假设为此需移动H(n)次,这样再移动1次就可将A塔上的最下面的一个大盘子移到C塔上,然后将B塔上的n个盘子移到C塔上,这又需要移动H(n)次,于是一共移动了H(n+1)=2*H(n)+1次,(n>1)。不难证明,H(n)=2的n次方-1。当n=64时,H(64)=2的64次方-1。

3.利用算法求解问题

    算法是完成特定任务的具体步骤集合的一种说明,也就是一组可执行操作的序列。因此,算法定义了问题求解的一系列步骤,是对求解过程的精确描述。描述算法的方法主要有流程图、自然语言、伪代码、计算机程序设计语言等。
    现在来设计一下汉诺塔问题的算法(自然语言描述)。
设计一个方法hanoitower(int n, char A, char B, char C),其中n是表示要移动的盘子数,A表示源塔,B表示辅助塔,C表示目的塔。则hanoitower(n, A,B,C)的处理过程是:
(1)如果n=1,则执行下列步骤:
① 输出“把第n号盘从A塔移到C塔”;
② 方法结束。
(2)如果n>1,则执行下列步骤:
① hanoitower(n-1,A,C,B);
② 输出“把第n号盘从A塔移到C塔”;
③ hanoitower(n-1,B,A,C)。
hanoitower()关键是采用了递归方法,每调用一次hanoitower(),则n值减1,总能够减到1,即算法能够结束。

4.算法的程序实现

    下面利用程序设计语言实现求解汉诺塔问题的算法,以便能够在计算机上运行,从而实际求解问题。这里分别以C语言为例。
C语言:汉诺塔问题的递归实现
#include
void hanoitower(int n, char A, char B, char C) 

if(n==1) 
   { 
   printf("Move disk %d from %c to %c\n", n, A, C); 
   }else { 
   hanoitower(n-1,A,C,B); 
   printf("Move disk %d from %c to %c\n", n, A, C); 
   hanoitower(n-1,B,A,C); 
   }   //end if-else
}   //end hanoitower method
main() 

   int n; 
   printf("请输入数字n, 以解决n阶汉诺塔问题:\n"); 
   scanf("%d",&n); 
   hanoitower(n,'A','B','C'); 
   while(1){ } 
}   //end main method

请读者尝试在计算机上实现,观测程序运行的结果。
    至此,已经建立了问题模型,探求了求解方法,设计了合适的数据结构和算法,并将其转换为可执行的程序,可以在计算机上运行。但问题求解的过程和方法是否正确,还有待进一步证明和评价。对算法的正确性、效果的分析为算法的改进提供了有效地指导,该部分内容的扩展知识读者可参阅算法分析与设计方面的书籍。

练习使用VC++6.0 环境调试算法。


1.算法分析 
2.建立问题的数学模型,画出程序流程图 
3.确定程序所采用的数据结构组织 
4.安装VC++6.0 软件 
5.编写简单程序 
6.启动VC++6.0环境,输入程序, 
7.编译、连接、执行程序,观察输出结果 
8.提交程序设计报告,包括算法流程图、程序代码及程序运行结果。 


友情提示:同学您好,此页面仅供预览,在此页面学习不会被统计哦! 请进入学习空间后选择课程学习。
练习