Chuyên Tin Pro

Chuyên Tin Pro

Chỉ có những bộ óc đươc chuẩn bị sẵn mới có được những phát minh tình cờ
 
IndexIndex  PortalPortal  CalendarCalendar  GalleryGallery  Trợ giúpTrợ giúp  Tìm kiếmTìm kiếm  Thành viênThành viên  NhómNhóm  Đăng Nhập  Đăng kýĐăng ký  
Chào mừng bạn đến với forum khối chuyên tin,trường THPT chuyên Nguyễn Trãi-Nơi kết nối những trái tim,nơi bạn thể hiện bản thân mình.Hãy cùng tham gia và cảm nhận.!
Tìm kiếm
 
 

Display results as :
 
Rechercher Advanced Search
Similar topics
December 2016
MonTueWedThuFriSatSun
   1234
567891011
12131415161718
19202122232425
262728293031 
CalendarCalendar
Your first subject
Sat Feb 06, 2010 5:40 pm by Admin
Take some time to read this information before starting to use the administration of your forum:

How to access your administration panel ?
In the top menu, click on Log In, a new page is displayed. Fill in the username "admin" and the password you have choosen during your registration. If you have lost or forgot it, click here. Once you are logged in, click on the link "Administration Panel" at …

[ Full reading ]
Comments: 0
Latest topics

Share | 
 

 BÀI TÓAN CHIA KẸO

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
flp_102
Mem VIP
Mem VIP


Tổng số bài gửi : 48
Reputation : 0
Join date : 06/02/2010
Age : 22
Đến từ : vương quôc ko có computer

Bài gửiTiêu đề: BÀI TÓAN CHIA KẸO   Thu Mar 18, 2010 11:43 am

BÀI TÓAN CHIA KẸO

Trong số báo THNT tháng 8/2003, chuyên mục Đề ra kỳ này, có bài tóan “Chia kẹo”. Nội dung của bài tóan như sau:



Có N gói kẹo, gói thứ i có A[i] cái kẹo.



Yêu cầu: Hãy tìm cách chia các gói kẹo này thành 2 phần sao cho độ chênh lệch giữa tổng số kẹo ở hai phần là ít nhất có thể được 0 <A[i] <1000, 2<=N<=10000

Dữ liệu vào:

Cho trong file Chiakeo.inp: Một dòng duy nhất gồm các giá trị là số kẹo trong mỗi gói, các số cách nhau bởi một dấu cách (N = số gói kẹo đọc được)



Dữ liệu ra:

Ghi ra file Chiakeo.out

<!--[if !supportLists]-->- <!--[endif]-->Dòng 1 lần lượt ghi 3 số: tổng số kẹo ở phần 1, phần 2 và độ chênh lệch giữa hai phần.

<!--[if !supportLists]-->- <!--[endif]-->Dòng 2,3 là giá trị các gói kẹo ở mỗi phần được chia.



Dạng bài tóan này xuất hiện nhiều trong các ứng dụng về lập lịch, nó còn có tên gọi là Number Partitioning. Đây là một bài tóan thuộc lớp NP đầy đủ, không có thuật tóan tốt để giải. Bài viết này xin được trình bày một cách giải Heuristic cho ra kết qủa khá tốt.



Ta phát biểu lại bài tóan: cho n số (trong trường hợp này là số nguyên), tìm cách chia thành 2 phần sao cho độ chênh lệch tổng các số của mỗi phần là ít nhất có thể được



Trước hết chúng ta hãy xem xét một số cách giải:

<!--[if !supportLists]-->1. <!--[endif]-->Duyệt vét cạn

Thuật tóan vét cạn dễ hiểu nhất là xét tất cả các tập con có thể, và trả về tập con có tổng gần với một nửa tổng các số nhất. Nếu có n số, độ phức tạp của thuật tóan sẽ là O(2n) bởi vì một tập n phần tử có 2n tập con. Không gian tính tóan sẽ là O(n). Như vậy cách tiếp cận này không thực tiễn khi n lớn.

Cũng với tư tưởng duyệt vét cạn, bạn có thể cải tiến thành một thuật tóan có độ phức tạp O(2n/2) nhưng ở đây sẽ không bàn kỹ về vấn đề này.

<!--[if !supportLists]-->2. <!--[endif]-->Quy họach động

Thuật giải quy họach động đòi hỏi một mảng bít a[i] có kích thước là tổng các số, a[i]=1 khi và chỉ khi tồn tại tập con có tổng bằng i. Ban đầu, ta khởi tạo mảng a bằng 0, đặt a[0]=1. Sau đó với mỗi số x , quét lại mảng a, và với mỗi phần tử a[i]=1, ta đặt a[i+x]=1. Tiếp tục cho đến khi xét hết dãy số. Không gian tính tóan của thuật giải này phụ thuộc vào tổng các số. Do đó, nó chỉ thực tiễn với các số là số nhỏ, và phải là số nguyên.

<!--[if !supportLists]-->3. <!--[endif]-->Tham lam

Thuật giải tham lam dễ thấy nhất cho bài tóan này như sau: sắp xếp các số theo thứ tự giảm, rồi đặt số lớn nhất vào một trong hai tập. Sau đó, đặt số tiếp theo vào tập đang có tổng bé hơn, tiếp tục cho đến khi tất cả các số được xét.

Thuật giải này cài đặt rất nhanh, nhưng thường cho ra kết qủa không được tốt lắm



Phương pháp Karmarkar-Karp

Dưới đây, chúng ta xem xét một phương pháp Heuristic cho kết qủa khá tốt và cũng không khó cài đặt lắm.

Phương pháp Karmarkar-Karp (KK) đầu tiên sẽ sắp xếp các số theo thứ tự giảm dần. Tại mỗi bước, thuật tóan sẽ lấy hai số lớn nhất phân vào hai phần khác nhau ; mà chưa cần quan tâm là số nào sẽ đi vào tập nào.

Cụ thể, thuật tóan sẽ lọai bỏ hai số lớn nhất, lấy hiệu của chúng – xem đó như một số khác và chèn trở lại vào danh sách đã sắp xếp. Thuật tóan sẽ tiếp tục cho đến khi chỉ còn lại 1 số duy nhất, đó chính là giá trị chênh lệch của hai tập.

Ví dụ, ta có dãy (8; 7; 6 ; 5 ;4 )

Bước
Dãy
Hiệu của 2 số lớn nhất

0
(8; 7; 6 ; 5 ; 4)
8 – 7 = 1

1
(6; 5; 4; 1)
6 – 5 = 1

2
(4; 1; 1)
4 – 1 = 3

3
(3; 1)
3 – 1 = 2

4
(2)





Trong ví dụ này, bạn sẽ thấy phương pháp KK chạy tốt hơn phương pháp tham lam, nhưng vẫn chưa đưa ra được kết qủa tối ưu nhất.



Nếu cần in ra nội dung của mỗi tập, ta cần phải xây dựng 1 cây, với mỗi nút đại diện cho một số trong dãy ban đầu. Mỗi khi phân 2 số lớn nhất vào 2 tập, bạn nối một cạnh giữa 2 nút tương ứng. Cuối cùng, ta sẽ có một đồ thị là một cây bao trùm của các nút ban đầu; sau đó ta sẽ dùng phép tô màu để xác định nội dung của mỗi tập.

Ví dụ, hình dưới đây cho thấy cây được tạo ra từ ví dụ trên. Đầu tiên, nối một cạnh giữa 8 và 7, sau đó nút lớn hơn là 8 bây giờ sẽ thay thế cho hiệu của chúng là 1. Tiếp theo, nối 1 cạnh giữa 6 và 5, thay 6 bởi 1, v.v...

<!--[if !vml]--><!--[endif]-->

Đồ thị tạo thành sẽ tạo thành một cây bao trùm của các nút ban đầu, đó là vì mọi số cuối cùng đều phải được kết hợp, và tổng cộng có n-1 cạnh được tạo ra. Bây giờ chúng ta tô các nút bằng 2 màu, sao cho không có 2 nút kề nào có mầu giống nhau; từ đó nhận ra được các phần tử của mỗi tập được phân chia. Để tô màu, đầu tiên tô một nút tùy ý, sau đó tô tất cả các nút kề với nút này bằng màu còn lại; tiếp tục như vậy, cho đến khi tất cả các nút đều được tô màu.

Trong ví dụ trên, sau khi tô màu, ta nhận được 2 tập con, mỗi tập chứa các nút cùng màu, (7; 4; 5) và (8; 6); cho ta độ chênh lệnh là 2.

Độ phức tạp của thuật tóan là O(n log n) để sắp xếp n số, O(n log n) cho các bước xử lý (bằng cách dùng heap), và O(n) cho bước tô màu. Như vậy tổng cộng độ phức tạp của thuật tóan là O(n log n)

Để giải thích tại sao phương pháp KK Heuristic lại tốt hơn so với thuật giải tham lam thông thường, cần phải có những đánh giá bằng tóan học mà chúng ta sẽ không bàn đến ở đây.



Sau đây là cài đặt của bài tóan JOHNNY (spoj.sphere.pl/problems/JOHNNY), một bài tóan có nội dung hòan tòan giống như bài tóan chia kẹo ở trên.

Để cho gọn, chúng ta chỉ xem qua quy cách input và output của bài tóan:



Input:

Dòng đầu tiên chứa số nguyên n (n<=10000) là số lượng các số trong dãy

N dòng sau, mỗi dòng chứa một số nguyên dương bé hơn 10^14.



Output:

In ra số thứ tự của các số thuộc 1 trong 2 tập (tập nào cũng được) mà ta phân chia, mỗi số trên một dòng.



Scoring

Số điểm bạn nhận được là log10(s/|d|+1) , trong đó s là tổng các số, còn d là chênh lệch giữa hai phần mà chương trình của bạn chia ra.



Ví dụ:

Input mẫu:

3

5

8

4



Output mẫu:

2

3



Bạn sẽ được số điểm là log10((5+8+4)/(8+4-5)+1))=0.327 điểm



Chương trình sau chạy trên nền Free Pascal; với chương trình này bạn có thể nhận được trên 17 điểm:



program johnny;



const finp='johnny.inp';

fout='johnny.out';



type

theap = record

sz:integer;

hh:array[1..10000] of integer;

end;



pnode = ^tnode;

tnode = record

v:integer;

next:pnode;

end;

llist = pnode;



var

tree:array[1..10000] of llist;

a,b:array[1..10000] of int64;

z:array[1..10000] of integer;

sum:array[0..1] of int64;

g:array[1..10000] of shortint;

d:int64; n:integer; h:theap;



procedure llist_insert(var l:llist; v:integer);

var p:pnode;

begin

new(p); p^.v:=v;

p^.next:=l; l:=p;

end;



procedure heapify(var h:theap; i:integer);

var l,r,j,t:integer;

begin

with h do

begin

l:=i shl 1; r:=i shl 1 + 1;

if (l<=sz) and (b[z[hh[l]]]>b[z[hh[i]]]) then

j:=l else j:=i;

if (r<=sz) and (b[z[hh[r]]]>b[z[hh[j]]]) then

j:=r;

if j<>i then

begin

t:=hh[i];

hh[i]:=hh[j];

hh[j]:=t;

heapify(h,j);

end;

end;

end;



procedure insert(var h:theap; k:integer);

var i:integer;

begin

with h do

begin

inc(sz);

i:=sz;

while (i>1) and (b[z[hh[i shr 1]]] < b[z[k]]) do

begin

hh[i]:=hh[i shr 1];

i:=i shr 1;

end;

hh[i]:=k;

end;

end;



procedure extractmax(var h:theap; var k:integer);

begin

with h do

begin

k:=hh[1];

hh[1]:=hh[sz];

dec(sz);

heapify(h,1);

end;

end;



procedure qsort(l,r:integer);

var i,j:integer;

p,t:int64;

begin

i:=l; j:=r; p:=a[z[(l+r) div 2]];

repeat

while a[z[i]]<p do inc(i);

while p<a[z[j]] do dec(j);

if i<=j then

begin

t:=z[i];

z[i]:=z[j];

z[j]:=t;

inc(i);

dec(j);

end;

until i>j;

if l<j then qsort(l,j);

if i<r then qsort(i,r);

end;



function str264(s:string):int64;

var code:integer;

begin

val(s,str264,code);

end;



procedure nhap;

var i:integer;

s:string;

begin

readln(n);

for i:=1 to n do

begin

readln(s);

a[i]:=str264(s);

z[i]:=i;

end;

end;



procedure chianhom;

var i,k1,k2:integer;

begin

b:=a;



for i:=n downto 1 do

insert(h,i);



for i:=1 to n-1 do

begin

extractmax(h,k1);

extractmax(h,k2);

llist_insert(tree[k1],k2);

llist_insert(tree[k2],k1);

b[z[k1]]:=b[z[k1]]-b[z[k2]];

insert(h,k1);

end;

end;



procedure tomau;

var q:array[1..10000] of integer;

x,y:integer;

i, top: integer;

p: pnode;

begin

for i:=1 to n do g[i]:=-1;

fillchar(sum,sizeof(sum),0);

x:=1; y:=1;

q[1]:=1; g[1]:=0;

sum[0]:=a[z[1]];



while x<=y do

begin

top:=q[x];

p:=tree[top];

inc(x);

while p<>nil do

begin

if g[p^.v]=-1 then

begin

inc(y);

q[y]:=p^.v;

g[p^.v]:=1-g[top];

inc(sum[g[p^.v]],a[z[p^.v]]);

end;

p:=p^.next;

end;

end;

end;



procedure xuly;

begin

qsort(1, n);

chianhom; tomau;

end;



procedure inkq;

var i:integer;

begin

for i:=1 to n do

if g[i]=0 then

writeln(z[i]);

end;



begin

assign(input, finp);

reset(input);

assign(output, fout);

rewrite(output);

nhap; xuly; inkq;

close(input);

close(output);

end.



Trên đây chỉ là bài tóan chia kẹo ở dạng đơn giản nhất (phân chia thành 2 tập). Bài tóan này còn có thể mở rộng hơn nữa; rất mong được có dịp trao đổi thêm cùng với các bạn.
Về Đầu Trang Go down
Xem lý lịch thành viên
_spam_
Học Viên 2
Học Viên 2


Tổng số bài gửi : 36
Reputation : 2
Join date : 06/02/2010
Age : 22
Đến từ : học viện chém gió

Bài gửiTiêu đề: Re: BÀI TÓAN CHIA KẸO   Sun Mar 21, 2010 8:53 pm

éo chỉ 17 điểm thôi ak
ko đc tối đa sao....
Về Đầu Trang Go down
Xem lý lịch thành viên
 
BÀI TÓAN CHIA KẸO
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Chia sẻ nick facebook cho nhau =))
» [26/5/15][News] PD của Running Man chia sẻ về buổi ghi hình cùng BIGBANG
» Độ ngập nước chân vịt
» cách hàng hải cung vòng lớn
» Bài tập phân chia tổn thất chung

Permissions in this forum:Bạn không có quyền trả lời bài viết
Chuyên Tin Pro :: Học sinh khối chuyên Tin trường THPT chuyên Nguyễn Trãi - Hải Dương :: [TPNT] G Ó C H Ọ C T Ậ P :: Tin-
Chuyển đến