算法设计与分析所有源码.docVIP

一、递归与分治 穷举n位二进制数 描述： 输入一个小于20的正整数n，要求按从小到大的顺序输出所有的n位二进制数，每个数占一行。 输入： 输入一个小于20的正整数n。 输出： 按从小到大的顺序输出所有的n位二进制数，每个数占一行。 输入样例： 3 输出样例： 000001010011100101110111 算法： #include stdio.h int n,a[20]; void Search(int m) { int i; if (m==n) { for(i=0;in;i++) printf(%d,a[i]); printf(\n); } else { a[m]=0;Search(m+1); a[m]=1;Search(m+1); } } int main() { int m=0; scanf(%d,n); Search(m); return 0; } 穷举所有排列 描述： 输入一个小于10的正整数n，按把每个元素都交换到最前面一次的方法，输出前n个小写字母的所有排列。 输入： 输入一个小于10的正整数n。 输出： 按把每个元素都交换到最前面一次的方法，输出前n个小写字母的所有排列。 输入样例： 3 输出样例： abcacbbacbcacbacab 算法： #include stdio.h void sort(int a,int b,char m[]) { int i; char temp; if(a==b-1) { for(i=0;ib-1;i++) printf(%c,m[i]); printf(%c\n,m[b-1]); } else { for(i=a;ib;i++) { temp=m[a]; m[a]=m[i]; m[i]=temp; sort(a+1,b,m); temp=m[a]; m[a]=m[i]; m[i]=temp; } } } int main() { int n,i; char a[100]; scanf(%d,n); for(i=0;in;i++) a[i]=97+i; a[n]=\0; sort(0,n,a); return 0; } 二分查找 描述： 给定一个单调递增的整数序列，问某个整数是否在序列中。 输入： 第一行为一个整数n，表示序列中整数的个数；第二行为n（n不超过10000）个整数；第三行为一个整数m（m不超过50000），表示查询的个数；接下来m行每行一个整数k。 输出： 每个查询的输出占一行，如果k在序列中，输出Yes，否则输出No。 输入样例： 51 3 4 7 113369 输出样例： YesNoNo 算法： #include stdio.h #include stdlib.h int NBinarySearch(int n,int s[],int x); void main() { int n; int i; int s[10000]; int m; int k; int l; int j[50000]; int h; scanf(%d,n); for(i=0;in;i++) { scanf(%d,s[i]); } scanf(%d,m); for (k=0;km;k++) { scanf(%d,j[k]); } for (k=0;km;k++) { l=j[k]; h=NBinarySearch(n,s,l); if(h==-1) printf(No\n); else printf(Yes\n); } } int NBinarySearch(int n,int s[],int x) { int low=0,high=n-1; while (low=high) { int mid=(low+high)/2; if(x==s[mid]) return mid; else if(xs[mid]) low=mid+1; else high=mid-1; }