Trang 2 trên tổng số 2 Đầu tiênĐầu tiên 12
Từ 11 tới 16 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. #11
    Ngày gia nhập
    09 2007
    Bài viết
    724

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

    zkday cũng có ý như của mèo
    việc chứng minh các biểu thức toán học là của mấy thằng cha học toán 'hói đầu'.
    chúng ta làm lập trình chỉ là một nghành khoa học ứng dụng thôi chúng ta chỉ cần hiểu nó chứ chẳng cần phải chứng minh lại làm gì

    vì zkday nghĩ chúng ta sẽ lấy máy tính + ngôn ngữ lập trình + thuật toán để chứng minh cho nó là đúng

  2. #12
    Ngày gia nhập
    04 2015
    Bài viết
    0

    Trích dẫn Nguyên bản được gửi bởi duoirong Xem bài viết
    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 ???
    .
    Hôm nay ngồi đọc lại đệ quy đến bài tìm UCLN tình cờ cũng thắc mắc về thuật toán euclid này, thấy câu hỏi của bạn vẫn chưa được giải quyết nên mình xin mạo muội post lời giải của mình, hi vọng các bạn mod không quy mình vào tội đào mộ . Trước hết coi lại lý thuyết về phân số tối giản :

    Phân số tối giản là phân số mà "tử" và "mẫu" CHỈ CÓ ước chung là 1 và -1 . Các tính chất liên quan khác :
    + a chia hết cho d, b chia hết cho d thì a + b hoặc a - b chia hết cho d.
    + 1 chia hết cho d thi d = 1 hoặc d = -1


    Trở lại với câu hỏi ở trên:
    Vì i/j là phân số tối giản nên i va j chỉ có ước chung là 1 hoặc -1.
    Ta có i/j - k = (i - kj)/j. Gọi d là ước chung của (i - kj) và j => j chia hết cho d và (i - kj) chia hết cho d.
    Vì j chia hết cho d => i cũng chia hết cho d.
    Vì i và j chỉ có ước chung là 1 va -1 nên d cũng chỉ có giá trị là 1 và -1 => i/j - k cũng là phân số tối giản.

    Hi vọng câu trả lời sẽ có ích cho các bạn còn đang có thắc mắc tương tự. Có gì sai mọi người góp ý nhé. Thanks.

  3. #13
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    ^ Đó chỉ là 1 trường hợp riêng.

    (Nguồn: http://www.math.lsa.umich.edu/~hderksen/math289.f03/math289/PS3numb.pdf)

    Quy ước gcd(0,0) = 0 và gcd(0,n) = |n|.
    Bổ đề: Nếu p chia hết cho gcd(m,n) thì gcd(m,n) <= gcd(n,p)
    - Do n và p cùng chia hết cho gcd(m,n) nên theo định nghĩa gcd, gcd(m,n) <= gcd(n,p).

    Áp dụng bổ đề trên, ta sẽ c/m với m,n,q thuộc Z thì gcd(m,n) = gcd(m,n-qm).
    - Do m, n và n-qm cùng chia hết cho gcd(m,n) nên gcd(m,n) <= gcd(m,n-qm).
    - Do m, n-qm và n = (n-qm)+qm cùng chia hết cho gcd(m,n-qm) nên gcd(m,n-qm) <= gcd(m,n).
    Từ 2 điều trên suy ra đpcm.

    Đến đây có thể đưa ra 1 thuật toán tính gcd(m,n) với m,n>=0 như sau:
    Code:
    while m!=0 and n!=0 do
       if(m>n) m = m - (m DIV n)*n
       else n - (n DIV m)*m
    if(m==0) return n
    else return m
    Dễ thấy m,n>=0 ở mọi thời điểm và gcd(m,n) giữ nguyên nên thuật này đúng.
    Thuật này chắc chắn dừng vì m và n không bao giờ tăng và:
    - Nếu n chia hết cho m thì n==0 ở vòng tiếp theo.
    - Số nào cũng chia hết cho 1.

    Trích dẫn Nguyên bản được gửi bởi zkday2686 Xem bài viết
    chúng ta làm lập trình chỉ là một nghành khoa học ứng dụng thôi chúng ta chỉ cần hiểu nó chứ chẳng cần phải chứng minh lại làm gì
    Như thế này gọi là cả tin.
    Đã được chỉnh sửa lần cuối bởi prog10 : 15-04-2015 lúc 12:00 PM.

  4. #14
    Ngày gia nhập
    04 2015
    Bài viết
    0

    Thank prog10 đã chia sẽ thêm những thông tin bổ ích, mong bạn đóng góp nhiều hơn nữa cho cộng đồng lập trình

  5. #15
    Ngày gia nhập
    09 2014
    Nơi ở
    Thành phố Hồ Chí Minh
    Bài viết
    2

    Có thể hiểu UCLN theo cách đơn giản như sau:
    Nhắc lại: UCLN của hai số nguyên a và b là số nguyên dương lớn nhất trong tập hợp các ước chung của hai số a và b.
    Trong trường hợp tổng quát, ta chỉ xét a và b nguyên dương, vì UCLN(a, b) = UCLN(|a|, |b|).
    Giả sử a chia cho b dư r: a = bq + r, với 0 <= r < b.
    Gọi d là một ước chung của a và b. Khi đó từ trên suy ra d cũng là ước của (a - bq) tức là d cũng là ước của r. Vậy d cũng là ước chung của b và r.
    Ngược lại, nếu d là ước của b và r thì từ trên suy ra d là ước của (bq + r), tức là d cũng là ước của a. Vậy d cũng là ước chung của a và b.
    Từ hai lập luận trên, suy ra tập hợp các ước chung của hai số a và b, b và r là hoàn toàn trùng nhau, nên suy ra UCLN(a, b) = UCLN(b, r).
    Sử dụng thêm tính chất UCLN(a, 0) = a, ta có được thuật toán tìm UCLN.
    Hi vọng có ích cho chủ thớt

  6. #16
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

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

    ^
    Tức là tập UC(a,b) là tập con của UC(b,r)
    sau đó là tập UC(b,r) là tập con của UC(a,b)
    => 2 tập bằng nhau

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