文档章节

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

失落的艺术
 失落的艺术
发布于 07/16 12:15
字数 335
阅读 48
收藏 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程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
04/01
0
0
C语言编程学习:C程序解析:用C语言编写你的第一个自定义函数

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

小辰带你看世界
05/26
0
0
C语言编程入门学习:用C语言输出九九乘法表

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

小辰带你看世界
05/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

flutter Expanded用法

使用的地方:一个分类,类似京东的,左右两边都可以滑动 Widget build(BuildContext context) { return Row(children: [ Column( children: <Widget>[ Ex......

大灰狼wow
14分钟前
2
0
Java8 Map中新增的方法使用总结

前言 得益于 Java 8 的 default 方法特性,Java 8 对 Map 增加了不少实用的默认方法,像 getOrDefault, forEach, replace, replaceAll, putIfAbsent, remove(key, value), computeIfPresent,......

kaixin_code
24分钟前
1
0
@TransactionConfiguration

@TransactionConfiguration过时与替代写法 @TransactionConfiguration 替代写法

miaojiangmin
26分钟前
0
0
浅谈Vue响应式(数组变异方法)

很多初使用Vue的同学会发现,在改变数组的值的时候,值确实是改变了,但是视图却无动于衷,果然是因为数组太高冷了吗? 查看官方文档才发现,不是女神太高冷,而是你没用对方法。 看来想让女...

开元中国2015
28分钟前
2
0
Elasticsearch通关教程(五):如何通过SQL查询Elasticsearch

  这篇博文本来是想放在全系列的大概第五、六篇的时候再讲的,毕竟查询是在索引创建、索引文档数据生成和一些基本概念介绍完之后才需要的。当前面的一些知识概念全都讲解完之后再讲解查询是...

SEOwhywhy
47分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部