算法-复习题2

考试总结

致谢：感谢gjx同学的笔记😁以及jjj的txt文本,感谢yfm和tyq同学的纠错，还找了好几个错误🤣

纠错小分队：

• yfm 找出3个错误并且还提供了一个手绘图
• tyq😘 1个错误
• xy 1个错误

看前须知：看每一个题前，需要看红字说明，介绍这个题是考还是不考

点我！我是在线编译网站

如何代码需要输入时，需要在网站这个位置，填上相应数字。

非空子集最好把代码背一下

谢谢美丽的syw🤣,写那么多，真是辛苦啦

#include<iostream>
using namespace std;
int s[4] = {1, 2, 3, 4};
int x[4];
int N = 4;
void SubSet(int i) {
    if(i >= N) {
        for(int j = 0; j < N; j++) 
            if(x[j]) 
                cout << s[j] << " ";
        cout<<endl;
        return;
    }
    x[i] = 1;
    SubSet(i+1);
    x[i] = 0;
    SubSet(i+1);
}

int main() {
    cout << "数组的子集合为：" << endl;
    SubSet(0);
    return 0;
}

分数化简题代码要会背

需要用到欧几里得求最大公约数

#include <iostream>
using namespace std;
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int num1, num2;
    cout << "输入两个分子和分母: ";
    cin >> num1 >> num2;
    int result = gcd(num1, num2);
    cout << "化简结果是：" << num1/result << "/" << num2/result << endl;
    return 0;
}

最长公共子序列（这个写出代码，或者画出表格图，困难😫）

注意：如果代码写不出来，要把矩阵图画出来,需要画2张图，一张s图，一张l图

这张图是网上找的，可以参考一下：

这张图是另外同学提供的，可以自己手算试一下，谢谢yfm同学😍：

书上的内容

这个可以输出具体的子串结果

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
    cin >> n >> a + 1 >> m >> b + 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1; // 如果a[i]和b[j]相等，更新f[i][j]
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    cout << f[n][m] << endl; // 输出最长公共子序列长度

    string res = "";
    for (int i = n, j = m; f[i][j] >= 1;) {
        if (a[i] == b[j]) {
            res += a[i];
            i--; j--;
        }
        else if (f[i - 1][j] >= f[i][j - 1]) i--;
        else j--;
    }
    int k=res.size();
    for(int i=k-1;i>=0;i--)
        cout<<res[i];

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main(){
    cin >> n >> a + 1 >> m >> b + 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            if (a[i] == b[j]) f[i][j] =  f[i - 1][j - 1] + 1; // 如果a[i]和b[j]相等，更新f[i][j]
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        }
    cout << f[n][m] << endl; // 输出最长公共子序列长度
    return 0;
}

测试用例：
6
abcbdb
9
acbbabdbb
结果：5

汉诺塔问题考结果，代码不用背

这个不考代码，考次数,如果给你n个盘子，那么就是需要2ⁿ-1次

这个有点难🤣

圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

例子😃：

• 当n=1时：
  1.将A柱上最后一个圆盘移动到C柱上（A →C）
• 当n=2时：
  1.将1个圆盘从A柱移动到B柱上，重复n=1时的步骤，只不过是将那1个圆盘（从A借助于B移动到C）改为（从A借助于C移动到B）
  2.将A柱上最后一个圆盘移动到C柱上（A →C）
  3.将B柱上的1个圆盘移动到C柱上。重复n=1时的步骤，只不过是将那个圆盘（从A借助于B移动到C）改为（从B借助于A移动到C）
• 当n=3时：
  1.将2个圆盘从A柱移动到B柱上。重复n=2时的步骤，只不过是将那2个圆盘（从A借助于B移动到C）改为（从A借助于C移动到B）
  2.将A柱上最后一个圆盘移动到C柱上（A →C）
  3.将B柱上的2个圆盘移动到C柱上。重复n=2时的步骤，只不过是将那2个圆盘（从A借助于B移动到C）改为（从B借助于A移动到C）
• 当n=4时：
  1.将3个圆盘从A柱移动到B柱上。重复n=3时的步骤，只不过是将那3个圆盘（从A借助于B移动到C）改为（从A借助于C移动到B）
  2.将A柱上最后一个圆盘移动到C柱上（A →C）
  3.将B柱上的3个圆盘移动到C柱上。重复n=3时的步骤，只不过是将那3个圆盘（从A借助于B移动到C）改为（从B借助于A移动到C）

代码实现思路：先将n-1个圆盘从A柱移动到B柱上，然后将A柱上
最后一个圆盘移动到C柱上，最后再把B柱上的n-1个圆盘移动到C柱上。

#include<iostream>
using namespace std;

// 感兴趣自己跑一下
int ans=0;
void HanoiTower(char A, char B, char C, int n){
    if (n == 1){
        cout<<"把第"<<n<<"个圆盘从"<<A<<"--->"<<C<<endl;
        ans++;
    }
    else{
        //将n-1个圆盘从A柱借助于C柱移动到B柱上
        HanoiTower(A, C, B, n - 1);
        //将A柱子最后一个圆盘移动到C柱上
        cout<<"把第"<<n<<"个圆盘从"<<A<<"--->"<<C<<endl;
        ans++;
        //将n-1个圆盘从B柱借助于A柱移动到C柱上
        HanoiTower(B, A, C, n - 1);
    }
}

int main()
{
    int n = 0;
    cout<<"输入A柱子上的圆盘个数：";
    cin>>n;
    //将n个圆盘从A柱借助于B柱移动到C柱上
    HanoiTower('A', 'B', 'C', n);
    cout<<"总共需要移动"<<ans<<"次"<<endl;
    return 0;
}

结论：若只有1个圆盘时，需要移动1次；若有2个圆盘时，需要移动3次；若有3个圆盘时，需要移动7次……不难看出，汉诺塔步数的数学规律为2的n次方减1（n为柱子上的圆盘个数）。所以若有64个圆盘那将会移动2^64-1次.

走台阶问题考结果，代码不用背

不考代码，考数字，按照斐波那契数列随机应变就行

本质是斐波那契数列

问题：
一个楼梯有50个台阶，每一步可以走一个台阶，也可以走两个台阶，请问走完这个楼梯共有多少种方法？

举个例子，假设有3个台阶，则有三种走法：分别是，1-1-1, 1-2, 2-1。

很简单的一道题，学过组合数学的人很快就能想到，这是一个递推关系。假设走完k个台阶有f(k)种走法。

• k = 1时，f(k) = 1
• k = 2时，f(k) = 2
• k = n时，第一步走一个台阶，剩n-1个台阶，有f(n - 1)种走法。第一步走两个台阶，剩n-2个台阶，有f(n - 2种走法。所以共有f(n - 1) + f(n - 2)种走法。于是有如下公式

#include<iostream>
using namespace std;

int fib(int n){
    if(n<2)
        return 1;
    else 
        return fib(n - 1) + fib(n - 2);
}
int main(){
    int n;
    cin>>n;
    cout<<fib(n)<<endl;
    return 0;
}

爬楼梯的前9个数字(例子)：1 2 3 5 8 13 21 34 55 …

快速排序不考代码，考时间复杂度

时间复杂度是nlogn

快速排序过程程是这样的：

• 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列。

3 1 2 5 4 6 9 7 10 8

方法其实很简单： 分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列次左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的次左边（即下标为1），指向数字1。让哨兵j指向序列的最右边（即下标为9），指向数字8。

哨兵i从左往右依次寻找到第一个比基准大的数，哨兵j从右往左依次寻找到第一个比基准小的数，然后交换。

交换：注意：交换之前需要检查i是否小于j，只有i < j的时候才能交换。否则不交换，然后进入最后的基准的位置调整。

再继续往前寻找（哨兵i寻找比基准大，哨兵j寻找比基准小的），直到哨兵i，j相遇或者j < i。

交换：

继续找：

这里由于不满足i < j，因此3和9不会进行交换。退出循环。

现在我们发现以3和9的中间为界，除了基准6以外，比6小的都在左边，比6大的都在右边。因此，此时还需要调整基准的位置。

这里需要注意的是，当选择的基准在最左边时，需要和右指针也就是j做交换；
如果选择的基准在最右边，则基准和左指针i进行交换。

当我们第一次排序结束以后，就需要对原数组进行划分处理，以上一个基准为界，分为两个数组，如下:

然后再对子数组进行上述的排序操作，这是一个递归的思想。

代码如下：

#include<iostream>
using namespace std;
void quick_sort(int q[], int l, int r){
    //递归的终止情况
    if (l >= r) return;
    //选取分界线。这里选数组中间那个数
    int i = l - 1, j = r + 1, x = q[(l + r) /2];
    //划分成左右两个部分
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    //对左右部分排序
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main(){
    int a[5]={9,2,4,7,1};
    quick_sort(a,0,4);
    for(int i=0;i<5;i++)
        cout<<a[i]<<" ";
    return 0;
}

递推关系式推导似乎要考，看一看

给你 F(1)=1,F(n)=F(n-1)+n,求F(n)的表达式。

求2000以内的合数问题背代码

题目要求：找到2000内的合数，并且这个合数的所有因子（除它自己）之和等于这个合数。

// 这个是输出具体因子
#include <iostream>
#include <cstring>
using namespace std;

void isComposite(int num) {
    int x[1000];
    int ans = 0,count=0; 
    if (num < 2) 
        return ;
    memset(x, 0, sizeof(x));
    for (int i = 1; i <= num / 2; i++) {
        if (num % i == 0) {
            ans += i;
            count++;
            x[count] = i;
        }
    }
    if (ans == num){
        cout << ans << "=";
        for (int i = 2; i <= count; i++){
            cout << x[i-1]<< "+";
            if (i == count){
                cout << x[count];
            }
        }
        cout << endl;
    }
}

int main() {
    cout << "2000 以内的合数是:" << endl;
    for (int i = 1; i <= 2000; i++) {
        isComposite(i);
    }
    return 0;
}

精简版

//这个是直接输出结果，不输出因子
#include <iostream>
#include <cstring>
using namespace std;
void isComposite(int num) {
    int ans = 0; 
    for (int i = 1; i <= num / 2; i++)
        if (num % i == 0) 
            ans += i;
    if (ans == num)
        cout << ans << endl;
}

int main() {
    cout << "2000 以内的合数是:" << endl;
    for (int i = 1; i <= 2000; i++) {
        isComposite(i);
    }
    return 0;
}

2000 以内的合数是: 6 28 496
6=1+2+3
28=1+2+4+7+14
496=1+2+4+8+16+31+62+124+248

蛮力法、分治法等思想简答题

蛮力法

蛮力法通过穷举所有可能的解来找到问题的答案，并通过对比来找到最优解或满足特定条件的解。
或者：遍历，采用一定策略依次处理待求解问题所有元素，找出问题的解

分治法

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。

动态规划

（1） 找出最优解的性质，并刻画其结构特征。
（2） 递归的定义最优值。
（3） 以自底向上的方式计算出最优值。
（4） 根据计算最优值得到的信息，构造最优解。

贪心法

目光短浅，只会根据当前已有的信息做出选择，一旦做出选择就不会改变

回溯法

从解空间树的根结点出发，按照深度优先策略搜索满足约束条件的解。在搜索至树中某结点时，先判断该结点对应的部分解是否满足约束条件，如果不满足则剪枝，否则进入以该结点为根的子树继续按照深度优先策略搜索。

杨辉三角这个代码要看懂哈🤣背代码

#include<iostream>
using namespace std;
int fun2(int num){//求num的阶乘
    int sum = 1;
    for (int i = 1; i <= num; i++){
        sum *= i;
    }
    return sum;
}

int fun(int n, int m){
    //求阶乘函数
    int ret = fun2(n);
    int dat = fun2(m);
    int un = fun2(n - m);
    //公式:C(n, m ) = (n)!/ [(m)!(n - m)!]
    return ret / (dat * un);
}

int main()
{
    int n = 0;
    cin>>n;
    //这里i和j要从1开始，否则公式就会出现求负数的阶乘
    for (int i = 1; i <= n; i++){
        // 输出空格可以不要
        // for (int k = 0; k < (n - i); k++){
        //     cout << "  ";           //输出每行前面的空格
        // }
        for (int j = 1; j <= i; j++){
            int C = fun(i - 1, j - 1);//利用公式求每个元素
            cout<<C<<" ";
        }
        cout<<endl;
    }
    return 0;
}

桥本分数式背代码

#include <iostream>
using namespace std;
int sum = 0;
void recursion(int i, int a[]) {
    if (i == 10) {//
        int m1 = a[2] * 10 + a[3];
        int m2 = a[5] * 10 + a[6];
        int m3 = a[8] * 10 + a[9];
        if (a[1] * m2 * m3 + a[4] * m1 * m3 == a[7] * m1 * m2) {
            sum++;
            cout << a[1] << " / " << m1 << " + " << a[4] << " / " << m2 << " = " << a[7] << " / " << m3 << endl;
        }
        return;
    }
    for (int t = 1; t < 10; t++) {
        bool flag = true;
        // 这段代码用于检查当前数字t是否在数组a的前面已经出现过。如果出现过，则将flag设置为false，表示当前数字t无法作为解的一部分。通过这个步骤可以排除重复的数字。
        for (int j = i - 1; j > 0; j--) {
            if (a[j] == t) {
                flag = false;
                break;
            }
        }
        // 前面的数字没有重复的
        if (flag) {
            a[i] = t;
            recursion(i + 1, a);
        }
    }
}

int main() {
    int a[10] = {0};
    recursion(1, a);
    cout << "\n\t总计有" << sum << "种解！" << endl;
    return 0;
}

数字游戏

#include <iostream>
using namespace std;
int sum = 0;
void recursion(int i, int a[]) {
    if (i == 10) {//
        int m1 = a[1] * 10 + a[2];
        int m2 = a[4] * 100 + a[5]*10+a[6];
        int m3 = a[8] * 10 + a[9];
        if (a[3]!=1&&a[7]!=1) {
            if (m1 * a[3] + m2 / a[7] == m3) {
                sum++;
                cout << m1 << " * " << a[3] << " + " << m2 << " / " << a[7] << " - " << m3<<" == 0 " << endl;
            }
        }
        return;
    }
    for (int t = 1; t < 10; t++) {
        bool flag = true;
        // 这段代码用于检查当前数字t是否在数组a的前面已经出现过。如果出现过，则将flag设置为false，表示当前数字t无法作为解的一部分。通过这个步骤可以排除重复的数字。
        for (int j = i - 1; j > 0; j--) {
            if (a[j] == t) {
                flag = false;
                break;
            }
        }
        // 前面的数字没有重复的
        if (flag) {
            a[i] = t;
            recursion(i + 1, a);
        }
    }
}

int main() {
    int a[10] = { 0 };
    recursion(1, a);
    cout << "\n\t总计有" << sum << "种解！" << endl;
    return 0;
}

0/1背包背代码

有n个物品和一个容量为m的背包，每个物品只能选或不选，第i个物品的体积为w[i]，价值为v[i]w:wight v:value，求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];

int main(){
    // n个背包 总体积是m
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ ){
            f[i][j] = f[i - 1][j]; // 初始化
            if (j >= w[i]) f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]); // 转移方程
        }

    cout << f[n][m] << endl; // 输出结果

    return 0;
}

下面是一维dp优化

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int n, m;
// 体积为w[i]，价值为v[i]
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= w[i]; j -- )
            f[j] = max(f[j], f[j - w[i]] + v[i]);

    cout << f[m] << endl; // 输出结果

    return 0;
}

下面是一维dp优化 精简版

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int n, m,v,w;
int f[N];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        // 输入体积w  输入价值v
        cin >> w >> v;
        for(int j = m; j >= w; j--)
            f[j] = max(f[j], f[j - w] + v);
    }
    cout << f[m] << endl; // 输出结果
    return 0;
}

输入格式：
4 5
1 2
2 4
3 4
4 5

解释：4个物品，容量是5，第一个物品体积是1价值是2，… ,最后的输出结果应该是8

埃及分数这个不考的，了解一下吧

要求表示为最少的埃及分数之和的形式，那就要求我们分解出来得到埃及分数的分母尽可能的小。
按照贪心的策略，我们可以在每一次分解时都取出最大的那个埃及分数，也就是分母最小的埃及分数。然后将所给的真分数分解为一个更小的真分数+埃及分
数的形式，然后对该真分数继续分解，直到把真分数都表示成埃及分数的形式。
那么，现在的问题就转成了怎么求出每次的最大的埃及分数了。下面就行相应分析：
假设一个真分数为a/b，那么就有b>a,那么，b就可以表示成以下形式：

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cout << "请输入两个数，分子与分母 ：";
    cin >> a >> b;
    while (a != 0) {
        int k = (b + a - 1) / a; // 向上取整
        cout << "1/" << k << " ";
        a = a * k - b;
        b = b * k;
    }
    return 0;
}

最优二叉查找树

这个是结果:1.4

感谢fyx的结果😁

感谢yfm的结果😁

活动安排问题不考

应该考这个题,贪心算法

活动安排问题：设有n个活动的集合C={1,2,…,n}，其中每个活动都要求使用同一个资源(如会议室)
，而在同一时间内只能有一个活动使用该资源。每个活动i都有要求使用该资源的起始时间si和结束时间fi，且si<
fi。如果选择了活动i使用会议室，那么它在半开区间［si, fi)内占用该资源。如果［si, fi)与［sj,fj)不相交，那么活动i与活动j是相容的。也就是
说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题要求在所给的活动集合中选出最大的相容活动子集，也即尽可能选择更多的活动来使用资源。

#include <iostream>
using namespace std;

const int N = 11;//活动的数量

void GreedySelector(int n, int s[], int f[], bool A[]){
    A[1]=true;//默认将第一个活动先安排
    int j=1;//记录最近一次加入A中的活动
    for (int i=2;i<=n;i++){//依次检查活动i是否与当前已选择的活动相容
        if (s[i]>=f[j]){//下一活动的开始时间晚于之前活动的结束时间
            A[i]=true;//标记该活动是可安排的
            j=i;
        }
        else{
            A[i]=false;//标记该活动是不可安排的
        }
    }
}

int main(){
    int s[] = {0,1,3,0,5,3,5,6,8,8,2,12};        //下标从1开始,存储活动开始时间
    int f[] = {0,4,5,6,7,8,9,10,11,12,13,14};    //下标从1开始,存储活动结束时间
    bool b[N+1];//存储被安排的活动编号
    cout<<"各活动的开始时间,结束时间分别为："<<endl;
    for(int i=1;i<=N;i++){
        cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
    }

    GreedySelector(N,s,f,b);

    cout<<"最大相容活动子集为："<<endl;
    for(int i=1;i<=N;i++){
        if(b[i]){
            cout<<"["<<i<<"]:"<<"("<<s[i]<<","<<f[i]<<")"<<endl;
        }
    }
    return 0;
}

图着色、哈密顿回路（回溯法）

八皇后背代码

代码直接背吧,可能会出个编程大题，这是我能找到的最简单的代码了

这段代码是一个经典的 N 皇后问题的解法。在一个 N × N
的棋盘上，放置N个皇后，使得它们互相之间不能攻击到对方。其中，皇后可以攻击同一行、同一列以及同一对角线上的其他皇后。
代码使用深度优先搜索（DFS）的思想进行求解。通过递归的方式，依次尝试在每一行放置皇后，保证每一行只有一个皇后，并且满足不被其他皇后攻击的
条件。具体实现中使用了三个辅助数组 col、dg 和 udg 来标记列、正对角线和反对角线上的位置是否已经放置了皇后。
在搜索过程中，如果成功放置了 N 个皇后，即找到了一种合法的摆放方式，就输出棋盘的情况，并将结果数量 res 加一。最终输出结果的个数。
这段代码可以帮助解决 N 皇后问题，对于给定的 N 值，求出所有合法的摆放方式，并统计结果的数量。

// N 皇后问题
#include <iostream>
#include <cstring>
using namespace std;

const int N = 20;

int n;
int res;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u){
    if (u == n){
        for (int i = 0; i < n; i++) cout<<g[i]<<endl;
        cout<<endl;
        res++;
        return;
    }
    for (int i = 0; i < n; i++)
        if (!col[i] && !dg[u + i] && !udg[n - u + i]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}

int main(){
    // cin >> n;
    n=8;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            g[i][j] = '.';
    dfs(0);
    cout<<"总共有"<<res<<"个结果";
    return 0;
}

在这段代码中，`dg`和`udg`分别表示主对角线和副对角线上是否存在皇后。
在棋盘上，每个格子可以通过行号和列号来表示，主对角线上的格子具有相同的行号减去列号，而副对角线上的格子具有相同的行号加上列号。
在代码中，`dg[u + i]`表示当前处理的行`u`和列`i`所在的主对角线，而`udg[n - u + i]`表示当前处理的行`u`和列`i`所在的副对角线。
对于每个格子`(u, i)`，如果在主对角线上已经存在皇后，则`dg[u + i]`的值为`true`，否则为`false`。同样地，如果在副对角线上已经存在皇后，则`udg[n - u + i]`的值为`true`，否则为`false`。
在回溯算法中，当我们选择一个格子放置皇后时，需要标记相应的主对角线和副对角线上已经存在皇后，以便在后续的递归过程中判断某个格子是否可放置皇后。

Kruskal算法不考

时间复杂度：ElogE E是边的个数

代码不要记，看看图一乐就行。

想要提升自己的话，代码可以自己看看

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int src;
    int dest;
    int weight;
};

bool compareEdges(const Edge& e1, const Edge& e2) {
    return e1.weight < e2.weight;
}

vector<int> parent;

int findRoot(int vertex) {
    while (parent[vertex] != vertex) {
        vertex = parent[vertex];
    }
    return vertex;
}

void unionVertices(int root1, int root2) {
    parent[root2] = root1;
}

void kruskalMST(vector<Edge>& edges, int numVertices) {
    int numEdges = 0;
    int minCost = 0;

    sort(edges.begin(), edges.end(), compareEdges);

    for (int i = 0; i < numVertices; i++) {
        parent[i] = i;
    }

    for (const Edge& edge : edges) {
        int root1 = findRoot(edge.src);
        int root2 = findRoot(edge.dest);

        if (root1 != root2) {
            cout << "边：" << edge.src << " - " << edge.dest << " (权值: " << edge.weight << ")" << endl;
            minCost += edge.weight;
            unionVertices(root1, root2);
            numEdges++;

            if (numEdges == numVertices - 1) {
                break;
            }
        }
    }

    cout << "最小生成树的总权值为：" << minCost << endl;
}

int main() {
    vector<Edge> edges = {
        {0, 1, 4},
        {0, 2, 3},
        {1, 2, 1},
        {1, 3, 2},
        {2, 3, 4},
        {3, 4, 2},
        {4, 5, 6}
    };

    int numVertices = 6;
    parent.resize(numVertices);

    kruskalMST(edges, numVertices);

    return 0;
}

棋盘覆盖问题不考

使用的是分治法

代码不考，感兴趣看一看得了

#include <iostream>
#include <vector>

using namespace std;

// 棋盘全局变量，使用二维数组表示
vector<vector<int>> board;

// L型骨牌编号，从1到n * n
int tile = 1;

// 棋盘覆盖函数
void chessboardCover(int tr, int tc, int dr, int dc, int size) {
    if (size == 1) {
        return;
    }

    int t = tile++;
    int s = size / 2;

    // 检查特殊方格所在的象限
    if (dr < tr + s && dc < tc + s) {
        // 特殊方格在左上象限
        chessboardCover(tr, tc, dr, dc, s);
    } else {
        // 在左上象限放置一个L型骨牌
        board[tr + s - 1][tc + s - 1] = t;
        // 覆盖其余方格
        chessboardCover(tr, tc, tr + s - 1, tc + s - 1, s);
    }

    if (dr < tr + s && dc >= tc + s) {
        // 特殊方格在右上象限
        chessboardCover(tr, tc + s, dr, dc, s);
    } else {
        // 在右上象限放置一个L型骨牌
        board[tr + s - 1][tc + s] = t;
        // 覆盖其余方格
        chessboardCover(tr, tc + s, tr + s - 1, tc + s, s);
    }

    if (dr >= tr + s && dc < tc + s) {
        // 特殊方格在左下象限
        chessboardCover(tr + s, tc, dr, dc, s);
    } else {
        // 在左下象限放置一个L型骨牌
        board[tr + s][tc + s - 1] = t;
        // 覆盖其余方格
        chessboardCover(tr + s, tc, tr + s, tc + s - 1, s);
    }

    if (dr >= tr + s && dc >= tc + s) {
        // 特殊方格在右下象限
        chessboardCover(tr + s, tc + s, dr, dc, s);
    } else {
        // 在右下象限放置一个L型骨牌
        board[tr + s][tc + s] = t;
        // 覆盖其余方格
        chessboardCover(tr + s, tc + s, tr + s, tc + s, s);
    }
}

// 打印棋盘
void printBoard(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << board[i][j] << "\t";
        }
        cout << endl;
    }
}

int main() {
    int n;
    cout << "输入棋盘尺寸，需要是2^n (n): ";
    cin >> n;

    // 初始化棋盘
    board.resize(n, vector<int>(n, 0));

    int Row, Col;
    cout << "输入特殊单元格的行和列索引: ";
    cin >> Row >> Col;

    // 覆盖棋盘
    chessboardCover(0, 0, Row, Col, n);

    // 打印棋盘
    printBoard(n);

    return 0;
}

最后

• P157 解空间树364个结点，只找14个
• P159 解空间树3906个结点，只搜索了21个
• P162 八皇后问题代码
• 最小生成树、批处理作业调度问题不考
• 子集合问题运算结果按输出顺序写出来
• 哈密顿回路不考
• 杨辉三角给定公式写出代码
• 写不出代码的题写伪代码
• P113 最长公共子序列可以写过程也可以写代码
• P22 递推式子推导
• 给一段代码算时间复杂度
• P118 最优二叉查找树的矩阵数字
• word文档复习课拿下
• 除了分支界限法和减治法的其他方法的思路要写出来
• 2000以内合数
• P115 动态规划01背包代码
• P170 课后习题桥本分数式
• 课后画的习题都得会
• 实验下周日之前全部收齐

祝大家考个好成绩