活动一认识算法

1、算法初探,上饶中学 李娜,算法初探,人鬼安全渡河,把三个人和三个鬼都送到对岸，船上必须有一个人或鬼才可以行驶，船上最多能坐两个人或鬼，在河的任何一边，当鬼的个数比人多时，鬼就会吃掉人。请问如何才能使人和鬼都平安的到达对岸？,请讨论并试验，设计成功过河方案。,算法的概念,算法初探,什么是算法？,解决问题的具体方法和步骤,Step1:一人一鬼乘船至对岸 ； Step2:鬼上岸，人乘船回； Step3:两个鬼乘船至对岸； Step4:一个鬼上岸，一个鬼乘船回； Step5:两个人乘船至对岸； Step6:一个人上岸，一人一鬼乘船回； Step7:两个人乘船至对岸。 Step8:两个人上岸，一个鬼乘船

2、回； Step9:两个鬼乘船至对岸； Step10:一个鬼上岸，一鬼乘船回； Step11:两个鬼乘船至对岸。,Step1:两个鬼乘船至对岸 ； Step2:一鬼上岸，另一鬼乘船回； Step3:两个鬼乘船至对岸； Step4:一个鬼上岸，一个鬼乘船回； Step5:两个人乘船至对岸； Step6:一个人上岸，一人一鬼乘船回； Step7:两个人乘船至对岸。 Step8:两个人上岸，一个鬼乘船回； Step9:两个鬼乘船至对岸； Step10:一个鬼上岸，一鬼乘船回； Step11:两个鬼乘船至对岸。,算法的概念,算法初探,什么是算法？,解决问题的具体方法和步骤,Step1:两个鬼乘船至对岸

3、； Step2:一鬼上岸，另一鬼乘船回； Step3:两个鬼乘船至对岸； Step4:一个鬼上岸，一个鬼乘船回； Step5:两个人乘船至对岸； Step6:一个人上岸，一人一鬼乘船回； Step7:两个人乘船至对岸。 Step8:两个人上岸，一个鬼乘船回； Step9:两个鬼乘船至对岸； Step10:一个鬼上岸，一鬼乘船回； Step11:两个鬼乘船至对岸。,Step1:一人一鬼乘船至对岸 ； Step2:鬼上岸，人乘船回； Step3:两个鬼乘船至对岸； Step4:一个鬼上岸，一个鬼乘船回； Step5:两个人乘船至对岸； Step6:一个人上岸，一人一鬼乘船回； Step7:两个人乘

4、船至对岸。 Step8:两个人上岸，一个鬼乘船回； Step9:两个鬼乘船至对岸； Step10:一个鬼上岸，一鬼乘船回； Step11:两个鬼乘船至对岸。,算法的概念,算法初探,生活中有哪些地方用到算法？,算法的概念,算法初探,计算机中的算法,两个卖油的伙计要平分10斤油，可手上没有秤。他们只有一个油桶，中油壶和小油壶（容积各为10斤、7斤、3斤）。两个伙计不知该怎么分，正在为难之时，遇上了骑马赶路的汉将韩信。韩信连马都没下，三言两语便说出了分油的办法。韩信立马分油故事,请尝试设计分油方案。,10 0 0,桶 中壶 小壶,3 7 0,算法初探,算法的概念,油桶A中的油量为a，油壶B（容积为b

5、v)中的油量为b，油壶C（容积为cv)中的油量为c，需要将A中油量a平分为两个i； 操作步骤如下：A-B-C-A step1.当B壶空（b=0）时，从A桶倒满B壶。 step2.从B壶分一次或多次倒满C壶 若b=cv-c，倒满C壶，操作step3; 若bcv-c，倒空B壶，操作step1; Step3:当C壶满（c=cv）时，从C壶倒回A桶。 操作中，若有a=i或b=i或c=i时，达到平分目的，操作结束。,算法的概念,算法初探,第二次分油,两个卖油的伙计要平分16斤油，可手上没有秤。他们只有一个油篓，一个油罐和一个油葫芦（容积各为16斤、9斤、5斤）。,算法初探,算法的概念,算法的概念,算法初

6、探,什么是计算机中算法？,在计算机中，算法是指可以用计算机来解决某一类问题的明确、有效的有限步骤。,算法的目的：解决某一类问题（通用性和价值） 算法的特征：明确性、可行性、有穷性、有序性,算法初探,易理解，不简洁，容易发生歧义,算法的描述方法,油桶A中的油量为a，油壶B（容积为m)中的油量为b，油壶C（容积为n)中的油量为c，需要将A中油量a平分为两个i； 操作步骤如下：A-B-C-A step1.当B壶空（b=0）时，从A桶倒满B壶。 step2.从B壶分一次或多次倒满C壶 若b=cv-c，倒满C壶，操作step3; 若bcv-c，倒空B壶，操作step1; Step3:当C壶满（c=cv）

7、时，从C壶倒回A桶。 操作中，若有a=i或b=i或c=i时，达到平分目的，操作结束。,算法初探,算法的描述方法,直观、简洁，逻辑关系清晰,以“韩信分油为例,用各种框图及文字表示各种操作步骤。,输入a，b，cv c=0，i = a / 2，a = a - b Do While a i And b i And c i print a, b, c If b = cv-c Then B壶倒满C壶（b = b - cv , c = cv） Print a, b, c C倒入A(a = a + c) Else B全部倒入C壶（ c = b，b = 0） Print a, b, c A桶倒满B壶 End I

8、f Loop Print a, b, c,算法初探,算法的描述方法,伪代码-介于自然语言和真正的程序代码之间的一种算法描述,“韩信分油” 伪代码,算法的描述,算法初探,如何表达和描述算法？,自然语言,流程图,伪代码,算法初探,有9个硬币，其中1个是假币（偏轻），给你1架天平，你能把这个假币找出来吗？ 请设计算法。,小试牛刀,算法初探,方法一：s1.任取2枚银币分别放在天平的两边，如果天平不平衡，则轻的那一边就是假银币；否则进行s2。s2.取下右边的银币，然后把剩下的7枚银币依次放在右边进行称量，直到天平不平衡，偏轻的那一边就是假银币。,方法二：s1.任取两枚银币分别放在天平的两端，如果天平左右

9、不平衡，则轻的那一边是假银币；否则进行s2。s2.重复执行s1，如果前4次天平都平衡，则剩下的那一枚是假银币。,方法三：s1.把9枚银币平均分成3组，每组3枚。s2.先将其中两组放在天平的两边，如果天平不平衡，那么假银币币就在轻的那一组；如果天平左右平衡，则假银币就在未称量的那一组内。s3.取出含有假银币的那一组，从中任取2枚银币放在天平左右两边进行称量，如果天平不平衡，则轻的那一边是假银币；如果天平平衡，则未称的那一枚就是假银币。,方法四： s1.分别取四枚银币放在天平两端，如果天平左右平衡，则剩下的那枚硬币是假银币；否则假硬币在较轻的那组，进行s2。 s2.将较轻的四枚硬币分成两份，分别放在天平两端，假硬币在较轻的那两枚硬币中。 s3.将含假硬币的两枚硬币分别放在天平两端，较轻的那一枚是假硬币。,小试牛刀,7次,4次,3次,2次,算法初探,算法优化思想,1、解决同一个问题，可以用不同的算法，其效果和效率可能大不相同。 2、算法很重要，我们要根据实际情况，有意识的设计最优的算法解决问题。,算法初探,课堂小结,算法的概念,算法的初探,第二次分油,两