文档章节

两个求最大公约数C/C++算法实现

失落的艺术
 失落的艺术
发布于 07/16 12:15
字数 335
阅读 28
收藏 0
F2
#include<stdio.h> 
#include<time.h> 
#include <iostream>
using namespace std;
//求最大公约数 LCD(Largest Common Division)

//短除法 
//m=8251, n=6105; 
int LCD_ShortDiv(int m, int n) {
	int i, time;
	int f = 1; //相同因子的乘积 
	for(time=0; time<100000000; time++) { 
		for(i=2; i<=m&&i<=n; ) { 
			while(m%i==0&&n%i==0) { 
				f*=i; //将该因子与 前面的因子相乘 
				m/=i; 
				n/=i; 
			} 
			i++; 
		} 
	}
	return f; 
} 

//辗转相除法(欧几里得算法) 
int LCD_EucAlgorithm(int m, int n) {
	int i, f, time;
	for(time=0; time<100000000; time++) { 
		i = m % n; //取余数 
		while(i) {
			m = n; //将小的n替换成m 
			n = i; //将余数i替换成n 
			i = m % n; //再次取余,直到i=0	
		}
	//	return n; //把最后除数返回
	}
	return n; //把最后除数返回
}

int main() { 
	int m=8251, n=6105; 	 
	int f1, f2;
	
	clock_t start, finish; 
	double duration1, duration2; 
	
	start= clock(); 
	f1 = LCD_ShortDiv(m, n);
	finish=clock(); 
	duration1=(double)(finish-start)/CLOCKS_PER_SEC; 
	//printf("time=%lf seconds\n",duration); 
	//printf("result=%d\n",f1); 
	cout << "LCD_ShortDiv用的时间为:"<< duration1 <<endl; 
	cout << "最大公约数为:"<< f1 <<endl; 
	
	start = clock(); 
	f2 = LCD_EucAlgorithm(m, n);
	finish = clock(); 
	duration2 = (double)(finish-start) / CLOCKS_PER_SEC; 
	cout << "LCD_EucAlgorithm用的时间为:"<< duration2 <<endl; 
	cout << "最大公约数为:"<< f2 << endl << endl; 
	cout << "相差倍数:" << duration1 / duration2; 
	
	return 0;
}

证明过程如下:

想成分苹果

证明

一个例题:

例题

做题方法:

方法

© 著作权归作者所有

共有 人打赏支持
失落的艺术
粉丝 1
博文 29
码字总数 11923
作品 0
焦作
程序员
10个经典的C语言编程算法—零基础新手小白也能学会

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
05/31
0
0
【Lesson 5】std::tuple与模板元编程

摘要:本文主要介绍Tuple库的使用,并指导读者用自己的方式来重新实现这个库,以此帮助其学习模板元编程的一些技巧。 推广:数十款阿里云产品限时折扣中,赶紧点击这里,领劵开始云上实践吧!...

李杉杉
04/19
0
0
C语言编程学习:C程序解析:用C语言编写你的第一个自定义函数

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
05/26
0
0
C语言编程基础学习如何定义一维数组和二维数组

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
04/01
0
0
CSDN回帖得分大全(近两年)

√ vs2005调用dll的时候Initialize()函数返回错误 [VC/MFC 基础类] √ 为什么我创建登陆框之后,然后获取登陆框的数据时候总是出现非法操作! [VC/MFC 界面] √ CFileFind::FindFile 支持通配...

junwong
2012/03/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 小心着凉 @红薯

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子:5.33起,其声呜呜然,如怨如慕,如泣如诉。余音袅袅,不绝如缕。分享Arch Enemy的单曲《Bridge Of Destiny (2009)》 《Bridge Of...

小小编辑
今天
170
4
what f,,

anlve
今天
2
0
初级开发-编程题

` public static void main(String[] args) { System.out.println(changeStrToUpperCase("user_name_abc")); System.out.println(changeStrToLowerCase(changeStrToUpperCase("user_name_abc......

小池仔
今天
14
0
现场看路演了!

HiBlock
昨天
21
0
Rabbit MQ基本概念介绍

RabbitMQ介绍 • RabbitMQ是一个消息中间件,是一个很好用的消息队列框架。 • ConnectionFactory、Connection、Channel都是RabbitMQ对外提供的API中最基本的对象。Connection是RabbitMQ的s...

寰宇01
昨天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部