Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Monday, December 16, 2013



Liệt kê các tổ hợp chặp K của N  phần tử 1..N theo thứ tự từ điển tăng dần.

TOHOP.INP
TOHOP.OUT

5 3




1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5

Dữ liệu vào: tệp văn bản TOHOP.INP
Dòng đầu tiên: hai số N và K cách nhau qua dấu cách,
1 £ N £ 9, K £ N.
Dữ liệu ra: tệp văn bản TOHOP.OUT
Mỗi dòng một tổ hợp, các số trên cùng dòng cách nhau qua dấu cách.

Thuật toán

Phương án 1. Ta khởi trị cho mảng x[1..K] là tổ hợp nhỏ nhất (1,2,…,K). Sau đó ta dùng hàm Next để sinh ra tổ hợp sát sau của x. Hàm Next hoạt động theo 2 pha như sau:
Pha 1. Dỡ. Duyệt ngược từ K qua trái bỏ qua những phần tử mang giá trị …N-2, N-1, N đứng cuối mảng. Nếu sau khi dỡ x không còn phần tử nào thì kết thúc với Next = false với ý nghĩa là sát sau tổ hợp x không còn tổ hợp nào. Thí dụ, nếu N = 7, K = 5, x[1..5] = (2,3,5,6,7) thì sau khi dỡ ba phần tử cuối của x ta thu được i = 2, x[1..2] = (2,3). Điều này cho biết sẽ còn tổ hợp sát sau.
Pha 2. Xếp.
2.1. Tăng phần tử x[i] thêm 1 đơn vị. Tiếp tục với thí dụ trên ta thu được x[1..2] = (2,4)
2.2. Xếp tiếp vào x cho đủ K phần tử theo trật tự tăng dần liên tục. Tiếp tục với thí dụ trên ta thu được x[1..5] = (2,4,5,6,7).
Ta sử dụng phần tử x[0] = N làm lính canh.
(* Pascal, Phuong an 1 *)
function Next: Boolean;
   var i, j, b: integer;
 begin
   Next := false; x[0] := N;
   { Pha 1. Do }
   i :=  k; b := n - k;
   while (x[i] = b + i) do i := i - 1;
   if (i = 0) then exit;
   { Pha 2. Xep }
   x[i] := x[i] + 1;
   for j := i + 1 to k do x[j] := x[j-1] + 1;
   Next := true;
 end;
Độ phức tạp: cho hàm Next: 2N, cho cả bài: 2N.CNK= (2N. N!) / (K! (N-K)!) .
Phương án 2.           Ta cải tiến hàm Next như sau. Giả sử sau pha 1 ta thu được vị trí i thỏa x[i] ≠ n-k+i. Ta gọi vị  trí này là vị trí cập nhật và sẽ điều khiển nó thông qua một biến v.  Ta khởi trị cho x và v như sau
 for i := 1 to k do x[i] := i;
      if (x[k] = n) then v := 0 else v := k;
Sau đó mỗi lần gọi hàm Next ta kiểm tra
Nếu v = 0 thì dừng hàm Next.
Nếu v ≠ 0 ta thực hiện pha 2 sau đó chỉnh lại giá trị của v như sau:
Nếu x[k] = n thì tức là x[v..k] = (n-k-v, ..., n-1, n) thì lần gọi Next tiếp theo sẽ cập nhật tại vị trí v-1, ngược lại, nếu x[k] ≠ n thì lần gọi Next tiếp theo sẽ cập nhật tại vị trí k.  
Độ phức tạp: cho hàm Next: N. Cho cả bài: N.CNK= (N. N!) / (K! (N-K)!).
(*  Pascal,  Phương án 2  *)
(***************************************
      To hop chap k cua n phan tu
              PHUONG AN 2
***************************************)
program ToHopKN;
uses crt;
const
  bl = #32; mn = 10;  fn = 'TOHOP.INP';  gn = 'TOHOP.OUT';
type
  mb1 = array[0..mn] of byte;
var
 x: mb1;
 n, k, v: byte;
 f,g: text;
 procedure Doc;
 begin
   assign(f,fn); reset(f); readln(f,n,k); close(f);
 end;
 function Next: Boolean;
   var i: byte;
 begin
   Next := false;
   if (v = 0) then exit;
   { Pha 2. Xep }
   x[v] := x[v] + 1;
   for i := v + 1 to k do x[i] := x[i-1] + 1;
   if (x[k] = n) then v := v - 1 else v := k;
   Next := true;
 end;
 procedure Run;
   var i: byte;
 begin
   Doc;
   assign(g,gn); rewrite(g);
   for i := 1 to k do x[i] := i;
   if (x[k] = n) then v := 0 else v := k;
   repeat
     for i := 1 to k do write(g,x[i],bl);
     writeln(g);
   until not Next;
   close(g);
 end;
 BEGIN
  Run;
 END.


Nguồn:

SÁNG TẠO
TRONG THUẬT TOÁN
LẬP TRÌNH


tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts