哈工程——算法实验代码&报告最新版

哈工程——算法实验代码&报告

#include 
using namespace std;

const int N = 7;//凸多边形边数+1
int weight[][N] = {{022355}{201523}{210224}{352062}{121601}{434210}};//凸多边形的权

int MinWeightTriangulation（int nint **tint **s）;
void Traceback（int iint jint **s）;//构造最优解
int Weight（int aint bint c）;//权函数

int main（）
{
	int **s = new int *[N];
    int **t = new int *[N];
    for（int i=0;i    {
        s[i] = new int[N];
        t[i] = new int[N];
    }
    cout<<“此多边形的最优三角剖分值为：“<    cout<<“最优三角剖分结构为：“<    Traceback（15s）; //s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置

    return 0;
}

int MinWeightTriangulation（int nint **tint **s）
{
    for（int i=1; i<=n; i++）
    {
        t[i][i] = 0;
    }
    for（int r=2; r<=n; r++） //r为当前计算的链长（子问题规模）
    {
        for（int i=1; i<=n-r+1; i++）//n-r+1为最后一个r链的前边界
        {
            int j = i+r-1;//计算前边界为r，链长为r的链的后边界

            t[i][j] = t[i+1][j] + Weight（i-1ij）;//将链ij划分为A（i） * （ A[i+1:j] ）这里实际上就是k=i

            s[i][j] = i;

            for（int k=i+1; k            {
                //将链ij划分为（ A[i:k] ）* （A[k+1:j]）
                int u = t[i][k] + t[k+1][j] + Weight（i-1kj）;
                if（u                {
                    t[i][j] = u;
                    s[i][j] = k;
                }
            }
        }
    }
    return t[1][N-2];
}

void Traceback（int iint jint **s）
{
    if（i==j） return;
    Traceback（is[i][j]s）;
    Traceback（s[i][j]+1js）;
    cout<<“三角剖分顶点：V“<}

int Weight（int aint bint c）
{
     return weight[a][b] + weight[b][c] + weight[a][c];
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-12-05 18:42  2014061523王延康\
     目录           0  2016-12-05 13:22  2014061523王延康\C++\
     目录           0  2016-12-05 18:26  2014061523王延康\C++\凸多边形最优三角剖分\
     文件        1848  2016-12-05 14:07  2014061523王延康\C++\凸多边形最优三角剖分\TheOptimalTriangulation.cpp
     文件     1048872  2016-12-05 18:26  2014061523王延康\C++\凸多边形最优三角剖分\TheOptimalTriangulation.exe
     文件        3199  2016-12-05 18:26  2014061523王延康\C++\凸多边形最优三角剖分\TheOptimalTriangulation.o
     目录           0  2016-12-05 18:24  2014061523王延康\C++\哈夫曼编码\
     文件        2477  2016-12-05 14:07  2014061523王延康\C++\哈夫曼编码\HuffmanEncoding.c
     文件       29724  2016-12-05 18:24  2014061523王延康\C++\哈夫曼编码\HuffmanEncoding.exe
     文件        2027  2016-12-05 18:24  2014061523王延康\C++\哈夫曼编码\HuffmanEncoding.o
     文件         661  2016-04-24 19:33  2014061523王延康\C++\哈夫曼编码\base1.h
     文件         251  2002-05-29 14:13  2014061523王延康\C++\哈夫曼编码\base2.h
     文件        1880  2016-12-05 14:11  2014061523王延康\ReadMe.txt
     目录           0  2016-12-05 13:22  2014061523王延康\java\
     目录           0  2016-12-05 13:16  2014061523王延康\java\ALGO_LAB_2014061523\
     文件         303  2016-12-05 10:45  2014061523王延康\java\ALGO_LAB_2014061523\.classpath
     文件         395  2016-12-05 10:45  2014061523王延康\java\ALGO_LAB_2014061523\.project
     目录           0  2016-12-05 13:16  2014061523王延康\java\ALGO_LAB_2014061523\.settings\
     文件          97  2016-12-05 12:52  2014061523王延康\java\ALGO_LAB_2014061523\.settings\org.eclipse.core.resources.prefs
     文件         603  2016-12-05 10:45  2014061523王延康\java\ALGO_LAB_2014061523\.settings\org.eclipse.jdt.core.prefs
     目录           0  2016-12-05 13:16  2014061523王延康\java\ALGO_LAB_2014061523\bin\
     目录           0  2016-12-05 13:16  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\
     文件        1927  2016-12-05 11:25  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\ActivityArrangementProblem.class
     文件        3680  2016-12-05 12:51  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\BBKnapsack.class
     文件         433  2016-12-05 12:51  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\BBnode.class
     文件        1058  2016-12-05 10:57  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\BinarySearch.class
     文件         738  2016-12-05 12:51  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\Element.class
     文件         845  2016-12-05 12:51  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\HeapNode.class
     文件         298  2016-12-05 13:11  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\HuffmanEncoding.class
     文件         941  2016-12-05 11:35  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\Knapsack$Element.class
     文件        3309  2016-12-05 11:35  2014061523王延康\java\ALGO_LAB_2014061523\bin\algo_lab_code\Knapsack.class
............此处省略46个文件信息