kết quả từ 1 tới 9 trên 9

Giúp bài tập Pascal về Phân số

  1. #1
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Giúp bài tập Pascal về Phân số

    Với số nguyên dương N cho trước, xét tập hợp A(N) gồm tất cả các phân số có giá trị thuộc đoạn [0,1] vs mẫu số ko lớn hơn N, Vd vs N=5, ta có phân số: 0/1; 1/5; 1/3; 2/5; 1/2; 3/5; 2/3; 3/4; 4/5; 1/1
    cho trc số nguyên dương N, viết chương trình in ra mọi phân số tối giản thuộc A(N) theo thứ tự tăng dần, mỗi phân số viết dưới dạng tử số/ mẫu số.

    Vd: FRAC.IN
    5


    FRAC.OUT
    0/1
    1/5
    1/4
    1/3
    2/5
    1/2
    3/5
    2/3
    3/4
    4/5
    1/1
    Bài 2
    Tìm MAX-UCLN
    cho dãy A gồm N phần tử nguyên dương a1
    ,a2,a3...aN và dãy B gồm M phần tử nguyên dương b1,b2,b3...bM
    ký hiệu UCLN(x;y) là ước chung lớn nhất của hai số x và y.
    Yêu cầu:tìm giá trị lớn nhất của UCLN(ai,bj) với i=1..N;j..M.
    Dữ liệu vào:cho trong tệ BAi3.INP:
    -Dòng 1: chứa giá trị N(số lượng phần tử của dãy A)(1<=N<=100)
    -Dòng 2:chứa N số nguyên dương là các giá trị của dãy A(Ạ<=10000)
    -Dòng 3:chứa giá trị M (số lượng phần tử của dãy B)1<=M<=100)
    -Dòng 4:chứa M số nguyên dương là các giá trị của dãy B(bj<=10000)
    Kết quả:ghi ra tệp BAI3.OUT:Ghi giá trị lớn nhất của UCLN(ai;bj)tìm đc
    Quick reply to this message Trả lời       


  2. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Giúp bài tập Pascal về Phân số

    Bài 1: bạn có thể tham khảo ở câu 2 trong link này. Bạn cần thêm 1 chút là đơn giản phân số đi nhé.
    HTML Code:
    http://vforum.vn/diendan/showthread.php?94983-Mot-so-bai-tap-pascal-giai-thuat-sap-xep-mong-su-chi-giao
    Bài 2: Vì M và N nhỏ, ta có thể quét toàn bộ M * N cặp. Nếu dùng thuật toán của Euclid thì số bc chạy không quá O(log(a[i] b[j])) ~ O(log a). Như vậy, tối đa chương trình chạy khoảng 270000 lần. Bạn có thể optimize nó một chút: nên quét từ lớn tới nhỏ (i.e., sort); nếu UCLN max hiện tại lớn hơn 1 trong 2 số từ mảng A hay B thì "dừng" luôn (dừng vòng loop trong hoặc cũng có thể dừng hẳn), ko cần duyệt nữa.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  3. #3
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Reply: Giúp bài tập Pascal về Phân số

    Nhờ bạn có thể giải thích cụ thể chi tiết cả hai bài cho mình dk ko ak, vì thực ra mình chưa hiểu rõ về đề lắm, vì thế ý tưởng cũng như giải thuât mình chưa co nghĩ ra
    cách đề biểu diễn 1 phân số như trên mình cũng chưa biết phải làm thế nào
    nói chung cả hai nhờ bạn chỉ giáo cụ thể hơn ak

  4. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Giúp bài tập Pascal về Phân số

    Trích Nguyên văn bởi vansonqtqb Xem bài viết
    Nhờ bạn có thể giải thích cụ thể chi tiết cả hai bài cho mình dk ko ak, vì thực ra mình chưa hiểu rõ về đề lắm, vì thế ý tưởng cũng như giải thuât mình chưa co nghĩ ra
    cách đề biểu diễn 1 phân số như trên mình cũng chưa biết phải làm thế nào
    nói chung cả hai nhờ bạn chỉ giáo cụ thể hơn ak
    Mình tưởng bạn đã hiểu đề, chỉ hỏi giải thuật nên chỉ tập trung cho thuật toán.
    Bài 1: Mình lấy ví dụ của đề n = 5 cho dễ hiểu nhé. Vì các phân số phải trong khoảng [0, 1] và mẫu số không vượt quá n = 5, nên A(5) phải là:
    - Mẫu số = 1 thì chúng ta có: 0/1, 1/1.
    - Mẫu số = 2 thì chúng ta có: 0/2, 1/2, 2/2.
    - Mẫu số = 3 thì chúng ta có: 0/3, 1/3, 2/3, 3/3.
    - Mẫu số = 4 thì chúng ta có: 0/4, 1/4, 2/4, 3/4, 4/4.
    - Mẫu số = 5 thì chúng ta có: 0/5, 1/5, 2/5, 3/5, 4/5, 5/5.
    Sau khi đơn giản thì chỉ còn: 0/1, 1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5.

    - Lưu ý: đề ko nói rõ nhưng có thể tự hiểu rằng: chỉ xét phân số (đơn giản nhất) với tử và mẫu số là số nguyên.
    - Để lưu phân số thì thường có 2 cách chính: dùng 2 biến riêng rẽ (a và b tượng trưng cho a/b), hoặc dùng record (tương ứng với struct trong C/C++). Ở trong bài cần lưu nhiều phân số nên phải đặt mảng; ví dụ:
    Mã:
    type fraction = record
                num, den : integer;
           end;
    var a : array[1..10000] of fraction;   // phân số thứ i có tử số là a[i].num và mẫu số là a[i].den.
    hoặc là:
    Mã:
    var a, b : array[1..10000] of integer;   // phân số thứ i có tử số là a[i] và mẫu số là b[i].
    Sau đó bạn dùng 2 vòng 'for' quét hết những cặp (i, j) có thể rồi lưu vào mảng 'a'. Trước khi lưu vào thì đơn giản phân số đi nhé; bạn ko cần phải biết cặp đó đã có hay chưa, cứ việc lưu nó vào. Sau đó bạn cần dùng quick sort để sort lại mảng phân số này.
    a) Lúc đổi chỗ thì nếu bạn chọn cách biểu diễn thứ 2 thì phải nhớ đổi chỗ cho 2 mảng a và b luôn.
    b) Mình để phần so sánh 2 phân số lại cho bạn.
    Cuối cùng khi sort ra rồi thì bạn bắt đầu ghi kết quả và lưu ý khi ghi thì ko ghi 2 phần tử trùng nhau (2 phân số bằng nhau sẽ đứng kế nhau trong mảng sau khi đã sort).
    Độ phức tạp của thuật toán O(n^2 log n), chủ yếu do hàm sort.

    Bài 2: Bài này mình nghĩ có lẽ dễ hơn bài đầu. Ví dụ:
    Mã:
     a = 3, 12, 6    và    b = 4, 5, 8;
    Chúng ta cần tìm UCLN của mấy cặp sau:
    Mã:
     (3, 4), (3, 5), (3, 8), (12, 4), (12, 5), (12, 8), (6, 4), (6, 5), (6, 8).
    Sau đó chọn ra giá trị lớn nhất. Ý tưởng của mình là sort mảng a và b từ lớn tới nhỏ, sau đó kiểm tra từng cặp (a[i], b[j]). Bạn lưu ý khi a[i] hay b[j] nhỏ hơn giá trị UCLN bạn đã tìm đc thì phải break ra. Bởi vì UCLN không vượt quá số nhỏ hơn trong 2 số (a[i], b[j]), nên ví dụ, khi UCLN đã lớn hơn b[j] thì nó cũng lớn hơn UCLN của cặp gồm (a[i], b[j + 1]), (a[i], b[j + 2]),... nên UCLN của mấy số sau cũng ko cần duyệt nữa. Tương tự cho a[i], và khi đó có thể dừng và in kết quả.
    Độ phức tạp của thuật toán O(m n k), với k là số lần chạy tối đa của thuật toán Euclid tìm UCLN (mình nghĩ k trong bài ko quá 14).

  5. #5
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 353068
    Giới tính: Nam
    Bài gửi
    22

    Reply: Giúp bài tập Pascal về Phân số

    trước khi lưu vào a thì mình phải rút gọn phân số phải không bạn..
    mình thắc mắc chỗ này.
    bài 1 : mảng a thì chỉ lưu các tư số vậy mảng b mình lưu lúc nào hả bạn
    với lại trong khi sort lai mảng thì đổi chỗ ca hai mảng là vì sao, và cách đổi chỗ như thế nào
    Bài 2 :ý bạn là sort lai hai mảng trên rồi so sánh như thế này phải ko bạn..bạn có thể chỉnh sửa thêm có phải ko
    sapxep(1,n)
    sapxep(1,m)
    uc:= ucln(a[i],b[i]);
    for i:=1 to n do
    begin
    for j:= to m do
    begin
    if uc < ucln(a[i],b[j]) then
    break
    end;

  6. #6
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Reply: Giúp bài tập Pascal về Phân số

    nhờ các bạn code lại những chỗ quan trọng nhất của bài cho mình với ak. vì thực chất mình hiểu đề nhưng ý tưởng giải thuật của bạn mình cũng còn long bung quá? mình thấy lưu bằng cách hai van dễ hiểu hơn, các bạn giúp mình bằng cách hai với

  7. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Giúp bài tập Pascal về Phân số

    Đoạn code sau sẽ quét hết toàn bộ phân số trong khoảng [0, 1] với mẫu số ko quá n.
    Mã:
    a[1] := 0; b[1] := 1;   // phân số  0/1.
    m := 1;   // số phần tử ban đầu là 1.
    for denominator := 1 to n do   // mẫu số ko quá n.
       for numerator := 1 to denominator - 1 do   // tử số phải nhỏ hơn mẫu số vì phân số trong khoảng [0, 1].
          begin
             t := gcd(numerator, denominator);   // UCLN của tử số và mẫu số.
             inc(m);
             a[m] := numerator div t;   // đơn giản phân số  'numerator / denominator' và lưu vào mảng.
             b[m] := denominator div t;   // a[m] chứa tử số của phân số thứ m, b[m] chứa mẫu số của phân số m.
          end;
    inc(m);
    a[m] := 1; b[m] := 1;   // phân số 1/1.
    Tới đây bạn sẽ có mảng phân số chứa m phần tử: mảng a chứa tử số, mảng b chứa mẫu số. Tiếp theo là sort lại. Trong lúc viết thuật toán sort, phải có đổi chỗ phải không bạn? Bình thường thì chỉ cần
    Mã:
     swap(a[i], a[j])
    Còn bây giờ thì
    Mã:
    swap(a[i], a[j]);
    swap(b[i], b[j]);
    Ngoài ra còn phải so sánh 2 phân số nữa. Thay vì a[i] < a[j] thì bây giờ phải là 1 hàm so sánh 2 phân số a[i]/b[i] và a[j]/b[j].
    Nếu bạn chưa biết viết sort phân số thì bạn viết code quick sort để sort mảng 'a' (tử số) đi rồi mình sẽ comment trực tiếp trên đó cho bạn. Bạn có thể bắt đầu bằng insertion sort, bubble sort,... code đơn giản nhất cho hiểu rồi sẽ sang quick sort cũng đc. Bài này nên dùng quick sort nhé.
    - Lời khuyên của mình: bạn nên nhớ 2 loại sort: 1 loại O(n^2) hiệu quả với số phần tử nhỏ như insertion sort, và 1 loại O(n log n) hiệu quả với số phần tử lớn như quick sort hay merge sort.

    Về bài 2 thì sau khi đã sort giảm dần rồi thì làm như thế này:
    Mã:
    maxGCD := -1;
    for i := 1 to n do
       begin
          for j := 1 to m do
             begin
                t := gcd(a[i], b[j]);
                if (t > maxGCD) then maxGCD := t;
                if (b[j] <= maxGCD) then break;   // khi maxGCD đã lớn hơn b[j] thì cũng lớn hơn UCLN của a[i] và b[j+1].
             end;
          if (a[i] <= maxGCD) then break; // khi maxGCD đã lớn hơn a[i] thì cũng lớn hơn UCLN của a[i+1] và b[j].
       end;
    PS: Về bài 1, mình ko rõ có cách nào vừa quét là biết thứ tự luôn hay không, ko cần sort. Mình nghĩ chắc là có, đòi hỏi toán một chút, chỉ tiếc mình ko có thời gian đào sâu cái này. :-(

  8. #8
    Ðến Từ
    Quảng Bình
    Thành Viên Thứ: 333805
    Giới tính: Nam
    Bài gửi
    62

    Reply: Giúp bài tập Pascal về Phân số

    Mình viết đoạn sort đây rồi nhờ bạn code cho mình ak.
    Mình chưa rõ đoạn này. trong quá trình sort lại phân số mình swap cho hai mảng luôn phải không bạn
    việc so sánh rồi đổi chỗ tất cả đều làm trên sort dưới đây phải ko bạn


    Var a,b[1..1000]of integer;
    N: interger;

    Procedure hoanvi(var x,y: integer);
    var tam:integer
    begin
    tam:=x
    x:=y
    y:=tam
    end;
    Procedure Sort( Left, Right: Integer);
    Var
    i, j, k: Integer;
    Begin
    i:= Left;
    j:= Right;
    k:= A[(Left + Right) Div 2];
    Repeat
    While A[i] < k Do Inc(i);
    While k < A[j] Do Dec(j);
    If i <> j Then
    Begin
    HoanVi(A[i],A[j]);
    Inc(i);
    Dec(j);
    end;
    Until i > j;
    If Left < j Then Sort(Left,j);
    If i < Right Then Sort(i,Right);
    end;
    Begin
    Sort(Left; Right);
    End;
    Begin
    Sort(1,n)
    End.

  9. #9
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

    Reply: Giúp bài tập Pascal về Phân số

    Theo như đoạn code của bạn:
    Mã:
    Procedure Sort( Left, Right: Integer);
    Var i, j, kA, kB: Integer;
    Begin
       i:= Left;
       j:= Right;
       kA:= A[(Left + Right) Div 2];   // tử số của phân số ở giữa mảng.
       kB:= B[(Left + Right) Div 2];   // mẫu số của phân số ở giữa mảng.
       Repeat
          While (compare(A[i], B[i], kA, kB) < 0) Do Inc(i);     // phân số A[i]/B[i] < phân số kA/kB.
          While (compare(kA, kB, A[j], B[j]) < 0) Do Dec(j);    // phân số kA/kB < phân số A[j]/B[j].
          If i <> j Then
             Begin
                HoanVi(A[i], A[j]);   // đổi chỗ tử số
                HoanVi(B[i], B[j]);   // đổi chỗ mẫu số
                Inc(i);
                Dec(j);
             end;
       Until i > j;
       If Left < j Then Sort(Left,j);
       If i < Right Then Sort(i,Right);
    end;
    Còn hàm so sánh 2 phân số mình để lại cho bạn nhé.