2019獨角獸企業重金招聘Python工程師標準>>>

一個正整數是否能被三個整數 a,b,c的非負整數線性組合所表示？

#include <stdio.h>int IsPossibleResult(int n,int a,int b,int c) {if(n==0) return 1;if(n<0) return 0;return IsPossibleResult(n-a,a,b,c)||IsPossibleResult(n-b,a,b,c)||IsPossibleResult(n-c,a,b,c); } int main(void) { printf("%d",IsPossibleResult(16,6,7,19));return 0; }

非遞歸版本：

#include <stdio.h>int IsPossibleResult_non_recur(int n,int a,int b,int c) {int na=0,nb=0,nc=0;int resultNum=0;for(na=0;na<=n;na++){ if(n-a*na<0)break;for(nb=0;nb<=n;nb++){if(n-a*na-b*nb<0)break;for(nc=0;nc<=n;nc++){if(n-a*na-b*nb-c*nc<0)break;if(n-a*na-b*nb-c*nc==0){printf("%d*%d+%d*%d+%d*%d=%d\n",na,a,nb,b,nc,c,n);resultNum++;break;}}}}return resultNum; }int main(void) { printf("%d",IsPossibleResult_non_recur(16,3,4,2));return 0; }

動態規劃版本：

#include <stdio.h> #include <stdlib.h>int IsPossibleResult_dp(int n,int a,int b,int c) {int *data=(int*)malloc(2*n*sizeof(int));data[0]=1;int i=0;while(i<n){if(data[i]==1){data[i+a]=1;data[i+b]=1;data[i+c]=1;}i++;}int res=data[n];free(data);return res;}int main(void) { printf("%d\n",IsPossibleResult_dp(16,3,4,2));return 0; }

三者的比較?

#include <stdio.h>int count_r,count,dp_count; int IsPossibleResult(int n,int a,int b,int c) {count_r++;if(n==0) return 1;if(n<0) return 0;return IsPossibleResult(n-a,a,b,c)||IsPossibleResult(n-b,a,b,c)||IsPossibleResult(n-c,a,b,c); }int IsPossibleResult_non_recur(int n,int a,int b,int c) {int na=0,nb=0,nc=0;int resultNum=0;for(na=0;na<=n;na++){if(n-a*na<0)break;for(nb=0;nb<=n;nb++){if(n-a*na-b*nb<0)break;for(nc=0;nc<=n;nc++){count++;if(n-a*na-b*nb-c*nc<0)break;if(n-a*na-b*nb-c*nc==0){//printf("%d*%d+%d*%d+%d*%d=%d\n",na,a,nb,b,nc,c,n);resultNum++;break;}}}}return resultNum; }int IsPossibleResult_dp(int n,int a,int b,int c) {int data[100000];data[0]=1;int i=0;while(i<n){dp_count++;if(data[i]==1){data[i+a]=1;data[i+b]=1;data[i+c]=1;}i++;}return data[n];}int main(void) { count=count_r=0;printf("%d\n",IsPossibleResult_non_recur(16,3,4,2));printf("%d\n",IsPossibleResult(16,3,4,2));printf("%d\n",IsPossibleResult_dp(16,3,4,2));printf("R:%d,NR:%d,DP:%d\n",count_r,count,dp_count);return 0; }

?

轉載于:https://my.oschina.net/betayuan/blog/1549663

總結

以上是生活随笔為你收集整理的整数问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。