Từ 1 tới 6 trên tổng số 6 kết quả

Đề tài: tim UCLN,BCNN

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

    Mặc định tim UCLN,BCNN

    nhờ các a/c giai thich dùm e doan code sau, và có cách nào dễ hiểu hơn ko ak?
    main()
    {
    int a, b, k;
    printf("\n nhap so duong a, b");
    scanf("%d%d",&a,&b);
    k=a*b;
    while(b!=0)
    {
    int tg=b;
    b=a%b;
    a=tg;
    }
    printf("/n UCNL= %d",a);
    printf("/n BCNN= %d",k/a);
    }
    Đã được chỉnh sửa lần cuối bởi quangdi : 11-01-2017 lúc 11:25 AM.

  2. #2
    Ngày gia nhập
    01 2013
    Bài viết
    1,397

    Thuật toán Euclid dựa trên khẳng định sau: với mọi a, b sao cho a > b >= 0, gcd(a,b) = gcd(a-b,b), vì nếu k là ước chung của a và b thì k cũng là ước chung của a-b và b, và ngược lại. Do a-b<a nên thuật toán phải dừng và nó đúng.

    Với phép chia Euclid ta có a = bq+r, vậy code trên dựa trên: gcd(bq+r, b) = gcd(b, r). Nếu k là ước chung của bq+r và b thì r cũng chia hết cho k. Chiều ngược lại tương tự.
    Đã được chỉnh sửa lần cuối bởi prog10 : 11-01-2017 lúc 12:30 PM.

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

    e xin cảm ơn ạk! còn có cách nào dễ hiểu hơn ko ak?

  4. #4
    Ngày gia nhập
    02 2016
    Bài viết
    230

    Trích dẫn Nguyên bản được gửi bởi quangdi Xem bài viết
    e xin cảm ơn ạk! còn có cách nào dễ hiểu hơn ko ak?
    Bươc đầu tiên để giúp dễ hiểu:
    Cóp py cái lời diễn giải ở #2 đặt vào làm comments cho code ở bài #1

    Đại khái như vầy:
    Code:
    main()
    {
    int a, b, k;
    printf("\n nhap so duong a, b");
    scanf("%d%d",&a,&b);
    
    /*    Thuật toán Euclid dựa trên khẳng định sau: với mọi a, b sao cho a > b >= 0, gcd(a,b) = gcd(a-b,b), vì nếu k là ước chung của a và b thì k cũng là ước chung của a-b và b, và ngược lại.
    
        Với phép chia Euclid ta có a = bq+r, code tsau đây dựa trên: gcd(bq+r, b) = gcd(b, r).  */
    
    k=a*b;
    while(b!=0)
    {
      int tg=b;
      b=a%b;
      a=tg;
    }
    printf("/n UCNL= %d",a);
    printf("/n BCNN= %d",k/a);
    }

  5. #5
    Ngày gia nhập
    01 2013
    Bài viết
    1,397

    Trực quan nhé https://en.wikipedia.org/wiki/File:Euclid%27s_algorithm_Book_VII_Proposition_2_3 .png

    N* là một UFD, tức là ta viết đc mọi n thuộc N* thành dạng duy nhất như sau: n -> {p0, p0,...,p1,p1,...,pn, pn...} (multiset) sao cho p0*p0*...*p1*p1*...*pn*pn = n với p_i nguyên tố. Vậy UCLN(m,n) ứng với giao của hai multiset ứng với m và n, vì nếu ta gạch bỏ hết các phần tử giống nhau thì ta có hai số nguyên tố cùng nhau do không có chung thừa số nguyên tố nào cả. Vậy nếu ta hiệu một tập với phần giao đó thì hai multiset tạo ra ứng với hai số nguyên tố cùng nhau. Mà bội chung nhỏ nhất của hai số nguyên tố cùng nhau là tích của chúng (*), hay BCNN(m,n) = m*(n/UCLN(m,n)).

    (*): Giả sử pq ko phải là BCNN, điều đó có nghĩa là pq/k là BCNN. Theo t/c BC, multiset của pq/k phải chứa cả multiset của p lẫn q. Mà UCLN(p,q) = 1 nên không thể loại bỏ bất cứ thừa số nào ra khỏi pq. Vậy k chỉ có thể bằng 1.
    Đã được chỉnh sửa lần cuối bởi prog10 : 13-01-2017 lúc 02:01 PM.

  6. #6
    Ngày gia nhập
    01 2017
    Bài viết
    3

    Mặc định tim UCLN,BCNN

    //Cách khác, lấy số lớn trừ số nhỏ tới khi 2 số bằng nhau thì đó là UCLN, BCNN= Tích 2 số chia cho UCLN
    Code:
    #include <stdio.h>

    main()
    {
    int a,b,p;
    printf("Nhap 2 so: ");
    scanf("%d%d",&a,&b);
    p=a*b;
    while(a!=b)
    {
    if(a>b)
    a=a-b;
    else
    b=b-a;
    }
    printf("UCLN: %d va BCNN: %d \n",a,p/a);
    }

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