Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Tin học Skkn chọn cấu trúc dữ liệu cho bài toán quy hoạch động...

Tài liệu Skkn chọn cấu trúc dữ liệu cho bài toán quy hoạch động

.PDF
29
1953
85

Mô tả:

SỞ GIÁO DỤC VÀ ĐÀO TẠO ĐỒNG NAI Đơn vị Trường THPT chuyên Lương Thế Vinh Mã số: ................................ SÁNG KIẾN KINH NGHIỆM CHỌN CẤU TRÚC DỮ LIỆU CHO BÀI TOÁN QUY HOẠCH ĐỘNG Người thực hiện: LÊ QUANG VINH Lĩnh vực nghiên cứu: - Quản lý giáo dục  - Phương pháp dạy học bộ môn: TIN HỌC  - Lĩnh vực khác: .......................................................  Có đính kèm: Các sản phẩm không thể hiện trong bản in SKKN  Mô hình  Đĩa CD (DVD)  Phim ảnh Năm học: 2014 - 2015  Hiện vật khác SƠ LƯỢC LÝ LỊCH KHOA HỌC –––––––––––––––––– I. THÔNG TIN CHUNG VỀ CÁ NHÂN 1. Họ và tên: LÊ QUANG VINH 2. Ngày tháng năm sinh: 19/12/1985 3. Nam, nữ: Nam 4. Địa chỉ: Phòng V3, KTX trường THPT chuyên Lương Thế Vinh 5. Điện thoại: (CQ)/ 6. Fax: (NR); ĐTDĐ: 0167 803 8755 E-mail: [email protected] 7. Chức vụ: Tổ trưởng 8. Nhiệm vụ được giao: giảng dạy 9. Đơn vị công tác: trường THPT chuyên Lương Thế Vinh II. TRÌNH ĐỘ ĐÀO TẠO - Học vị (hoặc trình độ chuyên môn, nghiệp vụ) cao nhất: Thạc sĩ - Năm nhận bằng: 2012 - Chuyên ngành đào tạo: Công nghệ thông tin III. KINH NGHIỆM KHOA HỌC - Lĩnh vực chuyên môn có kinh nghiệm: Giảng dạy Tin học Số năm có kinh nghiệm: 8 - Các sáng kiến kinh nghiệm đã có trong 5 năm gần đây: o Lý thuyết và bài tập đồ thị - Phần cây khung (năm 2011) o Website bồi dưỡng năng khiếu tin học (năm 2012) o Đưa bài tập trên website VNOI vào giảng dạy Tin học chuyên (năm 2013) o Định hướng ra đề các kì thi học sinh giỏi bộ môn Tin học (năm 2014) Tên SKKN : CHỌN CẤU TRÚC DỮ LIỆU CHO BÀI TOÁN QUY HOẠCH ĐỘNG I. LÝ DO CHỌN ĐỀ TÀI Trong các kì thi học sinh giỏi cấp tỉnh, cấp quốc gia hiện nay, dạng bài toán Quy hoạch động ngày càng phổ biến, chiếm đa số trong các bài thi. Bài toán Quy hoạch động đề cập ở đây là bài toán có thể giải bằng phương pháp Quy hoạch động. Tư tưởng của phương pháp này là tính kết quả của bài toán chính thông qua kết quả các bài toán con của nó theo một công thức truy hồi. Việc lưu trữ kết quả các bài toán con một cách tối ưu là nhiệm vụ chính của phương pháp này. Học sinh mới làm quen dạng bài này thường gặp khó khăn khi chọn cấu trúc dữ liệu để lưu trữ. Sáng kiến kinh nghiệm “Chọn cấu trúc dữ liệu cho bài toán Quy hoạch động” giới thiệu một số bài tập Quy hoạch động được phân loại theo các cấu trúc dữ liệu sử dụng. Giúp cho học sinh dễ dàng nhận biết dạng bài và có thêm “kinh nghiệm” để chọn đúng cấu trúc dữ liệu. Sáng kiến kinh nghiệm này nhằm mục đích:  Bồi dưỡng học sinh các lớp chuyên Tin  Bồi dưỡng các đội tuyển thi học sinh giỏi.  Giới thiệu, trao đổi với giáo viên đồng nghiệp về dạng bài toán Quy hoạch động và cách tiếp cận theo hướng cấu trúc dữ liệu. II. CƠ SỞ LÝ LUẬN VÀ THỰC TIỄN Hiện đã có một số tài liệu trình bày chuyên đề Quy hoạch động như:  Sách giáo khoa chuyên Tin quyển 1 [1, 97 - 107]: trình bày một số ví dụ đặc trưng và bài tập rèn luyện. Chưa có phân loại theo một tiêu chí nhất định.  Giải thuật và lập trình [2, 155 - 189]: trình bày giống Sách giáo khoa chuyên Tin quyển 1.  Tài liệu bồi dưỡng năng khiếu Tin học khối THPT [4, 85 – 109]: trình bày nhiều ví dụ về bài toán Quy hoạch động, có lời giải, chương trình cài đặt cụ thể. Tuy nhiên, chưa có phân loại bài tập.  Kho bài tập trên website spoj.com [5]: tổng hợp bài tập của tất cả các dạng bài, thích hợp để học sinh luyện tập. Các bài tập Quy hoạch động trên website cũng chưa được phân loại. Trong quá trình giảng dạy các lớp chuyên Tin, tác giả nhận thấy đa số các học sinh khi mới làm quen với dạng bài này, sau khi tìm ra công thức truy hồi, thường gặp khó khăn trong việc cài đặt, mà chủ yếu là chọn cấu trúc dữ liệu để lưu trữ các bài toán con. Cần có một sự phân loại chi tiết hơn các bài toán Quy hoạch động. Tác giả chọn tiêu chí phân loại theo cấu trúc dữ liệu để giúp học sinh có thêm “kinh nghiệm” để chọn đúng cấu trúc dữ liệu cho bài toán. 1 III. TỔ CHỨC THỰC HIỆN CÁC GIẢI PHÁP 1. Tổ chức thực hiện 1) Tìm hiểu nội dung chương trình tin học chuyên sâu, nội dung chuyên đề Quy hoạch động trong tài liệu “Chương trình chuyên sâu THPT chuyên – môn Tin học” do Bộ Giáo Dục và Đào Tạo phát hành năm 2009.  Theo tài liệu này, chuyên đề Quy hoạch động được giảng dạy trong 15 tiết ở khối 11, sau khi học xong yêu cầu học sinh phải làm được các bài toán quen thuộc như: - Bài toán dãy con đơn điệu tăng dài nhất; Bài toán xâu con chung dài nhất; Bài toán biến đổi xâu; Bài toán cái túi; Bài toán lũy thừa một số; Bài toán nhân các ma trận; Bài toán chia đa giác thành các tam giác; …  Để phù hợp hơn với thực tế giảng dạy ở trường, tác giả chia chuyên đề này thành 2 phần: phần cơ bản dạy ở khối 10 và phần nâng cao dạy ở khối 11. Các ví dụ trình bày trong đề tài này chủ yếu dành cho các học sinh lớp 10 mới làm quen với bài toán Quy hoạch động. 2) Tham khảo các tài liệu, giáo án, dự giờ các tiết dạy về chuyên đề Quy hoạch động của đồng nghiệp.  Sau khi tham khảo các tài liệu, dự giờ một số tiết dạy của đồng nghiệp. Tác giả nhận thấy phần lớn đều trình bày vấn đề từ dễ đến khó, từ ví dụ cụ thể đến bài tập vận dụng. Cách trình bày này có nhiều ưu điểm, học sinh nắm bắt vấn đề dễ dàng. Các ví dụ trong đề tài này được trình bày theo cách trên, bổ sung thêm phần phân loại các bài toán. 3) Tham khảo các đề thi học sinh giỏi Tin học cấp tỉnh, cấp quốc gia, Olympic 30.4 ...  Như đã trình bày ở trên, các bài toán Quy hoạch động chiếm đa số trong các bài thi học sinh giỏi. Trong đề tài này có sử dụng một số bài tập Quy hoạch động trích từ các đề thi. 4) Sưu tầm, xây dựng, phân loại các bài tập theo hướng Cấu trúc dữ liệu sử dụng.  Sau khi nghiên cứu cách giải các bài tập được tham khảo từ các đề thi, tài liệu, website, tác giả tiến hành phân loại theo tiêu chí cấu trúc dữ liệu sử dụng. 5) Giảng dạy thử nghiệm chuyên đề Quy hoạch động cơ bản cho lớp 10 Tin. Theo dõi khả năng tiếp thu của học sinh. Lấy ý kiến học sinh về những tích cực và hạn chế của việc phân loại bài tập. 2 Chuyên đề Quy hoạch động cơ bản được dạy trong 5 (buổi) x 4 (tiết) = 20 (tiết), theo phân bố như sau Buổi 1 Tên bài Nội dung Làm quen với bài  Nguyên lí tối ưu, đặc trưng các bài toán có toán Quy hoạch động. thể giải bằng thuật toán QHĐ, đặc trưng chính của thuật toán QHĐ.  Sự giống và khác nhau căn bản giữa thuật toán QHĐ và Đệ quy  Cách nhận biết được bài toán cụ thể có thể giải được bằng QHĐ hay không. 2 Dạng 1: dùng biến  Các bài tập dạng 1. đơn để lưu trữ lời giải cho bài toán QHĐ. 3 Dạng 2: dùng mảng 1  Các bài tập dạng 2. chiều để lưu trữ lời giải cho bài toán QHĐ 4 Dạng 3: dùng mảng 2  Các bài toán dạng 3. chiều để lưu trữ lời giải cho bài toán QHĐ 5 Ôn tập, kiểm tra  Để kiểm tra cuối chuyên đề. 5) Tổng kết, sửa chữa, hoàn thiện đề tài. Sau khi giảng dạy chuyên đề Quy hoạch động cơ bản cho lớp 10 Tin, tác giả tiến hành lấy ý kiến đồng nghiệp, học sinh để rút kinh nghiệm. Tiến hành sửa chữa và hoàn thiện đề tài. 2. Nội dung của đề tài Cấu trúc dữ liệu được sử dụng trong bài toán Quy hoạch động rất đa dạng. Từ các cấu trúc dữ liệu cơ bản có sẵn như: biến, mảng 1 chiều, mảng 2 chiều, … cho đến các kiểu dữ liệu nâng cao tự xây dựng như: stack, queue, tree, heap, … Vì giới hạn thời gian, và để học sinh mới làm quen dễ dàng tiếp thu, đề tài chỉ giới hạn các bài tập sử dụng các cấu trúc dữ liệu cơ bản. Các dạng nâng cao sẽ được tiếp tục bổ sung trong thời gian tới. 3 2.1. Dạng 1: Dùng biến đơn Trong công thức truy hồi để tìm lời giải của bài toán chính, chỉ cần sử dụng một số ít (hai, ba …) lời giải của bài toán con. Ví dụ Bài 1. FIBO Dãy Fibonacci Dãy fibonacci là dãy vô hạn các số nguyên dương 1, 1, 2, 3, 5, 8, … Yêu cầu: Cho n. Hãy số hạng thứ n của dãy Input: số nguyên dương n (n < 103). Output: số hạng thứ n của dãy Fibonacci. Input Output 6 8 Giải Gọi Fn là số hạng thứ n của dãy số. Để giải bài toán trên, thông thường ta phải tìm được một công thức tính được Fn từ số n đầu vào. Các nhà toán học đã mất rất nhiều thời gian để tìm ra công thức: (1) Việc tìm ra được những công thức tường minh như trên là rất khó, đòi hỏi nhiều công sức, thời gian và phải có trình độ toán học cao cấp. Tuy nhiên, ta có thể lập công thức tính Fn theo dạng truy hồi như sau:  fi =1 nếu i≤2  fi = fi – 1 + fi-2, nếu i≥3. Công thức này mô tả quy luật của dãy số là “số sau bằng tổng hai số trước” mà một học sinh tiểu học bình thường cũng có thể nghĩ ra được. Với công thức này, muốn tìm số hạng thứ n, ta phải tìm được hai số hạng ngay trước n, muốn tìm hai số hạng phía trước này, ta lại tiếp tục phải tìm các số hạng phía trước nữa ... Sau đây là chương trình dùng 2 biến để lưu lại bài toán con fi1 và fi2 Chương trình const fin='fibo.inp'; fon='fibo.out'; procedure solve; var fi1,fi2,t:QWORD; n,i:longint; begin readln(n); 4 Fi1:=1;//fi-1 fi2:=1;//fi-2 For i:=3 to n do begin T:=fi1; fi1:=fi1+fi2; fi2:=t; end; writeln(fi1); end; begin assign(input,fin);reset(input); assign(output,fon);rewrite(output); solve; close(input);close(output); end. Bài 2. NKTICK Xếp hàng mua vé Có N người sắp hàng mua vé dự buổi hoà nhạc. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. Mỗi người cần mua một vé, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ti là thời gian cần thiết để người i mua xong vé cho mình. Nếu người i+1 rời khỏi hàng và nhờ người i mua hộ vé thì thời gian để người thứ i mua được vé cho cả hai người là ri. 5 Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất. Dữ liệu  Dòng đầu tiên chứa số N (1 ≤ N ≤ 60000).  Dòng thứ 2 ghi N số nguyên dương t1, t2, ..., tN. (1 ≤ ti ≤ 30000)  Dòng thứ ba ghi N-1 số nguyên dương r1, r2, ..., rN-1. (1 ≤ ri ≤ 30000) Input 5 Output 18 25784 4 9 10 10 4 24 5784 50 50 50 Kết quả: In ra tổng thời gian phục vụ nhỏ nhất. Giải Gọi f[i] là tổng thời gian mua vé nhỏ nhất tính từ người 1..người i Ta có công thức truy hồi: fi=min(fi-1+ti, fi-2+ri-1) Chương trình sau dùng hai biến f1, f2 để lưu kết quả bài toán con. Chương trình const fin='nktick.inp';fon='nktick.out'; maxn=60000; var n,i:longint; t,r,f:array[1..maxn] of longint; f1,f2,tam:longint; function min(a,b:longint):longint; var x:longint; begin x:=a; if b thì fi = 0 ngược lại fi=fi-1+fi-2 7 Ta áp dụng 2 biến fi1 và fi2 để lưu lời giải bài toán con như bài trên. Bài 4. LATGACH Lát gạch Cho một hình chữ nhật kích thước 2xN (1≤N≤100). Hãy đếm số cách lát các viên gạch nhỏ kích thước 1x2 và 2x1 vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát. Input  Gồm nhiều test, dòng đầu ghi số lượng test T (T≤100).  T dòng sau mỗi dòng ghi một số N. Example Input Output 3 1 Output: Ghi ra T dòng là số cách lát tương ứng. 1 2 Time: 1s 2 3 3 Hướng dẫn Đầu tiên ta xét hình chữ nhật 2x1 thì có 1 cách xếp đó là xếp 1 viên gạch 2x1. Xét hình chữ nhật 2x2 thì có 2 cách xếp đó là xếp 2 viên 1x2 hoặc 2 viên 2x1. Xét hình chữ nhật 2xi có các trường hợp sau với f(i) là số cách xếp cho hình chữ nhật 2xi. 2x(i-1) 2x1 f(i-1) cách xếp 2x(i-2) 1x2 f(i-2) cách xếp 1x2 => f(i) = f(i-1) + f(i-2) với f(1) = 1 và f(2) = 2 => f(N) là kết quả của bài toán Công thức truy hồi trên chính là công thức của dãy Fibonacy. 8 Bài 5. NKCABLE Nối mạng Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống mặt bàn rồi đánh số thứ tự các máy từ 1 đến N theo chiều từ trái sang phải. Các học sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn bởi các đoạn dây nối sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các học sinh này tìm cách nối mạng thoả mãn yêu cầu đặt ra sao cho tổng độ dài cáp nối phải sử dụng là ít nhất. Dữ liệu  Dòng đầu tiên chứa số lượng máy N (1 ≤ N ≤ 25000).  Dòng thứ i trong số N-1 dòng tiếp theo chứa các khoảng cách từ máy i đến máy i+1 (i=1,2,...,N-1). Giả thiết rằng khoảng cách từ máy 1 đến máy N không vượt quá 106. Input Output Kết quả: Ghi ra độ dài của cáp nối cần sử dụng. 6 7 Giải thích: 2 Máy 1 với máy 2, mất 2 đơn vị (tức là số 2 đầu tiên) 2 Máy 3 với 4, mất 3 đơn vị (tức là số 3 trong input) 3 Máy 5 với 6, mất 2 đơn vị (tức là số 2 cuối cùng) 2 Tổng là 7. 2 Hướng dẫn Fi là tổng độ dài cáp nối ít nhất để nối i máy đầu tiên. Ta có công thức truy hồi: Fi =min(fi-1,fi-2)+ai-1 9 2.2. Dạng 2: dùng mảng Trong công thức truy hồi để tìm lời giải của bài toán chính, cần sử dụng tất cả lời giải của bài toán con. Ví dụ Bài 1. LIQ Dãy con tăng dài nhất Cho dãy a1, a2, .., an có n phần tử. Dãy con của dãy a được tạo thành bằng các xóa một số phần tử trong dãy a và vẫn giữ nguyên các vị trí còn lại. Ví dụ cho dãy a: 2 4 6 1 7  Dãy 2 1 7 là một dãy con của a (xóa 4 6)  Dãy 2 4 1 là một dãy con của a (xóa 6 7)  Dãy 4 2 không phải là một dãy con của a. Yêu cầu: Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy. Dữ liệu vào: gồm 2 dòng:  Dòng đầu là số nguyên dương n (n ≤ 103)  Dòng sau gồm N số, mỗi số là một số nguyên ai của dãy (-104 ≤ai ≤ 104, 1≤ i ≤ n) Input Output 10 6 5 2 3 4 9 10 5 6 7 3 234567 Dữ liệu ra: gồm 2 dòng  Dòng đầu là số lượng phần tử của dãy con  Dòng sau là các số thuộc dãy con Giải Fi là dãy con của dãy a1, a2, …, ai thỏa đề bài (tăng, dài nhất) và kết thúc ở ai. Ví dụ: i 1 2 3 4 5 6 7 8 9 10 A 5 2 3 4 9 1 5 6 7 3 F 1 1 2 3 4 5 4 5 6 2 Dãy con Fi được xây dựng bằng cách nối thêm phần tử ai vào một trong các dãy con Fj trước đó (j =1 .. n – 1) và ai ≥ aj. Để dãy con này là dài nhất có thể thì Fi = max(Fj, j= 1..i-1, aj< ai) + 1 Nhìn vào công thức truy hồi ta thấy để tính được Fi, ta cần lời giải của tất cả các bài toán con f1, f2, …, fi – 1. Chương trình sau dùng mảng 1 chiều f[] để lưu lời giải của các bài toán con này. 10 Chương trình const fin = 'test.inp'; fon = 'test.out'; maxn=10000;vc=maxlongint; var a,f,t:array[0..maxn] of longint; n:longint; procedure nhap; var i:longint; begin read(n); for i:=1 to n do read(a[i]); end; procedure xuli; var i,jmax,j,d:longint; kq:array[1..maxn] of longint; begin a[0]:=-vc;a[n+1]:=vc; F[0]:=1; For i:=1 to n+1 do begin Jmax:=0; For j:=1 to i-1 do If (a[j]f[jmax]) then jmax:=j; F[i]:=F[jmax]+1; T[i]:=jmax; end; Writeln(f[n+1]-2); //truy vet i:=n+1;d:=0;//luu k?t qu? vao mang kq[] 11 repeat i:=t[i]; inc(d); kq[d]:=i; until t[i]=0; //do truy vet nguoc nen ta xuat nguoc mang kq[] for i:=d downto 1 do write(a[kq[i]],' '); end; BEGIN assign(input,fin);reset(input); assign(output,fon);rewrite(output); nhap; xuli; close(input);close(output); END. Bài 2. NHAHANG Nhà hàng (HSG12_DNAI_2011_V2) Tập đoàn kinh doanh nhà hàng Phát Đạt xem xét mở một loạt các nhà hàng dọc trên đường cao tốc Bắc Nam. Có n vị trí dọc trên đường được đề nghị mở nhà hàng. Vị trí thứ i cách đầu đường cao tốc là ai (km) và dựa vào các yếu tố mật độ dân, điều kiện cơ sở, … xác định được khả năng dự kiến mở là bi. Yêu cầu: Hãy xác định các vị trí mở nhà hàng sao cho tổng khả năng dự kiến mở là tối đa. Nhưng hai nhà hàng được chọn gần nhau nhất hoặc giữa nhà hàng đầu tiên được chọn và đầu đường cao tốc phải cách Input Output ít nhất là P (km) 6 30 3 23 Input 30 8 1  Dòng đầu là hai số n và P (2 ≤ n ≤ 50000) 70 5 3  N dòng tiếp theo, dòng thứ i trong n dòng là hai số ai và 90 6 5 bi (1 ≤ ai ≤107, 1≤ bi ≤105) Output  Dòng đầu ghi hai số k và T, số lượng các nhà hàng được mở và tổng khả năng dự kiến  K dòng tiếp theo, mỗi dòng là vị trí nhà hàng được mở 145 3 170 9 195 5 trên đường cao tốc. Giải 12 Sắp xếp lại các vị trí theo tọa độ tăng dần. Hàm mục tiêu: Fi = tổng khả năng dự kiến lớn nhất lớn nhất của dãy Fi = max (Fj, j=1..i - 1: |ai – aj|>P) + bi Chương trình const fin='NHAHANG.inp'; fon='NHAHANG.out'; vc=1000000000000; nmax = 50000+5; type Tpt = record a,b:int64; end; var c:array[-1..nmax] of Tpt; f,t,kq:array[-1..nmax] of int64; n,i,p:longint; procedure xuli; var i,j,jmax,z,d:longint; begin c[0].a:=0;c[0].b:=0;c[n+1].a:=vc; c[n+1].b:=1; f[-1]:=-vc; for i:=1 to n+1 do begin jmax:=-1; for j:=0 to i-1 do if (c[i].a-c[j].a>=p) then if (f[j]>f[jmax]) then jmax:=j; if jmax=-1 then f[i]:=0 else f[i]:=f[jmax]+c[i].b; t[i]:=jmax; 13 end; {truy vet} z:=t[n+1]; d:=0; repeat inc(d); kq[d]:=z; z:=t[z]; until z=0; writeln(d,' ',f[n+1]-1); //for i:=d downto 1 do writeln(kq[i],' '); end; begin assign(input,fin);reset(input); assign(output,fon);rewrite(output); read(n,P); for i:=1 to n do read(c[i].a,c[i].b); xuli; close(input);close(output); end. Bài tập vận dụng Bài 3. ACTIVITY Bố trí phòng họp Có n cuộc họp đánh số từ 1 đến n đăng ký làm việc tại một phòng hội thảo. Cuộc họp thứ t cần được bắt đầu ngay sau thời điểm si và kết thúc tại thời điểm fi: Hỏi có thể bố trí phòng hội thảo phục vụ được nhiều nhất bao nhiêu cuộc họp, sao cho khoảng thời gian làm việc của hai cuộc họp bất kỳ là không giao nhau. Dữ liệu:  Dòng đầu tiên chứa số nguyên dương n 106  Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên si, fi 0  si fi  105 Input Output 5 3 79 3 68 5 13 1 06 37 Các số trên một dòng của Input file được ghi cách nhau ít nhất một dấu cách Kết quả:  Dòng đầu tiên ghi số k là số các cuộc họp được chấp nhận phục vụ 14  k dòng tiếp theo liệt kê số hiệu các cuộc họp được chấp nhận theo thứ tự từ cuộc họp đầu tiên tới cuộc họp cuối cùng , mỗi dòng ghi số hiệu một cuộc họp. Giải thích Hướng dẫn Sắp xếp các cuộc họp tăng dần theo thời điểm kết thúc (bi). Thế thì cuộc họp i sẽ bố trí được sau cuộc họp j nếu và chỉ nếu j= w[i]) and (f[i,j] f[n-1,m] then begin write(n,' '); m:=m-w[n] end; dec(n); until n=0; end; begin assign(input,fin);reset(input); assign(output,fon);rewrite(output); nhap;xuli; close(input);close(output); end. Bài 2. QBSTR Xâu con chung dài nhất Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X. Cho biết hai xâu ký tự A và B ít hơn 255 kí tự, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B. Input  Dòng 1: chứa xâu A  Dòng 2: chứa xâu B Output:  Dòng một ghi độ dài xâu C tìm được.  Dòng hai ghi xâu C Example Input: Output: abc1def2ghi3 10 abcdefghi123 abcdefghi3 Giải 18
- Xem thêm -

Tài liệu liên quan