常用的算法思想2

一、常用的算法思想1.穷举法思想基本概念：穷举法（ExhaustiveAttackmethod）,它是一种最为直接，最容易实现，同时又最为耗时的一种解决问题的算法思想。穷举法算法的基本思想是：在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中得到问题的答案。【实例\_1】寻找[1,100]之间的素数(code\_1.cpp)#includestdafx.h#includestdio.h#includemath.hintIs_Prime(inti){if(i==1)return0;if(i==2)return1;if(i2&&i%2==0)return0;intj;intt=0;for(j=3;j=sqrt(i);j+=2)if(i%j==0){t=1;return0;}if(t==0)return1;}voidGetPrime(intlow,inthigh){/*寻找[low,high]之间的素数*/inti;for(i=low;i=high;i++)if(Is_Prime(i))printf(%d,i);printf(\n);}intmain(intargc,char*argv[]){intlow,high;printf(\n请输入寻找的上、下区间\n);scanf(%d%d,&low,&high);printf(\n列出所有的素数\n);GetPrime(low,high);getchar();return0;}【实例\_2】TOM的借书方案：TOM共有5本书，要借给A、B、C3位同学，每人只能借1本书，则TOM可以有多少种不同的借书方案。借书方案的解集：#includestdafx.h#includestdio.hintmain(intargc,char*argv[]){inti,j,k;printf(\n示出所有的方案：\n);for(i=1;i=5;i++)for(j=1;j=5;j++)for(k=1;k=5;k++)if(i!=j&&j!=k&&i!=k){printf((%d,%d,%d),i,j,k);}printf(\nHelloWorld!\n);return0;}2.递归与分治思想基本概念：在解决一些比较复杂的问题，特别是解决一些规模较大的问题时，常常将问题分解。具体来说，就是将一个规模较大的问题分割成规模较小的同类问题，然后将这些小的子问题逐个加以解决，最终也就将整个大的问题解决。递归的思想也是一种常见的算法思想。所谓递归算法，就是一种直接或间接地调用原算法本身的一种算法。在实际的算法设计中，递归与分治如同一对兄，经常结合在一起使用。这是因为，由分治方法产生的子问题往往都是原问题的更小规模。反复使用分治的手段，可使子问题与原问题类型一致，但规模不断缩小，最终使子问题比较容易求解。既然子问题与原问题的类型一致，这就具有了所谓的递归，因此可以使用递归的方法用解决原问题的算法去解决同类的子问题。【实例_3】计算n的阶乘!n10!=9!*10,9!=8!*9,---2!=1!*2,1!=0!*1其实阶乘的数学定义可以用递归函数来简单地描述：10!(n1)!0nnnn这样的函数称为递归函数，因为该函数本身直接或间接地调用了该函数本身。基于阶乘的递归函数的描述。就不难设计出计算出!n的递归算法intfactorial(n){if(n==0)return1;elsereturnn*factorial(n-1)}【实例_4】将一个正整数n表示成一系列的正整数之和：12122(1,1)knnnnnnnk被称做正整数的一个划分，不同的划分的个数称为该正整数n的划分数。根据正整数划分的定义，可以总结以下规律：设标记(n,m)P表示正整数n的所有不同划分，最大加数不大于m的划分个数，可以得出计算(n,m)P的递归函数式：11(n,n)nm(n,m)1(n,n1)nm(n,m1)(nm,m)1mPPPPPnm程序如下：#includestdio.hintP(intn,intm){if(m==1||n==1)return1;if(mn)returnP(n,n);if(m==n)return1+P(n,m-1);returnP(n,m-1)+P(n-m,m);}main(){intn,s;printf(Pleaseinputaintegerforgettingthenumberofdivision\n);scanf(%d,&n);/*输入正整数n*/s=P(n,n);/*求出正整数n的划分数*/printf(Thenumberofdivisionof%dis%d\n,n,s);getche();}【实例_5】递归的折半查找算法#includestdio.hintbin_search(intkey[],intlow,inthigh,intk){intmid;if(lowhigh)return-1;else{mid=(low+high)/2;if(key[mid]==k)returnmid;if(kkey[mid])returnbin_search(key,mid+1,high,k);/*在序列的后半部分查找*/elsereturnbin_search(key,low,mid-1,k);/*在序列的前半部分查找*/}}main(){intn,i,addr;intA[10]={2,3,5,7,8,10,12,15,19,21};printf(ThecontentsoftheArrayA[10]are\n);for(i=0;i10;i++)printf(%d,A[i]);/*显示数组A中的内容*/printf(\nPleaseinputaintergerforsearch\n);scanf(%d,&n);/*输入待查找的元素*/addr=bin_search(A,0,9,n);if(-1!=addr)/*查找成功*/printf(%disatthe%dthunitisarrayA\n,n,addr);elseprintf(Thereisno%dinarrayA\n,n);/*查找失败*/getche();}练习1：有1、2、3、4个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？练习2：一球从100米高度自由落下，每次落地后反跳回原高度的一半；再落下，求它在第10次落地时，共经过多少米？第10次反弹多高？练习3：有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？二、数学趣题题目1（三色球问题）：由红、黄、绿三种颜色的球，其中红球3个，黄球3个，绿球6个。现将这12个球混放在一个盒子中，从中任意摸出8个球，编程计算摸出球的各种颜色搭配。分析：这是一道排列组合的问题。从12个球中任意摸出8个球，求颜色搭配的种类。解决这类问题的一种比较简单直观的方法是应用穷举法，在可能的解空间中找出所有的搭配，然后再根据约束条件加以排除，最终筛选出正确的答案。#includestdio.h/*三色球问题求解*/main(){intred,yellow,green;printf(redyellowgreen\n);for(red=0;red=3;red++)/*红色：0，1，2，3*/for(yellow=0;yellow=3;yellow++)/*黄色：0，1，2，3*/for(green=2;green=6;green++)/*绿色：2，3，4，5，6*/if(red+yellow+green==8)printf(%d%d%d\n,red,yellow,green);}题目2（百钱买百鸡问题）：我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题。该问题叙述如下：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁、母、雏各几何？请编写C程序，解决“百钱买百鸡”问题。#includestring.h#includestdio.hintaccord(inti,intj,intk);voidmain(){inti,j,k;printf(Thepossibleplansforbuying100fowlswith100yuanare:\n\n);for(i=0;i=100;i++)for(j=0;j=100;j++)for(k=0;k=100;k++)if(accord(i,j,k))printf(cock=%d,hen=%d,chicken=%d\n,i,j,k);getchar();}intaccord(inti,intj,intk){if(5*i+3*j+k/3==100&&k%3==0&&i+j+k==100)/*显然k必为3的整数倍*/return1;/*符合百千百鸡要求返回1*/elsereturn0;/*不符合百千百鸡要求返回0*/}题目3（爱因斯坦的阶梯问题）爱因斯坦曾出过这样一道有趣的数学题：有一个长阶梯，若每步上2阶，最后剩1阶；若每步上3阶，最后剩2阶；若每步上5阶，最后剩4阶；若每步上6阶，最后剩5阶；只有每步上7阶，最后刚好一阶也不剩。请问该阶梯至少有多少阶。编写一个C程序解决该问题。#includestring.h#includestdio.hvoidmain(){intx=7,i,res,flag=0;for(i=1;i=100;i++)/*将循环次数定为100*/{if((x%2==1)&&(x%3==2)&&(x%5==4)&&(x%6==5))/*如果x符合题目叙述的要求*/{res=x;flag=1;break;/*跳出循环，不再进行比较*/}x=7*(i+1);}if(1==flag)printf(TheresultofEinstein'squestionis%d,res);/*输出答案*/elseprintf(Inthisragecannotgetresult\n);/*在程序限定的范围内找不到答案*/}题目4（寻找水仙花数）：如果一个3位数等于其各位数字的立方和，则称这个数为水仙花数。例如：407=43+03+73，因此407就是一个水仙花数。编写一个程序，找出全部的水仙花数。分析：水仙花数是三位数，只要应用穷举法穷举出100~999闭区间中的每一个数字（正整数），然后对每一个正整数进行判断，看它是不是水仙花数，如果是水仙花数，则将该数输出，如果不是水仙花数，则不输出该数。intIsNarcissus(inta);voidNarcissus();voidmain(){printf(TheNarcissusnumbersbeloware\n);Narcissus();getche();}voidNarcissus(){/*寻找100-999之间的水仙花数*/inti;for(i=100;i=999;i++)if(IsNarcissus(i))printf(%d,i);}intIsNarcissus(inta){/*判断是否是水仙花数，是则返回1，不是返回0*/intsum=0,tmp;tmp=a;while(tmp0){sum=sum+(tmp%10)*(tmp%10)*(tmp%10);tmp=tmp/10;}if(sum==a)return1;/*a是水仙花数*/elsereturn0;/*a不是水仙花数*/}题目5（猴子吃桃问题）有一只猴子第一天摘下若干个桃子，当即吃掉了一半，又多吃了一个；第二天又将剩下的桃子吃掉一半，又多吃一个；按照这样的吃法每天都吃前一天剩下的桃子的一半又一个。到了第十天，就只剩下一个桃子。问题：这只猴子第一天摘了多少个桃子。#includestdio.hmain(){intsum=1,i;/*sum初始值为1，表示第十天的桃子数*/for(i=9