整除15问题-贪心算法算法设计(共6页).doc

精选优质文档-倾情为你奉上整除15 问题描述问题描述：给定一个只包含数字0.9的字符串，求使用字符串中的某些字符，构建一个能够整除15的最大的整数。注意，字符串中的每个字符只能使用一次。编程任务：求由给定字符串构建的能够整除15的最大整数。Input输入数据为一个只包含数字0.9字符串，字符串的长度为11000。Output将构建出的最大整数输出。如果无法构建出能够整除15的整数，请输出“impossible”Sample Input02041Sample Output4200Hint从原来的字串中选择出最少最小的数扣除以满足整除3和5的要求。把09数分为如下几类：0，3，6 ，9：这四种数不影响2，5，8：除3余21，4，7：除3余1这个题目，考虑能否满足整除5的情况，这比较简单，不详述。只要能满足整除5，进行如下步骤：然后再考虑从原字串中删除最少而且最小的数使得满足整除3。有以下几种情况：情况一： 这个