實驗1

實驗內容

本實驗要求基于演算法設計與分析的一般程序（即待求解問題的描述、演算法設計、演算法描述、演算法正確性證明、演算法分析、演算法實作與測驗），使用貪心法求解會場安排問題以及利用分治法的回圈日程表演算法，以期從實踐中理解分治法的思想、求解策略及步驟，（有余力者，鼓勵挑戰n≠2k的情形的回圈日程表問題，以及貪心法與分治法的其它應用實體）

實驗目的

1. 理解貪心法的核心思想以及分治法求解程序；
2. 理解分治法的核心思想以及分治法求解程序，

環境要求

無特別要求，演算法實作可以自由選擇C, C++, Java，甚至于其他程式設計語言，

本次選用c++

實驗結果

貪心法求解會場安排問題的解

Description

假設要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場，設計一個有效的貪心演算法進行安排， 對于給定的k個待安排的活動，計算使用最少會場的時間表，

Input

輸入資料的第一行有1 個正整數k（k≤10000），表示有k個待安排的活動，接下來的k行中，每行有2個正整數，分別表示k個待安排的活動開始時間和結束時間，時間以0 點開始的分鐘計，

Output

輸出一個整數，表示最少會場數，

Sample Input

5
1 23
12 28
25 35
27 80
36 50

Sample Output

3

解題思路

1. 對活動進行排序，開始時間越早排在越前面，如果兩個活動時間相同，則結束時間越早的排在越前面
2. 開始時間最早和持續時間最短的優先安排會場，并記錄會場號，
3. 其余活動的開始時間大于或等于已安排活動的結束時間的安排在同一會場，
4. 若某活動的開始時間小于已經安排了會場的活動的結束時間，則安排在另一會場，記錄會場號，
5. 依次回圈，直到所有活動均被安排

步驟2：

演算法設計，包括演算法策略與資料結構的選擇；

演算法設計

首先用快速排序按照結束時間進行非降序排序

然后設定flag進行安排，得到sum的值即為最終結果

步驟3：

描述演算法，希望采用源代碼以外的形式，如偽代碼、流程圖等；

偽代碼

while:n-count>0:
do
int:cur = 0;
for:i=0 to n do i++:
do
 if meeting[i].start_time > cur && meeting[i].flag == 0:
   do
        meeting[i].flag = 1;
        cur = meeting[i].end_time;
        count++;
    done
done
  sum++;
done

步驟4：

演算法的正確性證明，需要這個環節，在理解的基礎上對演算法的正確性給予證明；

步驟5：

演算法復雜性分析，包括時間復雜性和空間復雜性

• 1. 時間復雜度: O(n^2)
• 2. 空間復雜度: O(n)

步驟6：

演算法實作與測驗，附上代碼或以附件的形式提交，同時貼上演算法運行結果截圖

代碼運行結果

請輸入會議個數:
5
請輸入各個會議的開始時間和結束時間:1 23
12 28
25 35
27 80
36 50
所需要的最少會場總個數為:3
行程已結束，退出代碼 0

源代碼

#include <iostream>

class node {
public:
    int end_time;
    int flag;
    int start_time;
};

node copy(const node *a, node *b);

int comp(int a, int b) { return (a < b) ? 1 : 0; }

void quickSort(node *meeting, int low, int high);

int main() {
    int n;
    std::cin >> n;
    node *meeting = new node[n];

    for (int i = 0; i < n; ++i) {
        std::cin >> meeting[i].start_time >> meeting[i].end_time;
        meeting[i].flag = 0;
    }

    quickSort(meeting, 0, n - 1);//對所有會場按結束時間升序排序

    int sum = 0;
    int count = 0;
    while (n - count > 0) {
        int cur = 0;
        for (int i = 0; i < n; ++i) {
            if (meeting[i].start_time > cur && meeting[i].flag == 0) {
                meeting[i].flag = 1;
                cur = meeting[i].end_time;
                count++;
            }
        }
        sum++;
    }
    for (int i = 0; i < n; ++i) {
        std::cout << meeting[i].start_time << " " << meeting[i].end_time << std::endl;
    }
    std::cout << sum;
    return 0;
}


void quickSort(node *meeting, int low, int high) {
    int key = meeting[low].end_time;
    int start = low;
    int end = high;

    while (end > start) {
        while (end > start && meeting[end].end_time >= key) {
            end--;
        }
        if (meeting[end].end_time < key) {
            node temp = meeting[end];
            meeting[end] = meeting[start];
            meeting[start] = temp;
        }
        while (end > start && meeting[start].end_time <= key)start++;
        if (meeting[start].end_time > key) {
            node temp = meeting[start];
            meeting[start] = meeting[end];
            meeting[end] = meeting[start];
        }
    }
    if (start > low)quickSort(meeting, low, start - 1);
    if (end < high) quickSort(meeting, end + 1, high);
}

附上運行結果截圖

實驗總結

1. 貪心演算法的精髓是“今朝有酒今朝醉”，每個階段的決策一旦做出就不可更改，不允許回溯，

2. 和動態規劃的相似之處:
   
   如果大家比較了解動態規劃，就會發現它們之間的相似之處，最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的，貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對于這個子問題本身肯定也是最優的)，動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，并且以其中的最優值作為自身的值，其它的值舍棄，而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決于下面葉子的值，而只取決于當前問題的狀況，換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值，由于貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了，

3. 貪心選擇性質:
   
   所求問題的整體最優解可通過一系列區域最優的選擇獲得，即通過一系列逐步區域最優選擇使得最終得到的選擇方案是全域最優的，

4. 貪心演算法的實作框架

    從問題的某一初始解出發；
    while （能朝給定總目標前進一步）
    {
          利用可行的決策，求出可行解的一個解元素；
    }
    由所有解元素組合成問題的一個可行解；

基于分治法的回圈日程表演算法

問題描述

設有n=2k個運動員要進行羽毛球回圈賽，現要設計一個滿足以下要求的比賽日程表：

1. 每個選手必須與其它n-1個選手各賽一次；
2. 每個選手一天只能比賽一次；
3. 回圈賽一共需要進行n-1天，

采用分治策略求解的分析

??將所有的選手分為兩半，n個選手的比賽日程表就可通過為n/2個選手設計的比賽日程表來決定，遞回進行分割，直到只剩下2個選手時，比賽日程表的制定就變得很簡單，

? ?假設n位選手被順序編號為1,2,3,…,n，比賽的日程表是一個n行n-1列的表格，i行j列的表格內容是第i號選手在第j天的比賽對手，當 n 為奇數時，加入一個虛擬隊員，其他隊員與該隊員的比賽視為輪空，則仍可按照前述方法設計日程表，
? ?按分治策略，可將所有選手對分成為兩組，n 個選手的比賽日程表就可以通過為 n/2 個選手設計的比賽日程表來決定，遞回地用這種一分為二的策略對選手進行分割，直到只剩下2 個選手，可假設只有8位選手參賽，若1至4號選手之間的比賽日程填在日程表的左上角 (4行3列)，5至8號選手之間的比賽日程填在日程表的左下角(4行3列)；那么左下角的內容可由左上角的對應項加上數字4得到，至此，剩余的右上角(4行4列)是為編號小的1至4號選手與編號大的5至8號選手之間的比賽日程安排，例如，在第4天，讓1至4號選 手分別與5至8號選手比賽,以后各天，依次由前一天的日程安排，讓5至8號選手“回圈 輪轉”即可，最后，比賽日程表的右下角的比賽日程表可由，右上角的對應項減去數字4得到，

演算法設計

? ?任何一個可以用計算機求解的問題所需的計算時間都與其規模有關，問題的規模越小，越容易直接求解，解題所需的計算時間也越少，
分治法
? ?分治法是計算機科學中經常使用的一種演算法，設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之，但是不是所有問題都適合用分治法解決，當求解一個輸入規模為n且取值又相當大的問題時，使用蠻力策略效率一般得不到保證，其基本步驟如下：

• (1)分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
• (2)求解子問題：若子問題規模較小而容易被解決則直接解，否則再繼續分解為更小的子問題，直到容易解決；
• (3)合并：將已求解的各個子問題的解，合并為原問題的解，

資料結構

采用二維陣列存盤比賽資訊，i行j列的表格內容是第i號選手在第j天的比賽對手

描述演算法

偽代碼–遞回

ROUND-ROBIN-CALENDAR-REC(A, n) //A[1..n][1..n]
  IF n==1
    A[1][1] = 1
    RETURN
  ROUND-ROBIN-CALENDAR-REC(A, n/2)
  COPY-CALENDAR(A, n)

COPY-CALENDAR(A, n)
  m = n/2; 
  FOR i = 1 TO m 
    FOR j = 1 TO m
      A[i][j+m] = A[i][j] + m  //給右上角賦值
      A[i+m][j] = A[i][j+m]    //右上角抄到左下角
      A[i+m][j+m] = A[i][j]    //左上角抄到右下角

演算法的正確性證明

初始化：如果 n = 1 ( 2^0 = 1 )
則只有一個隊伍，自己跟自己打比賽，正確

保持: 先假設函式內部的所有遞回呼叫均滿足回圈不變式，再證明函式本身回傳后，回圈不變式仍然成立，每次呼叫都能保持正確，因為n是2的k次方，每次呼叫n變成原來的一半，直到最后，

終止：“最外層”的函式呼叫回傳后，演算法結果一定是正確的，

演算法實作與測驗

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
#include<stdio.h>
#include<math.h>
void calender(int **time_table,int n);
void copy_calender(int **time_table,int n);

int main()
{
    int n;
    int i,j;

    std::cin >> n;
    if(n & 1 == 0)
        n += 1;
    //如果是奇數，那么就構造成偶數,可有可無（狗頭）


    int **time_table = new int*[n+1];
    for(i = 0;i <= n-1;i++)
    {
       time_table[i] = new int[n+1];
    }
    //分配空間

    for(i = 0;i <n/2 ;i++)
         time_table[0][i]= i+1;//給第一行賦值

         calender(time_table,n);
    //分別對右上角，左下角，右下角進行賦值，

    for(int i = 0; i <= n-1; i++) {
        for (int j = 0; j <= n-1; j++)
            std::cout << time_table[i][j] << "|";
        std::cout << std::endl;
    }
    //進行輸出
    return 0;
}
void calender(int **time_table,int n)
{

    if (1 == n)
    {
        time_table[0][0] = 1;
        return;
    }

    calender(time_table,n/2);
    copy_calender(time_table,n);


}

void copy_calender(int **time_table,int n)
{
    int m = n/2;

    for(int i = 0; i < m ; i++)
        for(int j =0; j < m; j++)
        {
            //給右上角賦值
            time_table[i][j+m] = time_table[i][j] + m;
            //右上角賦值給左下角
            time_table[i+m][j] = time_table[i][j+m];
            //左上角賦值給右下角
            time_table[i+m][j+m] = time_table[i][j];
        }
}

運行結果

當n=8時

E:\Clion\C++Projects\untitled4\cmake-build-debug\untitled4.exe
8
1|2|3|4|5|6|7|8|
2|1|4|3|6|5|8|7|
3|4|1|2|7|8|5|6|
4|3|2|1|8|7|6|5|
5|6|7|8|1|2|3|4|
6|5|8|7|2|1|4|3|
7|8|5|6|3|4|1|2|
8|7|6|5|4|3|2|1|

行程已結束，退出代碼 0

當n=4時

E:\Clion\C++Projects\untitled4\cmake-build-debug\untitled4.exe
4
1|2|3|4|
2|1|4|3|
3|4|1|2|
4|3|2|1|

行程已結束，退出代碼 0

壓力測驗

實驗總結

1.分治演算法的基本思想

將一個規模為N的問題，分解成K個規模較小的子問題，這些子問題相互獨立且月原問題性質相同，

求解出子問題的解，合并得到原問題的解，

2.分治演算法特征分析

分治法能解決的問題一般具有以下幾個特征：

1. 該問題的規模縮小到一定程度就可以容易的解決；

2. 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；

3. 利用該問題分解出子問題的解，可以合并為該問題的解；

4. 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題；

分治演算法大多采用遞回實作，第二條特征就反應了遞回思想的參考，

如果滿足了第一條特征和第二條特征，不滿足第三條特征，可以考慮用貪心法或動態規劃法，

如果不滿足第四條特征，也可以用分治法，但是要做很多不必要的作業，重復的解公共的子問題，所以一般用動態規劃法比較好，

3.實際應用場景

二分查找，階乘計算，歸并排序，堆排序、快速排序、傅里葉變換都用了分治法的思想，

4.依據分治法設計程式的思維程序

實際上類似數學歸納法，找到解決本問題的求解方程公式，然后根據方程公式設計遞回程式，

1. 一定是先找到最小問題規模時的求解方法

2. 然后考慮隨著問題規模增大時的求解方法

) 該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質；

3. 利用該問題分解出子問題的解，可以合并為該問題的解；

4. 該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題；

分治演算法大多采用遞回實作，第二條特征就反應了遞回思想的參考，

如果滿足了第一條特征和第二條特征，不滿足第三條特征，可以考慮用貪心法或動態規劃法，

如果不滿足第四條特征，也可以用分治法，但是要做很多不必要的作業，重復的解公共的子問題，所以一般用動態規劃法比較好，

3.實際應用場景

二分查找，階乘計算，歸并排序，堆排序、快速排序、傅里葉變換都用了分治法的思想，

4.依據分治法設計程式的思維程序

實際上類似數學歸納法，找到解決本問題的求解方程公式，然后根據方程公式設計遞回程式，

1. 一定是先找到最小問題規模時的求解方法

2. 然后考慮隨著問題規模增大時的求解方法

3. 找到求解的遞回函式后，設計遞回程式即可，