第一次作业
例2-1 阶乘函数
#include<stdio.h> #include<stdlib.h> int main(){ int n=0; printf("输入数字："); scanf("%d",&n); if(n<0) printf("请输入大于0的数！\n"); int exam=n-(int)n; if(exam!=0) printf("请输入整数！\n") ; printf("%d的阶乘是%d\n",n,factorial(n)); } int factorial(int n){ if(n==0) return 1; else return n*factorial(n-1); }
例2-2Fibonacci数列
#include<stdio.h> #include<stdlib.h> int main(){ int n=0; printf("请输入斐波那契数列的第几项：\n"); scanf("%d",&n); printf("斐波那契数列的第%d项是%d",n,fibonacci(n)); } int fibonacci(int n){ if(n<=2) return 1; else return fibonacci(n-1)+fibonacci(n-2); }
例2-5整数划分问题
#include<stdio.h> #include<stdlib.h> int main(){ int n=0,m=0; printf("请输入想求的正整数的值和其不大于何个正整数的划分\n"); printf("(以空格分界)\n"); scanf("%d %d",&n,&m); printf("正整数%d不大于%d的划分个数为%d个",n,m,q(n,m)); } int q(int n,int m){ if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n<m) return q(n,n); if(n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); }
例2-6Hanoi问题
#include<stdio.h> #include<stdlib.h> int move(int a,int b){ printf("%d->%d\n",a,b); return 0; } void hanoi(int n,int a,int b,int c){ if(n>0){ hanoi(n-1,a,c,b); move(a,b); hanoi(n-1,c,b,a); } } int main(){ printf("此为汉诺塔问题\n"); printf("请输入数字表示想要解决的汉诺塔问题中的总盘子数目\n"); printf("并顺次输入数字以代替起始柱、目标柱和中转柱\n"); int n=0,a=0,b=0,c=0; scanf("%d %d %d %d",&n,&a,&b,&c); printf("此问题的解决步骤为：\n"); hanoi(n,a,b,c); }
第二次作业
二分搜索技术
#include<stdio.h> int BinarySearch(int a[],int x,int n){ //在数组中找到X在其中的位置，并返回下标 int left=0; int right=n-1; while(left<=right-1){ int middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left=middle; else right=middle; } if(x==a[left]) return left; else return-1; //未找到X } int main() { int a[]={0,1,2,3,4,5,6,7,8,9}; int k=BinarySearch(a,6,10); printf("%d",k); }
改进后的二分搜索法(课本p39 2-3)
//改进后的二分搜索法（课本p39 2-3） #include<stdio.h> int BinarySearch(int a[],int x,int l,int r){ int m; int n=r; //存储最后的数组元素下标 if(x<a[0]){ printf("%d不在数组中，它比数组中所有元素都小\n",x); } else if(x>a[n]){ printf("%d不在数组中，它比数组中所有元素都大\n",x); } else{ while(r>=l){ m=(l+r)/2; if(x==a[m]) { return m; } else if(x<a[m]) { r=m-1; } else{ l=m+1; } } printf("%d不在数组中，与它相邻的左右元素下标为%d和%d",x,r,r+1); } return -1; } int main(){ int x,l,r,n; int array[]={2,3,5,7,11,13,17,19,23,29}; l=0; r=9; printf("请输入要查找的整数x:"); scanf("%d",&x); n=BinarySearch(array,x,l,r); if(n!=-1){ printf("%d所在的数组下标是%d\n",x,n); } return 0; }
改进的合并排序
#include<stdio.h> #include<stdlib.h> //基于上课所讲，合并排序改进（非递归算法） void MergeSort(int *list,int length){ int i,left_min,left_max,right_min,right_max,next; int *tmp=(int*)malloc(sizeof(int) * length); for(i=1;i<length;i*=2){ for(left_min=0;left_min<length-i;left_min=right_max){ right_min=left_max=left_min+i; right_max=left_max+i; if(right_max>length) right_max=length; next=0; while(left_min<left_max&&right_min<right_max) tmp[next++]=list[left_min]>list[right_min]?list[right_min++]:list[left_min++]; while(left_min<left_max) list[--right_min]=list[--left_max]; while(next>0) list[--right_min]=tmp[--next]; } } } int main(int argc,char *argv[]){ int i; int array[]={49,38,65,97,76,13,27}; MergeSort(array,7); for(i=0;i<7;i++){ printf("%d ",array[i]); } printf("\n"); return 0; }
习题2-3改写二分搜索算法
#include<stdio.h> #include<stdlib.h> //基于P17页二分搜索技术 int BinarySearch(int a[],int x,int n){ int i=0;//i元素为小于x的最大元素位置 int j=0;//j元素为大于x的最小元素位置 //在a[0]<=a[1]<=...<=a[n-1]中搜索x if(n>0&&x>=a[0]){ int left=0; int i=0; int right=n-1; int j=n-1; while(left<=right){//这里有left=right的判断，可在进入循环体的第一个if处跳出 int middle=(left+right)/2; if(x==a[middle]){ i=middle; j=middle; return middle;//仅有这一个return语句 } if(x>a[middle]){ left=middle+1;//a[middle]的值被略过，因为已经比较了x和a[middle]的大小 i=middle+1; } else{ //x<a[middle] right=middle-1;//a[middle]的值同样被略过，因为已比较了x和a[middle]的大小 j=middle-1; } }//(left<=right)的判断 //该层为为找到的情况 return i;//返回小于x的最大元素位置 }//if(n>0&&x>=a[0])的判断 }//函数体 int main(){ int a[]={0,1,2,3,4,5,6,7,8,9}; float x=0;//这里x不能用整型，用int直接无条件跳转外else判断语句 printf("请输入要在0-9内查找的数字：\n"); scanf("%f",&x); if(x>=0&&x<=9){ float pd=x-(int)x; //这里pd也不能用整型，用int直接无条件跳转内else判断语句 if(pd==0) printf("查找的数字在队列中排第%d位\n",BinarySearch(a,x,10)+1); else{ printf("在0-9队列范围中但未找到该数字！\n"); printf("小于x的最大元素下标为第%d位\n",BinarySearch(a,x,10)); printf("大于x的最小元素下标为第%d位\n",BinarySearch(a,x,10)+1); } } else{ printf("所查找元素未在0-9队列范围内！\n"); if(BinarySearch(a,x,10)==0) printf("大于x的最小元素下标为第%d位\n",BinarySearch(a,x,10)); else printf("大于x的最小元素下标为第9位\n"); } return 0; }
第三次作业
O(1)空间合并算法
//设子数组a[0:k-1]和a[k:n-1]已排好序(0<=k<=n-1) //试设计一个合并这2个子数组为排好序的数组a[0:n-1]的算法 //要求算法在最坏情况下所用的计算时间为O(n)，且只用到O(1)的辅助空间 //循环移位合并算法-向右循环移位合并 //向右循环移位合并算法首先用二分搜索算法在数组段a[k:n-1]中搜索a[0]的插入位置 //即找到位置p使得a[p]<a[0]<=a[p+1],数组段a[0:p]向右循环移位p-k+1个位置， //使a[k-1]移动到a[p]的位置，直至只剩下一个数组段 //此时整个数组已排好序 //对剩余的数组元素重复上述过程，直至只剩下一个数组段，此时整个数组都已排好序 #include<stdio.h> #include<stdlib.h> void mergefor(int a[],int k,int n) {//Merge a[0:k-1] and a[k:n-1] int i=0,j=k; while(i<j&&j<n){//保证左数组a[0:k-1]和右数组a[k:n-1]至少有一个以上的元素 int p=binarySearch(a,a[i],j,n-1); shiftright(a,i,p,p-j+1);//向右循环移位 j=p+1; i+=p-j+2; } } int binarySearch(int a[],int *x,int left,int right) {//二分搜素，用于在数组段a[left:right]中搜索元素x的插入位置 int middle; while(left<=right){ middle=(left+right)/2; if(x==a[middle]) return middle; if(x>a[middle]) left=middle+1; else right=middle-1; } if(x>a[middle]) return middle; else return middle-1; } void shiftright(int a[],int s,int t,int k){//用于将数组段a[s:t]中元素循环右移位k个位置 int i; for(i=0;i<k;i++){ int tmp=a[t]; int j; for(j=t;j>s;j--) a[j]=a[j-1]; a[s]=tmp; } } //上述算法中，数组段a[0:k-1]中元素的移动次数不超过k次，数组段a[k:n-1]中元素最多移动1次。 //因此，算法的元素移动总次数不超过k方+(n-k)次 //算法元素的比较次数不超过klog(n-k)次 //当k<根号n时，算法的计算时间为O(n) //而当k=O(n)时，算法的计算时间为O(n方) //由于数组段循环右移算法只用了O(1)的辅助空间，所以整个算法所用的辅助空间为O(1) int main(){ int a[]={15,34,65,21,34,54}; int i; printf("合并前的数组为:\n"); for (i =0; i < 6; i++)//输入合并前的数组 printf("%d ", a[i]); printf("\n"); mergefor(a,3,6); printf("合并后的数组为:\n"); for (i =0; i < 6; i++)//输出合并后的数组 printf("%d ", a[i]); }
O(1)空间合并算法(另解)
//2-9.O(1)空间合并算法（向右循环换位合并） #include <stdio.h> int binarySearch(int *a,int x,int l,int r) { //改进的二分搜索，搜索a[0]的插入位置，本函数返回p，a[0]在p和p+1之间 int m; while (l<=r){ m=(l+r)/2; if (x==a[m]) return m; if (x>a[m]) { l=m+1; } else{ r=m-1; } } if (x>a[m]) return m; else{ return m-1; } } void shiftRight(int *a,int s,int t,int k) { //将数组a[s...t]向右循环移动k个位置 for (int i=0;i<k;i++) { int temp=a[t]; for (int j=t;j>s;j--) { a[j]=a[j-1]; } a[s]=temp; } } void mergeArray(int *a,int k,int n){ int i=0; int j=k; while (i<j && j<n){ int x=a[i]; int p=binarySearch(a,x,j,n-1); shiftRight(a,i,p,p-j+1); //将数组前半a[0...p]向右循环换位p-k+1个位置，此时a[k-1]移动到a[p]的位置 j=p+1; i+=p-j+2; } } int main(){ int a[]={17,19,23,29,2,3,5,7,11,13}; int i; mergeArray(a,4,10); for(i=0;i<10;i++){ printf("%d ",a[i]); } return 0; }
Hoare版本递归-快速排序
//Hoare版本的单趟排序的基本步骤如下： //1、选出一个key，一般是最左边或是最右边的。 //2、定义一个L和一个R，L从左向右走，R从右向左走。 //（需要注意的是：若选择最左边的数据作为key，则需要R先走； //若选择最右边的数据作为key，则需要L先走）。 //3、在走的过程中，若R遇到小于key的数，则停下，L开始走， //直到L遇到一个大于key的数时，将L和R的内容交换，R再次开始走， //如此进行下去，直到L和R最终相遇，此时将相遇点的内容与key交换即可。 //（选取最左边的值作为key） //经过一次单趟排序，最终使得key左边的数据全部都小于key，key右边的数据全部都大于key。 //然后我们在将key的左序列和右序列再次进行这种单趟排序， //如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时， //便停止操作，因为这种序列可以认为是有序的。 #include<stdio.h> #include<stdlib.h> //快速排序（Hoare版本） void Swap(int* p1, int* p2){//传地址，实现交换 int tmp; tmp = *p1; *p1 = *p2; *p2 = tmp; } void QuickSort1(int* a, int begin, int end)//第一个参数为数组，第二个为数组起始元素下标，第三个为数组末尾元素下标 { if (begin>= end)//当只有一个数据或是序列不存在时，不需要进行操作 return; int left = begin;//L int right = end;//R int keyi = left;//key的下标 while (left < right) { //right先走，找小 while (left < right&&a[right] >= a[keyi])//若元素值大于key，继续向中间移动不进行对换操作 { right--; } //left后走，找大 while (left < right&&a[left] <= a[keyi])//若元素值小于key，继续向中间移动不进行对换操作 { left++; } if (left < right)//若这时满足左标记在右标记左边，则交换left和right的值 { Swap(&a[left], &a[right]); } } int meeti = left;//L和R的相遇点 Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值 QuickSort1(a, begin, meeti - 1);//key的左序列进行此操作 QuickSort1(a, meeti + 1, end);//key的右序列进行此操作 } int main(){ int a[]={15,34,65,21,54,34}; int i; printf("排序前的数组为:\n"); for (i =0; i < 6; i++)//输入排序前的数组 printf("%d ", a[i]); printf("\n"); QuickSort1(a,0,5);//调用快速排序函数 printf("排序后的数组为:\n"); for (i =0; i < 6; i++)//输出排序后的数组 printf("%d ", a[i]); }
Hoare版本非递归-快速排序
#include<stdio.h> #include<stdlib.h> #include "Stack.h" //当我们需要将一个用递归实现的算法改为非递归时，一般需要借用一个数据结构，那就是栈。 //将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本，其实主体思想一致，只是调用的单趟排序的算法不同而已。 //于是我们可以先将Hoare版本、挖坑法和前后指针法的单趟排序单独封装起来。 //然后写一个非递归的快速排序，在函数内部调用单趟排序的函数即可。 //Hoare版本（单趟排序） //快速排序的非递归算法基本思路： //1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。 //2、当栈不为空时，读取栈中的信息（一次读取两个：一个是L，另一个是R）， //然后调用某一版本的单趟排序，排完后获得了key的下标，然后判断key的左序列和右序列是否还需要排序， //若还需要排序，就将相应序列的L和R入栈；若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。 //3、反复执行步骤2，直到栈为空为止。 //初始化 void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; } //销毁 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } //入栈--进栈--压栈 void StackPush(ST* ps, STDataType x) { assert(ps); //判断能否需要扩容 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; ps->a =(STDataType*)realloc(ps->a, newCapacity * sizeof(STDataType)); if (ps->a == NULL) { printf("realloc fail\n"); exit(-1); } ps->capacity = newCapacity; } ps->a[ps->top] = x; ps->top++; } //出栈 void StackPop(ST* ps) { assert(ps); assert(ps->top > 0); --ps->top; } //判断是否为空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //栈的大小 int StackSize(ST* ps) { assert(ps); return ps->top; } //栈顶 STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } void Swap(int* p1, int* p2){//传地址，实现交换 int tmp; tmp = *p1; *p1 = *p2; *p2 = tmp; } int PartSort1(int* a, int left, int right) { int keyi = left;//将key的下标设置为left while (left < right) { //right走，找小 while (left < right&&a[right] >= a[keyi]) { right--; } //left先走，找大 while (left < right&&a[left] <= a[keyi]) { left++; } if (left < right) { Swap(&a[left], &a[right]);//交换left和right的值 } } int meeti = left;//L和R的相遇点 Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值 return meeti;//返回相遇点，即key的当前位置 } //快速排序（非递归实现） void QuickSortNonR(int* a, int begin, int end) { ST st;//创建栈 StackInit(&st);//初始化栈 StackPush(&st, begin);//待排序列的L StackPush(&st, end);//待排序列的R while (!StackEmpty(&st)) { int right = StackTop(&st);//读取R StackPop(&st);//出栈 int left = StackTop(&st);//读取L StackPop(&st);//出栈 //该处调用的是Hoare版本的单趟排序 int keyi = PartSort1(a, left, right); if (left < keyi - 1)//该序列的左序列还需要排序 { StackPush(&st, left);//左序列的L入栈 StackPush(&st, keyi - 1);//左序列的R入栈 } if (keyi + 1 < right)// 该序列的右序列还需要排序 { StackPush(&st, keyi + 1);//右序列的L入栈 StackPush(&st, right);//右序列的R入栈 } } StackDestroy(&st);//销毁栈 } int main(){ int a[]={15,34,65,21,54,34}; int i; printf("排序前的数组为:\n"); for (i =0; i < 6; i++)//输入排序前的数组 printf("%d ", a[i]); printf("\n"); QuickSortNonR(a,0,5);//调用快速排序函数 printf("排序后的数组为:\n"); for (i =0; i < 6; i++)//输出排序后的数组 printf("%d ", a[i]); }
第四次作业
捡拾硬币问题
//现有n个硬币按顺序依次排列在你面前，可以看为一个数组coins[]={5,1,2,10,6,2} //请在此中捡取若干个硬币，使得所取硬币累加值最大，捡取个数不限，但相邻两个硬币不得捡取 //请设计相应算法，并输出累加值 //提示：硬币面值必须是正数，不能有负值。建立数组dp[i]存储选取前i个硬币的累加值 //动态规划算法 #include<stdio.h> #include<stdlib.h> #define N 6 int j=0; int selectcoins(int c[],int n,int s[]) { int i,dp[n]; dp[0]=0;//只有0个硬币时dp自然为0 dp[1]=c[0];//只有1个硬币，dp=c[0] s[j]=1;//因为dp[1]=c[0]，暂时选择了第一个硬币，所以暂时给s[0]赋值为1 for(i=2;i<=n;i++) { //dp[i]的值却决于新添加的硬币与dp[i-2]的和是否大于dp[i-1] if(dp[i-2]+c[i-1]>dp[i-1]) { dp[i]=dp[i-2]+c[i-1]; if(s[j]==i-1) j--;//注意s[j]被赋值后值还可能会变，当满足这种情况时， //s[j]会被再次赋值，即新的值覆盖原来的值 s[++j]=i;//记录选取硬币的序号，j自增 } else { dp[i]=dp[i-1];//这种情况不需要记录新的硬币序号，因为此时dp[i]选取的硬币情况和dp[i-1]一样 } } return dp[--i];//i最后跳出循环时多加了一次1，故还要减一 } int main() { int coins[N]={5,1,2,10,6,2};//初始化硬币数组 int s[N/2+1]={0};//该数组用来存储选择的硬币序号。因为最多选择N/2+1项，所以数组初始大小为N/2+1 int max,i;//max用来存放最大的硬币总金额 max=selectcoins(coins,N,s);//调用selectcoins函数，max为函数的返回值 printf("max=%d\n",max); printf("选取的硬币编号为：");//硬币编号从1开始 for(i=0;i<=j;i++)//输出硬币编号，注意此处是i<=j，而不是i<N，表示后面未被赋值的s[j]不输出 printf("%d ",s[i]); return 0; }
最大子段和(书上解法)
//最大子段和问题（动态规划算法） #include<stdio.h> #include<stdlib.h> int MaxSum(int n,int *a){ int sum=0,b=0; int i; //若数组中只有1个数，则这个数就是最大子段和，将a[0]赋给b，然后判断b是否大于0确定sum //如果数组中有2个数： //如果经过第一轮的赋值，b<0（即a[0]的值小于0），则将a[2]赋值给b，重复第一轮循环的操作 //如果b>0，b=b+a[1]，并进行判断新b是否大于0，如果大于0则将b的值暂时赋值给sum //注意这里没有判断a[1]是否大于0，因为循环进行计算的是a[1:1]、a[1:2]...a[1:n]的最大子段和计算 //如果b<0则不会走到最后 for(i=1;i<=n;i++){ if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; } return sum; } int main(){ int a[]={1,3,4,-5,4,-6,9,-7,5,4}; int n=10; printf("最大子段和为：%d",MaxSum(n,a)); }
最长公共子序列(书上解法)
//最长公共子序列问题 #include<stdio.h> #include<stdlib.h> void LCSLength(int m,int n,char *x,char *y,int **c,int **b){ int i,j; for(i=1;i<=m;i++) c[i][j]=0; for(i=1;i<=n;i++) c[0][i]=0; for(i=1;i<=m;i++){ for(j=1;j<=n;j++){ if(x[i]==y[j]){ c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]){ c[i][j]=c[i][j-1]; b[i][j]=2; } else{ c[i][j]=c[i][j-1]; b[i][j]=3; } } } } void LCS(int i,int j,int *x,int **b){ if(i==0||j==0) return; if(b[i][j]==1){ LCS(i-1,j-1,x,b); printf("%c",x[i]); } else if(b[i][j]==2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); } int main(){ int a[]={a,d,f,g,r}; int b[]={w,r,g,r,f,a,d}; int i=5,j=7; LCS(5,7,) }
最长公共子序列
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 10 int c[MAXSIZE][MAXSIZE]; int flag[MAXSIZE][MAXSIZE]; int a[MAXSIZE] = {1,2,3,2,4,1,2,5}; int b[MAXSIZE] = {2,4,3,1,2,1,5}; //递归找最长公共子序列长度 int find_longest(int asize,int bsize) { int onenum,twonum; if(asize==0 || bsize == 0) { return 0; } else { if(a[asize-1]==b[bsize-1]) { flag[asize][bsize]=1; c[asize][bsize] = c[asize-1][bsize-1]+1; return 1+find_longest(asize-1,bsize-1); } else { onenum = find_longest(asize-1,bsize); twonum = find_longest(asize,bsize-1); if(onenum>twonum) { c[asize][bsize] = onenum; flag[asize][bsize] = 2; return onenum; } else { c[asize][bsize] = twonum; flag[asize][bsize] = 3; return twonum; } } } } //动态规划寻找最长公共子序列长度 void dynamic_longest(int asize,int bsize) { int i,j; for(i=1;i<=asize;i++) { for(j=1;j<=bsize;j++) { if(a[i-1]==b[j-1]) { c[i][j] = c[i-1][j-1]+1; flag[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j] = c[i-1][j]; flag[i][j] = 2; } else { c[i][j] = c[i][j-1]; flag[i][j]=3; } } } } void find_more(int i,int j) { if(i==0 || j==0) { return ; } if(flag[i][j] ==1) { find_more(i-1,j-1); printf("%d",a[i-1]); } else if(flag[i][j]==2) { find_more(i-1,j); } else { find_more(i,j-1); } } int main() { int i,j; int count=0; for(i=0;i<=MAXSIZE;i++) { for(j=0;j<=MAXSIZE;j++) { c[i][j] = 0; flag[i][j] = 0; } } //count = find_longest(8,7); //printf("count=%d\n",count); dynamic_longest(8,7); printf("count = %d\n",c[8][7]); printf("--------------------------\n"); for(i=0;i<=MAXSIZE;i++) { for(j=0;j<=MAXSIZE;j++) { printf("%5d",c[i][j]); } printf("\n"); } printf("----------------\n"); for(i=0;i<=MAXSIZE;i++) { for(j=0;j<=MAXSIZE;j++) { printf("%5d",flag[i][j]); } printf("\n"); } find_more(8,7); }
最长公共子序列(另解)
//解决LCS问题同样是动态规划思想。LCS问题的结果同时受到两个字符串的影响，所以状态需要用二维表示。 //我们以f[i][j]表示a中从1到i、b中从1到j范围内的最长公共子序列的长度，那么考虑对于状态f[i][j]可以由哪些状态转移过来， //在每一阶段我们能做出的决策有以下几种： //若a[i]=b[j]，则a[i]、b[j]同时属于公共子序列： //f[i][j]由f[i-1][j-1]转移而来，f[i][j]=f[i-1][j-1]+1； //若a[i]!=b[j]，则a[i]、b[j]不能同时属于公共子序列： //①a[i]不属于公共子序列：f[i][j]由f[i-1][j]转移而来，f[i][j]=f[i-1][j]； //②b[j]不属于公共子序列：f[i][j]由f[i][j-1]转移而来，f[i][j]=f[i][j-1]； //③a[i]、b[j]都不属于公共子序列：f[i][j]=f[i-1][j-1]，这种决策可以舍去， //因为只要f[i][j]发生了更新，都是由f[i-1][j-1]+1得到，其一定>f[i-1][j-1]； //该情形下舍去最后一项决策后，f[i][j]=max(f[i-1][j], f[i][j-1]); int Lcs(int a[], int b[]) { int f[7][10]={0}; int i=0,j=0; for(i=1;i<=6;++i) { for(j=1;j<=9;++j) { if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;//满足第3中情况，f[i][j]=f[i-1][j-1]+1 else//其他情况，进行判断 f[i][j]=Max(f[i-1][j], f[i][j-1]); } } return f[6][9]; } int Max(int a,int b){ if(a>b) return a; else return b; } int main(){ int a[]={1,3,4,5,8,7}; int b[]={3,4,7,2,3,1,5,8,7}; printf("最长公共子序列为:%d",Lcs(a,b)); }
