[c语言日寄]论地球online新手程序猿是什么时候意识到算法的重要性~[链表][免费全代码][辗转相除法][欧几里得算法][详细分析]

siy2333

发布于 2025-02-05 12:46:41

5100

代码可运行

文章被收录于专栏：来自csdn的博客来自csdn的博客

运行总次数：0

代码可运行

在今天的快乐刷题中，博主遇到一个很哟西的题目：

题目内容

给定两个数，求这两个数的最大公约数

例如：输入：20 40 输出：20

博主的答案

思路与框架

题目内容简洁明了，稍微思考了一下给出一下算法框架： 1.scanf接受输入的数字 2.使用取余数求得两个数的所有公约数 3.使用链表储存两个数的公约数 4.遍历求得最大公约数

具体实现

头文件部分

#include<stdio.h>
#include<stdlib.h>

第一个头文件大家应该都知道，标准输入输出嘛。第二个头文件主要是为malloc函数服务的，这个函数是动态内存分配的核心函数。

链表结构体定义

//链表结构体
struct divisor {
    int common;
    struct divisor* next;
};

//简化结构体名称
typedef struct divisor DIV;

这里俺定义了一个链表结构体divisor，包含一个整数common（用于存储因式）和一个指向下一个节点的指针next。然后又使用typedef简化了结构体的名称为DIV，使得代码更简洁，易读。

主函数

int main() {
    int num1, num2;
    printf("请输入2个正整数,中间使用空格分隔：");
    scanf_s("%d%d", &num1, &num2);
    
    DIV *list1_head = MakeListsed();
    DIV *list2_head = MakeListsed();
    
    common(num1,list1_head);
    common(num2,list2_head);

    sort(list1_head, list2_head);

    return 0;
}

博主使用的是VS，所以用scanf_s 函数代替scanf 函数（Microsoft特有的scanf函数报错）。不过这里还可以添加一些诸如用户输入有效性检查之类的东西。其他的函数我会在下文一一展示。

MakeListsed函数：建立链表并返回头指针

DIV *MakeListsed() {
    DIV* head = NULL;
    
    head = (DIV*)malloc(sizeof(DIV));
    if (head == NULL) {
        printf("Error: 无法分配头节点内存单元");
        return (NULL);
    }
    head->next = NULL;
    head->common = 0;
    return head;
}

这个函数创建一个链表的头节点，并返回头节点的指针。如果malloc(分配内存函数)失败，函数会打印错误信息并返回NULL~

common函数：找出公因子并储存到链表里

void common(int num, DIV* list_head) {
    DIV* tail = list_head;
    
    for (int i = 1; i <= num; i++) {
        if (num % i == 0) {
            tail = write(tail, i);
        }
    }
}

这个b遍历从1到num的所有整数，找出所有公因数，并将它们添加到链表中。可以添加一个检查点，检查write函数是否成功添加节点，不过我比较懒，没有弄（doge）。

write函数：链表写入

DIV* write(DIV* tail, int num) {
    DIV * pnew;
    pnew = (DIV*)malloc(sizeof(DIV));
    if (pnew == NULL) {
        printf("Error: 无法分配新结点内存单元");
        return (NULL);
    }
    pnew->common = num;
    pnew->next = NULL;
    tail->next = pnew;
    return pnew;
}

这个坨可以在链表的末尾添加一个新的节点，包含一个公因数。如果malloc失败，函数会打印错误信息并返回NULL。

sort函数：比较出最大公因数

void sort(DIV* head1, DIV* head2) {
    DIV* p, *q;
    int max = 1;
    
    for (p = head1->next; p != NULL; p = p->next) {
        for (q = head2->next; q != NULL; q = q->next) {
            if (p->common == q->common) { 
                max = (p->common); 
            }
        }
    }
    printf("他们的最大公因式为%d", max);
}

如题，这个函数的目的是找出两个链表的公共元素，即最大公因数。 max的作用是储存局部比较中最大的公因式，以谋求全局最大公因式。这里由于链表的建立过程已经使得公因式由小到大排列，所以使用遍历两两比较公因式是否相等，相等就一定比原来的max大，故可以直接更新max的值。

总结

博主废了九牛二虎之力，花费了90行代码和很多头发，最终还是解决了这一个问题。虽然中间排查bug很痛苦，但是看到最后成果破解了这一道题目，俺也是流下了欣慰的眼泪QWQ。（为方便阅读，全过程代码放在文末）

大佬的代码

秉持者人外有人，天外有天的想法，我查看了榜一大哥的算法。

#include <stdio.h>
int gcd(int a, int b);
int main() {
    int num1, num2;
    printf("请输入两个正整数：");
    scanf("%d %d", &num1, &num2);
    printf("最大公因数是：%d\n", gcd(num1, num2));
    return 0;
}

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

没……没了？这TM只有18行？？？？一想到我用了90行代码实现这玩意，我就要爆炸了啊啊啊TAT

辗转相除法（也称为欧几里得算法）

于是我去网上查询一下相关资料，这里的gcd函数运用了辗转相除法。

辗转相除法，也称为欧几里得算法（Euclidean algorithm），是一种求两个正整数的最大公约数（Greatest Common Divisor，GCD）的方法。这种方法基于一个简单的原理：两个整数的最大公约数不变，即使将较大的数字替换为这两个数的差。

具体步骤如下：

输入两个正整数：设这两个数为a和b，其中a > b。
用较小的数去除较大的数：将a除以b，得到商q和余数r，即a = bq + r，其中0 ≤ r < b。
替换较大的数：将a替换为b，将b替换为r。
重复步骤2和3：继续用新的b去除新的a，直到余数r为0。
得到最大公约数：当余数r为0时，最后的除数b就是a和b的最大公约数。

举个例子，求48和18的最大公约数：

48除以18，商为2，余数为12（48 = 18 * 2 + 12）。
将48替换为18，将18替换为12，然后用18除以12。
18除以12，商为1，余数为6（18 = 12 * 1 + 6）。
将18替换为12，将12替换为6，然后用12除以6。
12除以6，商为2，余数为0（12 = 6 * 2 + 0）。
余数为0，所以6就是48和18的最大公约数。

没错，这就解决了！！高质量的算法竟然和普通算法差别这么大！所以大家一定要和博主一起学好数学啊（哭）

博主的菜鸡完整代码

#include<stdio.h>
#include<stdlib.h>

//链表结构体
struct divisor {
	int common;
	struct divisor* next;
};

//简化结构体名称
typedef struct divisor DIV;

void common(int num, DIV* list_head);
DIV* MakeListsed();
DIV* write(DIV* tail, int num);
void sort(DIV* head1, DIV* head2);

int main() {

	int num1, num2;
	printf("请输入2个正整数,中间使用空格分隔：");
	scanf_s("%d%d", &num1, &num2);
	
	DIV *list1_head = MakeListsed();
	DIV *list2_head = MakeListsed();
	
	common(num1,list1_head);
	common(num2,list2_head);

	sort(list1_head, list2_head);

	return 0;
}

//找出公因子
void common(int num, DIV* list_head) {
	DIV* tail = list_head;
	
	for (int i = 1; i <= num; i++)//遍历数组
	{
		if (num % i == 0) {
			tail = write(tail, i);
		}
	}
}


//创建链表
DIV *MakeListsed(){

	DIV* head = NULL;
	
	head = (DIV*)malloc(sizeof(DIV));//创建头节点
	if (head == NULL) {
		printf("Error: 无法分配头节点内存单元");
		return (NULL);
	}
	head->next = NULL;//头节点的指针域置NULL
	head->common = 0;
	return head;//返回头节点地址
}

//链表写入
DIV* write(DIV* tail, int num) {
	DIV * pnew;
	pnew = (DIV*)malloc(sizeof(DIV));
	if (pnew == NULL)
	{
		printf("Error: 无法分配新结点内存单元");
		return (NULL);
	}
	pnew->common = num;//新结点存入数据
	pnew->next = NULL;//新结点指针域置NULL

	tail->next = pnew;//新结点插入链表尾
	return pnew;//返回尾结点
}

//比较排序
void sort(DIV* head1,DIV* head2){
	DIV* p, *q;
	int max = 1;

	for (p = head1->next;p != NULL;p = p->next) {
		for (q = head2->next;q != NULL; q = q->next ) {
			if (p->common == q->common) { max = (p->common); }
		}
	}
	printf("他们的最大公因式为%d", max);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-05，如有侵权请联系 cloudcommunity@tencent.com 删除

程序