C#第5章 C#程序算法选讲 4H.ppt

1、面向对象的编程-Visual c#。NET Programming，聊城大学理工学院曹寅杰caoyinjie，第5章C#程序算法选择，著名的计算机程序设计艺术(计算机程序设计)，算法导论(典型算法的示例1。递归方法2。递归方法3。彻底的方法4。贪心算法5。重复方法6。数值积分，1，递归，递归：用多步骤可重复的简单运算(法则)描述复杂问题的方法。利用特定关系进行中间推理的算法，直到通过已知条件得到结果。将复杂的计算过程转换为简单过程的多次迭代，每次迭代都会基于旧值传递新值，将旧值替换为新值。该算法利用了计算机速度和孜孜不倦的机械特性。斐波那契数列是1，1，2，3，5，8，。系列中的第一项和第二项

2、都是1，从第三项开始，分别是前面两项的和。示例1:递归斐波那契数列第n个值；初始：f1=1，F2=1；循环：从i=3开始重复f3=f1 F2和f2=f3，f1=f2，然后执行下一个循环。Fibonacci列第n个值，private void button 1 _ click(object sender，eventargs e) intf1=1，F2=1，F3=int n=convert . toint 16(textbox 1 . text)；if(n=1 | | n=2)F3=1；else for(int I=3)；I 0；-I) lastn=(last 1)* 2；textbox 1 .

3、text=lastn . tostring()“ r n”； ，2，递归方法，程序本身的编程技术称为递归。在C#中，您可以定义在内部调用自己的方法(或静态方法)。递归可以通过与原问题大小相似的小问题分层解决大而复杂的问题。递归功能用于使用受限语句定义对象的无限集合，代码简洁。递归问题：可以使用自己的结构来说明自己的问题，如：阶乘。专用int fact (int n) .n=n * fact(n-1)；，在递归处理中使用堆栈实现。堆栈存储参数、本地变量和返回地址。递归进程：每次调用都会堆栈当前参数，直到达到递归结束条件。回归过程：在堆栈中继续弹出当前参数，直到堆栈为空。递归算法很简单，但占用了很

4、多内存空间，需要很长时间。1、可以看到构成递归的结构，例如迭代结束条件和结束时的值。2、可以递归形式表示，可以递归发展为终止条件。递归，回归，示例3:求阶乘n的递归方法！private intfact(intn) if(n=1)n=1；else n=n * Fact(n-1)；return n；，private void button 1 _ click(object sender，eventargs e) intn=convert . toint 16(textbox 1 . text)；TextBox2。Text=Fact(n)。ToString()；，示例4: Fibonacci系列中第

5、n项的值，public static int fibon acci(int I)/)计算序列1，1，2，3，5，8. I项值if(I=0)return 0；if(I=1)return 1；else return fibon acci(I-1)fibon acci(I-2)；，private void button 1 _ click(object sender，eventargs e) intn=convert . toint 16(textbox 1 . text)；Textbox2.text=Fibonacci (n)。tostring()；，示例5:递归梵文(Hanoi)问题*，古代的一

6、个梵文中有a、b和c三个塔，a柱上有64个不同大小的金盘，大的在下面。僧侣们的任务是将这64个板块从阿站移到c列，利用b柱，但一次只能移动一个板块，在移动的过程中，在每个柱子上总是保持广阔的市场，完成这个任务，世界的末日就要到了。编制程序要求打印移动步骤。梵文(河内)问题，反推：1，和尚1先把上面63个板块移到b位置，和尚2再把最大的移到c位置，和尚3最后把63个板块移到c位置，完成了这一切。第二，问题是要把63个板块移到b位置，同样要把上面的62个板块移到c位置，把第63个板块移到b位置，然后把62个板块移到b位置。3、同样，直到最后一个板块的移动。可以看出，这也是说明自己的问题，可以用递归

7、的方法处理。梵文塔(河内)问题，静态Hanoi计数=0；/移动盘子总数static string plan=；/移动程序，碟子的数量太多了，可能会溢出来！private void button 1 _ click(object sender，event args e) intn=convert . toint 16(textbox 1 . text)；Textbox2.text=Hanoi (n，a，b，c)。tostring()；TextBox3。Text=plancount=0；plan=；，梵文塔问题，public static int Hanoi (int n，char a，char

8、b，char c) if(n=1) couiPlan=plan A to C ！Return count else count河内(n-1，a，c，b)；/将第n个磁盘(n-1)上的盘子移到另一个磁盘上。Plan=plan a to c/要将第n个磁盘移动到目标塔式机，请执行以下操作：河内(n-1，b，a，c)；/使用中心塔将原始第n个磁盘的(n-1)上移到第n个磁盘的塔上；Return count，3，彻底的方法，彻底的方法，枚举方法，枚举方法，测试方法，暴力破解方法。通过逐一测试即将发生的各种情况，判断条件是否满足，通常使用循环实现这一点。解密后，将逐个计算密码，直到找出实际密码。例如，已

9、知为4个字符，全部由数字组成的口令可以是10，000个组合。因此，最多尝试10，000次，就可以找到正确的口令。理论上，使用这个方法可以破解任何密码，问题在于如何缩短试报时间。所以有些人用电脑提高效率，有些人补充词典，缩小密码组合的范围。例6:在宫里寻找水仙花数，“水仙花数”表示3位数的整数。这个整数等于数字的立方和数字本身。编程在文本框1中显示所有水仙的数量，在文本框2中显示数字。水仙花的数量有153，370，371，407等4种。水仙花数，private void button 1 _ click(object sender，eventargs e) intnum，I=0；Int a、b、

10、c； 100，10，位数for(num=100；Num1000Num) a=Convert。toint 16(num/100)；/获取100位b=convert . toint 16(num-a* 100)/10)。/获取10位c=convert . toint 16(num-a* 100-b * 10)。/if(num=a* a* b * b * b c * c * c) textbox 1 . text=num . tostring()；I； textBox2。text=I . ToString()；，中国古代数学家张秋健在他的算经中有名的“100美元购买100只鸡的问题”:鸡翁1，5价值

11、，鸡妈妈1，价值3，鸡3，价值1，100美元购买100只鸡程序列出所有可能的鸡购买程序。将鸡翁、继母、小鸡分别设置为x、y、z，并根据标题要求列出方程式。x y z=100 5x3 z/3=100 3三个未知方程，此问题有几个解决方案。要解决这种问题，采用“考试方法”，把各种情况都考虑在内。3个未知数是使用三重循环实现的。示例7:购买100只鸡的彻底资金，private void button 1 _ click(object sender，eventargs e) for(int x=1；X=100X) /鸡翁x for(int y=1)；Y=100Y) /鸡妈妈y for(int z=3)

12、；Z=100Z=3) /小鸡z if (x y z=100)，购买100美元100只鸡，范例8:彻底变更，将1角钱变更为零钱(1分、2分、1角钱)构成拐角的零钱中最多有10个1分，5个2分，2个5分。判断在所有组合中需要多少次，总和正好是一个角(10分)。，更改更改的彻底方法，private void button 1 _ click(object sender，eventargs e) for(int x=0；X=10X) /1分钟数字 for(int y=0；y=5；Y) /2等分计数 for(int z=0；z=2；/5分钟数字 if(x y * 2 z * 5=10) textbox

13、1 . text= scenario I . ToString() 1分钟数字3360 x，4，贪心算法，贪心算法是对寻找最佳解决方案的某些问题的更简单、更快的设计技术。其特征是根据当前情况做出最佳选择，而不考虑各种可能的总体情况，并基于当前情况而不是节约时间。自下而上，进行反复的贪心选择，每次做贪心的选择，都会将问题简化为较小的子问题，每一步都可以通过贪心的选择，获得问题的最佳答案。虽然每个阶段都是局部最佳解决方案，但生成的全局解决方案不一定是最佳解决方案，因此不要反方向进行贪心的方法。例9:贪心的算法寻找变化，一个孩子用不到1美元的钱买了不到1美元的糖，售货员想用最少的硬币找孩子。硬币面值

14、为25美分、10美分、5美分和1美分的硬币。推销员组成了要分阶段寻找的零钱数，每次都加了一枚硬币。选择硬币时使用的贪婪指南如下。每次选择的时候，要尽可能多的零钱，但要选择除硬币值和0以外的所有硬币。假设要给孩子67美分，首先放两个25美分的硬币，当然不能再抽的25美分的硬币第三个，第三个10美分的硬币，然后放两个5美分的硬币，最后放两个1美分的硬币。贪心算法查找变化，private void button 1 _ click(object sender，eventargs e) text box 2 . text= ；Int m=25，10，5，1 ；/硬币面值int n=convert . toint 16(textbox 1 . text)；/0 intnum=new intm . Length；/硬币类型阵列num=赵令(m，n)；/各种数字分配for(int I=0；I m . LengthI) textBox2。Text=numi mi面值；public static intzhaoling(intm，int n) intk=m . length；intnum=new intk；for(int I=0)；I k；I) numI=n/mI；/模式，硬币数n=n % mI；/剩馀 return num、5、迭代方法、迭代方法(也称为迭代方法)是