算法与程序设计(第一章)

算法与程序设计第一章揭开计算机解决问题的

神秘面纱计算机解决问题的过程算法与算法的描述程序与程序设计语言算法与程序设计1、具体问题：华南太阳能设备厂在计划期内拟生产甲、乙、丙三种适销产品，每件销售收入分别为4万元、3万元、2万元。按工艺规定，甲、乙、丙三种产品都需要在A、B、C、D四种不同的设备上加工，其加工所需要的时间见下表。已知A、B、C、D四种设备在计划期内有效使用台时数分别为12、8、16、12。如何安排生产可使收入最大？设备产品

A

B

C

D甲2140乙2204丙1100探究的问题探究过程找出已知和未知已知甲乙丙销售收入，ABCD四种设备有效使用台时数，甲乙丙加工的台时数，未知的是甲乙丙的产量及总销售额。明确已知和未知之间关系甲乙丙加工的台时数不能超过ABCD有效使用台时数。人工求解问题甲乙丙的产量及总销售额。写出解题的算法穷举2、分析问题：算法与程序设计2x+2y+z≤12X+2y+z≤84x≤164y≤120≤x≤6;0≤y≤6;0≤z≤120≤x≤8;0≤y≤4;0≤z≤80≤x≤40≤y≤30≤x≤40≤y≤30≤z≤8算法与程序设计3、设计算法：x=0x>4y=0y>3z=0z>82*x+2*y+z<=12x+2*y+z<=8f(x,y,z)=4*x+3*y+2*zz=z+1f(x,y,z)=0y=y+1x=x+1开始NYYYYNNNx=0x>4y=0y>3z=0z>8f_max<f(x,y,z)f_max=f(x,y,z)x_max=xy_max=yz_max=zz=z+1y=y+1x=x+1NYYYYNN结束输出结果算法与程序设计4、编写程序DimxAsInteger,yAsInteger,zAsIntegerDimx_maxAsInteger,y_maxAsInteger,z_maxAsIntegerDimf(4,3,12)AsSingleDimf_maxAsSingleForx=0To4Fory=0To3Forz=0To8If(2*x+2*y+z<=12)And(x+2*y+z<=8)Thenf(x,y,z)=4*x+3*y+2*zElsef(x,y,z)=0EndIfNextzNextyNextx算法与程序设计f_max=0Forx=0To4Fory=0To3Forz=0To8Iff_max<f(x,y,z)Thenf_max=f(x,y,z)x_max=xy_max=yz_max=zEndIfNextzNextyNextxPrint"当x=";x_max;",y=";y_max;",z=";z_max;”时,“Print"f(x,y,z)的最大值=";f_max算法与程序设计5、调试程序、得到结果1）、新建工程；2）、在窗体添加按钮控件；3）、给按钮添加单击事件过程；4）、在单击事件过程内输入编写好的程序；5）、运行程序调试结果。6、在计算机上执行该指令序列5、通过编辑、编译和连接产生计算机能够识别的指令序列4、选用一种编程语言根据算法编写程序4、验证计算结果3、生成解题算法3、用笔、纸和算盘、计算器等工具进行计算2、寻找解题的途径和方法2、寻找解题的途径和方法1、理解和分析所要解决的问题1、理解和分析所面临的问题计算机解题步骤人工解题步骤相同点：无论何种解题方式，在解决某一实际问题时，都应该正确的理解问题的题意，从看似复杂的问题中整理出一个头绪，然后通过算法（即解决问题的一个一个步骤）描述出某一问题的解决过程，进行一定量的计算，最后都必须验证计算结果。不同点：当计算量较大时，人工解题就有点力不从心了，而计算机每秒上亿次的计算速度却不在话下，并且只要算法正确，编程语句无误的话，使用计算机编写的解题程序可以反复使用。例如：sum=1+2+3+4+5……+（n-1）+n这样的问题。算法与程序设计1.1计算机解决问题的过程从一个生产方案问题了解用计算机解决问题的步骤:P6具体问题分析问题设计算法编写程序调试程序得到答案掌握用自然语言表达算法。（P8实践与练习）算法与程序设计想一想算法与程序设计辗转相除法

又名欧几里德算法（Euclideanalgorithm）是求两个正整数之最大公约数的算法。它是已知最古老的算法,其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。1.a÷b，令r为所得余数（0≤r＜b），若r=0，b即为最大公约数；算法结束。

2.互换：置a←b，b←r，并返回第一步。

例如:求112和64的最大公约数.算法如下:

(1).112除以64,余数为______;

(2)．_____除以_____余数为_______;

(3)．_____除以_____余数为_______.

答：112和64的最大公约数为______.两数的最大公约数乘以其最小公倍数=两数相乘例如：求112和64的最小公倍数．

(1).利用辗转相除法求得它们的最大公约数为______;

(2).利用表达式求得最小公倍数：

答：112和64的最小公倍数为______.练习：求164和64的最大公约数．求256和24的最大公约数．练习：求164和64的最小公倍数．求256和24的最小公倍数．算法与程序设计1.2算法和算法的描述1、算法的概念算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。即，用计算机求解某一问题的方法,是能被机械地执行的动作或指令的有穷集合。算法的特征：1）、有0或多个输入。解题算法中可以没有数据输入，也可以同时输入多个需

要算法处理的数据。2）、确定性。解题方法中的任何一个操作步骤都是清晰无误的，不会使人产生

歧义或者误解。3）、有穷性。任何一种提出的解题方法都是在有限的操作步骤内可以完成的，

哪怕是失败的解题方法。4）、有1个或多个输出。一个算法执行结束之后必须有数据处理结果输出，哪怕

是输出错误的数据结果，没有输出的算法使毫无意义的。5）、能行性。解题方法中的任何一个操作步骤在现有计算机软硬件条件下和逻

辑思维中都能够实施实现。算法与程序设计2、算法的描述表示算法的语言有自然语言、流程图、伪代码等。1）、用自然语言描述算法；2）、用流程图描述算法：掌握流程图的基本图形及其功能。3）、用伪代码描述算法。注意对比三种算法描述方式的优劣。1).输入m和n的值;

2).r=m除以n的余数;

3).如果r=0,则输出n