实验目的和要求

（1）了解前缀编码的概念，理解数据压缩的基本方法；

（2）掌握最优子结构性质的证明方法；

（3）掌握贪心法的设计思想并能熟练运用

（4）设计贪心算法求解多机调度问题；

（5）设计贪心算法求解哈夫曼编码方案；

（6）设计测试数据，写出程序文档。

\* MERGEFORMAT

实验内容

1设有n个活动的集合E={1, 2, …, n}，其中每个活动都要求使用同一资源（如演讲会场），而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si <fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题要求在所给的活动集合中选出最大的相容活动子集。例如，设有11个活动等待安排，这些活动按结束时间的非减序排列如下：

i	1	2	3	4	5	6	7	8	9	10	11
Si	1	3	0	5	3	5	6	8	8	2	12
Fi	4	5	6	7	8	9	10	11	12	13	14

 用两种贪心策略求解该问题。

2设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。

实验环境

     Turbo C 或VC++

实验学时

    2学时，必做实验

核心源代码

1.（1）采用最早结束时间

//
// Created by hp on 2022/10/26.
//

#include "huodong.h"
   #include<iostream>
   using namespace std;

   //活动按照结束时间升序排列
   void sort(int n,int s[],int f[]){
           int temp1,temp2;
           for(int i=0;i<n-1;i++){
                   for(int j=i+1;j<n;j++){
                           if(f[j]<f[i]){
                                   temp1=s[i];s[i]=s[j];s[j]=temp1;
                                   temp2=f[i];f[i]=f[j];f[j]=temp2;
                               }
                       }
               }
       }

   //活动选择与安排
   int ActiveManage(int n,int s[],int f[],bool flag[]){
           //先安排结束时间最早的活动1
           int count=1;
           flag[0]=true;
           //依次考察每一个活动
           int j=0;//第1个活动的结束时间
           for(int i=1;i<n;i++){
                 if(s[i]>=f[j]){
                           flag[i]=true;//安排第i+1个活动
                           j=i;//更新最早的结束时间
                           count++;
                       }else{
                           flag[i]=false;//与当前活动不相容则舍弃
                       }
               }
           return count;
       }

   int main(){
           int n;//活动个数
           int s[100],f[100];//活动的开始时间与结束时间的数组
           bool flag[100];//标志数组，flag[i]=true 表面第i个活动被安排上
            cout<<"请输入活动的总数n：";
           cin>>n;
           cout<<"请分别依次输入每个活动的开始时间与结束时间："<<endl;
           for(int i=0;i<n;i++){
                   cin>>s[i]>>f[i];
               }
            sort(n,s,f);//将活动按照结束时间进行升序排列
           cout<<"按照活动的结束时间进行升序排列后活动顺序如下："<<endl;
           cout<<"序号\t开始时间\t结束时间\t"<<endl;
           for(int i=0;i<n;i++){
                   cout<<i+1<<"\t"<<s[i]<<"\t\t"<<f[i]<<endl;
               }
           cout<<"根据贪心策略共安排了"<<ActiveManage(n,s,f,flag)<<"个活动"<<endl;
           cout<<"活动序列如下：";
           for(int i=0;i<n;i++){
                   if(flag[i]){
                        cout<<i+1<<" ";
                       }
               }
        return 0;
       }

测试结果：

1.（2）采用最早开始时间

//
// Created by hp on 2022/10/26.
//

#include "huodong.h"
   #include<iostream>
   using namespace std;

   //活动按照结束时间升序排列
    void sort(int n,int s[],int f[]){
        int temp1,temp2;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(s[j]<s[i]){
                    temp1=s[i];s[i]=s[j];s[j]=temp1;
                    temp2=f[i];f[i]=f[j];f[j]=temp2;
                }
            }
        }
    }


//活动选择与安排
   int ActiveManage(int n,int s[],int f[],bool flag[]){
           //先安排结束时间最早的活动1
           int count=1;
           flag[0]=true;
           //依次考察每一个活动
           int j=0;//第1个活动的结束时间
           for(int i=1;i<n;i++){
                 if(s[i]>=f[j]){
                           flag[i]=true;//安排第i+1个活动
                           j=i;//更新最早的结束时间
                           count++;
                       }else{
                           flag[i]=false;//与当前活动不相容则舍弃
                       }
               }
           return count;
       }

   int main(){
           int n;//活动个数
           int s[100],f[100];//活动的开始时间与结束时间的数组
           bool flag[100];//标志数组，flag[i]=true 表面第i个活动被安排上
            cout<<"请输入活动的总数n：";
           cin>>n;
           cout<<"请分别依次输入每个活动的开始时间与结束时间："<<endl;
           for(int i=0;i<n;i++){
                   cin>>s[i]>>f[i];
               }
            sort(n,s,f);//将活动按照结束时间进行升序排列
           cout<<"按照活动的结束时间进行升序排列后活动顺序如下："<<endl;
           cout<<"序号\t开始时间\t结束时间\t"<<endl;
           for(int i=0;i<n;i++){
                   cout<<i+1<<"\t"<<s[i]<<"\t\t"<<f[i]<<endl;
               }
           cout<<"根据贪心策略共安排了"<<ActiveManage(n,s,f,flag)<<"个活动"<<endl;
           cout<<"活动序列如下：";
           for(int i=0;i<n;i++){
                   if(flag[i]){
                        cout<<i+1<<" ";
                       }
               }
        return 0;
       }

测试结果：

2.编码方案

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<stdio.h>
using namespace std;
struct Node {
    Node(double d, Node* l = NULL, Node* r = NULL, Node* f = NULL) :data(d), left(l), right(r), father(f) {}
    double data;
    Node* father, * left, * right; //父节点、左右孩子节点
    string code;   //存储哈夫曼编码
};
typedef Node* Tree;
//通过中序，构建编码
void creatCode(Node* node, string s) {
    if (node != NULL) {
        creatCode(node->left, s + '0');
        if (node->left == NULL && node->right == NULL)    //是叶子节点就更新编码
            node->code = s;
        creatCode(node->right, s + '1');
    }
}
int main() {
    vector<double> w;
    vector<Node*> node;
    double tmp;
    Tree tree;
    cout << "请输入各个权值：";
    do {
        cin >> tmp;
        w.push_back(tmp);
    } while (getchar() != '\n');
    sort(w.begin(), w.end(), greater<double>());   //降序排序
    for (int i = 0; i < w.size(); i++)
        node.push_back(new Node(w[i]));
    vector<Node*> out = node;
    Node * left, *right;
    do {
        right = node.back(); node.pop_back();     //取出最小的两个
        left = node.back(); node.pop_back();
        node.push_back(new Node(left->data + right->data, left, right));      //将新结点（求和）推进数组中
        left->father = node.back();          //更新父结点
        right->father = node.back();
        out.push_back(node.back());          //存储此结点
        for (int i = node.size() - 1; i > 0 && node[i]->data > node[i - 1]->data; i--)    //从末尾冒泡，排序
            swap(node[i], node[i - 1]);
    } while (node.size() != 1);      //构建树结构
    tree = node.front();         //剩余的一个结点即根结点
    creatCode(tree, "");
    printf("结点\t父结点\t左孩子\t右孩子\t编码\n");
    for (int i = 0; i < out.size(); i++)
        printf("%.2lf\t%.2lf\t%.2lf\t%.2lf\t%s\n", out[i]->data, out[i]->father == NULL ? 0 : out[i]->father->data, out[i]->left == NULL ? 0 : out[i]->left->data, out[i]->right == NULL ? 0 : out[i]->right->data, out[i]->code.c_str());
    return 0;
}

测试结果：