整除15问题-贪心算法算法设计-C

1、精选优质文档-倾情为你奉上整除15 问题描述问题描述：给定一个只包含数字0.9的字符串，求使用字符串中的某些字符，构建一个能够整除15的最大的整数。注意，字符串中的每个字符只能使用一次。编程任务：求由给定字符串构建的能够整除15的最大整数。Input输入数据为一个只包含数字0.9字符串，字符串的长度为11000。Output将构建出的最大整数输出。如果无法构建出能够整除15的整数，请输出“impossible”Sample Input02041Sample Output4200Hint从原来的字串中选择出最少最小的数扣除以满足整除3和5的要求。把09数分为如下几类：0，3，6 ，9：这四种数不

2、影响2，5，8：除3余21，4，7：除3余1这个题目，考虑能否满足整除5的情况，这比较简单，不详述。只要能满足整除5，进行如下步骤：然后再考虑从原字串中删除最少而且最小的数使得满足整除3。有以下几种情况：情况一： 这个数上各位数字和除3余0。不用删除操作。情况二： 给定的数上各位数字和除3余1。那么只要删除余1的那一类数中最小的一个。如果没有数串 中没有余1的数，就删除两个余2的数。情况三： 给定的数上各位数字和除3余2。那么只要删除余2的那一类数中最小的一个。如果没有数串 中没有余2的数，就删除两个最小的余1的数。最后，剩余的数串以最大的并且以满足整除5的要求输出。在0存在的时候，就按计数的

3、顺序输出即可。如果在数串中没有0，则必须有个5放在个位。代码实现：#include"iostream"#include"cstring"#include"cstdio"using namespace std;#define N 10typedef struct int x; bool bo; /记住此数是否已用 int rest; /记住该数除3的余数node;node aN;int onefast(int low,int high) /一次快排 int key = alow.x; a0.x = key; while(low<h

4、igh) while(low<high&&ahigh.x<=key) -high; alow.x = ahigh.x; while(low<high&&alow.x>=key) +low; ahigh.x = alow.x; ahigh.x = a0.x; return high;void fsort(int low,int high) /快速排序 if(low<high) int q = onefast(low,high); fsort(low,q-1); fsort(q+1,high); void find(int len);v

5、oid del(int t,int len) int flag = -1; if(t = 1) for(int i = len;i>0;i-) if(ai.rest = 1&&ai.bo = false) ai.bo = true; flag = i; break; if(flag>0) find(len); else for(int j = len;j>0;j-) if(aj.rest = 2&&aj.bo = false) +flag; aj.bo = true; if(flag = 1) break; if(flag = 1) find(

6、len); else if(flag < 1) cout<<"impossible"<<endl; else for(int i = len;i>0;i-) if(ai.rest = 2&&ai.bo = false) ai.bo = true; flag = i; break; if(flag>0) find(len); else for(int j = len;j>0;j-) if(aj.rest = 1&&aj.bo = false) +flag; aj.bo = true; if(fla

7、g = 1) break; if(flag = 1) find(len); else if(flag < 1) cout<<"impossible"<<endl; void find(int len) int flag = -2; if(alen.x!=0) /字符串中没有 0 时 for(int i = 1;i<len;i+) if(ai.x=5) flag = i; break; if(flag<0) /字符串中没有 0 且没有 5 时。 cout<<"impossible"<<end

8、l; else /字符串没有 0 ，但有 5 时。 aflag.bo = true; int sum = 0; for(int j = 1;j<=len;j+) if(aj.bo = false) sum += aj.x; int t = (sum + 5)%3; if( t= 0)/找到 for(int k = 1;k<=len;k+) if(ak.bo = false) cout<<ak.x; cout<<5; cout<<endl; else / 此数不符合时 del(t,len); else /字符串中有 0 时 /alen.bo = true; int sum = 0; for(int j = 1;j<=len;j+) if(aj.bo = false) sum += aj.x; int t = sum%3; if( t= 0)/找到 for(int k = 1;k<=len;k+) if(ak.bo = false) cout<<ak.x; cout<<endl; else / 此数不符合时 del(t,len); int main() char sN; cin>>s; int len = strlen(s); for(int i = 1;i<