ALGO-2 最大最小公倍数贪心算法

r囧r小猫 2022-05-31 11:48 151阅读 0赞

#### **问题描述** ####

> 已知一个正整数N，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。

#### **输入格式** ####

> 输入一个正整数N。

#### **输出格式** ####

> 输出一个整数，表示你找到的最小公倍数。  
> 样例输入  
> 9  
> 样例输出  
> 504  
> 数据规模与约定  
> 1 <= N <= 106。

代码来自[http://blog.csdn.net/gloriaxixi/article/details/43925049][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行业的，数学家研究出来的算法，程序员来实现，大概都是天才。今天了解了一点贪心算法，以前从没有听说过，人类的智慧真是无穷的，数学家+程序员=天才。

[http_blog.csdn.net_gloriaxixi_article_details_43925049]: http://blog.csdn.net/gloriaxixi/article/details/43925049