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