咪咕视讯mg101怎么搜台

書名：算法學習與應用從入門到精通
作者名：張玲玲
本章字數： 2069字
更新時間： 2019-01-05 04:15:47

2.4 分治算法思想

知識點講解：光盤：視頻講解\第2章\分治算法思想.avi

在本節將要講解的分治算法也采取了各個擊破的方法，將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。只要求出子問題的解，就可得到原問題的解。

2.4.1 分治算法基礎

在編程過程中，經常遇到處理數據相當多、求解過程比較復雜、直接求解法會比較耗時的問題。在求解這類問題時，可以采用各個擊破的方法。具體做法是：先把這個問題分解成幾個較小的子問題，找到求出這幾個子問題的解法后，再找到合適的方法，把它們組合成求整個大問題的解。如果這些子問題還是比較大，還可以繼續再把它們分成幾個更小的子問題，以此類推，直至可以直接求出解為止。這就是分治算法的基本思想。

使用分治算法解題的一般步驟如下。

① 分解，將要解決的問題劃分成若干個規模較小的同類問題。

② 求解，當子問題劃分得足夠小時，用較簡單的方法解決。

③ 合并，按原問題的要求，將子問題的解逐層合并構成原問題的解。

2.4.2 實踐演練——解決“大數相乘”問題

為了說明分治算法的基本用法，接下來將通過一個具體實例的實現過程，詳細講解分治算法思想在編程中的基本應用。

實例2-7 解決“大數相乘”問題

源碼路徑光盤\daima\2\fenzhi.c

問題描述：所謂大數相乘，是指計算兩個大數的積。

算法分析：假如計算123×456的結果，則分治算法的基本過程如下所示。

第一次拆分為：12和45，具體說明如下所示。

設char *a = "123", *b = "456"，對a實現t = strlen(a), t/2得12(0,1位臵)余3(2位臵)為3和6。

同理，對另一部分b也按照上述方法拆分，即拆分為456。

使用遞歸求解：12×45，求得12×45的結果左移兩位補0右邊，因為實際上是120×450;12×6（同上左移一位其實是120×6）;3×45（同上左移一位其實是3×450）;3×6（解的結果不移動）。

第二次拆分：12和45，具體說明如下所示。

1和4：交叉相乘并將結果相加，1×4左移兩位為400,1×5左移一位為50,2×4左移一位為80,2×5不移為10。

2和5：相加得400+50+80+10=540。

另外幾個不需要拆分得72、135、18，所以：54000+720+1350+18=56088。

由此可見，整個解法的難點是對分治的理解，以及結果的調整和對結果的合并。

具體實現：根據上述分治算法思想，編寫實例文件fenzhi.c，具體實現代碼如下所示。

        #include <stdio.h>
        #include <malloc.h>
        #include <stdlib.h>
        #include <string.h>

        char *result = '\0';
        int  pr=1;
        void getFill(char *a, char *b, int ia, int ja, int ib, int jb, int tbool, int move){
        int  r, m, n, s, j, t;
        char *stack;

            m = a[ia] -48;
            if(tbool){// 直接將結果數組的標志位填入，這里用了堆棧思想
              r = (jb - ib > ja - ia) ? (jb - ib) : (ja - ia);
        stack = (char *)malloc(r + 4);
        for(r = j = 0, s = jb; s >= ib; r ++, s --){
                  n = b[s] -48;
        stack[r] = (m * n + j) % 10;
                  j = (m * n + j) / 10;
              }
        if( j ){
        stack[r] = j;
        r ++;
              }
        for(r --; r >= 0; r --, pr ++)
        result[pr] = stack[r];
        free(stack);
        for(move = move + pr; pr < move; pr ++)
        result[pr] = '\0';
            }
            else{ //與結果的某幾位相加，這里不改變標志位pr的值
              r = pr - move -1;
        for(s = jb, j = 0; s >= ib; r --, s --){
                  n = b[s] -48;
                  t = m * n + j + result[r];
        result[r] = t % 10;
                  j = t / 10;
              }
        for( ; j ; r -- ){
                  t = j + result[r];
        result[r] = t % 10;
                  j = t / 10;
              }
            }
        }

        int  get(char*a, char*b, int ia, int ja, int ib, int jb, int t, int move){
        int m, n, s, j;
        if(ia == ja){
              getFill(a, b, ia, ja, ib, jb, t, move);
        return 1;
            }
        else if(ib == jb){
              getFill(b, a, ib, jb, ia, ja, t, move);
        return 1;
        }
    else{
            m = (ja + ia) / 2;
            n = (jb + ib) / 2;
            s = ja - m;
            j = jb - n;
            get(a, b, ia, m, ib, n, t, s + j + move);
            get(a, b, ia, m, n + 1, jb,0, s + move);
            get(a, b, m + 1, ja, ib, n,0, j + move);
            get(a, b, m + 1, ja, n + 1, jb,0,0 + move);
        }
    return 0;
    }

    int  main(){
    char *a, *b;
    int  n, flag;

        a = (char *)malloc(1000);
        b = (char *)malloc(1000);
    printf("The program will computer a*b\n");
    printf("Enter a b:");
    scanf("%s %s", a, b);
    result = (char *)malloc(strlen(a) + strlen(b) + 2);
    flag = pr = 1;
    result[0] = '\0';
    if(a[0] == '-' && b[0] == '-')
            get(a, b,1, strlen(a)-1,1, strlen(b)-1,1,0);
    if(a[0] == '-' && b[0] ! = '-'){
    flag = 0;
            get(a, b,1, strlen(a)-1,0, strlen(b)-1,1,0);
        }
    if(a[0] ! = '-' && b[0] == '-'){
    flag = 0;
            get(a, b,0, strlen(a)-1,1, strlen(b)-1,1,0);
        }
    if(a[0] ! = '-' && b[0] ! = '-')
            get(a, b,0, strlen(a)-1,0, strlen(b)-1,1,0);
    if(! flag)
    printf("-");
    if( result[0] )
    printf("%d", result[0]);
    for(n = 1; n < pr ; n ++)
    printf("%d", result[n]);
    printf("\n");
    free(a);
    free(b);
    free(result);
    system("pause");
    return 0;
    }

執行后先分別輸入兩個大數，例如123和456，按下【Enter】鍵后將輸出這兩個數相乘的積。執行效果如圖2-9所示。

圖2-9 “大數相乘”問題的執行效果

2.4.3 實踐演練——歐洲冠軍杯比賽日程安排

實例2-8 使用分治算法解決“歐洲冠軍杯比賽日程安排”問題

源碼路徑光盤\daima\2\ouguan.c

問題描述：一年一度的歐洲冠軍杯馬上就要打響，在初賽階段采用循環制，設共有n隊參加，初賽共進行n-1天，每隊要和其他各隊進行一場比賽，然后按照最后積分選拔進入決賽的球隊。要求每隊每天只能進行一場比賽，并且不能輪空。請按照上述需求安排比賽日程，決定每天各隊的對手。

算法分析：根據分治算法思路，將所有參賽隊伍分為兩半，則n隊的比賽日程表可以通過n/2個隊的比賽日程來決定。然后繼續按照上述一分為二的方法對參賽隊進行劃分，直到只剩余最后2隊時為止。

假設n隊的編號為1,2,3, …, n，比賽日程表制作為一個二維表格，每行表示每隊所對陣隊的編號。例如8支球隊7天比賽的日程表如表2-2所示。

表2-2 8隊比賽日程表

根據表2-2的分析，可以將復雜的問題分治而解，即分解為多個簡單的問題。例如有4隊的比賽日程如表2-3所示。

表2-3 4隊比賽日程表

具體實現：根據上述分治算法思想，編寫實例文件ouguan.c，具體實現代碼如下所示。

                  #include <stdio.h>
                  #define MAXN 64
                  int a[MAXN+1][MAXN+1]={0};
                  void gamecal(int k, int n)//處理編號k開始的n個球隊的日程
                  {
                  int i, j;
                  if(n==2)
                      {
                        a[k][1]=k;  //參賽球隊編號
                        a[k][2]=k+1; //對陣球隊編號
                        a[k+1][1]=k+1; //參賽球隊編號
                        a[k+1][2]=k; //對陣球隊編號
                  }else{
                        gamecal(k, n/2);
                        gamecal(k+n/2, n/2);
                        for(i=k; i<k+n/2; i++) //填充右上角
                        {
                        for(j=n/2+1; j<=n; j++)
                            {
                  a[i][j]=a[i+n/2][j-n/2];
                            }
                        }
                        for(i=k+n/2; i<k+n; i++) //填充左下角
                        {
                            for(j=n/2+1; j<=n; j++)
                            {
        a[i][j]=a[i-n/2][j-n/2];
                  }
              }
            }
        }

        int main()
        {
            int m, i, j;
            printf("參賽球隊數：");
            scanf("%d", &m);
            j=2;
        for(i=2; i<8; i++)
            {
              j=j*2;
              if(j==m) break;
            }
        if(i>=8)
            {
              printf("參賽球隊數必須為2的整數次冪，并且不超過64! \n");
              getch();
              return 0;
            }
            gamecal(1, m);
            printf("\n編號 ");
        for(i=2; i<=m; i++)
              printf("%2d天 ", i-1);
              printf("\n");
              for(i=1; i<=m; i++)
            {
        for(j=1; j<=m; j++)
        printf("%4d ", a[i][j]);
        printf("\n");
            }
        getch();
        return 0;
        }

執行后先輸入參賽球隊數目，輸入完成并按下【Enter】鍵會顯示具體的比賽日程，執行效果如圖2-10所示。

圖2-10 比賽日程安排的執行效果

官术网_书友最值得收藏!

算法學習與應用從入門到精通

2.4 分治算法思想

2.4.1 分治算法基礎

2.4.2 實踐演練——解決“大數相乘”問題

2.4.3 實踐演練——歐洲冠軍杯比賽日程安排