C++经典问题

竞赛 / 算法 / 经典问题
Word count: 3.1k   |   Reading time≈ 14 min

C++经典问题

求整数的两个质数因子

关键理论：\textcolor{red}{关键理论：}

质数分解唯一性是一个重要的数论概念，它指出任何一个大于1的正整数都可以被唯一地表示成若干个质数的积。

具体来说，对于一个大于1的正整数n，它可以写成以下形式的质因数积：

n = p1^k1 * p2^k2 * … * pn^kn

其中p1, p2, …, pn为质数，k1, k2, …, kn为正整数。这个表示方式称为n的质因数分解式，也称为n的标准分解式。

质数分解唯一性指出：任何一个正整数n都有且仅有一种质因数分解式。也就是说，不管用什么方法，只要将n分解成若干个质数的积，得到的分解式都是唯一的。

这个性质在数论和其它领域中都有广泛的应用。例如，在密码学中，**RSA公钥加密算法**就是基于质数分解唯一性的安全性原理而设计的。

1
2
3
4
5
6
7
8
// 计算两个质数p，q
for(ll i=2;i<sqrt(n);++i) {// "质数分解唯一性":一个数有且只有1种质因数分解式
    if(n%i==0){
        p = i, q = n/i;
        break;
    }
}
cout<<p<<" "<<q;

求整数的所有因子

1
2
3
for (int k = 1; k <= n; k++)
	if (n % k == 0)
		cout << k << " ";

背包问题

  1. 01背包问题（每种物品只能选一次）

  2. 完全背包问题（每种物品都可以选无限次）

  3. 多重背包问题（每种物品具有不同的选择上限）

    • 可以转换为01背包问题；
    • 或是添加附加数量限制条件；

3.多重背包问题

转换为01背包问题

解法代码：

1
// 按照别人AC的代码写的居然死活过不了？？？
添加附加数量限制条件

解法代码：

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
#include<bits/stdc++.h>
using namespace std;
// 多重背包问题 ——添加附加数量限制条件 
const int N = 1e3+10;
int dp[N][N], v[N], w[N], s[N];// v体积，w价值，s数量 
int n, V;
int f[N];

int main() {
	cin>>n>>V;
	for(int i=1;i<=n;++i){
		cin>>v[i]>>w[i]>>s[i];
	}
	for(int i=1;i<=n;++i){
		for(int j=0;j<=V;++j){
			for(int k=0;k<=s[i];++k){// 这里的k必须从0开始,k=0时有dp[i-1][j] 
				if(j>=k*v[i]){
					dp[i][j] = max(dp[i][j], dp[i-1][j-k*v[i]]+k*w[i]);// 在01-背包问题的基础上作次数限制 
				}
			}
		}
	}
	//空间压缩
//	for(int i=1;i<=n;++i){
//		for(int j=V;j>=v[i];--j){
//			for(int k=1;k*v[i]<=j&&k<=s[i];++k){
//				f[j] = max(f[j], f[j-k*v[i]]+k*w[i]);
//			}
//		}
//	}
	cout<<dp[n][V];
//	cout<<f[V];
	return 0;
}

01背包与完全背包问题可以参考PDF:LeetCode 101;

判断闰年

如果一个年份能够被4整除但不能被100整除，或者能够被400整除，则该年份是闰年。

1
(year%4==0&&year%100!=0)||(year%400==0)

LCS

在C++中，LCS是最长公共子序列（Longest Common Subsequence）的缩写，它是一种经典的计算机科学问题，通常用于比较两个字符串或序列之间的相似性。给定两个序列X和Y，LCS问题的目标是找到一个最长的序列Z，使得Z既是X的子序列又是Y的子序列。

LCS问题在自然语言处理、生物信息学、数据压缩等领域都有广泛应用。C++提供了许多实现LCS问题的算法，包括动态规划、贪心算法、分治算法等。

下面是一个使用动态规划算法实现LCS问题的C++代码示例：

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
#include <iostream>
#include <cstring>

using namespace std;

int lcs(string X, string Y)
{
    int m = X.length();
    int n = Y.length();
    int L[m + 1][n + 1];
    
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                L[i][j] = 0;
            } else if (X[i - 1] == Y[j - 1]) {
                L[i][j] = L[i - 1][j - 1] + 1;
            } else {
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
            }
        }
    }
    
    return L[m][n];
}

int main()
{
    string X = "AGGTAB";
    string Y = "GXTXAYB";
    
    cout << "Length of LCS is " << lcs(X, Y);
    
    return 0;
}

该程序使用二维数组L[m+1][n+1]存储最长公共子序列长度的计算结果。在计算L[i][j]时，如果字符串X的第i个字符等于字符串Y的第j个字符，则L[i][j]的值为L[i-1][j-1]+1；否则，L[i][j]的值为L[i-1][j]和L[i][j-1]中的较大值。最终，函数返回L[m][n]的值，即X和Y的最长公共子序列的长度。

LIS

C++ LIS 是指最长上升子序列（Longest Increasing Subsequence）的算法实现，它是一种常用的动态规划算法。在一个序列中找到一个最长的子序列使得这个子序列中的所有元素都按照顺序递增排列，这个子序列就被称为最长上升子序列。

C++ 中可以使用动态规划来解决最长上升子序列问题，具体实现步骤如下：

  1. 定义一个长度为 n 的数组 dp，dp[i] 表示以第 i 个元素结尾的最长上升子序列的长度。

  2. 初始化 dp 数组，将每个元素的最长上升子序列长度初始化为 1。

  3. 遍历数组，对于每个元素 i，从头开始遍历到 i - 1，如果发现一个元素 j 比 i 小，并且 dp[j] + 1 > dp[i]，则更新 dp[i] 的值为 dp[j] + 1。

  4. 最后遍历整个 dp 数组，找到最大的 dp[i] 值即可。

C++ LIS 算法的时间复杂度为 O(n^2)，因此，在处理较长的序列时，该算法可能会比较耗时。

下面是 C++ 实现最长上升子序列（LIS）的典型代码：

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
#include <iostream>
using namespace std;

int lis(int arr[], int n) {
    int dp[n];
    for (int i = 0; i < n; i++)
        dp[i] = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int max_len = 0;
    for (int i = 0; i < n; i++)
        max_len = max(max_len, dp[i]);
    return max_len;
}

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

在该实现中，lis() 函数计算最长上升子序列的长度。首先创建一个大小为 n 的数组 dp，并将所有元素初始化为 1。然后，使用嵌套的循环遍历整个数组，如果找到一个比当前元素小的元素，则更新 dp[i] 的值。最后，遍历整个 dp 数组，找到最大的值即为最长上升子序列的长度。

编辑距离

  1. 编辑距离为两个字符串，a 和 b 通过多少次变换，使得 a 变成 b。

  2. 修改包含三种：

    1. 删除操作，将 a[i] 从 a 中移除
    2. 插入操作，在 a[i] 后加上 b[j]
    3. 替换操作，将 a[i] 修改为 b[j]

  3. 初始状态，i=j=0，都在字符串的开头。

    然后开始判断 a[i]=?b[j]

    • 如果相同，那么就不需要修改，所以dp[i+1][j+1]=dp[i][j]

      所以在a[i-1]等于b[j-1]时，dp[i][j]这个状态由dp[i-1][j-1]转移而来。

      dp[i][j]=dp[i-1][j-1]

    • 如果不同，那就需要进行三种可能的操作

    1. 修改操作：

      a[i] 修改为 b[j]， 因为编辑了一次，所以+1

      dp[i+1][j+1]=dp[i][j]+1

      所以在a[i-1]不等于b[j-1]时，dp[i][j]这个状态由dp[i-1][j-1]转移而来。

      dp[i][j]=dp[i-1][j-1]+1

    2. 删除操作，直接把 a[i] 删除，此时转移到 dp[i][j+1] ，因为 a[i] 被删除，但是下一个字符到了 a[i] 的位置，而对应比较的位置到了b[j+1]。

      所以此时状态转移到了dp[i][j+1]

      dp[i][j+1]=dp[i][j]+1

      因为编辑了一次，所以+1

      所以在a[i-1]不等于b[j-1]时，dp[i][j]就有可能通过dp[i-1][j]转移而来。

    3. 插入操作，在a[i]后添加一个b[j]，那么此时a[i+1]和b[j]对应，因为加了一个字符就变成了a[i+1],而且跟b[j]对应，那么下一个状态转移到了dp[i+1][j]

      dp[i+1][j]=dp[i][j]+1

      此时状态转移到了 dp[i+1][j]=dp[i][j]+1

      因为编辑了一次，所以+1

      所以在a[i-1]不等于b[j-1]时，dp[i][j]就有可能通过dp[i][j-1]转移而来。

    那么不同时，我们选择他们的最小值即可。

模版代码：

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
#include<iostream>
#include<algorithm>
#include<set>
#include<string>

using namespace std;
#define INF 99999999
string s, t;
int dp[1010][1010];

void init(){
    for (int i = 0; i <= s.size(); i++) dp[i][0] = 0;
    for (int j = 1; j <= t.size(); j++) dp[0][j] = INF;// 这里不能用INT_MAX，因为后面有+1操作，这样会使得INT_MAX+1为负数,那么min求得的就是负数,不是最终答案 
}

int main() {
    cin >> s >> t;
    
    init();
    
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 1; j <= t.size(); j++) {
            if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else  
                dp[i][j] = min(dp[i - 1][j - 1],min(dp[i - 1][j], dp[i][j - 1])) + 1;
        }
    }
    cout << dp[s.size()][t.size()];
    return 0;
}

最大公约数

以下是使用C++求最大公约数的两种方法：

方法一：辗转相除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;

int gcd(int x, int y) {
    if (x < y) swap(x, y);
    while (y != 0) {
        int r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

方法二：递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;

int gcd(int x, int y) {
    if (x % y == 0) return y;
    else return gcd(y, x % y);
}
// 或者写成：
int gcd(int a, int b) { // 辗转相除法的递归实现
	return b==0?a:gcd(b, a%b);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

这两种方法都可以求出最大公约数，其中辗转相除法比较容易理解，而递归法则比较简洁。

最小公倍数

可以通过先求最大公约数，再用两个数的乘积除以最大公约数来求得最小公倍数。

以下是一个C++函数实现：

1
2
3
4
5
6
7
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

其中gcd函数为求最大公约数的函数，lcm函数则调用了gcd函数来求解最小公倍数，返回值即为a和b的最小公倍数。

蛇形填数

以8*8的填充矩阵为例：

填充顺序

实现代码：

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
/**
*	矩阵的左上三角形与右下三角形的填充规则是不同的
*/
#include<bits/stdc++.h>
using namespace std;

int n;//扫描数据的个数
double M[8][8];//填充矩阵 
//针对蛇形填充——定义4个方向 ：右，左下，下，右上(上三角形);(下三角形)需要交换dx[0]与dy[0]以及dx[2]与dy[2] 
int dx[4]={1,-1,0,1},dy[4]={0,1,1,-1};//dx控制列，dy控制行 

int main() {
	cin>>n;
	memset(M,0,sizeof(M));//赋值全0 
	int y=0,x=0,md=0;
	cin>>M[y][x];
	for(int i=1;i<n;++i){//循环直到将所有的数据填充到矩阵中 
		y+=dy[md];
		x+=dx[md];
		cin>>M[y][x];
		if(md==0||md==2)md=(md+1)%4;//每一次在经过向右或向下操作后，需要转换为左下或右上。 
		else if(md==1||md==3){//确保是因下或右上操作
			if(x==0||y==0||x==7||y==7)md=(md+1)%4;//左下或右上达到矩阵边界之后需要进行操作的切换 
		}
		if(y==7&&x==0){//遍历到了右下三角形，需要交换dx[0]与dy[0]以及dx[2]与dy[2]
			swap(dx[0],dy[0]);
			swap(dx[2],dy[2]);
		}
	}
	return 0;
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2024 Guijie Wang
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信