codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include<stdio.h> #include<stdlib.h> #include<time.h> long F[10000]={0}; long count1=0,count2=0,count3=0,count4=0; void CoinRow(long *c,long n)//币值最大化的动态规划 { F[0]=0; F[1]=c[1]; for(long i=2;i<=n;i++) { F[i]=(c[i]+F[i-2])>F[i-1]?(c[i]+F[i-2]):F[i-1]; count1++; } } long CoinRow1(long *c,long n) //币值最大化的递归算法 { count2++; long temp1,temp2; if(n==0) F[n]=0; else if(n==1) F[n]=c[1]; else { temp1=c[n]+CoinRow1(c,n-2); temp2=CoinRow1(c,n-1); F[n]=temp1>temp2?temp1:temp2; } return F[n]; } void yesangeMaking(long *D,long n,long m) //找零问题的动态规划 { long temp; long j; F[0]=0; for(long i=1;i<=n;i++) { temp=100000; j=1; while(j<=m&&i>=D[j]) { count3++; temp=F[i-D[j]]<temp?F[i-D[j]]:temp; j=j+1; } F[i]=temp+1; } } long yesangeMakingDG(long *D,long n,long m) { long j,s,temp; if(n==0) F[n]=0; else { temp=1000000; j=1; while(j<=m&&n>=D[j]) { (count4)++; s=yesangeMakingDG(D,n-D[j],m); temp=s<temp?s:temp; j+=1; } F[n]=temp+1; } return F[n]; } void no() { clock_t start; clock_t finish; double totaltime1,totaltime2; long i,n; long c[10000]={0}; printf("请输入硬币的总个数:"); scanf("%ld",&n); fflush(stdin); for(i=1;i<=n;i++) c[i]=c[i-1]+rand()%10; printf("币值最大化动态规划\n"); printf("硬币个数 运行次数 运行时间\n"); for(i=1;i<=n;i++) { count1=0; start=clock(); CoinRow(c,i); //动态规划 finish=clock(); totaltime1=(double)(finish-start)/CLOCKS_PER_SEC; printf(" %d\t\t%d\t\t%10lf\n",i,count1,totaltime1); } printf("币值最大化递归算法\n"); printf("硬币个数 运行次数 运行时间\n"); for(i=1;i<=n;i++) { count2=0; start=clock(); CoinRow1(c,i); finish=clock(); totaltime2=(double)(finish-start)/CLOCKS_PER_SEC; printf(" %d\t\t%d\t\t%10lf\n",i,count2,totaltime2); } } void yes() { long c[10000]={0}; c[1]=1; long n,m,i; clock_t start; clock_t finish; double totaltime3,totaltime4; srand(time(NULL)); printf("请输入要找零的金额:"); scanf("%ld",&n); printf("请输入要硬币的总个数:"); scanf("%ld",&m); fflush(stdin); for(i=2;i<=m;i++) c[i]=c[i-1]+rand()%2+2; printf("找零问题动态规划\n"); printf("硬币个数 运行次数 运行时间\n"); for(i=1;i<=m;i++) { count3=0; start=clock(); yesangeMaking(c,i,n); finish=clock(); totaltime3=(double)(finish-start)/CLOCKS_PER_SEC; printf(" %d\t\t%d\t\t%10lf\n",i,count3,totaltime3); } printf("找零问题递归算法\n"); printf("硬币个数 运行次数 运行时间\n"); for(i=1;i<=m;i++) { count4=0; start=clock(); yesangeMakingDG(c,i,n); finish=clock(); totaltime4=(double)(finish-start)/CLOCKS_PER_SEC; printf(" %d\t\t%d\t\t%10lf\n",i,count4,totaltime4); } } void main() { // no(); yes(); }
Private
[
?
]
Run code
Submit