Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
Bảng giá phần mềm
Educations Software

Đại Lý - Chi Nhánh

Bản tin điện tử
 
Đăng nhập/Đăng ký
Bí danh
Mật khẩu
Mã kiểm traMã kiểm tra
Lặp lại mã kiểm tra
Ghi nhớ
 
Quên mật khẩu | Đăng ký mới

 
Giỏ hàng

Xem giỏ hàng


Giỏ hàng chưa có sản phẩm

 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (701 bài viết)
  • Sản phẩm mới (217 bài viết)
  • Dành cho Giáo viên (552 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (155 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (126 bài viết)
  • Hỗ trợ khách hàng (482 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (182 bài viết)
  • Thông tin khuyến mại (80 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (71 bài viết)
  • Cùng Học (98 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (74 bài viết)
  • Thông tin tuyển dụng (55 bài viết)
  • School@net 15 năm (153 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (123 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (360 bài viết)
  • Các vấn đề giáo dục (1209 bài viết)
  • Bài học trực tuyến (1033 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (276 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (181 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8179 bài viết)
  •  
    Thành viên có mặt
    Khách: 5
    Thành viên: 0
    Tổng cộng: 5
     
    Số người truy cập
    Hiện đã có 54824901 lượt người đến thăm trang Web của chúng tôi.

    Nói thêm về Cặp Ghép

    Ngày gửi bài: 10/01/2009
    Số lượt đọc: 1786

    Cho N sinh viên( N<=12 ) và N vấn đề cần nghiên cứu. Mỗi sinh viên sẽ hứng thú với 1 số vấn đề, và khi sinh viên được giao vấn đề họ thích thì họ sẽ làm việc hiệu quả hơn rất nhiều. Ngài giáo sư đáng kính của chúng ta muốn biết có bao nhiêu cách ghép sao cho mỗi sinh viên sẽ giải quyết 1 vấn đề mà họ thích.

    Giáo sư sẽ cung cấp cho chúng ta 1 ma trận A kích thước NxN trong file PROBLEM.TXT với

    + A[i,j]=1 khi sinh viên i thích vấn đề j.

    + A[i,j]=0 khi sinh viên i không thích vấn đề j.

    Yêu cầu:Bạn hãy viết 1 chương trình tính số ghép thoả mãn yêu cầu của giáo sư và gửi file kết quả SOLVE.TXT cho giáo sư.

     

    Ví dụ:

    PROBLEM.TXT

    3
    1 1 1
    1 1 1
    1 1 0

     

    SOLVE.TXT

    4

    Giải thích : 4 cặp ghép là

    ((1,2),(2,3),(3,1))

    ((1,1),(2,3),(3,2))

    ((1,3),(2,1),(3,2))

    ((1,3),(2,2),(3,1))

     

    Bài toán trên ta có thể giải theo cách tầm thường là tìm toàn bộ cách khả năng có thể ghép bằng cách vét cạn, độ phức tạp là N!. Trong trường hợp ma trận A gồm toàn số 1, số cách chọn sẽ là N!.

    Dù N<=12 nhưng N! vẫn là 1 giá trị “khủng khiếp”.

     

    Sau đây tôi xin đề xuất cách giải với thuật toán QHĐ trạng thái. Xin nói qua về QHĐ trạng thái.

    QHĐ trạng thái là QHĐ trên các trạng thái, các trang thái thường được biều diễn bằng 1 dãy bít hoặc tính trước.

    Ví dụ 1: Bài 1 thi QG năm 2006 bảng B ( tôi không nói lại đề ) : Ta dùng QHĐ trạng thái với 8 trạng thái cho mỗi dòng : (0,0),(0,1),(0,2),(0,3),(0,4),(1,3),(1,4),(2,4) với ý nghĩa (i,j) là chọn ô i và ô j, giá trị 0 là không chọn ô nào.

    Ví dụ 2: Bài viết “chia sẻ 1 thuật toán hay” của bạn Nguyễn Hiển. Bạn đã dùng 1 dãy bít với ý nghĩa là bít thứ i bằng 1 nếu công việc đó được chọn, bằng 0 nếu công việc đó không được chọn.

     

    Trở lại bài toán của chúng ta. Ta biết: 1 cách ghép cặp là cách ghép 1 sinh viên và 1 vấn đề. Giả sử ta có 1 cách ghép cặp (x1,y1),(x2,y2),…,(xn,yn). Bây giờ ta bỏ đi 1 cặp (x1,y1). Cặp ghép còn lại là (x2,y2),(x3,y3),…,(xn,yn) vẫn là 1 cặp ghép, ta có bài toán với kích thước nhỏ hơn. Như vậy các bạn đã thấy rõ bản chất QHĐ của bài toán này. Để tìm số cách ghép của N sinh viên, ta phải tìm số cách ghép của N-1 sinh viên.

    Ta định nghĩa 1 dãy bít X thay cho các trạng thái của các vấn đề. X[i]=1 nếu vấn đề i được chọn. X[i]=0 nếu vấn đề i không được chọn. Độ dài dãy bít tối đa là 12 nên ta thay 1 dãy bít X bằng 1 giá trị TX.

    Vì cặp ghép là đầy đủ nên số sinh viên ghép với 1 trạng thái X là số giá trị 1 trong X. Ta cố định các sinh viên này và duỵêt qua tất cả các trạng thái X. Gọi D[TX] là số cách ghép cặp 1 trạng thái X với sl sinh viên đầu tiên, sl là số bít 1 của trạng thái X. Ta có công thức QHĐ:

    D[TX] := D[TX]+D[TX xor (1 shl i)] với i thoả mãn X[i]=1 và có sinh viên sl thích vấn đề i.

    TX xor (1 shl i) có ý nghĩa là thay giá trị bít thứ i thành 0, ta đã giảm số vấn đề được chọn đi 1.

    Sau đây là chương trình:

    { Sử dụng Free Pascal }

     

    Constmax =1 shl 12;

    fi='PROBLEM.TXT';

    fo='SOLVE.TXT';

     

    Varn :Integer;

    f ,g: text;

    A:array[0..20,0..20] of Boolean;

    D:array[0..max] of longInt; {Mảng D có ý nghĩa như trên }

    T:array[0..20]ofInteger; { T lưu lại vị trí các bít 1 để dễ dàng QHĐ hơn }

     

    Procedure Tinh( TX : LongInt );

    Vargt , j , i , sl : LongInt;

    {sl là số lượng bít 1}

    Begin

    gt := TX;

    i:= -1;

    sl := -1;

    While gt> 0 do {vong while de tim cac bit 1 trong phan tich nhi phan so TX}

    Begin

    Inc( i );

    If gt and 1 = 1 then {neu bít i là 1 }

    Begin

    Inc(sl);

    T[pt]:=i; {luu lai vi tri cac bit 1}

    End;

    gt:= gt shr 1;

    End;

    D[TX]:=0;

    For j :=0 to sl do

    If A[ sl , T[j] ] then {Sinh viên sl thích vấn đề T[j]}

    Inc( D[TX] , D[ TX xor (1 shl T[j])] );

    {TX xor (1 shl T[j] là tắt bit thứ T[j]}

    End;

     

    Procedure Xuli;

    VarTX:LongInt;

    Begin

    D[0]:=1;

    For TX:=1 to (1 shl n)-1 do

    Tinh(TX); {QHD voi so TX

    Writeln(g, D[1 shl n-1] );

    End;

     

    Procedure Nhap;

    Vari ,j,t:Integer;

    Begin

    Read(f,n);

    For i:=0 to n-1 do

    For j:=0 to n-1 do

    Begin

    Read(f,t);

    A[i,j]:= t =1;

    End;

    End;

     

    Begin

    assign(f,fi);reset(f);

    assign(g,fo);rewrite(g);

    fillchar(d,sizeof(d),0);

    Nhap;

    Xuli;

    close(f);close(g);

    End.

     

    Thuật toán trên có độ phức tạp khoảng 2^N, hiệu quả hơn rất nhiều so với cách duyệt bình thường.

    Bài toán trên đã giải quyết xong. Bây giờ, ta sẽ thay đổi bài toán trên 1 chút:

    Vị giáo sư đáng kính muốn biết có bao nhiêu cách ghép cặp mà trong đó có chứa cặp sinh viên x và vấn đề y.

    Khi ta đã giải quyết được bài toán trên thì bài toán mở rộng trở nên quá dễ.

    Trên đây, tôi xin bàn thêm về bài toán cặp ghép. Để nói hết thì thật là khó. Hi vọng các bạn sẽ cùng tôi khám phá những điều mới mẻ và lý thú từ những thuật toán hay.

     

    Lưu Tuấn Anh

    School@net (Theo THNT)



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 1407 - Nhà 17T2 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Điện thoại: (024) 62511017 - Fax: (024) 62511081
    Email: school.net@hn.vnn.vn / thukhachhang@yahoo.com


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.