算法课习题汇总（3）

循环日程表

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

例如4个人进行比赛：
在这里插入图片描述

思路：

把表格分为四个部分，每个部分的起点分别为红色的圆圈
左上角的坐标为（l，r），表格长度为len/2，表格内的数据为v
右上角的坐标为（l，r+len/2），表格长度为len/2，表格内的数据为v+len/2
左下角的坐标为（l+len/2，r），表格长度为len/2，表格内的数据为v+len/2
右下角的坐标为（l+len/2，r+len/2），表格长度为len/2，表格内的数据为v
递归的结束条件为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=rfor (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;
}