【算法作业】不同策略求GCD，求子集

Uncategorized
1.6k words

问题描述

  1. 给出不同策略求两个数的最大公约数GCD(a,b)，并进行分析。

  2. 给出不同策略列出一个集合的所有子集。

解题思路

T1

这里我提供了三种常见的求最大公约数（GCD）的算法：欧几里得算法、更相减损术和辗转相除的递归形式。

  1. 欧几里得算法：

    • 这个算法是基于一个简单的观察：两个数的最大公约数等于其中较小数与两数相除的余数的最大公约数。
    • 在每次迭代中，算法通过不断取余来缩小问题规模，直到找到余数为0为止。
    • 时间复杂度：欧几里得算法的时间复杂度主要取决于两个数的大小，最坏情况下的时间复杂度为O(log(max(a, b)))。 （时间复杂度请自行证明）

  2. 更相减损术：

    • 这个算法也是基于一个简单的观察：两个数的最大公约数等于它们的差与较小数的最大公约数。
    • 在每次迭代中，算法通过不断相减来缩小问题规模，直到两个数相等为止。
    • 时间复杂度：更相减损术的时间复杂度主要取决于两个数的大小，最坏情况下的时间复杂度为O(max(a, b))。

  3. 辗转相除的递归形式：

    • 这个算法是欧几里得算法的一种递归实现，递归终止条件是其中一个数为0，返回另一个数。
    • 在每次递归调用中，算法通过取余操作来缩小问题规模，直到找到余数为0为止。
    • 相较非递归版本的辗转相除法，递归加上三模运算符版本的简洁性更受算法比赛选手的青睐。
    • 时间复杂度：辗转相除的递归形式与欧几里得算法相同，时间复杂度为O(log(max(a, b)))。

总体而言，欧几里得算法是求最大公约数的最优选择，因为它在平均情况下具有较好的时间复杂度，并且不需要大量的递归调用或大量的相减操作。

T2

  1. **深度优先搜素(DFS)**：

    其实这个DFS思路很容易想到，这个方法更加符合人类的思考习惯。

    • 主函数一个的循环遍历主集合的个数，表示现在要深搜的子集的元素个数。
    • dfs有三个参数，一个是需要的子集的元素个数num。一个是目前搜索到元素个数进行的步数step，也是目前该子集暂时拥有的元素个数。
    • 这个DFS可以做一个最优化剪枝，因为集合具有无序性，所以我们只需要考虑一种顺序即可，就采用从小到大。因此第三个参数是当前状态子集的最大元素x。下一次for循环的起点就等于x + 1。
    • DFS边界条件就是step>num，打印子集，return。
    • 空集单独考虑，拎出来首先单独打印。

    时间复杂度：因为DFS没有搜索多余或是不可能的情况，所以深搜次数就等于子集的个数$2^n$，时间复杂度为O($2^n$)。

  2. 二进制：

利用集合中的元素在子集中的选中与否可以通过二进制数表示的特点（真是个骚操作）。

  • 计算集合的所有子集的总数 totalSubsets，即集合中元素的个数 n 的幂次方，这里使用了 pow 函数来计算。
  • 外层循环遍历所有可能的二进制数，其中二进制数的个数与集合的子集个数相同，即 totalSubsets。
  • 在内层循环中，对集合中的每个元素进行遍历，判断当前元素是否在当前子集中。具体方法是使用按位与操作 i & (1 << j)，其中 i 表示当前二进制数，(1 << j) 表示将 1 左移 j 位，用来判断第 j 位是否为 1。如果结果为非零，则表示第 j 个元素在当前子集中。
  • 如果第 j 个元素在当前子集中，则将其输出。
  • 输出完当前子集的元素后，用退格符 \b 将最后一个多余的逗号删除，以保证输出格式的正确性。

这样，通过遍历所有可能的二进制数，并根据每个二进制数的每一位是否为 1 来选择集合中的元素，最终输出了集合的所有子集。

时间复杂度为：本方法有两层循环，外循环$2^n$次循环，内循环有n次，所以时间复杂度为O($n2^n$)。

完整代码

T1

源代码

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
36
37
38
39
#include <iostream>
using namespace std;

// 欧几里得算法 
int gcd_euclidean(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 更相减损术
int gcd_subtraction(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a;
}

// 辗转相除的递归形式 
int gcd_recursion(int a,int b) {
    return b>0 ? gcd_recursion(b,a%b):a;
}

int main(){
	int a,b;
	cin>>a>>b;
	cout<<"欧几里得算法GCD："<<gcd_euclidean(a,b)<<endl;
	cout<<"辗转相减法GCD: "<<gcd_subtraction(a,b)<<endl;
	cout<<"辗转相减法GCD: "<<gcd_recursion(a,b)<<endl;
	 
	return 0;
}

运行结果

1
2
3
4
12 18
欧几里得算法GCD：6
辗转相减法GCD: 6
辗转相减法GCD: 6

T2

方法一(DFS)

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

int n,a[100];

void dfs(int x,int num,int step){
	if(step > num){
		cout<<"{";
		for(int i=1;i<=num;i++)
			cout<<a[i]<<",";
		cout<<"\b}"<<endl; // "\b"退掉多余的, 
		return ;
	}
	// 最优化剪枝 
	for(int i=x+1;i<=n;i++){
		a[step] = i;
		dfs(i,num,step+1);
	}
}

int main(){
	
	cout<<"请输入正整数集合元素个数：";
	cin>>n;
	cout<<"{}"<<endl;  
	for(int num=1;num<=n;num++){
		dfs(0,num,1);
	}		
	
	
	return 0;
}

运行结果

1
2
3
4
5
6
7
8
9
请输入正整数集合元素个数：3
{}
{1}
{2}
{3}
{1,2}
{1,3}
{2,3}
{1,2,3}

方法二(二进制)

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

using namespace std;

void generateSubsets(int set[], int n) {
    int totalSubsets = pow(2, n);
    // 外层循环遍历所有可能的二进制数
    for (int i = 1; i < totalSubsets; ++i) {
        cout << "{";
        for (int j = 0; j < n; ++j) {
            // 如果当前元素在当前子集中，则输出
            if (i & (1 << j)) { 
			// &是按位与 1<<j转成二进制 
                cout << set[j] << ",";
            }
        }
        cout<<"\b}"<<endl; // "\b"退掉多余的, 
    }
}

int main() {
	int n,set[100];
	cout<<"请输入正整数集合元素个数：";
	cin>>n;
	cout<<"{}"<<endl;
    for(int i = 0;i < n;i++)
		set[i] = i + 1; 
    generateSubsets(set, n);

    return 0;
}

运行结果

1
2
3
4
5
6
7
8
9
请输入正整数集合元素个数：3
{}
{1}
{2}
{1,2}
{3}
{1,3}
{2,3}
{1,2,3}