整除15问题 贪心算法算法设计 c

《整除15问题 贪心算法算法设计 c》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、整除15问题描述问题描述：给定一个只包含数字[0..9]的字符串，求使用字符串中的某些字符，构建一个能够整除15的最大的整数。注意，字符串中的每个字符只能使用一次。编程任务：求由给定字符串构建的能够整除15的最大整数。Input输入数据为一个只包含数字[0..9]字符串，字符串的长度为1~1000。Output将构建出的最大整数输出。如果无法构建出能够整除15的整数，请输出“impossible”SampleInput02041SampleOutput4200Hint从原来的字串中选择出最少最小的数扣除以满足整除

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

3、个。如果没有数串中没有余2的数，就删除两个最小的余1的数。最后，剩余的数串以最大的并且以满足整除5的要求输出。在0存在的时候，就按计数的顺序输出即可。如果在数串中没有0，则必须有个5放在个位。代码实现：#include"iostream"#include"cstring"#include"cstdio"usingnamespacestd;#defineN10typedefstruct{intx;boolbo;//记住此数是否已用intrest;//记住该数除3的余数}node;nodea[N];intonefas

4、t(intlow,inthigh){//一次快排intkey=a[low].x;a[0].x=key;while(low=key)++low;a[high].x=a[low].x;}a[high].x=a[0].x;returnhigh;}voidfsort(intlow,inthigh){//快速排序if(low

5、onefast(low,high);fsort(low,q-1);fsort(q+1,high);}}voidfind(intlen);voiddel(intt,intlen){intflag=-1;if(t==1){for(inti=len;i>0;i--){if(a[i].rest==1&&a[i].bo==false){a[i].bo=true;flag=i;break;}}if(flag>0){find(len);}else{for(intj=len;j>0;j--){if(a[j].rest==2&&a

6、[j].bo==false){++flag;a[j].bo=true;if(flag==1)break;}}if(flag==1)find(len);elseif(flag<1){cout<<"impossible"<0;i--){if(a[i].rest==2&&a[i].bo==false){a[i].bo=true;flag=i;break;}}if(flag>0){find(len);}else{for(intj=len;j>0;j--){if(a

7、[j].rest==1&&a[j].bo==false){++flag;a[j].bo=true;if(flag==1)break;}}if(flag==1)find(len);elseif(flag<1){cout<<"impossible"<

8、没有5时。cout<<"impossible"<