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

《整除15问题-贪心算法算法设计-C.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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。那么只要删除

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

4、nodea[N];intonefast(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){

5、//快速排序if(low0;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=l

6、en;j>0;j--){if(a[j].rest==2&&a[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(l

7、en);}else{for(intj=len;j>0;j--){if(a[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、x==5){flag=i;break;}}if(flag<0){//字符串中没有0且没有5时。cout<<"impossible"<