動態(tài)規(guī)劃算法實驗報告-文庫吧
2025-07-07 00:25 本頁面
【正文】 } else { c[i][j] = c[i][j1]。 flag[i][j] = 1。 } } return c[m][n]。}//求出最長公共子序列char* getLCS(char *x, char *y,int len,char *lcs){ int i = strlen(x)。 int j = strlen(y)。 while(iamp。amp。j) { if(flag[i][j]==0) { lcs[len] = x[i1]。 i。 j。 } else if(flag[i][j]==1) i。 else j。 } return lcs。}int main(){ int i。 cout請輸入字符串x：endl。 cinstr1。 cout請輸入字符串y：endl。 cinstr2。 int lcsLen = LCSLength(str1,str2)。 cout最長公共子序列長度：lcsLenendl。 char *p = getLCS(str1,str2,lcsLen,lcs)。 cout最長公共子序列為：。 for(i=0。ilcsLen。i++) coutlcs[i] 。 return 0。}運行結(jié)果最大子段和//分治法求最大子段和includeiostreamusing namespace std。int MaxSubSum(int *a,int left,int right){ int sum=0。 if(left==right) sum=a[left]0?a[left]:0。 else { int center = (left+right)/2。 //最大子段和在左邊 int leftsum=MaxSubSum(a,left,center)。 //最大子段和在右邊 int rightsum=MaxSubSum(a,center+1,right)。 //最大子段和在中間 int s1=0。 int lefts=0。 for(int i=center。i=left。i) { lefts+=a[i]。 if(leftss1) s1=lefts。 } int s2=0。 int rights=0。 for(int i=center+1。i=right。i++) { rights+=a[i]。 if(rightss2) s2=rights。 } sum=s1+s2。//前后子段和相加 //判斷最大子段和 if(sumleftsum)sum=leftsum。 if(sumrightsum) sum=rightsum。 } return sum。}int MaxSum(int *a,int n){ return MaxSubSum(a,1,n1)。}int main(){ int a[8]={2,3,5,4,1,7,1,5}。 cout最大子段和為：MaxSum(a,8)。 return 0。}//動態(tài)規(guī)劃法includeiostreamusing namespace std。int MaxSum(int *a,int n){ int sum=0,b=0。 for(int i=1。in。i++)//此處不能=n， { if(b0) b+=a[i]。 else b=a[i]。 if(bsum) sum=b。 } return sum。}int main(){ int a[8]={2,3,5,4,1,7,1,5}。 cout最大子段和為：MaxSum(a,8)。 return 0。}運行結(jié)果 凸多邊形最優(yōu)三角剖分includeiostreamincludecmathincludecstdlibdefine N 50using namespace std。struct point{ int x。 int y。}。int distance(point X, point Y)//兩點距離{ int dis = ()*() + ()*()。 return (int)sqrt(dis)。}int w(point a, point b, point c)//權(quán)值{ return distance(a,b) + distance(b,c) + distance(
公司管理相關(guān)推薦
鄂ICP備17016276號-1