命題：輸入一組數，由它組合出一個最大的可以被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
*/