GXUOJ-算法-第一次作业

1.整数划分

问题描述

GXUOJ | 整数划分

题解

#include<bits/stdc++.h>
using namespace std;
const int N=1010,mod=1e9+7;int n;
int f[N];int main(){cin>>n;f[0]=1;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){f[j]=(f[j]+f[j-i])%mod;}}cout<<f[n];
}

2.汉诺塔

问题描述

GXUOJ | 汉诺塔

题解

#include<bits/stdc++.h>
using namespace std;
int n;void hnt(int n,char A,char B,char C){if(n==1) cout<<"Move disk "<<n<<" from "<<A<<" to "<<C<<endl;else{hnt(n-1,A,C,B);cout<<"Move disk "<<n<<" from "<<A<<" to "<<C<<endl;hnt(n-1,B,A,C);}	
}int main(){cin>>n;hnt(n,'A','B','C');return 0;
}

3.算法训练 排列问题

问题描述

GXUOJ | 算法训练 排列问题

题解

#include <bits/stdc++.h>
using namespace std;// 定义全局变量n表示排列的元素个数，k表示要找的第k个排列
int n, k;
// 二维数组table用于存储限制条件，table[i][j]表示j - 1能否出现在i - 1后面
// 1标识 j-1可以出现在 i-1后面  0 标识不能
// 并保证第i行第i列为0
int table[20][20];
// 数组l用于存储当前生成的排列
int l[20];
// sum用于记录满足条件的排列的数量
int sum = 0;int main() {// 输入排列元素个数n和要找的第k个排列cin >> n >> k;// 读取限制条件表for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {// 输入table[i][j]的值，0表示不能，1表示能cin >> table[i][j];}}// 初始化排列为0到n - 1for (int i = 0; i < n; ++i) {l[i] = i;}// 使用do - while循环生成全排列并检查是否满足条件do {// flag用于标记当前排列是否满足限制条件bool flag = true;// 检查相邻元素是否满足限制条件for (int i = 0; i < n - 1; ++i) {// 如果当前相邻元素不满足限制条件（table值为0）if (!table[l[i]][l[i + 1]]) {// 将flag设为false，表示不满足条件flag = false;// 跳出内层循环，不再继续检查后续相邻元素break;}}// 如果当前排列满足限制条件if (flag) {// 满足条件的排列数量加1sum++;// 如果找到第k个满足条件的排列if (sum == k) {// 跳出外层循环break;}}} while (next_permutation(l, l + n));	//C++标准库中的一个循环结构，用于生成数组l所有元素的全排列 // 输出结果for (int i = 0; i < n; ++i) {// 输出排列中的元素cout << l[i];// 如果不是最后一个元素，则输出一个空格if (i < n - 1) {cout << ' ';}}return 0;
}

思路解析
 

1. 布尔变量 flag 的作用：

   • flag 就像是一个 “标记器”，初始化为 true 时，它假设当前生成的排列是满足所有限制条件的。在后续对排列的检查过程中，如果发现任何不符合限制条件的情况，就把 flag 设为 false。这样，当整个检查过程结束后，通过查看 flag 的值，就能知道这个排列是否满足所有限制条件。

2. for 循环遍历相邻元素对：

   • for (int i = 0; i < n - 1; ++i) 这个循环的目的是依次检查排列中每一对相邻的元素。因为要检查相邻元素关系，所以循环到 n - 1 即可，因为 l[n - 1] 没有下一个相邻元素可检查了。
   • 对于每一对相邻元素 (l[i], l[i + 1])，程序会去查看 table[l[i]][l[i + 1]] 的值。这里的 table 数组存储着限制条件，table[l[i]][l[i + 1]] 表示 l[i + 1] 这个数能否出现在 l[i] 这个数后面。

3. 判断与处理：

   • 如果 table[l[i]][l[i + 1]] 为 0，这就表明在给定的限制条件下，l[i + 1] 不允许出现在 l[i] 后面，也就意味着当前排列不满足限制条件。此时，将 flag 设为 false，并使用 break 跳出内层 for 循环。因为只要发现一对不满足条件的相邻元素，就可以确定整个排列不满足条件了，无需再检查后面的相邻元素对。

4. 实例说明：

   • 假设 n = 3，限制条件 table 如下：

     0 1 1
     1 0 0
     0 1 0
     

      

     并且当前生成的排列 l 为 [1, 0, 2]。

   • 初始化 flag = true。

   • 进入 for 循环：

     • 当 i = 0 时，相邻元素对是 (l[0], l[1])，即 (1, 0)。查看 table[1][0]（因为 l[0]=1，l[1]=0），table[1][0] = 1，说明 0 可以出现在 1 后面，继续循环。
     • 当 i = 1 时，相邻元素对是 (l[1], l[2])，即 (0, 2)。查看 table[0][2]（因为 l[1]=0，l[2]=2），table[0][2] = 1，说明 2 可以出现在 0 后面。

   • 由于整个循环过程中没有出现 table[l[i]][l[i + 1]] 为 0 的情况，所以 flag 仍然为 true，这就表示排列 [1, 0, 2] 满足限制条件。

   • 再假设当前生成的排列 l 为 [0, 2, 1]。

   • 初始化 flag = true。

   • 进入 for 循环：

     • 当 i = 0 时，相邻元素对是 (l[0], l[1])，即 (0, 2)。查看 table[0][2]，table[0][2] = 1，继续循环。
     • 当 i = 1 时，相邻元素对是 (l[1], l[2])，即 (2, 1)。查看 table[2][1]，table[2][1] = 0，这表明 1 不允许出现在 2 后面，所以将 flag 设为 false 并跳出循环。此时就确定排列 [0, 2, 1] 不满足限制条件。

通过这种方式，程序可以逐个检查生成的排列是否符合给定的限制条件。

4.数塔问题

问题描述

GXUOJ | 数塔问题

题解

#include <bits/stdc++.h>
using namespace std;const int MAX_N = 101;int main() {int n;cin >> n; // 读取数塔层数int f[MAX_N][MAX_N]; // 存储数塔的值int a[MAX_N][MAX_N]; // 存储到每个点的最大路径和// 读取数塔的每一层的数字for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {cin >> a[i][j];}}// 初始化最后一层的最大路径和for (int i = 0; i < n; i++) {f[n - 1][i] = a[n - 1][i];}// 从下到上计算每一层的最大路径和for (int i = n - 2; i >= 0; i--) {for (int j = 0; j <= i; j++) {f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];}}// 输出从顶部到底部的最大路径和cout << f[0][0] << endl;return 0;
}