返回頂部

『嗨威說』算法設計與分析 - 分治法思想小結

本文索引目錄:

一、分治算法的基本思想

二、一道二分題點撥分治思想

三、結對編程小結

 

 

一、分治算法的基本思想:

  1.1  基本概念:

  “分而治之”( Divide and conquer)方法 (在ACM玩家中還有一種說法叫 分治術) ,是追求高效算法中常用的一種算法思想。

  所謂“分而治之” 就是把一個復雜的算法問題按一定的“分解”方法分為等價的規模較小的若干部分,然后逐個解決,分別找出各部分的解,把各部分的解組成整個問題的解,這種樸素的思想來源于人們生活與工作的經驗,也完全適合于技術領域。

 

  1.2  使用條件:

  (1)問題規模當縮小到某種規模時易于解決的狀態。

  (2)分解成的子問題是相同類型的子問題,具有最優子結構性質。

  (3)分解而成的更小的問題在解決之后可以合并出正確答案。

  (4)子問題是相互獨立的,即子問題之間沒有公共的子問題,當然也可以有,但是會降低效率,在出現眾多重復子問題的時候常使用動態規劃dp。

 

  1.3  使用步驟:

  (1)確定需要分解的問題大類。

  (2)分解成小問題后,解決小問題。

  (3)最后進行合并小問題,簡稱歸并。

 

  1.4  常用工具:

  遞歸方法,遞歸,是指子程序(或函數)直接調用自己或通過一系列調用語句間接調用自己,是一種描述問題和解決問題的常用方法。遞歸有兩個基本要素:
  ①邊界條件,即確定遞歸到何時終止,也稱為遞歸出口。
  ②遞歸模式,即大問題是如何分解為小問題的,也稱為遞歸體。

 

  1.5  基本模板:

T getAns(T l, T r,T i)
{
        /* 結束條件 */
    if(l >= r)
        return r;

        /* 取得中值 */
    T mid = (l+r) >> 1;

        /* 二分遞歸 */
    if(滿足的條件)      return getAns(l,mid,i+1);
    else              return getAns(mid,r,i+1);
} 

 

 

 

二、一道二分題點撥分治思想:

2.1  題目來源:

POJ:http://poj.org/problem?id=1064

 

2.2  題目題干:

Cable master

 

 2.3題目大意:

  每條電纜的長度都可以達到一厘米,并且告知必須切割的長度,可以精確地切割一厘米。
  通過編寫一個程序確定可以從電纜上切下的電纜的最大可能長度,以獲得指定的電纜數量。

 

2.4題目思路:

  第一步:先書寫滿足要求的判斷函數,即如下的(isGetNum)

  第二步:套用二分模板,修改部分內容。

  第三步:綜合結果

 

2.5題目AC代碼:

#include<stdio.h>
#include<math.h>
int n,m;
double Ntemp[10005],maxx;
bool isGetNum(double x)
{
    int cnt = 0;
    for(int i = 0;i<n;i++)
        cnt += (int)(Ntemp[i] / x);
    return cnt >= m;
}
double getAns(double l, double r,int i)
{
    if(fabs(l-r) < 1e-6)
        return r;
    if(i == 100) return r;
    double mid = (l+r) / 2;
    if(!isGetNum(mid))    return getAns(l,mid,i+1);
    else                return getAns(mid,r,i+1);
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        maxx = 0;
        for(int i = 0;i<n;i++)
        {
            scanf("%lf",&Ntemp[i]);
            if(Ntemp[i] > maxx) maxx = Ntemp[i];
        }
        printf("%.2f\n",floor(getAns(0,100001,1) * 100) / 100);
    }
    return 0;
 } 

 

 

 

三、結對編程小結:

  剛開始很自信的就上來打題,過了樣例就很自信的提交了,結果在一些測試點WA了,思前想后都覺得代碼沒有問題,結果是沒有完整理清題意,在部分邊界處理上出了點問題,還好最后也解決了出來,在后面的題中就很順利就求解了。

  結對編程可以互相找出對方的不足之處,也可以齊心協力想出一個更好的算法,隊友VS編碼debug能力很強,編碼過程愉快和諧,下次繼續一起加油~。

 

posted @ 2019-10-13 01:56  嗨威er  閱讀(...)  評論(...編輯  收藏
三d开奖结果走势图