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

1许恒迎[e-mail]办公室：实验楼B305面向对象的程序设计—C#程序设计第五章C#程序算法选讲关于算法的书籍很多，如著名的《计算机程序设计艺术》（TheArtOfComputerProgramming)、《算法导论》（IntroductionToAlgorithms）。常用算法举例–1.递推法–2.递归法–3.穷举法–4.贪心算法–5.迭代法–6.数值积分21、递推法递推：一种用若干步可重复的简运算（规律）来描述复杂问题的方法。通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。把一个复杂的计算过程转化为简单过程的多次重复，每次重复都从旧值的基础上递推出新值，并由新值代替旧值。该算法利用了计算机速度快和不知疲倦的机器特点。如Fibonacci数列为：1，1，2，3，5，8，……。3实例1：递推法Fibonacci数列第n项值初始：f1=1,f2=1；循环：从i=3开始，f3=f1+f2，再让f2=f3,f1=f2迭代后,进行下次循环；4privatevoidbutton1_Click(objectsender,EventArgse){intf1=1,f2=1,f3=0;intn=Convert.ToInt16(textBox1.Text);if(n==1||n==2)f3=1;else{for(inti=3;i=n;i++){f3=f1+f2;f1=f2;f2=f3;}}textBox2.Text=Convert.ToString(f3);}5实例2：递推法猴子吃桃猴子吃桃：小猴在一天摘了若干个桃子，当天吃掉一半多一个；第二天接着吃了剩下的桃子的一半多一个；以后每天都吃尚存桃子的一半零一个，到第10天早上要吃时只剩下一个了，问小猴那天共摘下了多少个桃子？设第n天的桃子为xn，那么它前一天的桃子数xn-1：21)(xx也就是：1x21x即：n1n1nn6privatevoidbutton1_Click(objectsender,EventArgse){intlastn=1;//前一天桃子数，第10天早晨有1个textBox1.Text=1+“\n;for(inti=9;i0;--i){lastn=(lastn+1)*2;textBox1.Text+=lastn.ToString()+\r\n;}}72、递归法)!2()1()!1()!1(!nnnnnn程序调用自身的编程技巧称为递归。C#中可定义方法（或静态方法），该方法内部调用自身。递归可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归问题：能用自身结构描述自身的问题，例:阶乘。privateintFact(intn){…n=n*Fact(n-1);…}8在递归处理中，用栈来实现。栈中存放形参、局部变量、返回地址。递推过程：每调用自身，当前参数压栈，直到达到递归结束条件。回归过程：不断从栈中弹出当前的参数，直到栈空。递推回归9实例3：递归法求阶乘n!privateintFact(intn){if(n==1)n=1;elsen=n*Fact(n-1);returnn;}1)1fac(*11)fac(nnnnnprivatevoidbutton1_Click(objectsender,EventArgse){intn=Convert.ToInt16(textBox1.Text);textBox2.Text=Fact(n).ToString();}10实例4：递归法求Fibonacci数列第n项值publicstaticintFibonacci(inti){//计算数列{1,1,2,3,5,8.......}第i项值if(i==0)return0;if(i==1)return1;elsereturnFibonacci(i-1)+Fibonacci(i-2);}privatevoidbutton1_Click(objectsender,EventArgse){intn=Convert.ToInt16(textBox1.Text);textBox2.Text=Fibonacci(n).ToString();}113、穷举法穷举法，也称列举法、枚举法、试凑法、暴力破解法。即将可能出现的各种情况一一测试，判断是否满足条件，一般采用循环来实现。如密码的破译，即将密码进行逐个推算直到找出真正的密码为止。例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。12实例5：穷举法求水仙花数“水仙花数”是指一种三位整数，它各位数字的立方和等于该数本身。编程将所有的水仙花数显示在文本框1上，并在文本框2中显示个数。水仙花数共有4个：153、370、371和407。13privatevoidbutton1_Click(objectsender,EventArgse){intnum，i=0;inta,b,c;//百、十、个位上的数for(num=100;num1000;num++){a=num/100;//取百位上的数b=(num-a*100)/10;//取十位上的数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();}14中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？☺编程列出所有可能的购鸡方案。设鸡翁、鸡母、鸡雏各为x、y、z只，根据题目要求，列出方程为：x+y+z=1005x+3y+z/3=100三个未知数，两个方程，此题有若干个解。解决此类问题采用“试凑法”，把每一种情况都考虑到。三个未知数利用三重循环来实现。实例6：穷举法百钱买百鸡15privatevoidbutton1_Click(objectsender,EventArgse){for(intx=0;x=100;x++)//鸡翁x{for(inty=0;y=100;y++)//鸡母y{for(intz=0;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()+\r\n;}}}}16实例7：穷举法换零钱将一角钱换成零钱（可以包括含1分、2分、5分中的任意多个面值），共有多少种换法？组成一角的零钱中，最多有10个1分、5个2分、2个5分。判断所有的组合中，总和正好是一角（10分）的情况有多少次即为所求。17privatevoidbutton1_Click(objectsender,EventArgse){for(intx=0;x=10;x++)//1分个数{for(inty=0;y=5;y++)//2分个数{for(intz=0;z=2;z++)//5分个数{if(x+y*2+z*5==10){textBox1.Text+=方案+壹分个数:+x.ToString()+贰分个数:+y.ToString()+伍分个数:+z.ToString()+\r\n;}}}}}184、贪心算法贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，比穷举节省时间。它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解。19实例8：贪心算法找零钱一小孩用1美元买了价值少于1美元的糖，售货员希望用数目最少的硬币找给小孩。（硬币面值为25美分、10美分、5美分、及1美分。）售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大，但所选择的硬币值和不超过找零总数。67美分2个25美分1个10美分1个5美分2个1美分20privatevoidbutton1_Click(objectsender,EventArgse){textBox2.Text=;int[]m={25,10,5,1};//硬币面值intn=Convert.ToInt16(textBox1.Text);//找零数int[]num=newint[m.Length];//硬币种类数组num=zhaoling(m,n);//各种个数赋值for(inti=0;im.Length;i++)textBox2.Text+=num[i]+枚+m[i]+面值+;;}publicstaticint[]zhaoling(int[]m,intn){intk=m.Length;int[]num=newint[k];for(inti=0;ik;i++){num[i]=n/m[i];//模、硬币数n=n%m[i];//余数}returnnum;}215、迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程。迭代算法是用计算机解决问题的一种基本方法，利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令进行重复执行，在每次执行这组指令时，都从变量的原值推出它的一个新值。典型的应用是高次方程求根：–二分迭代法–牛顿迭代法221)二分迭代法高次方程求根二分迭代法求一元高次方程的解。步骤：找y=f(x)的一个有根单调区间[x1,x2];选区间中点x3=(x1+x2)/2，–如f(x1)*f(x3)0，说明根在[x1,x3]内，x2=x3;–否则在[x3,x2],x1=x3；对有根区间继续进行上述操作，当剩余区间|x2-x1|足够小（满足某一给定精度）时，则认为区间的中点是方法的数值解。23实例9：二分迭代法求高次方程根,x3-x-1=0在区间[0,2]中的数值解（精度e=10-6）privatevoidbutton1_Click(objectsender,EventArgse){doublex1=0,x2=2,x3=0;while(x2-x10.00000001)//判断是否满足精度要求{x3=(x1+x2)/2;if((x1*x1*x1-x1-1)*(x3*x3*x3-x3-1)0)x2=x3;elsex1=x3;//改变区间}textBox1.Text=x3.ToString();}24牛顿迭代法(弦截法)•迭代公式：•对方程给定一个初值x1作为方程的近似根，利用迭代公式，求得x1,•当x2为求得的近似根，否则x1=x2，利用迭代公式，求新的x2。)(')(1iiiixfxfxx12xx2)牛顿迭代法高次方程求根25实例10：牛顿迭代法高次方程求根求x3-x–1=0在2附近的根privatevoidbutton1_Click(objectsender,EventArgse){inti=0;//迭代次数doublex1=0,x2=2;while(Math.Abs(x2-x1)0.0001){x1=x2;//迭代公式x2=x1-(x1*x1*x1-x1-1)/(3*x1*x1-1);i++;}textBox1.Text=x2.ToString();textBox2.Text=i.ToString();}266、数值积分多数函数f找不到其原函数F，计算机可以编程求其数值解。定积分的几何意义是求函数曲线和x轴、x=a、x=b三条直线所围成区域的面积。位于x轴上方的面积为正值，下方为负值。求积分有：矩形法、梯形法、抛物线法等。27矩形面