命题：输入一组数，由它组合出一个最大的可以被15整除。
思路：能被15整除的数，必然能被5和3整除，则必须要满足整除5和整除3的特征。
用贪心法可以组合出这些数中最大的一个。（代码如下）如果组合不出来，则输出impossible。否则输出这个数。
// Divide3.cpp : 定义控制台应用程序的入口点。
//
#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;
#define MAX 1000
#define IMPOSSIBLE "impossible"
char str[MAX];
// 0的ASCII码是48，9的ASCII码是57,因此计数器数组的大小取为58，以利于快速取值
int counter[58];
// 附加检验代码，本程序中可不执行
bool checkInput(char *s);
// 整理所有数字，并分别统计'0'-'9'各个数的计算结果
void collect(char *s);
// 判断是否涵盖'5'或者'0'
// 证明：能被整除的数末尾必须是或者
bool canDivideBy5or0();
// 判断一个字符是不是'3' '6' '9'中的一个
inline bool belongsTo369(char c);
// 贪心法将数字转换成可以被整除的数，并输出结果
bool connect();
int main( )
{
freopen("input.txt", "r", stdin); //文件输入输出
freopen("output.txt", "w", stdout);
scanf("%s", str);
// 为了加快速度略去字符串检查，假设所有输入都是合法的
//if(!checkInput(str))
// printf("err");
collect(str);
// 输出计数器
//int i;
//for(i='0'; i<='9'; ++i)
//{
// printf("%c:%d\n", i,counter[i]);
//}
if(!canDivideBy5or0())//假如canDivideBy5or0()=false，即不能整除，则输出impossible
{
//printf("Can not be divided by 5 or 0!\n");
printf(IMPOSSIBLE);
return 0;
}
if(!connect())//假如connect()=false，即无法把字符数组连接起来，则输出impossible
printf(IMPOSSIBLE);
//printf("%s", str);
return 0;
}
void collect(char *s)//分别统计字符串中'0'-'9'的出现个数
{
int i = 0; //i表示字符串的第i个字符
while(s[i] != '\0' && i < MAX)
{
++counter[s[i]];
++i;
}
}
bool canDivideBy5or0()//如果字符串中出现过或，即能被整除，则输出true，否则输出false
{
if(counter['5'] > 0)
return true;
if(counter['0'] > 0)
return true;
return false;
}
bool belongsTo369(char c)//判断一个字符是不是'3' '6' '9'中的一个，如果是，则输出true，否则输出false
{
if(c == '3' || c == '6' || c == '9')
return true;
return false;
}
bool connect()//把整个字符数组连接起来,并输出
{
bool canConnect = true;// canConnect是一个标志，表示是否可以开始连接了？
int i;
int sum = 0;
// 从最大的数开始递减到，并将所有不是、、的数加起来，将结果存放在sum中
for(i='9'; i>'0'; --i)
{
if(counter[i] == 0 || belongsTo369(i))//如果某个数字没有的话，比如一个序列里没有'9'就跳过，或者如果有数字，但是它属于，，，那也跳过。然后把剩下的数字都加起来
continue;
sum += (counter[i] * (i - '0'));//(i - '0')因为都是字符'1','2'，…所以，要-'0'得到它的数值，，…，然后乘以它的数量
}
int mod = sum % 3;
if( mod == 0 )
canConnect = true;
else if(mod == 1)
{
canConnect = false;
for(i = '1'; i <= '9'; i+=3)
{
if(counter[i] != 0)
{
--counter[i];
canConnect = true;
break;
}
//else
// canConnect = false;
}
}
else if(mod == 2)
{
canConnect = false;
for(i = '2'; i <= '8'; i+=3)
{
if(counter[i] != 0)
{
--counter[i];
if(i=='5')
{
if(counter['5']==0 && counter['0'] == 0)
{
canConnect = false;
break;
}
}
canConnect = true;
break;
}
//else
// canConnect = false;
}
}
if(!canConnect) //如果canConnect=false，返回false
return false;
//以下为输出。此时计数器里面的数值已经是最终方案了,根据下面的规律，用贪心法生成输出结果
// 贪心法：
// 要凑齐一个最大的整数，那么它必须满足两个条件
// 1、位数最多，比如和比？
// 2、高位的数字尽量地大，比如和相比
// 因此：应该先满足位数最多，因为结果必然可以得到一个整除的数（定理）？
// 则只需要满足高位数字大即可，而既然是'9'到'0'，因此依次从大到小输出即可
// 并且为了结果能乘除，所以最后一位必须为或者
bool endWith5 = false;//endWith5是一个标记，如果为true表示以结尾，如果为false表示以结尾
int j = 0;
int r = 0;
if(counter['0'] == 0)//如果输入的字符串中没有，则必然要以结尾,这部分有错，例如：输出
{
endWith5 = true;
--counter['5'];//减掉的目的是为了保留一个，留在末尾才输出
}
for(i = '9'; i >= '0'; --i)//计算器中的数字是'9'到'0'，为了得到结果是最大的数，依次从大到小输出数字即可
{
for(j = counter[i]; j > 0; --j)
{
//printf("%c", i);
str[r++] = i;
}
}
if(endWith5)//如果以结尾，则在末尾输出一个
//printf("5");
str[r++] = '5';
str[r] = '\0';
printf("%s", str);
return true;
}
/*
关于整除的理论基础：http://www.cbe21.com/subject/maths/printer.phparticle_id=818
“能被３整除的数的特征”教学实录与评析
金中
一、复习旧知
师：前面同学们学习了能被、整除的数的特征，下面老师就来检查一下（板书出三个数字：、、），你能用、、这三个数字组成能被整除的三位数吗？
学生根据教师要求组数，教师板书出学生组数的情况：、。
师：为什么这样组数？
生：因为个位上是、、、、的数能被整除……
师：同样用这三个数字，你们能组成被整除的数吗？
教师根据学生组数的情况板书出：、。
师：你们是怎样想的？
生：因为个位上是或的数都能被整除。
［评］铺垫复习不落俗套，采用组数的方法，既复习了能被、整除的数的特征，又激发了学生学习的兴趣。
二、讲授新课
（一）设置教学“陷阱”。
师：如果仍用这三个数字，你能否组成能被整除的数呢？试一试。
教师根据学生组数的情况板书出：、。
师：这两个数能被整除吗？
学生试除验证这两个数能被整除。
师：从这两个能被整除的数，你想到了什么？能被整除的数有什么特征？
生：个位上是的倍数的数能被整除。（引导学生提出假设①）
（二）制造认知矛盾。
师：刚才同学们是从个位上去寻找能被整除的数的“特征”的，那么个位上是的倍数的数就一定能被整除吗？
教师紧接着举出、、等数让学生试除判断，由此引导学生推翻假设①。
师：这几个数个位上都是的倍数，有的数能被整除，而有的数却不能被整除。我们能从个位上找出能被3整除的数的特征吗？
生：不能。
（三）设疑问激兴趣。
师：请同学们仍用、、这三个数字，任意组成一个三位数，看看它们能不能被整除。
学生用、、这三个数字任意组成一个三位数，通过试除发现：所组成的三位数都能被整除。
师：能被整除的数有没有规律可循呢？下面我们一起来学习“能被整除的数的特征。”（板书课题）
［评］教师通过设置教学“陷阱”，引导学生提出能被整除的数的特征的假设，到推翻假设，引发认知矛盾，并再次创设学生探究的问题情境，不仅有效地避免了“能被、整除的数的特征”思维定势的影响，而且进一步地激发了学生的求知欲望。
（四）引导探究新知。
师：观察用、、任意组成的能被整除的三位数，虽然它们的大小不相同，但它们有什么共同点？
引导学生发现：组成的三位数的三个数字相同，所不同的是这三个数字排列的顺序不同。
师：三个数字相同，那它们的什么也相同？
生：它们的和也相同。
师：和是多少？
生：这三个数字的和是。
师：这三个数字的和与有什么关系？
生：是的倍数。
师：也就是说它们的和能被什么整除？
生：它们的和能被整除。
师：由此你想到了什么？
学生提出假设②：一个数各位上的数的和能被整除，这个数就能被整除。
师：通过同学们的观察，有的同学提出了能被整除的数特征的假设，但是同学们观察的仅是几个特殊的数，是否能被整除的数都有这样的特征呢？要说明同学们的假设是正确的，我们需要怎么做？
生：进行验证。
师：怎样进行验证呢？
引导学生任意举一些能被整除的数，看看各位上的数的和能否被整除。（为了便于计算和研究，可让学生任意举出以内的自然数，然后乘以。）
根据学生举出的数，教师完成如下的板书，并让学生计算出各个数各位上的数的和进行验证。
附图{图}
师：通过上面的验证，说明同学们提出的能被整除的数特征的假设怎样？
生：是正确的。
师：请同学们翻开书，看看书上是怎样概括出能被整除的数的特征的。引导学生阅读教材第页的有关内容。
师：什么叫各位？它与个位有什么不同？根据这个特征，怎样判断一个数能不能被整除？
组织学生讨论，加深能被整除的数的特征的认识，掌握判断一个数能否被整除的方法。
［评］在学生观察的基础上，引导他们提出能被整除的数特征的假设，并验证假设是否正确，不仅充分调动了学生学习的主动性、积极性，而且渗透了从特殊到一般的数学思想方法，指导了学法。
三、课堂练习
（一）判断下面各数能否被整除，并说明理由。
54 83 114 262 837
（二）数能被整除吗？你是怎样判断的？有没有更简捷的判断方法？
引导学生发现：、、这三个数字本身就能被整除，因此它们的和自然能被整除。判断时用不着把它们相加。
（三）数能被整除吗？（将中插入一些数字改编而成。）
引导学生概括出迅速判断一个数能否被整除的方法：（）先去掉这个数各位上是、、的数；（）把余下数位上的数相加，并去掉相加过程中凑成、、的数；（）看剩下数位上的数能否被整除。
（四）运用上述判断一个数能否被整除的方法，迅速判断、、能否被整除。
（五）在下面每个数的□里填上一个数字，使这个数有约数。它们各有几种不同的填法？
□4□□56□
引导学生掌握科学的填数方法：（）先看已知数位上的数字的和是多少；（）如果已知数位上的数字和是的倍数，那么未知数位的□里最小填“”，要填的其它数字可依次加上；如果已知数位上的数字和不是的倍数，那么未知数位的里可先填一个最小的数，使它能与已知数位上的数字和凑成是的倍数，要填的其它数字可在此基础上依次加上。
（六）写出两个能被整除的多位数。
［评］练习设计紧扣教学重点，既注意遵循学生的认识规律，循序渐进，又注重了学生的思维训练和科学解题方法的指导，使学生数学能力的培养落到了实处。
［总评］这节课教师采用“引导学习”的方法进行教学，有以下鲜明的特点：.充分调动了学生学习的积极性、主动性，让他们参与数学知识形成的全过程，从而确保了学生在学习中的主体地位。.教师在整个教学过程中立足于科学地引导学生的逻辑思维，辅导学生学会研究一类数学问题的方法，指导学生掌握解题的技能技巧，体现出了教师善“导”、会“导”、科学地“导”、巧妙地“导”。.教师把数学知识的传授、数学思想方法的渗透、学生学习方法的指导、学生的思维训练和数学能力的培养有机地结合起来，收到优质、高效的教学效果。
成师附小
来自: 中基网>>教学参考
www.cbe21.com
*/