Python程序設(shè)計(jì)實(shí)踐- 習(xí)題及答案 ch03 典型算法介紹

第3章典型算法介紹一、選擇題1.以下哪些是分治算法的步驟（）。A.分解B.求解C.合并D.計(jì)算結(jié)果2.關(guān)于貪心算法，下列敘述中錯(cuò)誤的是：（）A.貪心算法無法求得問題的最優(yōu)解。B.貪心算法所做出的選擇只是在某種意義上的局部最優(yōu)選擇。C.貪心算法的時(shí)間效率比枚舉法高。D.貪心算法并不從整體最優(yōu)考慮。E.思維是大腦的基本功能，大腦是人體的直接感覺器官。參考答案:ABC；A。二、填空題1.經(jīng)典的算法策略主要包括____、____、____、____、____、____、____等。2.枚舉算法又叫____，也稱為暴力破解法，是指針對(duì)要解決的問題，列舉出所有可能的情況，逐個(gè)判斷哪些符合問題所要求的約束條件，從而得到問題的解。3.遞推算法充分利用了計(jì)算機(jī)____、可以自動(dòng)____的特點(diǎn)。4.迭代算法在數(shù)學(xué)上也稱為“____”，是一種不斷用舊值遞推新值的過程，在解決問題時(shí)，總是重復(fù)利用一種方法。參考答案:枚舉算法、遞推算法、遞歸算法、迭代算法、分治算法、貪心算法、回溯算法；窮舉法；運(yùn)算速度快，進(jìn)行重復(fù)操作。遞推法三、簡(jiǎn)答題1.雞兔同籠問題參考答案:2.找零錢問題將一張面值為?100?元的人民幣等值換成?100?張?5?元、1?元、?0.5?元的零鈔，要求每種零鈔不少于?1?張，問有哪幾種組合？參考答案:使用for……range循環(huán)結(jié)構(gòu)：運(yùn)行得到:3.三色球問題設(shè)有?3?個(gè)紅球、3?個(gè)黃球、6?個(gè)綠球，現(xiàn)將這?12?個(gè)球混放在一個(gè)盒子里，從中任意摸出?8?個(gè)球，求摸出球的各種顏色搭配。提示：三色球問題最簡(jiǎn)單、直接的解法是枚舉算法。4.算?24?點(diǎn)游戲給定?4?個(gè)整數(shù)（數(shù)字范圍為?1～13），使用“+”“?”“×”“/”“()”構(gòu)造一個(gè)計(jì)算式，使計(jì)算結(jié)果是?24，例如(2-1)×4×6=24。5.斐波那契數(shù)列問題用遞歸算法求解斐波那契數(shù)列問題。6.找零幣問題假設(shè)某超市只有?1?分、2?分、5?分、1?角、2?角、5?角、1?元的硬幣。在超市結(jié)賬時(shí)，如果需要找零錢，收銀員希望找給顧客的硬幣數(shù)最少。給定需要找的零錢數(shù)目，如何求得最少的硬幣數(shù)（可用貪心算法）？7.求立方根用迭代算法編寫程序，求解?a?的立方根。8.會(huì)議室安排問題假設(shè)現(xiàn)在只有一個(gè)會(huì)議室，需要舉行?8?場(chǎng)會(huì)議。每場(chǎng)會(huì)議都有開始時(shí)間?b?和結(jié)束時(shí)間?e（若前一場(chǎng)會(huì)議的結(jié)束時(shí)間早于后一場(chǎng)會(huì)議的開始時(shí)間，則稱這兩場(chǎng)會(huì)議之間沒有沖突，否則稱這兩場(chǎng)會(huì)議之間有沖突）。每場(chǎng)會(huì)議的開始時(shí)間和結(jié)束時(shí)間如表?3-2?所示。請(qǐng)使用貪心算法解決這個(gè)問題，使會(huì)議室能夠滿足最優(yōu)的安排。9.n皇后問題在?n×n?格的棋盤上放置?n?個(gè)皇后，使其不能相互攻擊，即任意兩個(gè)皇后不能處于同一行、同一列或同一斜線上，有多少種不同的放置方