《【2017年整理】C#第5章 C#常用算法程序设计 4Hnew》由会员分享，可在线阅读，更多相关《【2017年整理】C#第5章 C#常用算法程序设计 4Hnew（47页珍藏版）》请在金锄头文库上搜索。
1、面向对象的程序设计Visual C# Programming,聊城大学 理工学院曹银杰,第五章 C#程序算法选讲,关于算法的书籍很多，如著名的计算机程序设计艺术（The Art Of Computer Programming) 、算法导论（Introduction To Algorithms）。常用算法举例 1.递推法2.递归法3.穷举法4.贪婪算法5.迭代法求方程的根6.数值积分搜索、排序、动态规划本章提交作业：每个题目的代码、截图、流程图,1、递推法,递推：一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。把一个复杂的计算
2、过程转化为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。该算法利用了计算机速度快和不知疲倦的机器特点。 又分顺推法与倒推法。如Fibonacci数列：1，1，2，3，5，8，。该数列第一项和第二项均为1，从第三项开始，每一项都是前面两项的和。,实例1.1：Fibonacci数列第n项值顺推法,初始：i=1 or i=2 时 f1=1,f2=1； 循环：从i=3开始， f3=f1+f2； /递推公式，推出新值 f1=f2； f2=f3；/新值代替旧值，递推下个新 值（下轮循环）做好准备循环到第n项，即得出第n项值。,Fibonacci数列第n项值,private vo
3、id button1_Click(object sender, EventArgs e) int f1 = 1 , f2 = 1 , f3 = 0; int n = Convert.ToInt16(textBox1.Text); if (n = 1 | n = 2) f3=1; else for (int i = 3; i 0; -i ) textBox1.Text += i.ToString()+天：+lastn.ToString() + rn; / Convert.ToChar(13) + Convert.ToChar(10); lastn = (lastn + 1) * 2; ,2、递归
4、法,递归问题：能用自身结构描述自身的问题。,例：阶乘,递归法,程序设计中函数(方法)调用自身的编程技巧称为递归。例:阶乘,private int Fact(int n ) n = n * Fact(n - 1); ,递归可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归的能力在于用有限的语句来定义对象的无限集合，代码简洁。,计算机用栈来实现递归，5! = ？分两步:递推-进栈过程：每调用自身时，将当前参数 f(5)=5*f(4)首先进栈，直到递归结束条件:f(1)=1。,f(5)=5*f(4),f(4)=4*f(3),f(1)=1,f(2)=2*f(1),f(3)=
5、3*f(2),栈底,栈顶,递归法,递归法,回归、出栈：不断从栈中弹出当前的参数，直到栈底。,递归算法简单，但占内存多、耗时长。由此可见构成递归的结构如下：1、递归结束条件及结束时的值；2、能用递归形式表示，并且递归向终止条件发展。,f(1)=1,f(2)=2*1=2,f(3)=3*2=6,f(4)=4*6=24,f(5)=5*24=120,栈顶,栈底,实例2.1：递归法求阶乘n!,private int Fact(int n ) if (n=1) n = 1; /结束条件 else n = n * Fact(n - 1); return n; ,private void button1_Cli
6、ck(object sender, EventArgs e) int n = Convert.ToInt16(textBox1.Text); textBox2.Text = Fact(n).ToString(); ,实例2.2：递归法求Fibonacci数列第n项值,public static int Fibonacci( int i ) if(i=1 | i = 2) return1; /结束条件 else return Fibonacci(i - 1) + Fibonacci(i - 2) ; ,private void button1_Click(object sender, Event
7、Args e) /计算数列1,1,2,3,5,8.第i项值 int n = Convert.ToInt16(textBox1.Text); textBox2.Text = Fibonacci(n).ToString(); ,3、穷举法,穷举法，也称列举法、枚举法、试凑法、暴力破解法。即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。如密码的暴力破解法破译，即将密码进行逐个推算直到找出真正的密码为止。例如一个四位数字组成的密码，最多尝试10000次就能找到正确的密码。
8、银行等部门是怎么解决这个暴力破解问题的？,实例3.1：穷举法求水仙花数,穷举法求水仙花数,private void button1_Click(object sender, EventArgs e) int i=0; int a, b, c; 百、十、个位上的数 for (int num=100; num1000; num+ ) /穷举i a = Convert.ToInt16(num / 100);/取百位上的数 b = Convert.ToInt16(num% 100) / 10); /取十位上的数 c = Convert.ToInt16(num % 10);/取个位上的数 if (num
9、 = a * a * a + b * b * b + c * c * c) textBox1.Text += num.ToString()+ ; i+; textBox2.Text =i.ToString (); ,穷举法求水仙花数 法二,private void button1_Click(object sender, EventArgs e) for (int i = 1; i = 9; i+) for (int j = 0; j = 9; j+) for (int k = 0; k = 9; k+) if (i * 100 + j * 10 + k = i * i * i + j * j
10、 * j + k * k * k) textBox1.Text += (i * 100 + j * 10 + k).ToString()+rn; ,实例3.2：穷举法百钱买百鸡,古代数学家张丘建在他的算经中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？设鸡翁、鸡母、鸡雏各为x、y、z只，列出方程为：x+y+z=1005x+3y+z/3=100三个未知数，两个方程，此题有若干个解。解决此类问题采用穷举法，把每一种情况都考虑到。穷举三个未知数，利用三重循环来实现。,private void button1_Click(object sender, EventArgs e) for (int x = 1; x = 100/5; x+) /穷举鸡翁x for (int y = 1; y = 100/3; y+) /穷举鸡母y for (int z = 3; z = 100; z += 3) /穷举鸡雏z if (x + y + z = 100) & (x * 5 + y *3 + z / 3 = 100) textBox1.Text += 鸡翁: + x.ToString() + 鸡母: + y.ToString() + 鸡雏: + z.ToString()+rn ; ,
