Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 16 kết quả

Đề tài: Giải thích giúp Giải thuật Euclid (tìm ƯSCLN)

  1. #1
    Ngày gia nhập
    09 2008
    Bài viết
    0

    Mặc định Giải thích giúp Giải thuật Euclid (tìm ƯSCLN)

    Mình có bài tập tìm ƯSCLN(a,b), mình search trên mạng thì tìm thấy thuật toán Euclid, có đoạn như thế này :

    Tính ước số chung lớn nhất của 91 và 287.

    Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:

    287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)

    Nhận xét: bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14. Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287. Do đó, ƯSCLN(91,287) = ƯSCLN(91,14). Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:

    91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)
    14 = 7*2 (không còn số dư, kết thúc, nhận 7 làm kết quả)

    Cuối cùng ta có: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91).

    bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi 287 - 91*3 = 14.
    Cái này là dựa trên cơ sở toán học nào ? Mình nghĩ mãi mà không hiểu .


    Mong các bác giải thích giúp. Cám ơn !



    p/s: câu "...chia hết bởi..." là gì ?

  2. #2
    Ngày gia nhập
    09 2007
    Bài viết
    724

    1 - Bạn nhìn xuống cái "bổ đề" ở ngay dưới đó là hiểu mà
    2 :
    a chia hết bởi b ===> b%a == 0;

  3. #3
    Ngày gia nhập
    09 2008
    Bài viết
    0

    ý mình là vì sao khi r # 0 thì : ƯSCLN(a,b)=ƯSCLN(b,r)


    //cái "chia hết bởi" nghe có vẻ khó hiểu quá .
    a chia hết bởi b : mình hiểu thì a là số bị chia, b là số chia.

    khó quá !

  4. #4
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    ý mình là vì sao khi r # 0 thì : ƯSCLN(a,b)=ƯSCLN(b,r)


    //cái "chia hết bởi" nghe có vẻ khó hiểu quá .
    a chia hết bởi b : mình hiểu thì a là số bị chia, b là số chia.

    khó quá !
    UCLN là số lớn nhất mà cả a và b cùng chia hết cho nó.

    c là UCLN của 287 và 91 thì người ta nói. c được chia hết bởi 287 và 91. Và tất nhiên c cũng được chia hết bởi 91 và 14

    Vậy dễ hiểu chứ bạn. Còn code thứ 2 trong chữ kí của mình chính là hàm tìm UCLN áp dụng thuật toán này đấy.

  5. #5
    Ngày gia nhập
    09 2008
    Bài viết
    0

    Trích dẫn Nguyên bản được gửi bởi QuangHoang Xem bài viết
    c là UCLN của 287 và 91 thì người ta nói. c được chia hết bởi 287 và 91. Và tất nhiên c cũng được chia hết bởi 91 và 14.
    Nếu c được chia hết bởi 287 và 91 thì cơ sở nào ta có thể kết luận c cũng được chia hết bởi 91 và 14. , 14 là số dư của phép chia 287/91 chẳng thấy gì liên quan cả .

    em mới học C mà gặp cái code của anh thì ... đi ngũ luôn .
    Đã được chỉnh sửa lần cuối bởi duoirong : 21-10-2008 lúc 11:52 PM.
    --------

  6. #6
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    Mặc định Giải thích giúp Giải thuật Euclid (tìm ƯSCLN)

    Mèng ơi, cần chứng minh thuật toán chi cho mệt vậy ko biết. Chuyện đó đã có mấy ông nhà toán học hói đầu lo. Cả mấy thế kỷ nay chưa nghe ai bác bỏ gì cả. Tụi mình là dân tin học thì cứ vui vẻ lấy thuật toán đó mà áp dụng thôi.
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

  7. #7
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Ẹc, mình sẽ chứng minh lại cho bạn, chán bạn quá, cái này là toán thuần túy đấy.

    c là UCLN của a và b;

    -> a chia hết cho c <=> a=c*i;
    và b chia hết cho c <=> b=c*j;

    vì c là UCLN nên i/j là phân số tối giản.

    Coi như a> b đi cho máu a= b*k + m;

    Cần chứng minh m chia hết cho c và sẽ có một phân số tối giản nào đó nữa.

    Thay vào nhau: c*i = c*j*k + m <=> m = c*(i+j*k); <=> m chia hết cho c
    (i+j*k)/j = i/j +k vậy là thằng này cũng tối giản.

    Tất cả một mớ linh tinh cho thấy, c là UCLN của m và b

    Đọc cái trên nếu bạn còn không hiểu thì công nhận luôn đi cho nhanh.

  8. #8
    Ngày gia nhập
    09 2008
    Bài viết
    0

    ah' ah' hay quá .

    Nhưng mà m = c(i-jk) mới đúng chứ anh,
    tiếp theo là chứng minh (i-jk) & j là 2 số nguyên tố cùng nhau { (i-jk)/j tối giản}.

    (i - jk)/j = i/j - k { i/j tối giản }


    Hỏi 1 xíu nữa anh ơi , vì sao i/j tối giản thì i/j - k cũng là 1 phân số tối giản ???



    //Em có tìm thấy 1 bài viết về ƯSCLN như sau :
    Thuật Toán Euclid:
    Không biết có nên gọi thuật toán này là định lý hay không?
    Ước chung lớn nhất giữa 2 số a và b:

    nếu a >b, thì lấy a:b.
    + Nếu phần dư bằng 0, thuật toán đến đây kết thúc vì chia hết.
    + Nếu phần dư khác 0, thì lấy b chia cho phần dư (làm được vì b lớn hơn phần dư. =>hiển nhiên).
    Và cứ thế tiếp tục.
    Tại sao ta có điều này: ta nhìn thử phần sau:

    a = H[1]*b + M [1] (a chia b được H[1] dư M[1])
    b = H[2]*M1 + M[2] (b chia M[1] được H[2] dư M[2])
    M[1] = H[3]*M[2] +M[3]
    .
    .
    .
    .
    cứ thế tiếp tục, đến phần tử thứ k là kết thúc thì:
    M[k-2] = H[k]*M[k-1] + 0.

    nếu ta thay kết quả này trở ngược lên trên thì sẽ thấy:
    M[k-3] = H[k-1]*M[k-2] + M[k-1] = H[k-1]*H[k]*M[k-1] + M[k-1] = (H[k-1]*H[k]+1)*M[k-1]

    (H[k-1]*H[k]+1) là một số nguyên, và cứ thế tiếp tục ta sẽ thấy a và b đều viết được dưới dạng một số nguyên nhân với M[k-1], có nghĩa là:
    a = n*M[k-1]
    b = m*M[k-1]
    => Bài toán đến đây là gần kết thúc rồi, chỉ việc chứng minh thêm một điều là n với m là 2 số nguyên tố cùng nhau(giữa chúng không có ước số chung khác 1.) => kết thúc.

    cả 2 bài toán đều phải cm 2 số là nguyên tố cùng nhau, tới đây thì bí rồi .
    --------

  9. #9
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Mèng ơi, cần chứng minh thuật toán chi cho mệt vậy ko biết. Chuyện đó đã có mấy ông nhà toán học hói đầu lo. Cả mấy thế kỷ nay chưa nghe ai bác bỏ gì cả. Tụi mình là dân tin học thì cứ vui vẻ lấy thuật toán đó mà áp dụng thôi.
    - Không có toán là sao có thuật toán hả mèo ?
    - Số học liên quan đến lập trình rất nhiều, cố mà làm cho quen đi cậu

  10. #10
    Ngày gia nhập
    07 2008
    Nơi ở
    /media/Anime
    Bài viết
    2,288

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    - Không có toán là sao có thuật toán hả mèo ?
    - Số học liên quan đến lập trình rất nhiều, cố mà làm cho quen đi cậu
    Mình ko có ý bác bỏ toán học, tuy nhiên mình thích công nhận và áp dụng hơn là chứng minh
    Càng yêu mèo thì mèo càng mập. Mèo càng mập ta lại càng yêu.

Các đề tài tương tự

  1. Giải thuật shaker sort. Giúp mình giải thuật với?
    Gửi bởi nguyenhai trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 6
    Bài viết cuối: 29-01-2015, 10:53 PM
  2. Bài tập C Cần giải giúp 3 câu trong đề thi kĩ thuật lập trình C và Cấu trúc dữ liệu và giải thuật
    Gửi bởi nguyenthi0602 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2012, 08:42 PM
  3. cách tìm đối số trong giải thuật euclid mở rộng tìm số nghịch đảo
    Gửi bởi junkilo trong diễn đàn Thắc mắc chung
    Trả lời: 0
    Bài viết cuối: 05-06-2012, 08:12 PM
  4. Giải thuật Euclid mở rộng tìm số nghịch đảo
    Gửi bởi trieutulonga trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 26-04-2011, 09:02 AM
  5. Tài liệu về giải thuật mã hóa. Mã hóa file theo giải thuật DES. Ai có giúp mình?
    Gửi bởi daolong83 trong diễn đàn Công cụ, ebooks C#, ASP.NET, và Windows Mobile
    Trả lời: 6
    Bài viết cuối: 17-07-2009, 11:28 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn