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

1、1范鑫烨办公室：实验楼B304 面向对象的程序设计 C#程序设计第1页，共26页。第五章 C#程序算法选讲关于算法的书籍很多，如著名的计算机程序设计艺术（The Art Of Computer Programming) 、算法导论（Introduction To Algorithms）。常用算法举例 1.递推法2.递归法3.穷举法4.贪心算法5.迭代法6.数值积分2第2页，共26页。1、递推法递推：一种用若干步可重复的简运算（规律）来描述复杂问题的方法。通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。 把一个复杂的计算过程转化为简单过程的多次重复，每次重复都从旧值的基础上递推出新值

2、，并由新值代替旧值。该算法利用了计算机速度快和不知疲倦的机器特点。 如Fibonacci数列为：1，1，2，3，5，8，。3第3页，共26页。实例1：递推法Fibonacci数列第n项值初始：f1=1,f2=1； 循环：从i=3开始，f3=f1+f2，再让f2=f3,f1=f2迭代后,进行下次循环；4第4页，共26页。 private void button1_Click(object sender, EventArgs e) int f1 = 1 , f2 = 1 , f3 = 0; int n = Convert.ToInt16(textBox1.Text); if (n = 1 | n

3、= 2) f3=1; else for (int i = 3; i 0; -i ) lastn = (lastn + 1) * 2; textBox1.Text += lastn.ToString() +rn; 7第7页，共26页。2、递归法程序调用自身的编程技巧称为递归。C#中可定义方法（或静态方法），该方法内部调用自身。递归可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归问题：能用自身结构描述自身的问题，例:阶乘。private int Fact(int n ) n = n * Fact(n - 1); 8第8页，共26页。在递归处理中，用栈来实现。栈中存放形

4、参、局部变量、返回地址。递推过程：每调用自身，当前参数压栈，直到达到递归结束条件。回归过程：不断从栈中弹出当前的参数，直到栈空。递推回归9第9页，共26页。实例3：递归法求Fibonacci数列第n项值public static int Fibonacci(int i) /计算数列1,1,2,3,5,8.第i项值 if(i=0)return0; if(i=1)return1; else return Fibonacci(i - 1) + Fibonacci(i - 2); private void button1_Click(object sender, EventArgs e) int n

5、= Convert.ToInt16(textBox1.Text); textBox2.Text = Fibonacci(n).ToString(); 10第10页，共26页。3、穷举法穷举法，也称列举法、枚举法、试凑法、暴力破解法。即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。如密码的破译，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码

6、组合的范围。 11第11页，共26页。实例4：穷举法求水仙花数“水仙花数”是指一种三位整数，它各位数字的立方和等于该数本身。编程将所有的水仙花数显示在文本框1上，并在文本框2中显示个数。水仙花数共有4个：153、370、371和407。12第12页，共26页。private void button1_Click(object sender, EventArgs e) int num，i=0; int a, b, c; /百、十、个位上的数 for (num=100; num1000; num+ ) a = num / 100; /取百位上的数 b = (num - a * 100) / 10

7、; /取十位上的数 c = num - a * 100 - b * 10; /取个位上的数 if (num = a * a * a + b * b * b + c * c * c) textBox1.Text += num.ToString()+ ; i+; textBox2.Text =i.ToString (); 13第13页，共26页。中国古代数学家张丘建在他的算经中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？编程列出所有可能的购鸡方案。设鸡翁、鸡母、鸡雏各为x、y、z只，根据题目要求，列出方程为：x+y+z=1005x

8、+3y+z/3=100三个未知数，两个方程，此题有若干个解。解决此类问题采用“试凑法”，把每一种情况都考虑到。三个未知数利用三重循环来实现。 实例5：穷举法百钱买百鸡14第14页，共26页。private void button1_Click(object sender, EventArgs e) for (int x = 0; x = 100; x+) /鸡翁x for (int y = 0; y = 100; y+) /鸡母y for (int z = 0; z = 100; z += 3) /鸡雏z if (x + y + z = 100) & (x * 5 + y *3 + z / 3

9、 = 100) textBox1.Text += 鸡翁: + x.ToString() + 鸡母: + y.ToString() + 鸡雏: + z.ToString()+rn ; 15第15页，共26页。4、贪心算法贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，比穷举节省时间。它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解。16第16页，共26页。实例6：贪心算法找零钱 一小孩用1美

10、元买了价值少于1美元的糖，售货员希望用数目最少的硬币找给小孩。（硬币面值为25美分、10美分、5美分、及1美分。） 售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大，但所选择的硬币值和不超过找零总数。67美分2个25美分1个10美分1个5美分2个1美分17第17页，共26页。private void button1_Click(object sender, EventArgs e) textBox2.Text = ; int m = 25, 10, 5, 1 ; /硬币面值 int n = Convert.ToInt16(textBo

11、x1.Text); /找零数 int num = new intm.Length;/硬币种类数组 num = zhaoling(m, n); /各种个数赋值 for (int i = 0; i m.Length; i+) textBox2.Text += numi + 枚 + mi + 面值+; public static int zhaoling(int m, int n) int k = m.Length; int num = new intk; for (int i = 0; i k; i+) numi = n / mi; /模、硬币数 n = n % mi; /余数 return nu

12、m; 18第18页，共26页。5、迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法，利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令进行重复执行，在每次执行这组指令时，都从变量的原值推出它的一个新值。典型的应用是高次方程求根：二分迭代法19第19页，共26页。1)二分迭代法高次方程求根二分迭代法求一元高次方程的解。步骤：找 y=f(x) 的一个有根单调区间x1,x2;选区间中点x3=(x1+x2)/2，如f (x1) * f (x3) 0.00000001)/判断是否满足精度要求 x3 = (x1 + x2) / 2; if

13、 (x1 * x1 * x1 - x1 - 1) * (x3 * x3 * x3 - x3 - 1) 0 ) x2 = x3 ; else x1 = x3 ;/改变区间 textBox1.Text =x3.ToString(); 21第21页，共26页。6、数值积分多数函数f找不到其原函数F，计算机可以编程求其数值解。定积分的几何意义是求函数曲线和x轴、x = a、x = b 三条直线所围成区域的面积。位于x轴上方的面积为正值，下方为负值。求积分有：矩形法、梯形法、抛物线法等。22第22页，共26页。矩形面积法求数值积分可将此区域分割成很多等宽度的矩形，用矩形的面积和近似表示区域的面积。n等分w=(b-a)/n高h=f(a+w*i)S=(w*h)23第23页，共26页。实例8：矩形面积法求积分24第24页，共26页。 private void button1_Click(object sender, EventArgs e) double s = 0;/积分和 double a = 0, b = 2;/积分区间 long n = Convert.ToInt32(textBox1.Text);/划分矩形个