本文主要是介绍ALGO-2 最大最小公倍数 贪心算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述
已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。
输入格式
输入一个正整数N。
输出格式
输出一个整数,表示你找到的最小公倍数。
样例输入
9
样例输出
504
数据规模与约定
1 <= N <= 106。
代码来自http://blog.csdn.net/gloriaxixi/article/details/43925049
#include <iostream>
using namespace std;
int main()
{ long long n,ans; cin>>n; if(n<3) //小于3时,就是最大的这个数ans=n; else{ if(n%2!=0) //是奇数,用贪心算法,找最大的三个数相乘ans=n*(n-1)*(n-2); else if(n%3!=0) //是偶数ans=n*(n-1)*(n-3); else //是偶数,也是3的倍数,变成奇数的情况来求ans=(n-1)*(n-2)*(n-3); } cout<<ans<<endl; return 0;
}
对别人的代码分析学到了一点东西,这个我只想到了让最大的三个数相乘,这么想好像过于简单了哈,研究之后发现分为三种情况。
原则:尽可能让最大的两个数相乘,相邻的两个数最小公倍数一定数他们的乘积。
代码思路:
1、奇数的时候就是最大的三个数相乘
2、偶数时又分为两种:
①是偶数的话,最大的相邻的三个数,N和N-2一定可以约分2,那么就需要让最小的那个数-1在相乘,即为N*(N-1)*(N-2-1)
②是偶数同时也是3的倍数,在采取N*(N-1)*(N-2-1)的公式会不行,因为N和N-3会有公约数3,在-1会有偶数的公约数出现,所以只能让三个数同时-1,变成N是奇数的问题来求解。
举个例子:
1、当N为奇数:7 8 9,最大公倍数就是7*8*9
2、当N为偶数:
①不是3的倍数:12 13 14,最大公倍数是14*13*(12-1),因为12和14可以约分,11就没有公约数
②是3的倍数:16 17 18,最大公倍数是17*16*15,因为18*17*(16-1),15可以和18约分,所以让N变成奇数的情况来求。
贪心算法
看百度百科解释的好复杂。。。其实就是每次拿能拿的最大的。在这个题就是每次都要尽可能地取最大的数进行相乘。
看别人拿钱举这个例子真合适:
贪心算法最经典的例子,给钱问题。
比如中国的货币,只看元,有1元2元5元10元20、50、100如果我要16元,可以拿16个1元,8个2元,但是怎么最少呢?
如果用贪心算,就是我每一次拿那张可能拿的最大的。
比如16,我第一次拿20拿不起,拿10元,OK,剩下6元,再拿个5元,剩下1元
也就是3张 10、5、1。每次拿能拿的最大的,就是贪心。
但是一定注意,贪心得到的并不是最优解,也就是说用贪心不一定是拿的最少的张数
贪心只能得到一个比较好的解,而且贪心算法很好想得到。
再注意,为什么我们的钱可以用贪心呢?因为我们国家的钱的大小设计,正好可以使得贪心算法算出来的是最优解(一般是个国家的钱币都应该这么设计)。如果设计成别的样子情况就不同了
比如某国的钱币分为 1元3元4元
如果要拿6元钱 怎么拿?贪心的话 先拿4 再拿两个1 一共3张钱
实际最优呢? 两张3元就够了
总结:
佩服那些搞数学研究的人,当然也佩服我们IT行业的,数学家研究出来的算法,程序员来实现,大概都是天才。今天了解了一点贪心算法,以前从没有听说过,人类的智慧真是无穷的,数学家+程序员=天才。
这篇关于ALGO-2 最大最小公倍数 贪心算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!