算法設計與分析分治法-基本思想信息工程大學國家級實驗教學示范中心計算機學科組規(guī)劃教材算法設計與分析Python案例詳解微課視頻版尋找假幣和金塊問題的共同點把問題分解為規(guī)模更小的問題求解小規(guī)模問題得到原問題的解

算法策略：分而治之總體思想適用條件代碼框架一二三T(n)將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。對k個子問題分別求解。如果子問題的規(guī)模仍然不夠小，則再劃分為k個子問題，如此遞歸的進行下去，直到問題規(guī)模足夠小，很容易求出其解為止。T(n/m)T(n/m)T(n/m)T(n/m)………………………………邊界和遞歸式T(n)將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出原來問題的解。T(n/m)T(n/m)T(n/m)T(n/m)………………………………分治法的思想：將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分治就是“分而治之”，實質(zhì)是將原問題分成n個規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題，然后遞歸地解這些子問題，最后合并其結(jié)果就得到原問題的解。子問題求解(conquer)問題S問題S1……問題S2問題Sn問題SiS1的解……S2的解Sn的解Si的解S的解問題的分解(divide)子問題解的合并(combine)選擇題分治法的設計思想是將一個難以直接解決的大問題分割成規(guī)模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解，要求原問題和子問題的問題規(guī)模

，問題性質(zhì)

。A：相同，相同B：相同，不同C：不同，相同D：不同，不同測試分治法所能解決的問題一般具有以下幾個特征：該問題的規(guī)模縮小到一定的程度就可以容易地解決；該問題可以分解為若干個規(guī)模較小的相同問題；利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。divide-and-conquer(P){if(|P|<=n0)adhoc(P);//解決小規(guī)模的問題

//分解

dividePintosmallersubinstancesP1,P2,...,Pk；

//遞歸求解各子問題

for(i=1;i<=k;i++)yi=divide-and-conquer(Pi);

//將子問題的解合并為原問題的解

returnmerge(y1,...,yk);}分治法設計的平衡原則：使子問題的規(guī)模大致相同測試：博彩詐騙為什么可以成功背景設定你是一位足球迷，當前正在進行某個足球賽事，你在看球的同時想娛樂一下，參與一下博彩事業(yè)，當前正在進行16進8的比賽，你想買張彩票，正在你準備下注時，收到了一個信息。選擇題：1信息中說：A隊肯定會在這場比賽中獲勝，此時你會相信嗎？A：不信 B：信 C：半信半疑無論你信不信，你買了A隊勝，此后，當A和C比賽時，你又收到了信息2信息中說：C隊肯定會在這場比賽中獲勝，此時你會相信嗎？A：不信 B：信 C：半信半疑無論你信不信，你買了C隊勝，此后，當C和E比賽時，你又收到了信息3信息中說：C隊肯定會在這場比賽中獲勝，此時你會相信嗎？A：不信 B：信 C：半信半疑你買了C隊勝，決賽時，你又收到了信息4要想知道比賽結(jié)果，需要付費查看，此時你會付