本文共 1551 字，大约阅读时间需要 5 分钟。
已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
输入一个正整数N。
输出一个整数，表示你找到的最小公倍数。
样例输入 9 样例输出 504 数据规模与约定 1 <= N <= 106。
代码来自
#includeusing 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< <
对别人的代码分析学到了一点东西，这个我只想到了让最大的三个数相乘，这么想好像过于简单了哈，研究之后发现分为三种情况。
原则：尽可能让最大的两个数相乘，相邻的两个数最小公倍数一定数他们的乘积。
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行业的，数学家研究出来的算法，程序员来实现，大概都是天才。今天了解了一点贪心算法，以前从没有听说过，人类的智慧真是无穷的，数学家+程序员=天才。
转载地址：http://icqmi.baihongyu.com/