算法概论实验五

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
实验五

实验目的与要求：掌握动态规划方法的基本思想与设计策略。
1．最长递增子序列问题
【问题描述】
给定一个整数数组，设计一个动态规划算法求出该数组中的最长递增子序列。

2．矩阵连乘问题
【问题描述】
给定n个矩阵{A1，A2，…,An},其中AiAi+1是可乘的，i=1，2，…，n-1,考察这n个矩阵的连乘积A1A2…An，设计一个动态规划算法，求出这个矩阵连乘积问题的最优计算顺序。
实现要求：随机生成n个合法的可连乘的矩阵，以完全加括号的方式输出其最优计算顺序。

#LIS Question
01.jpg-311.8kB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// test5.1.cpp : 
// 1．最长递增子序列问题
//【问题描述】
//给定一个整数数组，设计一个动态规划算法求出该数组中的最长递增子序列。
//

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


// 输出LIS  序列
void outputLIS(int * arr, int index, int lis, int *L)
{
	//终止条件
	if (lis == 0 || index < 0)
		return;

	//找到第一个L[index]==lis
	while (L[index]!=lis && index>0)
		index--;

	//反序输出
	if (index >= 0  && L[index]==lis)
	{
		outputLIS(arr, index - 1, lis - 1, L);
		cout << arr[index] << ",";
	}
}


int LIS(int *a, int n)
{
	//定义一个存取结果的数组
	int *L = new int[n];

	//填写次序 0 to n-1
	for (int j = 0; j < n;j++)
	{
		L[j] = 1;//BaseCase
		//find max L[i]
		for (int i = 0; i < j;i++)
		{
			if (a[i]<a[j] && L[i]+1 > L[j])
			{
				L[j] = L[i] + 1;
			}
		}
	}

	//return the max of L[0~n-1]
	int max = L[0];
	for (int i = 0; i < n; i++)
	{
		//cout << L[i] << "  ";
		if (L[i]>max)
		{
			max = L[i];
		}
	}

	//回溯输出
	cout << "LIS如下：";
	outputLIS(a, n,max, L);
	
	return max;
}

int main()
{
	int a[] = { 5, 2, 8, 6, 3, 6, 9, 7, };
	int n = sizeof(a) / sizeof(int);
	cout<<endl<<"长度为：" << LIS(a, n) << endl;
	return 0;
}

#矩阵连乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<vector>
using namespace std;
vector<int> save;
void getalise(int *v,int n);
void main()
{
	int a[7]={3,4,52,13,8,1,6};
	getalise(a,7);
}
int Max(int a,int b)
{
	return a>b?a:b;
}
void getalise(int *v,int n)
{
	int *pre=new int[n];
	int *max=new int[n];
	for (int i = 0; i < n; i++)
	{
		max[i]=1;
		pre[i]=-1;
	}
	vector<int> *sta= new vector<int>[n];
	for (int i = 0; i < n-1; i++)
	{
		for (int j = i+1; j < n; j++)
		{
			if (v[i]<v[j])
			{
				sta[i].push_back(j);
			}
		}
	}
	for (int i = n-1; i >=0 ; i--)
	{
		for (int j = 0; j < sta[i].size(); j++)
		{
			max[i]=Max(max[i],1+max[sta[i].at(j)]);
			if (max[i]==1+max[sta[i].at(j)])
			{
				pre[i]=sta[i].at(j);
			}
		}
	}
	int idmax=0;
	int temp=-1;
	for (int i = 0; i < n; i++)
	{
		if (temp<max[i])
		{
			idmax=i;
			temp=max[i];
		}
	}
	while (pre[idmax]!=-1)
	{
		cout<<v[idmax]<<" ";
		idmax=pre[idmax];
	}
	cout<<v[idmax];
	delete []pre;
	delete []max;
	delete []sta;
}