C#第5章 C#程序的算法选讲

1、1.徐恒英办公室：B305，面向对象编程C#编程；2.在第五章中，选择了C#编程算法。有很多关于算法的书，比如著名的计算机编程艺术和算法导论。常用算法示例1。递归方法2。递归方法3。穷举方法4。贪婪算法5。迭代法6。数值积分3，1。递归方法：用几个可重复的简单操作(规则)来描述复杂问题的方法。通过已知的条件，利用特定的关系得到中间推论，直到得到结果。一个复杂的计算过程被转换成一个简单的过程，重复几次，每次从旧值推导出一个新值，旧值被新值替换。该算法利用了计算机的快速和不懈的机器特性。例如斐波纳契数列：1，1，2，3，5，8，4，例1:递归法的斐波那契数列的第n个值，初始值：f1=1，F2=1；

2、循环：从i=3开始，f3=f1 f2，然后迭代f2=f3，f1=f2，然后执行下一个循环。5，私有无效按钮1_Click(对象发送者，事件参数e) int f1=1，f2=1，F3=0；整数n=转换。至16(文本框1)。文本)；如果(n=1 | | n=2)F3=1；else for(int I=3；I=n；I)F3=f1 F2；f1=f2f2=f3文本框2。文本=转换。ToString(F3)；例2:猴子吃桃子，猴子吃桃子：小猴子每天摘几个桃子，当天吃掉一半以上；第二天，我吃了一半以上剩下的桃子；之后，我会每天吃剩下的一半和一个桃子，第十天早上我想吃的时候只剩下一个桃子。我问小猴子那天摘了多

3、少桃子。假设第n天的桃子是xn，那么前一天的桃子编号是xn-1:7，私有无效按钮1 _ click(对象发送者，事件参数e)int lastn=1；/前一天桃子的数量，有一个文本框1。text=第10天上午1 n ;for(int I=9；I 0；-I)lastn=(lastn 1)* 2；文本框1。Text=lastn。ToString()rn；递归方法，程序调用自身的编程技巧称为递归。方法(或静态方法)可以用C#定义，它在内部调用自己。递归可以将一个大而复杂的问题转化为一个与原问题相似的小问题。递归问题：你可以用你自己的结构描述你自己的问题，例如，阶乘。私有整数事实(整数n ) n=n *

4、事实(n-1)；9，在递归处理中，它是通过堆栈实现的。堆栈存储形式参数、局部变量和返回地址。递归过程：每次你调用自己的时候，当前的参数被推到堆栈中，直到达到递归结束条件。回归过程：不断从堆栈中弹出当前参数，直到堆栈为空。递归，回归，10，示例3:阶乘n的递归方法！如果(n=1) n=1，则为私有整数(整数n)；否则n=n *事实(n-1)；返回n；私有无效按钮1_Click(对象发送者，事件参数)int n=转换。至16(文本框1)。文本)；文本框2。文本=事实(n)。ToString()；11，例4:递归法求斐波那契数列的第n个值，公共静态int斐波那契(int I)/计算数列1，1，2，3

5、，5，8的I值.如果(i=0)返回0；如果(i=1)返回1；否则返回斐波纳契(i - 1)斐波纳契(I-2)；私有无效按钮1_Click(对象发送者，事件参数)int n=转换。至16(文本框1)。文本)；文本框2。文本=斐波那契(n)。ToString()；穷举法，又称枚举法、枚举法、试错法和蛮力法。逐一测试所有可能的情况，并判断条件是否满足，通常是通过循环实现的。如密码解密，则逐个计算密码，直到找到真正的密码。例如，一个已知为四位数字并由所有数字组成的密码可能有10，000个组合，因此最多尝试10，000次后就可以找到正确的密码。理论上，任何一种密码都可以用这种方法破解，但问题只在于如何缩

6、短试错时间。因此，一些人使用电脑来提高效率，而另一些人使用字典来缩小密码组合的范围。，13，例5:水仙花的数量是用穷举法计算的。“水仙花数”是指一个三位数的整数，其每位数的三次和等于数本身。编程将在文本框1中显示所有水仙花，并在文本框2中显示数字。有4朵水仙花：153，370，371和407。14，私有无效按钮1_Click(对象发送者，事件参数e)整数，I=0；int a，b，c；/100、10和1位上的数字代表(数字=100；num1000数量)a=数量/100；/取百位数上的数字b=(num-a * 100)/10；/取十位数c=num-a * 100-b * 10；/如果(num=a

7、* a * ab * b * BC * c * c)text box 1 . text=num . tostring()则取数字；我；文本框2。文本=I . ToString()；中国古代数学家张秋俭，在他的计算中提出了著名的“百元买百只鸡”的问题：鸡翁一只，值五，鸡妈妈一只，值三，鸡小鸡三只，值一，用一百元买百只鸡，问翁、妈妈和小鸡什么几何？程序列出了所有可能的鸡肉购买计划。让鸡翁、鸡妈妈和鸡小鸡分别是x、y和z。根据题目的要求，方程如下：x y z=100 5x 3y z/3=100，三个未知数和两个方程。这个问题有几种解决方法。为了解决这些问题，我们采用了“试错法”，并且考虑了各种情况。

8、三个未知数通过三重循环实现。示例6:穷举方法：用100美元买100只鸡，16，私有无效按钮1 _ click(对象发送者，eventargs e)为(int x=0；x=100X) /鸡翁x为(int y=0；y=100Y) /鸡妈妈y为(int z=0；z=100Z=3) /奇克z如果(x y z=100)，17，示例7:零钱的穷举方法，将一角硬币换成零钱(包括任意数量的面值，包括1美分、2美分和5美分)。有多少种方法？组成一角硬币的零钱有十个1美分、五个2美分和两个5美分。判断所有组合的总和正好是一个角(10分)的多少倍是你想要的。18，私有无效按钮1_Click(对象发送者，事件参数e)

9、为(int x=0；x=10X) /1分钟数为(int y=0；y=5；Y) /2分钟(int z=0；z=2；Z) /5分钟，如果(x y*2 z*5=10)文本框1。文本=方案一分钟数字： x.ToString()两分钟数字： y.ToString()五分钟数字3360z。tostring()rn；贪婪算法，这是一种更简单、更快速的解决一些优化问题的设计技术。其特点是循序渐进，经常根据当前情况，根据一定的优化措施做出最佳选择，而不考虑所有可能的全局情况，与穷举相比节省了时间。它采用自顶向下的迭代方法进行连续的贪婪选择。每一个贪婪的选择都将问题简化为一个更小的子问题，通过每一个贪婪的选择，都

10、可以得到一个最优解。20，例8:贪婪算法找零，一个孩子用一美元买了不到一美元的糖，售货员想给孩子最小的硬币。(硬币的面值是25美分、10美分、5美分和1美分。)，销售员一步一步地补上零钱，一次加一枚硬币。在硬币选择中使用的贪婪标准如下：在每次选择中应该尽可能地增加零钱的数量，但是所选硬币的总和不应该超过零钱的总量。21，私人空间按钮1 _点击(对象发送者，事件)文本框2。文本=；int m=25，10，5，1；/硬币面额int n=convert . toint 16(text box 1 . text)；/查找零数字int num=新intm。长度；/硬币式阵列数=赵(m，n)；/为(int

11、 I=0；长度；I)文本框2。文本=numi mi面值；公共静态整数(整数m，整数n)整数k=m长度；int num=新intk对于(int I=0；I k；I)numi=n/mi；/模块和硬币数量n=n % mi/余数返回数；迭代方法，也称为旋转方法，是从变量的旧值中递归出新值的过程。迭代算法是计算机解决问题的基本方法。利用计算机运算速度快、适合重复运算的特点，计算机可以重复执行一组指令，每次执行这组指令时，都会从其原始值中导出一个新的变量值。典型的应用是求高阶方程的根：牛顿迭代法与二元迭代法，23，1)用二元迭代法求高阶方程的根，用二元迭代法求一元高阶方程的解。步骤：找到y=f(x)的根单

12、调区间x1，x2；选择区间中点x3=(x1 x2)/2，如f (x1) * f (x3)0，表示根在x1和x3，且x2=x3否则在x3，x2，x1=x3上述操作在根区间内继续进行。当剩余区间|x2-x1|足够小时(满足给定精度)，区间的中点被认为是该方法的数值解。24，例9:用二进制迭代法求高阶方程的根，x3-x-1=0是区间0，2(精度e=10-6)中的数值解，private void button 1 _ click(object sender，eventargs e) double x1=0，x2=2，x3=0；(x2-x1 0.0000001)/判断是否满足精度要求x3=(x1 x2)

13、/2；如果(x1 * x1 * x1-x1-1)*(x3 * x3 * x3-x3-1)0)x2=x3；否则x1=x3/更改间隔文本框1。文本=x3。ToString()；25，牛顿迭代法(弦切法)迭代公式：给出一个初始值x1作为方程的近似根，用迭代公式得到x1，如果x2是近似根，否则x1=x2，用迭代公式得到一个新的x2。2)牛顿迭代法求高阶方程的根，26，例10:牛顿迭代法求高阶方程的根，x3-x 1=0近2，私有空按钮1 _ click(对象发送者，事件变量e)int I=0；/迭代次数加倍x1=0，x2=2；而(数学。Abs(x2 - x1 ) 0.0001) x1=x2。/迭代公式x2=x1-(x1 * x1 * x1-x1-1)/(3 * x1 * x1-1)；我；文本框1。文本=x2。ToString()；文本框2。文本=I . ToString()；27，6，数值积分，大多数函数f找不到它原来的函数f，计算机可以对它的数值解进行编程