C語言之實現(xiàn)輾轉(zhuǎn)相除法的兩種方式

更新時間：2023年08月10日 09:45:03 作者：你的代碼沒bug

這篇文章主要介紹了C語言之實現(xiàn)輾轉(zhuǎn)相除法的兩種方式,具有很好的參考價值,希望對大家有所幫助,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

C語言實現(xiàn)輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法

又名“歐幾里德算法”

圖片來自搜狗搜索。

第一種方式

根據(jù)定義就可以寫出一種比較簡單的實現(xiàn)方法：、

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
	int a,b,c;
	scanf("%d %d",&a,&b);
	c=a%b;
	while(c!=0)
	{
		a=b;
		b=c;
		c=a%b;	
	}
	printf("%d",b);//將除數(shù)輸出 
	return 0;
}

第二種方式

熟練掌握輾轉(zhuǎn)相除法之后，可以用遞歸的形式來實現(xiàn)：

#include <stdio.h>
#include <stdlib.h>
//遞歸函數(shù)
int gcd(int a,int b){
	if(b==0) return a;//返回a，即返回上一步的b 
	return gcd(b,a%b);
}
int main(int argc, char *argv[]) {
	int a,b;
	scanf("%d %d",&a,&b);
	printf("%d",gcd(a,b));
	return 0;
}

C語言求最大公約數(shù)（輾轉(zhuǎn)相除法）

歐幾里得算法又稱輾轉(zhuǎn)相除法，是指用于計算兩個非負整數(shù)a，b的最大公約數(shù)。

計算公式為gcd（a，b） = gcd（b，a mod b）= gcd（a mod b，b mod （a mod b））→直到gcd（m，0）。

b處的值放入a，b處的值變?yōu)樵璦的值對原b的值

比如：a=12，b=8，gcd（12，8）=gcd（8，4）=gcd（4，0），所以m=4，即最大公約數(shù)為4。

#include<stdio.h>
int main()
{
	int a=0,b=0;//求a,b的最大公約數(shù)
	scanf("%d %d",&a,&b);
	int m=0;//用于存放最大公約數(shù) 
	int t=0;//設(shè)置一個存放器，用于存放a值 
	while(b!=0)//直到b變量為0，a變量就是所求的最大公約數(shù) 
	{
		t=b; 
		b=a%b;//b為a對b取余數(shù) 
		a=t;//把原來b的值放入a變量中 
	}
	printf("%d",a); 
	return 0;
}

總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

opencv4.5.4+VS2022開發(fā)環(huán)境搭建的實現(xiàn)
本文主要介紹了opencv4.5.4+VS2022開發(fā)環(huán)境搭建的實現(xiàn)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2022-02-02
C語言sizeof與字符串處理與動態(tài)內(nèi)存分配及main函數(shù)參數(shù)詳解
這篇文章主要介紹了C語言字符串處理函數(shù)、sizeof、動態(tài)內(nèi)存分配函數(shù)、main函數(shù)參數(shù)問題，static在修飾變量的時候，如果是修飾全局變量，則跟全局變量功能一樣，通過示例代碼給大家介紹的非常詳細，需要的朋友可以參考下
2022-07-07
詳解C++內(nèi)存的代碼區(qū),全局區(qū),棧區(qū)和堆區(qū)
這篇文章主要為大家介紹了C++內(nèi)存的代碼區(qū),全局區(qū),棧區(qū)和堆區(qū)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助
2021-12-12
利用C語言實現(xiàn)任務(wù)調(diào)度的示例代碼
這篇文章主要為大家詳細介紹了如何利用純C語言實現(xiàn)任務(wù)調(diào)度(可用于STM32、C51等單片機)，文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下
2023-04-04
C++哈希表之閉散列方法的模擬實現(xiàn)詳解
閉散列指（開放定址法）發(fā)生沖突時，如果哈希表沒有被填滿，則表內(nèi)一定還有其他空閑位置，可以把沖突值放到下一個沒有被占用的空余位置上。本文將模擬實現(xiàn)閉散列方法，需要的可以參考一下
2022-11-11
c++驗證哥德巴赫猜想
這篇文章主要介紹了c++驗證哥德巴赫猜想，哥德巴赫猜想就是任一大于2的偶數(shù)，都可表示成兩個素數(shù)之和,需要的朋友可以參考下
2014-04-04
C語言學(xué)生成績管理系統(tǒng)課程設(shè)計
這篇文章主要為大家詳細介紹了C語言學(xué)生成績管理系統(tǒng)課程設(shè)計，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2018-01-01
C++超細致講解隊列queue的使用
隊列先進先出,即只能在容器的末尾添加新元素,只能從頭部移除元素,下面這篇文章主要給大家介紹了關(guān)于C++中隊列queue用法的相關(guān)資料,文中通過示例代碼介紹的非常詳細,需要的朋友可以參考下
2022-05-05
C++動態(tài)內(nèi)存分配（new/new[]和delete/delete[]）詳解
這篇文章主要介紹了C++動態(tài)內(nèi)存分配（new/new[]和delete/delete[]）詳解的相關(guān)資料,需要的朋友可以參考下
2017-05-05
C++實現(xiàn)LeetCode(59.螺旋矩陣之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(59.螺旋矩陣之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
2021-07-07