第4章循環(huán)控制(參考版)
2024-10-15 13:37本頁面
【正文】 但不一定對所有問題都能得到最優(yōu)解。 } 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 42 小結(jié) ? 計(jì)算機(jī)的強(qiáng)項(xiàng)是不厭其煩地做同樣的操作，這是通過循環(huán)語句實(shí)現(xiàn)的 ? 循環(huán)語句： while、 do...while和 for ? 基于循環(huán)的算法： ? 枚舉法：對某些問題，在尋找它的解時(shí)需要檢查所有的可能的方案，從中找出可行解。 cout 1分硬幣數(shù)： onefen endl。 cout 5分硬幣數(shù)： fivefen endl。 money = ONEFEN。 money = TWOFEN。 money = FIVEFEN。 money = ONEJIAO。 cin money。 int onefen = 0, twofen = 0, fivefen = 0, onejiao = 0。 ? 不斷嘗試的過程就是循環(huán) 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 40 includeiostream using namespace std。如要找零的值小于最大的硬幣值，則嘗試第二大的硬幣。 ?將所有解綜合起來 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 38 硬幣找零問題 ? 對于一種貨幣，有面值為 1分 , 2分 , 5分和 1角的硬幣，最少需要多少個(gè)硬幣來找出 K分錢的零錢。 } 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 36 第 4章 循環(huán)控制 重復(fù) N次循環(huán) While循環(huán) Do … while 循環(huán) 循環(huán)的中途退出 枚舉法 貪婪法 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 37 貪婪法的基本思想 ? 在求解過程的每一步都選取一個(gè)局部最優(yōu)的策略，把問題規(guī)?？s小，最后把每一步的結(jié)果合并起來形成一個(gè)全局解。 ++c3) if ((c3 == a1 || c3 == c2)) continue。 else for (c3 = ?A‘。 c2 = ?C‘。 c1 = ?C‘。 } } } } } 改進(jìn)版 2 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 34 列出 ABC三個(gè)字母的全排列 ? 解題思路： ? 讓第一個(gè)位置的值從 A依次變到 C ? 讓第一個(gè)位置的值從 A依次變到 C ? 讓第一個(gè)位置的值從 A依次變到 C ? 注意三個(gè)位置的值不能相同 ? 可以用一個(gè)三層的嵌套循環(huán)實(shí)現(xiàn)，循環(huán)變量是字符類型 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 35 int main() { char c1, c2, c3。 flag = true。amp。amp。amp。 else {d=10 – a – b c。 c=4 。 ++b) { if ( a == b) continue。amp。 ++a) { for (b=1。amp。 for (a=1。} } 改進(jìn)版 1： 程序不夠簡練 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 33 main() { int a, b, c, d。 } } if (flag) break。 flag = true。amp。amp。amp。 else {d=10 – a – b c。 c=4。 ++b) { if ( a == b) continue。 ++a) { for (b=1。 for (a=1。 } } 問題：效率差 解決方法：一旦找到答案就應(yīng)該結(jié)束 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 32 main() { int a, b, c, d。amp。amp。amp。 else {d=10 – a – b c。 c=4。 ++b) if ( a == b) continue。 ++a) for (b=1。 for (a=1。這種結(jié)構(gòu)就是循環(huán)結(jié)構(gòu)。同樣， b, c ,d的值也都可能從 1變到 4。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 30 枚舉法 —續(xù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1