黑马程序员技术交流社区
标题: 1111-练习-求两个整数最小公倍数和最大公约数的一种算法 [打印本页]
作者: donkey2 时间: 2014-11-11 13:44
标题: 1111-练习-求两个整数最小公倍数和最大公约数的一种算法
本帖最后由 donkey2 于 2014-11-15 10:00 编辑
/*
输入两个数,求最小公倍数和最大公约数
*/
//这题拿着没什么思路,于是去百度了一下小学的基础知识.下面的就是算法。
/*分别把两个数做质因数分解,
把相同质因数跳出来,取两者较小的次幂乘起来,就是最大公约数
两个数的积除以最大公约数,就是最小公倍数
比如说12和40
12=2^2*3
40=2^3*5
最大公约数=2^2=4
最小公倍数=12*40/4=120
*/
#import <Foundation/Foundation.h>
int main(int argc, const char * argv[]){
//定义两个数
int a = 0;
int b = 0;
int gys = 0; //最大公约数
int gbs = 0; //最小公倍数
printf("请输入两个数:\n");
scanf("%d%d", &a, &b);
int c = a * b;
// 保证a是较小的那个数。
if(a > b){
int temp = b;
b = a;
a = temp;
}
//最大公约数从小的数开始往下找,当某个数i能被a,b两个数整除时,即为最大公约数。
//用到循环结构,初始值为a,递减查找。
for (int i = a; ; i--) {
if (a%i == 0 && b%i == 0) {
gys = i;
NSLog(@"最大公约数为:%i",i);
break;
}
}
// 最小公倍数:两个数的乘积处以最大公倍数。
gbs = c / gys;
NSLog(@"最小公倍数为:%i",gbs);
return 0;
}
运算的结果正确。
不过之前由于NSLog(@"最小公倍数为:%i",gbs);
这句里把 gbs 打成了 c,所以结果总不对。
又回去检查了好一会算法。
其实不用这么麻烦,直接设置断点调试就可以了。
以后就有经验了。
其他:< Objective-c 程序设计(第六版)>里面好像还有一种求公约数的算法。
有机会再补充,也希望大家提供其他的算法。
谢谢!:D
作者: donkey2 时间: 2014-11-11 13:47
另外,刚才百度了一下。负数有没有最小公倍数和最大公约数的说法。普遍说讨论绝对值才有意义。于是可以在代码的for循环中加上 i > 0 的约束条件,更加严谨一些。以上!
作者: 浅木头 时间: 2014-11-11 13:59
11.11快乐!
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |