算法课习题汇总（3）

循环日程表

设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N−1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N−1天，要求每天没有选手轮空。

例如4个人进行比赛：

思路：

1. 把表格分为四个部分，每个部分的起点分别为红色的圆圈
2. 左上角的坐标为（l，r），表格长度为len/2，表格内的数据为v
3. 右上角的坐标为（l，r+len/2），表格长度为len/2，表格内的数据为v+len/2
4. 左下角的坐标为（l+len/2，r），表格长度为len/2，表格内的数据为v+len/2
5. 右下角的坐标为（l+len/2，r+len/2），表格长度为len/2，表格内的数据为v
6. 递归的结束条件为l==r，将数组进行赋值即可返回
   

#include<iostream>
using namespace std;

int a[100][100];
void f(int l, int r, int len, int v)
{
if (len == 1)
{
a[l][r] = v;
return;
}
f(l, r, len / 2, v);
f(l, r + len / 2, len / 2, v+len/2);
f(l + len / 2, r, len / 2, v+len/2);
f(l + len / 2, r + len / 2, len / 2, v);
}

int main()
{
int n;
cin >> n;
f(1, 1, n, 1);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl;
return 0;
}

矩阵连乘问题

给定n个矩阵{A1, A2, A3, …, An}，其中矩阵Ai的维度为Pi-1 x Pi（i=1, 2, …, n），且满足Ai的列数等于Ai+1的行数（即Pi = Pi+1，i=1, 2, …, n-1），要求计算这n个矩阵的连乘积A1A2…An，并寻找一种计算次序，使得所需的标量乘法次数最少。

方法一：递归

#include<iostream>
using namespace std;

int p[100], m[100][100];

int f(int i, int j)
{
if (m[i][j])
return m[i][j];//当该数不为0时则表示该数已经计算过了，直接跳过即可
if (i == j)
return 0;
int min = 1000000;
for (int k = i; k < j; k++)//Ai.....Ak||Ak+1....Aj
{
int tmp = f(i, k) + f(k + 1, j) + p[i - 1] * p[k] * p[j];
if (tmp < min)
min = tmp;
}
return m[i][j]=min;
}

int main()
{
int n;
cin >> n;
for (int i = 0; i <= n; i++)
cin >> p[i];
cout << f(1, n) << endl;
return 0;
}

方法二：动态规划

int m[100][100], p[100], s[100][100];

void f(int l, int r)
{
if (l == r)
{
cout << "A" << r;
return;
}
int k = s[l][r];
cout << "(";
f(l, k);
f(k + 1, r);
cout << ")";
}

int main()
{
int n;
cin >> n;
for (int i = 0; i <= n; i++)
cin >> p[i];
for (int r = 2; r <= n; r++)
{
//Ai....Ak||Ak+1....An  n-i+1=r
for (int i = 1; i <= n - r + 1; i++)
{
int j = r + i - 1;
m[i][j] = 1000000;
for (int k = i; k < j; k++)
{
int tmp = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
if (tmp < m[i][j])
{
m[i][j] = tmp;
s[i][j] = k;
}
}
}
}
f(1, n);
cout << endl;
cout << m[1][n] << endl;
return 0;
}

原文地址：https://blog.csdn.net/2302_79180171/article/details/142615057

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！