常用的算法思想2.doc

常用的算法思想 1. 穷举法思想 基本概念：穷举法（Exhaustive Attack method）,它是一种最为直接，最容易实现，同时又最为耗时的一种解决问题的算法思想。穷举法算法的基本思想是：在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中得到问题的答案。 【实例\_1】寻找[1,100]之间的素数(code\_1.cpp) #include stdafx.h #include stdio.h #include math.h int Is_Prime(int i){ if (i==1) return 0; if (i==2) return 1; if(i2 i%2==0) return 0; int j; int t=0; for(j=3;j=sqrt(i);j+=2) if(i%j==0) {t=1;return 0;} if(t==0) return 1; } void GetPrime(int low,int high){ /*寻找[low,high]之间的素数*/ int i; for(i=low;i=high;i++) if(Is_Prime(i)) printf( %d ,i); printf(\n); } int main(int argc, char* argv[]) { int low,high; printf(\n请输入寻找的上、下区间\n); scanf(%d %d,low,high); printf(\n列出所有的素数\n); GetPrime(low,high); getchar(); return 0; } 【实例\_2】TOM 的借书方案：TOM共有5本书，要借给A、B、C 3位同学，每人只能借1本书，则TOM可以有多少种不同的借书方案。借书方案的解集： #include stdafx.h #include stdio.h int main(int argc, char* argv[]) { int i,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!=ki!=k) {printf( (%d,%d,%d) ,i,j,k);} printf(\nHello World!\n); return 0; } 2. 递归与分治思想 基本概念：在解决一些比较复杂的问题，特别是解决一些规模较大的问题时，常常将问题分解。具体来说，就是将一个规模较大的问题分割成规模较小的同类问题，然后将这些小的子问题逐个加以解决，最终也就将整个大的问题解决。 递归的思想也是一种常见的算法思想。所谓递归算法，就是一种直接或间接地调用原算法本身的一种算法。在实际的算法设计中，递归与分治如同一对兄，经常结合在一起使用。这是因为，由分治方法产生的子问题往往都是原问题的更小规模。反复使用分治的手段，可使子问题与原问题类型一致，但规模不断缩小，最终使子问题比较容易求解。既然子问题与原问题的类型一致，这 就具有了所谓的递归，因此可以使用递归的方法用解决原问题的算法去解决同类的子问题。 【实例_3】计算的阶乘10!=9!*10,9!=8!*9,---2!=1!*2,1!=0!*1 其实阶乘的数学定义可以用递归函数来简单地描述： 这样的函数称为递归函数，因为该函数本身直接或间接地调用了该函数本身。基于阶乘的递归函数的描述。就不难设计出计算出的递归算法 int factorial(n){ if(n==0) return 1; else return n* factorial(n-1) } 【实例_4】将一个正整数n表示成一系列的正整数之和： 被称做正整数的一个划分，不同的划分的个数称为该正整数n的划分数。根据正整数划分的定义，可以总结以下规律：设标记表示正整数n的所有不同划分，最大加数不大于的划分个数，可以得出计算的递归函数式： 程序如下： #include stdio.h int P(int n,int m) { if(m==1 || n == 1) return 1; if(mn) return P(n,n); if(m==n) return 1+P(n,m-1); return P(n,m-1)+P(n-m,m); } main() { int n,s; printf(Pleas