文档章节

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

失落的艺术
 失落的艺术
发布于 07/16 12:15
字数 335
阅读 11
收藏 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
CSDN回帖得分大全(近两年)

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

junwong
2012/03/09
0
0
C语言编程基础学习如何定义一维数组和二维数组

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

小辰带你看世界
04/01
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

day63-20180821-流利阅读笔记-待学习

性别歧视在日本:“我是女生,所以社会不让我学医” 毛西 2018-08-21 1.今日导读 大家在看病的时候,有留意过女医生的比例吗?在性别歧视现象十分严重的日本,男医生和女医生的比例达到了惊人...

aibinxiao
39分钟前
2
0
Ubuntu18.04 显卡GF-940MX安装NVIDIA-390.77

解决办法: 下面就给大家一个正确的姿势在Ubuntu上安装Nvidia驱动: (a)首先去N卡官网下载自己显卡对应的驱动:www.geforce.cn/drivers (b)下载后好放在英文路径的目录下,怎么简单怎么来...

AI_SKI
今天
4
0
深夜胡思乱想

魔兽世界 最近魔兽世界出了新版本, 周末两天升到了满级,比之前的版本体验好很多,做任务不用抢怪了,不用组队打怪也是共享拾取的。技能简化了很多,哪个亮按哪个。 运维 服务器 产品 之间的...

Firxiao
今天
1
0
MySQL 8 在 Windows 下安装及使用

MySQL 8 带来了全新的体验,比如支持 NoSQL、JSON 等,拥有比 MySQL 5.7 两倍以上的性能提升。本文讲解如何在 Windows 下安装 MySQL 8,以及基本的 MySQL 用法。 下载 下载地址 https://dev....

waylau
今天
1
0
微信第三方平台 access_token is invalid or not latest

微信第三方开发平台code换session_key说的特别容易,但是我一使用就带来无穷无尽的烦恼,搞了一整天也无济于事. 现在记录一下解决问题的过程,方便后来人参考. 我遇到的这个问题搜索了整个网络也...

自由的开源
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部