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

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

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

1 Like

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

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

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

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

1 Like

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

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

1 Like

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

đấy là cách viết tắt thôi bạn:
(biểu thức điều kiện)? (trả về nếu điều kiện đúng):(trả về nếu điều kiện sai)

VD:

(a > b)? a:b; 

Thì cũng tương đương với cấu trúc:


if (a > b)
     return a;
else return b;
4 Likes

Thanks a
e hiểu r :smile:

Mình nghĩ khác 1 chút : ví dụ 3 số a,b,c đi (n số cũng tương tự)
Tìm ra được số lớn nhất rồi, thì mình sẽ chỉ kiểm tra bội số của số lớn nhất với các số còn lại thôi như vậy sẽ nhanh hơn,
Ví dụ : a,b,c =2,3,4
Như cách của bạn thì sẽ kiểm tra lần lượt 4,5,6,7,8,9,10,11,12 thì mới tìm ra được số 12 là bscnn đúng k ?
sao k kiểm tra bội số của 4 thôi : 4,8,12 thế sẽ ít hơn độ phức tạp .
Đây là code của mình (mình là sysadmin, học python vì nhận ra 1 điều k biết dev thì chả làm được sản phẩm gì của riêng mình cả, mãi mãi dùng đồ người khác.) vì thế nếu code có khó đọc khó hiểu hay sai chỗ nào mong các bạn chỉ giáo :

 def bscnn(a, b, c):
  #tim so lon nhat
  if a > b and a > c:
    max1 = a
  elif b > c:
    max1 = b
  else :
    max1 = c
  # bien i de xac dinh buoc nhay boi so cua so lon nhat
  i = 1
  # max 1 de kiem tra so lon nhat co phai la bscnn k
  # max 2 de luu gia tri so lon nhat trong 3 so
  max2 = max1
  while (True):
    if((max1 % a == 0) and (max1 % b == 0) and (max1 % c == 0)):
      bsc = max1
      break
    i += 1
    max1 = max2*i
  return bsc, i
a = int(input("Nhap Vao a: "))
b = int(input("Nhap Vao b: "))
c = int(input("Nhap Vao c: "))
print bscnn(a, b, c)
1 Like
a = int(raw_input())
b = int(raw_input())
c = int(raw_input())

i = 0

while True:

       	i += 1

       	if i % a == 0 and i % b == 0 and i % c == 0:
                  	print "bcnn: %s" % i
                   	break

em mới học chút python + pascal nên nghĩ code thế này cho nhanh :smile:

Bài này cuối cùng là thế nào? em chẳng hiểu gì!!!, em cũng muốn tìm bội số chung nhỏ nhất của n số!!!

BCNN(a, b) = b/UCLN(a, b)*a :slight_smile: làm như thớt không hay đâu.

thế UCLN(a,b) tính làm sao?
Với lại n số mà bạn?

Thuật toán Euclid ấy: cứ lấy số lớn trừ số bé (nói ít hiểu nhiều :v)

À, BCNN có tính kết hợp :slight_smile: tức là có thể đặt dấu ngoặc ở đâu cũng đúng. BCNN(a, b, c) = BCNN(BCNN(a, b), c) = BCNN(a, BCNN(b, c)), hay viết gọn (nên quy ước trước): [a, b, c] = [[a, b], c] = [a, [b, c]].

1 Like

từ từ nhé
tham khảo cái này
daynhauhoc tim uoc chung lon nhất

#include<math.h>
int uCLN(int a, int b)
{
	a = abs(a); // trị tuyệt đối cho số âm
	b = abs(b);  // trị tuyệt đối cho số âm
	if (a == 0 && b != 0)
	{
		return b;
	}
	else if (a != 0 && b == 0)
	{
		return a;
	}
	while (a != b)
	{
		if (a > b)
		{
			a -= b;
		}
		else
		{
			b -= a;
		}
	}
	return a;

}

để test nó cái
Dường như ok, thank to author


// Add your javascript here
$(function() {
  function ucln(a, b) {
    a=Math.abs(a);
    b=Math.abs(b);
    if (a === 0 && b !== 0) {
      return b;
    } else {
      if (a !== 0 && b === 0) {
        return a;
      }
    }
    while (a != b) {
      if (a > b) {
        a = a - b;
      } else {
        b = b - a;
      }
    }
    return a;
  }

  var l = [
  ];
  l.push( {func:"ucln(1,2)",result:ucln(1,2)} )
  l.push( {func:"ucln(2,4)",result:ucln(2,4)} )
  l.push( {func:"ucln(3,4)",result:ucln(3,4)} )
  l.push( {func:"ucln(4,4)",result:ucln(4,4)} )
  l.push( {func:"ucln(100,200)",result:ucln(100,200)} )
  $("#msg").html(JSON.stringify(l,null,2))
});



function ucln

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

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

Mối quan hệ giữa BCNN và UCLN?

gọi
aa=a/UCLN(a,b);//aa: int
bb=b/UCLN(a,b);//bb: int

hay là :slight_smile:

a=aaUCLN(a,b);
b=bb
UCLN(a,b);

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

==>

//Đây là Công thức suy diễn cuối cùng
BCNN(a,b) = a * b / UCLN(a,b)

Thật là okey
https://plnkr.co/edit/l6Nzrq?p=preview

okey bạn

Túm lại là

BCNN(x1,x2,x3)=BCNN ( BCNN(x1,x2),x3 )
BCNN(x1,x2,x3,x4)=BCNN ( BCNN(x1,x2,x3),x4 )

hay nhỉ…
Vậy code là thế này :

  function bcnn_of_n(list){
    if(list.length > 1){
      var kq=bcnn(list[0],list[1]);
      for(var i=2;i<list.length;i++){
        kq=bcnn(kq,list[i]);
      }
      return kq;
    }else{
      return -1;
    }
  }

Demo thế này :slight_smile:
https://plnkr.co/edit/l6Nzrq?p=preview

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