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
 
Sửa lần cuối:
T

tengiday

Happy life
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: 
https://vfo.vn/t/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 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.
 
Sửa lần cuối:
V

vansonqtqb

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
 
T

tengiday

Happy life
vansonqtqb:
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
Nhấn để mở rộng...
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, b[j]). Bạn lưu ý khi a 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, 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, b[j + 1]), (a, 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, 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).
 
Sửa lần cuối:
T

tuongsonqt

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,b);
for i:=1 to n do
begin
for j:= to m do
begin
if uc < ucln(a,b[j]) then
break
end;
 
Sửa lần cuối:
V

vansonqtqb

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
 
T

tengiday

Happy life
Đ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 < a[j] thì bây giờ phải là 1 hàm so sánh 2 phân số a/b 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. :-(
 
Sửa lần cuối:
V

vansonqtqb

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 < k Do Inc(i);
While k < A[j] Do Dec(j);
If i <> j Then
Begin
HoanVi(A,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.
 
T

tengiday

Happy life
Theo như đoạn code của bạn:
Mã: 
Procedure Sort( Left, Right: Integer);
Var i, j, [COLOR=#ff0000]kA, kB[/COLOR]: Integer;
Begin
   i:= Left;
   j:= Right;
   [COLOR=#ff0000]kA:= A[(Left + Right) Div 2];   [/COLOR]// tử số của phân số ở giữa mảng.
   [COLOR=#ff0000]kB:= B[(Left + Right) Div 2];   [/COLOR]// mẫu số của phân số ở giữa mảng.
   Repeat
      While [COLOR=#ff0000](compare(A[i], B[i], kA, kB) < 0)[/COLOR] Do Inc(i);     // phân số A[i]/B[i] < phân số kA/kB.
      While [COLOR=#ff0000](compare(kA, kB, A[j], B[j]) < 0)[/COLOR] Do Dec(j);    // phân số kA/kB < phân số A[j]/B[j].
      If i <> j Then
         Begin
            [COLOR=#ff0000]HoanVi(A[i], A[j]);   [/COLOR]// đổi chỗ tử số
            [COLOR=#ff0000]HoanVi(B[i], B[j]);   [/COLOR]// đổ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é.
 
Đăng nhập bằng tài khoản VFO hoặc Google

Bài viết mới nhất

Thống kê

Chủ đề
100,657
Bài viết
467,424
Thành viên
339,832
Thành viên mới nhất
tiendungmobi

Bài viết được quan tâm nhiều

Top