命題：輸入一組數(shù)，由它組合出一個(gè)最大的可以被15整除。
思路：能被15整除的數(shù)，必然能被5和3整除，則必須要滿足整除5和整除3的特征。
用貪心法可以組合出這些數(shù)中最大的一個(gè)。（代碼如下）如果組合不出來，則輸出impossible。否則輸出這個(gè)數(shù)。
// Divide3.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//
#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;
#define MAX 1000
#define IMPOSSIBLE "impossible"
char str[MAX];
// 0的ASCII碼是48，9的ASCII碼是57,因此計(jì)數(shù)器數(shù)組的大小取為58，以利于快速取值
int counter[58];
// 附加檢驗(yàn)代碼，本程序中可不執(zhí)行
bool checkInput(char *s);
// 整理所有數(shù)字，并分別統(tǒng)計(jì)'0'-'9'各個(gè)數(shù)的計(jì)算結(jié)果
void collect(char *s);
// 判斷是否涵蓋'5'或者'0'
// 證明：能被整除的數(shù)末尾必須是或者
bool canDivideBy5or0();
// 判斷一個(gè)字符是不是'3' '6' '9'中的一個(gè)
inline bool belongsTo369(char c);
// 貪心法將數(shù)字轉(zhuǎn)換成可以被整除的數(shù)，并輸出結(jié)果
bool connect();
int main( )
{
freopen("input.txt", "r", stdin); //文件輸入輸出
freopen("output.txt", "w", stdout);
scanf("%s", str);
// 為了加快速度略去字符串檢查，假設(shè)所有輸入都是合法的
//if(!checkInput(str))
// printf("err");
collect(str);
// 輸出計(jì)數(shù)器
//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，即無法把字符數(shù)組連接起來，則輸出impossible
printf(IMPOSSIBLE);
//printf("%s", str);
return 0;
}
void collect(char *s)//分別統(tǒng)計(jì)字符串中'0'-'9'的出現(xiàn)個(gè)數(shù)
{
int i = 0; //i表示字符串的第i個(gè)字符
while(s[i] != '\0' && i < MAX)
{
++counter[s[i]];
++i;
}
}
bool canDivideBy5or0()//如果字符串中出現(xiàn)過或，即能被整除，則輸出true，否則輸出false
{
if(counter['5'] > 0)
return true;
if(counter['0'] > 0)
return true;
return false;
}
bool belongsTo369(char c)//判斷一個(gè)字符是不是'3' '6' '9'中的一個(gè)，如果是，則輸出true，否則輸出false
{
if(c == '3' || c == '6' || c == '9')
return true;
return false;
}
bool connect()//把整個(gè)字符數(shù)組連接起來,并輸出
{
bool canConnect = true;// canConnect是一個(gè)標(biāo)志，表示是否可以開始連接了？
int i;
int sum = 0;
// 從最大的數(shù)開始遞減到，并將所有不是、、的數(shù)加起來，將結(jié)果存放在sum中
for(i='9'; i>'0'; --i)
{
if(counter[i] == 0 || belongsTo369(i))//如果某個(gè)數(shù)字沒有的話，比如一個(gè)序列里沒有'9'就跳過，或者如果有數(shù)字，但是它屬于，，，那也跳過。然后把剩下的數(shù)字都加起來
continue;
sum += (counter[i] * (i - '0'));//(i - '0')因?yàn)槎际亲址?1','2'，…所以，要-'0'得到它的數(shù)值，，…，然后乘以它的數(shù)量
}
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;
//以下為輸出。此時(shí)計(jì)數(shù)器里面的數(shù)值已經(jīng)是最終方案了,根據(jù)下面的規(guī)律，用貪心法生成輸出結(jié)果
// 貪心法：
// 要湊齊一個(gè)最大的整數(shù)，那么它必須滿足兩個(gè)條件
// 1、位數(shù)最多，比如和比？
// 2、高位的數(shù)字盡量地大，比如和相比
// 因此：應(yīng)該先滿足位數(shù)最多，因?yàn)榻Y(jié)果必然可以得到一個(gè)整除的數(shù)（定理）？
// 則只需要滿足高位數(shù)字大即可，而既然是'9'到'0'，因此依次從大到小輸出即可
// 并且為了結(jié)果能乘除，所以最后一位必須為或者
bool endWith5 = false;//endWith5是一個(gè)標(biāo)記，如果為true表示以結(jié)尾，如果為false表示以結(jié)尾
int j = 0;
int r = 0;
if(counter['0'] == 0)//如果輸入的字符串中沒有，則必然要以結(jié)尾,這部分有錯(cuò)，例如：輸出
{
endWith5 = true;
--counter['5'];//減掉的目的是為了保留一個(gè)，留在末尾才輸出
}
for(i = '9'; i >= '0'; --i)//計(jì)算器中的數(shù)字是'9'到'0'，為了得到結(jié)果是最大的數(shù)，依次從大到小輸出數(shù)字即可
{
for(j = counter[i]; j > 0; --j)
{
//printf("%c", i);
str[r++] = i;
}
}
if(endWith5)//如果以結(jié)尾，則在末尾輸出一個(gè)
//printf("5");
str[r++] = '5';
str[r] = '\0';
printf("%s", str);
return true;
}
/*
關(guān)于整除的理論基礎(chǔ)：http://www.cbe21.com/subject/maths/printer.phparticle_id=818
“能被３整除的數(shù)的特征”教學(xué)實(shí)錄與評(píng)析
金中
一、復(fù)習(xí)舊知
師：前面同學(xué)們學(xué)習(xí)了能被、整除的數(shù)的特征，下面老師就來檢查一下（板書出三個(gè)數(shù)字：、、），你能用、、這三個(gè)數(shù)字組成能被整除的三位數(shù)嗎？
學(xué)生根據(jù)教師要求組數(shù)，教師板書出學(xué)生組數(shù)的情況：、。
師：為什么這樣組數(shù)？
生：因?yàn)閭€(gè)位上是、、、、的數(shù)能被整除……
師：同樣用這三個(gè)數(shù)字，你們能組成被整除的數(shù)嗎？
教師根據(jù)學(xué)生組數(shù)的情況板書出：、。
師：你們是怎樣想的？
生：因?yàn)閭€(gè)位上是或的數(shù)都能被整除。
［評(píng)］鋪墊復(fù)習(xí)不落俗套，采用組數(shù)的方法，既復(fù)習(xí)了能被、整除的數(shù)的特征，又激發(fā)了學(xué)生學(xué)習(xí)的興趣。
二、講授新課
（一）設(shè)置教學(xué)“陷阱”。
師：如果仍用這三個(gè)數(shù)字，你能否組成能被整除的數(shù)呢？試一試。
教師根據(jù)學(xué)生組數(shù)的情況板書出：、。
師：這兩個(gè)數(shù)能被整除嗎？
學(xué)生試除驗(yàn)證這兩個(gè)數(shù)能被整除。
師：從這兩個(gè)能被整除的數(shù)，你想到了什么？能被整除的數(shù)有什么特征？
生：個(gè)位上是的倍數(shù)的數(shù)能被整除。（引導(dǎo)學(xué)生提出假設(shè)①）
（二）制造認(rèn)知矛盾。
師：剛才同學(xué)們是從個(gè)位上去尋找能被整除的數(shù)的“特征”的，那么個(gè)位上是的倍數(shù)的數(shù)就一定能被整除嗎？
教師緊接著舉出、、等數(shù)讓學(xué)生試除判斷，由此引導(dǎo)學(xué)生推翻假設(shè)①。
師：這幾個(gè)數(shù)個(gè)位上都是的倍數(shù)，有的數(shù)能被整除，而有的數(shù)卻不能被整除。我們能從個(gè)位上找出能被3整除的數(shù)的特征嗎？
生：不能。
（三）設(shè)疑問激興趣。
師：請(qǐng)同學(xué)們?nèi)杂谩ⅰ⑦@三個(gè)數(shù)字，任意組成一個(gè)三位數(shù)，看看它們能不能被整除。
學(xué)生用、、這三個(gè)數(shù)字任意組成一個(gè)三位數(shù)，通過試除發(fā)現(xiàn)：所組成的三位數(shù)都能被整除。
師：能被整除的數(shù)有沒有規(guī)律可循呢？下面我們一起來學(xué)習(xí)“能被整除的數(shù)的特征。”（板書課題）
［評(píng)］教師通過設(shè)置教學(xué)“陷阱”，引導(dǎo)學(xué)生提出能被整除的數(shù)的特征的假設(shè)，到推翻假設(shè)，引發(fā)認(rèn)知矛盾，并再次創(chuàng)設(shè)學(xué)生探究的問題情境，不僅有效地避免了“能被、整除的數(shù)的特征”思維定勢(shì)的影響，而且進(jìn)一步地激發(fā)了學(xué)生的求知欲望。
（四）引導(dǎo)探究新知。
師：觀察用、、任意組成的能被整除的三位數(shù)，雖然它們的大小不相同，但它們有什么共同點(diǎn)？
引導(dǎo)學(xué)生發(fā)現(xiàn)：組成的三位數(shù)的三個(gè)數(shù)字相同，所不同的是這三個(gè)數(shù)字排列的順序不同。
師：三個(gè)數(shù)字相同，那它們的什么也相同？
生：它們的和也相同。
師：和是多少？
生：這三個(gè)數(shù)字的和是。
師：這三個(gè)數(shù)字的和與有什么關(guān)系？
生：是的倍數(shù)。
師：也就是說它們的和能被什么整除？
生：它們的和能被整除。
師：由此你想到了什么？
學(xué)生提出假設(shè)②：一個(gè)數(shù)各位上的數(shù)的和能被整除，這個(gè)數(shù)就能被整除。
師：通過同學(xué)們的觀察，有的同學(xué)提出了能被整除的數(shù)特征的假設(shè)，但是同學(xué)們觀察的僅是幾個(gè)特殊的數(shù)，是否能被整除的數(shù)都有這樣的特征呢？要說明同學(xué)們的假設(shè)是正確的，我們需要怎么做？
生：進(jìn)行驗(yàn)證。
師：怎樣進(jìn)行驗(yàn)證呢？
引導(dǎo)學(xué)生任意舉一些能被整除的數(shù)，看看各位上的數(shù)的和能否被整除。（為了便于計(jì)算和研究，可讓學(xué)生任意舉出以內(nèi)的自然數(shù)，然后乘以。）
根據(jù)學(xué)生舉出的數(shù)，教師完成如下的板書，并讓學(xué)生計(jì)算出各個(gè)數(shù)各位上的數(shù)的和進(jìn)行驗(yàn)證。
附圖{圖}
師：通過上面的驗(yàn)證，說明同學(xué)們提出的能被整除的數(shù)特征的假設(shè)怎樣？
生：是正確的。
師：請(qǐng)同學(xué)們翻開書，看看書上是怎樣概括出能被整除的數(shù)的特征的。引導(dǎo)學(xué)生閱讀教材第頁的有關(guān)內(nèi)容。
師：什么叫各位？它與個(gè)位有什么不同？根據(jù)這個(gè)特征，怎樣判斷一個(gè)數(shù)能不能被整除？
組織學(xué)生討論，加深能被整除的數(shù)的特征的認(rèn)識(shí)，掌握判斷一個(gè)數(shù)能否被整除的方法。
［評(píng)］在學(xué)生觀察的基礎(chǔ)上，引導(dǎo)他們提出能被整除的數(shù)特征的假設(shè)，并驗(yàn)證假設(shè)是否正確，不僅充分調(diào)動(dòng)了學(xué)生學(xué)習(xí)的主動(dòng)性、積極性，而且滲透了從特殊到一般的數(shù)學(xué)思想方法，指導(dǎo)了學(xué)法。
三、課堂練習(xí)
（一）判斷下面各數(shù)能否被整除，并說明理由。
54 83 114 262 837
（二）數(shù)能被整除嗎？你是怎樣判斷的？有沒有更簡捷的判斷方法？
引導(dǎo)學(xué)生發(fā)現(xiàn)：、、這三個(gè)數(shù)字本身就能被整除，因此它們的和自然能被整除。判斷時(shí)用不著把它們相加。
（三）數(shù)能被整除嗎？（將中插入一些數(shù)字改編而成。）
引導(dǎo)學(xué)生概括出迅速判斷一個(gè)數(shù)能否被整除的方法：（）先去掉這個(gè)數(shù)各位上是、、的數(shù)；（）把余下數(shù)位上的數(shù)相加，并去掉相加過程中湊成、、的數(shù)；（）看剩下數(shù)位上的數(shù)能否被整除。
（四）運(yùn)用上述判斷一個(gè)數(shù)能否被整除的方法，迅速判斷、、能否被整除。
（五）在下面每個(gè)數(shù)的□里填上一個(gè)數(shù)字，使這個(gè)數(shù)有約數(shù)。它們各有幾種不同的填法？
□4□□56□
引導(dǎo)學(xué)生掌握科學(xué)的填數(shù)方法：（）先看已知數(shù)位上的數(shù)字的和是多少；（）如果已知數(shù)位上的數(shù)字和是的倍數(shù)，那么未知數(shù)位的□里最小填“”，要填的其它數(shù)字可依次加上；如果已知數(shù)位上的數(shù)字和不是的倍數(shù)，那么未知數(shù)位的里可先填一個(gè)最小的數(shù)，使它能與已知數(shù)位上的數(shù)字和湊成是的倍數(shù)，要填的其它數(shù)字可在此基礎(chǔ)上依次加上。
（六）寫出兩個(gè)能被整除的多位數(shù)。
［評(píng)］練習(xí)設(shè)計(jì)緊扣教學(xué)重點(diǎn)，既注意遵循學(xué)生的認(rèn)識(shí)規(guī)律，循序漸進(jìn)，又注重了學(xué)生的思維訓(xùn)練和科學(xué)解題方法的指導(dǎo)，使學(xué)生數(shù)學(xué)能力的培養(yǎng)落到了實(shí)處。
［總評(píng)］這節(jié)課教師采用“引導(dǎo)學(xué)習(xí)”的方法進(jìn)行教學(xué)，有以下鮮明的特點(diǎn)：.充分調(diào)動(dòng)了學(xué)生學(xué)習(xí)的積極性、主動(dòng)性，讓他們參與數(shù)學(xué)知識(shí)形成的全過程，從而確保了學(xué)生在學(xué)習(xí)中的主體地位。.教師在整個(gè)教學(xué)過程中立足于科學(xué)地引導(dǎo)學(xué)生的邏輯思維，輔導(dǎo)學(xué)生學(xué)會(huì)研究一類數(shù)學(xué)問題的方法，指導(dǎo)學(xué)生掌握解題的技能技巧，體現(xiàn)出了教師善“導(dǎo)”、會(huì)“導(dǎo)”、科學(xué)地“導(dǎo)”、巧妙地“導(dǎo)”。.教師把數(shù)學(xué)知識(shí)的傳授、數(shù)學(xué)思想方法的滲透、學(xué)生學(xué)習(xí)方法的指導(dǎo)、學(xué)生的思維訓(xùn)練和數(shù)學(xué)能力的培養(yǎng)有機(jī)地結(jié)合起來，收到優(yōu)質(zhì)、高效的教學(xué)效果。
成師附小
來自: 中基網(wǎng)>>教學(xué)參考
www.cbe21.com
*/