首页 > 试题广场 > 最小众倍数
[编程题]最小众倍数
  • 热度指数:519 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给定5个正整数, 它们的最小的众倍数是指的能够被其中至少三个数整除的最小正整数。 给定5个不同的正整数, 请计算输出它们的最小众倍数。

输入描述:
输入包括一行,一行中有五个各不相同的正整数a, b, c, d, e(1 ≤ a, b, c, d, e ≤ 100), 以空格分割


输出描述:
输出一个整数,表示它们的最小众倍数
示例1

输入

1 2 3 4 5

输出

4

方法一:暴力搜索。复杂度等于搜索下限减去上限

  • 搜索下限:第3大的数。
  • 搜索上限:前3小的数的乘积。

方法二:寻找所有三个数的组合的最小众倍数,取其中最小的那个。复杂度等于O(n^3),n为输入数的个数,本题 n = 5。

如何求3个数a,b,c的最小众倍数?

  • 求出b*c,a*c的最大公约数A;
  • 求出a*c,a*b的最大公约数B;
  • 求出A,B的最大公约数C;
  • 使用(a*b*c) / C即得到结果。

代码如下:

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int[] nums = new int[5];
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 5; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(zbs(nums));
    }
    public static int zbs(int[] seq) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < seq.length; i++) {
            for (int j = i+1; j < seq.length; j++) {
                for (int k = j+1; k < seq.length; k++) {
                    min = Math.min(min, findZBS(seq[i], seq[j], seq[k]));
                }
            }
        }
        return min;
    }
    public static int findZBS(int a, int b, int c) {
        return (a*b*c) / GCD(GCD(b*c, a*c), GCD(a*c, a*b));
    }
    public static int GCD(int a, int b) {
        int c;
        while ( b != 0 ) {
            c = a % b;
            a = b;
            b = c;
        }
        return a;
    }
}
编辑于 2019-08-30 14:24:25 回复(0)
更多回答
import java.util.Scanner;
public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        int e = sc.nextInt();
        int count = 0;
        int result=1;
        for(result=1; result<Integer.MAX_VALUE; result++)
        {
            if(result % a == 0) count++;
            if(result % b == 0) count++;
            if(result % c == 0) count++;
            if(result % d == 0) count++;
            if(result % e == 0) count++;
            if(count >= 3)
                break;
            else
                count = 0;//若count值小于3,则count置为0
        }
        System.out.println(result);
    }

}


编辑于 2019-09-27 16:16:36 回复(0)
def fun(nums):
    tmp = nums[2]  # 众倍数必定是>=nums[2]的
    while tmp:
        count = 0
        for j in range(5):
            if tmp % nums[j] == 0:
                count += 1
                # print nums[j], count
        if count >= 3:   # 注意这里是>=  不是==
            return tmp
        else:
            tmp += 1
            # print tmp


res = fun([5,7,13,14,16])
print res

发表于 2019-09-02 12:27:47 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n;
    vector<int> res;
    while(cin>>n){
        res.push_back(n);
    }
    sort(res.begin(),res.end());
    
    for(int i=res[2];;i++){//i至少得是第三个数
        int count=0;
        for(int j=0;j<5;j++){
            if(i%res[j]==0)
                count++;
        }
        if(count>=3){cout<<i<<endl;break;}
    }
}

发表于 2019-08-26 10:15:01 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int gbs(int num1, int num2)
{
    int x1 = num1*num2;
    while(num1 != num2)
    {
        if(num1 > num2)
            num1 = num1 - num2;
        else
            num2 = num2 - num1;
    }
    return x1/num1; 
}
int gbs3 (int a, int b, int c)
{
    int d = gbs(a,b);
    return gbs(d,c);
}
int main() {
    vector <int> data;
    for(int i=0; i<5; i++)
    {
        intn = 0;
        cin >> n;
        data.push_back(n);
    }
    int res = gbs3(data[0], data[1], data[2]);
    for(int i=0; i<5; i++)
    {
        for(int j=i+1; j<5; j++)
        {
            for(int k=j+1; k<5; k++)
            {
                int tmp = gbs3(data[i], data[j], data[k]);
                res = min(res, tmp);
            }
        }
    }
    cout << res;
    return 0;
}
发表于 2019-08-04 13:56:43 回复(0)
链接:https://www.nowcoder.com/questionTerminal/792b17400b1b4915bb13c872e7ba48f7?orderByHotValue=1&commentTags=Java
来源:牛客网
importjava.util.*;
 
publicclassMain {
   publicstaticvoidmain(String[] args) {
        int[] arr =newint[5];
        Scanner input =newScanner(System.in);
        for(inti=0;i<5;i++) {
            arr[i] = input.nextInt();
        }
       intcount =0;
       intresult =0;
        Arrays.sort(arr);//将数组排序
        for(inti = arr[2];;i++) {//最小的最小众倍数肯定是大于或等于arr[2]
            count =0;
            for(intj=0;j<5;j++) {
                if(i%arr[j]==0) {
                    count++;//每满足一次条件加1
                }                 }
            if(count >=3) {//如果count>=3 则满足题目条件
             result = i;
             break;
             }
   }
        System.out.println(result);
   }
发表于 2019-07-03 21:58:19 回复(0)
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int [] a=new int[5];
        for(int i=0;i<=4;i++){
            a[i]=sc.nextInt();
        }
        Arrays.sort(a);//题目没说这四个的大小关系,从小到大排序
        for(int i=a[2];;i++){//从第三个开始,依次增大。
            int flag=0;
            for(int j=0;j<5;j++)//判断这几个数中能有几个被整除的数
            {
                if(i%a[j]==0)//能够整除
                {
                    flag++;
                }
            }
            if(flag >= 3)//个数达到了,输出结果。结束循环
            {
                System.out.println(i);
                break;
            }
        }
    }


}


编辑于 2018-08-10 23:40:06 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[5];
        Scanner input = new Scanner(System.in);
        for(int i=0;i<5;i++) {
            arr[i] = input.nextInt();
        }
        int count = 0;
        int result = 0;
        Arrays.sort(arr);//将数组排序
        for(int i = arr[2];;i++) {//最小的最小众倍数肯定是大于或等于arr[2]
            count = 0;
            for(int j=0;j<5;j++) {
                if(i%arr[j]==0) {
                    count++;//每满足一次条件加1
                }                 }
            if(count >= 3) {//如果count>=3 则满足题目条件
             result = i;
             break;
             }
    }
         System.out.println(result);
    }
} 

发表于 2018-08-10 01:37:49 回复(0)