[Brute force] Tìm bội chung nhỏ nhất của 3 số bất kỳ

#1

Yêu cầu

  • Input: nhập 3 số nguyên: a, b, c
  • Output: BCNN(a, b, c)

Khái niệm

Bội chung nhỏ nhất của các số nhất kỳ là số nhỏ nhất có thể chia hết cho tất cả các số đó

Ý tưởng, hướng giải

Ta sẽ tìm số lớn nhất nhất từ các số vừa nhập và cho nó chạy từ số đó đến khi nào số đang chạy có thê chia hết cho 3 số đã nhập thì dừng báo kết quả.

Giải quyết bài toán

  • Bước 1: nhập 3 số a, b, c
  • Bước 2: Tìm số lớn nhất từ 3 số a, b, c vừa nhập, gán vào i
  • Bước 3: cho biến cho biến greater chạy -> vô cưc, đồng thời ra điều kiện nếu 3 số i đều chia hết cho 3 số a, b, c thì gán bcnn <- greater
  • Bước 4: dừng vòng lập và in ra biến bcnn.

Chương trình mẫu (Python, PHP, C++)

Python

# Tìm BCNN của 3 số
# đinh nghĩa hàm

def bcnn(a, b, c):
   # tìm số lớn nhất trong 3 số
   if a > b and a > c:
       greater = a
   elif b > c:
       greater = b
   else:
       greater = c

  # chạy và tìm BCNN
   while(True):
       if((greater % x == 0) and (greater % y == 0) and (greater % z == 0)):
           bcnn = greater
           break
       greater += 1

   return bcnn

# Người dùng nhập vào 3 số a, b, c
a = int(input("Nhập vào a: "))
b = int(input("Nhập vào b: "))
c = int(input("Nhập vào c: "))

print "Vậy BCNN(a, b, c) = ", bcnn(a, b, c)

PHP

<?php
# Tìm BCNN của 3 số

# Kiem tra nguoi dung gui du lieu
  if (isset($_POST['send']){

  # đinh nghĩa hàm

  function bcnn($a, $b, $c){
     # tìm số lớn nhất trong 3 số
     if ($a > $b && $a > $c)
         $greater = $a;
     elseif (b > c)
         $greater = $b;
     else
         $greater = $c;

    # chạy và tìm BCNN
     while(true){
         if(($greater % $x == 0) && ($greater % $y == 0) && ($greater % $z == 0)){
             $bcnn = $greater;
             $break;
         }
         $greater++;
     }

     return $bcnn;
  }

  # Người dùng nhập vào 3 số a, b, c
  $a = $_POST['a'];
  $b = $_POST['c'];
  $c = $_POST['b'];

  echo "Vậy BCNN(a, b, c) = ", bcnn($a, $b, $c);
}

## nguoi dung nhap du lieu
?>
<form method="POST">
    Nhap a: <input type="number" name="a" /><br />
    Nhap b: <input type="number" name="b" /><br>
    Nhap c: <input type="number" name="c" /><br />
    <input type="submit" name="send" value="OK" />
</form>

C++

#include <iostream>
using namespace std;


int bcnn( int a, int b, int c);

int main() {
    int a, b, c;
    cout << "Nhap 3 so a, b, c: ";
    cin >> a >> b >> c;
    
    cout << "BCNN(a, b, c) = : " << bcnn(a, b,c);
    
    return 0;
}

// Tìm BCNN của 3 số
int bcnn( int a, int b, int c) {
     // tìm số lớn nhất trong 3 số
     int greater, bcnn;
     greater = (a > b && a > c ) ? a : ((b > c) ? b : c);

     // chạy và tìm BCNN
     while (true) {
        if (greater%a == 0 && greater%b == 0 && greater%c == 0){
            bcnn = greater;
            break;
        }
        ++greater;
     } 
}

Có gì góp ý cho mình nha :smiley:

7 Likes
#2

Em thấy người ta hay dùng thuật toán Euclid để tìm ƯCLN, sau đó tính BCNN theo công thức

BCNN(a,b) = (a * b) / UCLN(a, b)

Không biết cách này có nhanh hơn không nữa.

Em có nên làm 1 bài về nó không nhỉ ?

4 Likes
#3

ừ, mình thấy thông thường là theo cách này, nhưng 3 số thì cách của Kayz đơn giản hơn :smiley:

1 Like
#4

Thật ra thuật toán Euclid chỉ dành cho 2 số :v

2 Likes
#5

một thuật toán đơn giản để hiểu được cách thức tìm thôi. Với 2 số ta có thể sd cách trên hoặc thuật toán của Euclid :smiley:

Có ai rebuild sang Java, C, Perl, Ruby cho đủ bộ :wink:

1 Like
#6

Mình nghĩ nên bắt đầu từ i=2*greatest và kiểm tra luôn greatest
cách này sẽ lời greatest-1 lần kiểm tra

1 Like
#7

Nhỡ 1, 2, 4 -> BCNN nó là 4, nếu bắt đầu i=2*greatest -> i=8 thành ra sai rồi :smiley:

2 Likes
#8

:smiley: đầy đủ nhé, lời được (greatest-1)*3 phép tính nè

1 Like
#9

hợp lý! tại sao lại (greatest-1)*3 nhĩ :slight_smile:

#10

Tại vì mình phải thực hiện 3 phép tính để kiểm tra i/a, i/b, i/c :smile:

1 Like
#11

Good idea :wink:

$message = new Post(RequirePostCharacter 20);
1 Like
#12

Nếu mình biết các số còn lại có chứa snt nào thì còn lợi hại hơn. Lập hẳn một array snt và kiểm tra, cơ mà cách này thô quá :smile: dàng cho số bự bự, khoảng cách xa nhau thì ổn.

Có lẽ mình sẽ cải tiến một chút là chỉ kiểm tra những số i là bội của greatest thôi.
Vì điều kiện cần để là bội của 3 số là nó là bội của từng số.
Số lớn nhất là c thì chỉ kiểm tra các số c, 2c, 3c,…

2 Likes
#13

ngày xưa toàn làm thế này thôi :imp:

1 Like
#14

Thuật toán của mình tìm bcnn cho n tham số:

#include <bits/stdc++.h>
using namespace std;


template<class T>
T gcd(T v){
    return v;    
}

template <class T,class ... Args>
T gcd(T first,Args... args){
    return __gcd(first,gcd(args...));
}

template <class T>
T lcm(T v){
    return v;
}
template <class T,class ... Args>
T lcm(T first,Args... args){
    T t=lcm(args...);
    return first/__gcd(first,t)*t;
}


int main() {
    cout<<gcd(5,10,20,100)<<endl;
    cout<<lcm(5,10,20,100)<<endl;
    cout<<lcm(5,10,20)<<endl;
    return 0;
}
5 Likes
#15

Ý tưởng là gì vậy gió? :smiley:

#16

Tìm bội chung của n số:
Tư tưởng là BCNN(n số) = BCNN(n,(BCNN(n-1) số) :d

1 Like
#17

greater = (a > b && a > c ) ? a : ((b > c) ? b : c);
dòng này là sao vậy bạn :grin:

1 Like
#18

tìm số lớn nhất trong 3 số theo cách thủ công :smiley:

#19

(condition)? a : b;
if condition is true -> return a
else return b;
…

1 Like
#20

Vẫn chưa hiểu :unamused:
mấy dấu ? và : là gì a

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?