SKKN Ứng dụng phương pháp quy hoạch động trong bồi dưỡng học sinh giỏi môn tin học THPT

1. MỞ ĐẦU
 - LÝ DO CHỌN ĐỀ TÀI
Đất nước của chúng ta đang trong xu thế phát triển và hội nhập trên phạm vi toàn cầu hoá đặt ra những yêu cầu mới đối với người lao động, do đó cũng đặt ra những yêu cầu mới cho ngành Giáo dục phải đổi mới một cách mạnh mẽ cả mục tiêu, nội dung, phương pháp, phương tiện dạy học, phương pháp kiểm tra đánh giá học sinh để tạo ra những người lao động đáp ứng được những đòi hỏi của sự nghiệp công nghiệp hoá, hiện đại hóa đất nước. 
Tin học là hành trang thiết yếu trên con đường nghề nghiệp. Phần lớn các ngành nghề trong xã hội hiện đại đòi hỏi hiểu biết tin học. Thêm nữa, rất nhiều ngành nghề mới xuất hiện trong lĩnh vực tin học như: lập trình viên, quản trị mạng, thiết kế cơ sở kỹ thuật, an ninh mạng, Đối với chính ngành giáo dục, tin học là cơ sở hạ tầng của giáo dục. Tin học là môi trường dạy học, công cụ quản lý giáo dục, công cụ sư phạm, thiết bị học tập cá nhân, làm việc của nhóm giáo viên, học sinh.
Đảng và Nhà nước đã vạch ra đường lối rất đúng đắn về “chiến lược con người” là“nâng cao dân trí, đào tạo nhân lực, bồi dưỡng nhân tài”. Ngành giáo dục và đào tạo cũng đang hướng tới phát triển tối đa những năng lực còn tiềm ẩn trong mỗi học sinh. Trong các trường học hiện nay, việc phát triển bồi dưỡng học sinh giỏi góp phần đào tạo nhân tài cho đất nước được xem là nhiệm vụ cần thiết và quan trọng. Nhiều năm qua tôi được sự tín nhiệm của trường đã tham gia bồi dưỡng học sinh giỏi môn tin học. Qua quá trình bồi dưỡng, tôi luôn cố gắng tìm hiểu nội dung cơ bản và nâng cao, tìm ra phương pháp tối ưu để cho công tác bồi dưỡng có hiệu quả nhất. Công tác bồi dưỡng học sinh giỏi là nhiệm vụ nặng nề nhưng cũng rất vinh dự cho giáo viên khi tham gia bồi dưỡng. Những câu hỏi mà bất cứ ai khi tham gia bồi dưỡng học sinh giỏi cũng luôn đặt ra là: Làm thế nào để các em lĩnh hội tốt các kiến thức khi tham gia ôn luyện? Làm thế nào để kết quả đạt được tốt nhất? Làm thế nào để mang lại thành tích cho các em và mang lại vinh dự cho nhà trường. Bồi dưỡng học sinh giỏi là nhiệm vụ khó không chỉ từ việc lựa chọn học sinh, lựa chọn phương pháp mà còn đòi hỏi nhiều kiến thức, kỹ năng vận dụng cao. 
Qua việc tham khảo những đề thi học sinh giỏi cấp tỉnh THPT thì xu hướng rất nhiều đề có một số bài toán sử dụng phương pháp quy hoạch động lại cho hiệu quả cao hơn hơn hẳn so với nhiều phương pháp khác, lượng bài toán tin học được giải bằng phương pháp quy hoạch động cũng rất lớn. Số lượng các bài thi có thể áp dụng phương pháp quy hoạch động để giải trong đề thi học sinh giỏi môn Tin học thường rất cao. Vậy “Có phải tất cả bài toán tối ưu đều áp dụng phương pháp quy hoạch động để giải?; Làm thế nào để nhận dạng được bài toán đó có thể áp dụng phương pháp quy hoạch động để giải?; Làm thế nào có thể giải một bài toán bằng phương pháp quy hoạch động?”;Vì những lý do trên tôi xin chọn đề tài “ỨNG DỤNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG TRONG BỒI DƯỠNG HỌC SINH GIỎI MÔN TIN HỌC THPT” Mong cùng góp một phần nhỏ vào công tác bồi dưỡng học sinh giỏi chung của trường, của tỉnh, để đội ngũ học sinh giỏi của trường, của tỉnh ngày càng đạt kết quả cao hơn. 
 - MỤC ĐÍCH NGHIÊN CỨU.
Đưa ra một số phương pháp để giải quyết các bài toán cơ bản về phương pháp quy hoạch động, nâng cao khả năng tư duy sáng tạo cho học sinh, nâng cao chất lượng học sinh giỏi. Nêu vấn đề, phân dạng bài toán tin học có liên quan, thực hiện ví dụ minh họa để học sinh quan sát qua đó nắm vững kiến thức về phương pháp quy hoạch động. 
Đặc biệt hình thành ở học sinh kỹ năng phân tích, xử lý các vấn đề thường gặp trong khi làm việc với kiểu dữ liệu. Tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho học sinh, giáo viên dạy tin học bồi dưỡng học sinh giỏi THPT
- ĐỐI TƯỢNG NGHIÊN CỨU.
 + Nghiên cứu lí luận về bài tập giải bài toán bằng phương pháp quy hoạch động trong dạy học bồi dưỡng học sinh giỏi.
 + Dạy học Tin học ở trường PT Nguyễn Mộng Tuân.
 + Học sinh khá giỏi lớp 11 chương trình cơ bản.
 + Giáo viên giảng dạy môn tin học trong trường.
 + Máy tính,máy chiếu để mô tả các thuật toán.
 + Xây dựng qui trình giảng dạy với bài tập sử dụng phương pháp quy hoạch động trong việc tích cực hóa hoạt động nhận thức cho học sinh.
 + Dạy bài tập giải các bài toán tối ưu bằng quy hoạch động ở trường PT Nguyễn Mộng Tuân, Huyện Đông Sơn, Tỉnh Thanh Hóa.
- PHƯƠNG PHÁP NGHIÊN CỨU.
 + Phương pháp nghiên cứu xây dựng cơ sở lý thuyết.
 + Kỷ thuật phân tích thuật toán.
+ Phát triển tư duy học sinh.
+ Tìm hiểu và phát triển kỹ năng.
	 + Tham khảo các tài liệu lấy từ nhiều nguồn nhất là các học liệu mở trên mạng internet và phân tích có hệ thống các dạng bài tập theo nội dung đã đề ra.
2. NỘI DUNG SÁNG KIẾN KINH NGHIỆM.	
2.1. CƠ SỞ LÍ LUẬN VÀ CƠ SỞ THỰC TIỄN CỦA VIỆC ỨNG DỤNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG TRONG BỒI DƯƠNG HỌC SINH GIỎI MÔN TIN HỌC THPT.
	- Nghị quyết Hội nghị trung ương 8 khóa XI về đổi mới căn bản, toàn diện giáo dục và đào tạo xác định “Tiếp tục đổi mới mạnh mẽ và đồng bộ các yếu tố cơ bản của giáo dục đào tạo theo hướng coi trọng phát triển phẩm chất, năng lực của người học”; “tập trung phát triển trí tuệ, thể chất, hình thành phẩm chất, năng lực công dân, phát hiện và bồi dưỡng năng khiếu, định hướng nghề nghiệp cho học sinh. Nâng cao chất lượng giáo dục toàn diện, chú trọng giáo dục lý tưởng, truyền thống, đạo đức, lối sống, ngoại ngữ, tin học, năng lực và kỹ năng thực hành, vận dụng kiến thức vào thực tiễn. Phát triển khả năng sáng tạo, tự học, khuyến khích học tập suốt đời”. 
	- Nghị quyết số 44/NQ-CP, ngày 09/6/2014 Ban hành chương trình hành động của chính phủ thực hiện nghị quyết số 29-NQ/TW ngày 04/11/2013 Hội nghị lần thứ 8 Ban chấp hành Trung ương khóa XI về đổi mới căn bản, toàn diện giáo dục và đào tạo, đáp ứng yêu cầu công nghiệp hóa trong điều kiện kinh tế thị trường định hướng xã hội chủ nghĩa và hội nhập quốc tế xác định “Đổi mới hình thức, phương pháp thi, kiểm tra và đánh giá kết quả giáo dục theo hướng đánh giá năng lực của người học; kết hợp đánh giá cả quá trình với đánh giá cuối kỳ học, cuối năm học theo mô hình của các nước có nền giáo dục phát triển”.
	- Luật Giáo dục số 38/2005/QH11, Điều 28 quy định: “Phương pháp giáo dục phổ thông phải phát huy tính tích cực, tự giác, chủ động, sáng tạo của học sinh; phù hợp với đặc điểm của từng lớp học, môn học; bồi dưỡng phương pháp tự học, khả năng làm việc theo nhóm; rèn luyện kỹ năng kiến thức vào thực tiễn; tác động đến tình cảm, đem lại niềm vui, hứng thú học tập cho học sinh”
- Căn cứ vào những quan điểm, định hướng trên để xác định ra nhiệm vụ cụ thể của môn Tin học, tổ chức hoạt động đào tạo góp phần thực hiện mục tiêu giáo dục mà Đảng và nhà nước đề ra. Ngoài việc tạo điều kiện cho học sinh chiếm lĩnh những tri thức và kỹ năng Tin học cần thiết, Tin học còn có tác dụng phát triển năng lực trí tuệ chung như: phân tích, tổng hợp, trừu tượng hoá, khái quát hoárèn luyện những đức tính, phẩm chất của người lao động mới. Học sinh sẽ thấy rõ hiệu quả mạnh mẽ của công nghệ thông tin và nhận thức cần có.
- Căn cứ vào việc lựa chọn đội tuyển dự thi học sinh giỏi của nhà trường, để đội ngũ học sinh giỏi của trường PT Nguyễn Mộng Tuân ngày càng đạt kết quả cao hơn. Giúp cho học sinh chuyên tin khối THPT thi đạt kết quả ngày càng cao, tạo ra nguồn tài liệu tham khảo về thuật toán hỗ trợ cho giáo học sinh và giáo viên dạy đội tuyển học sinh giỏi trong nhà trường.
2.2.THỰC TRẠNG VẤN ĐỀ VỀ VIỆC KHAI THÁC, SỬ DỤNG QUY HOẠCH ĐỘNG TRONG BỒI DƯỠNG HỌC SINH GIỎI THPT HIỆN NAY.
2.2.1. Về tài liệu dạy học tập.
Nhìn chung trong quá trình dạy học Tin học trong trường phổ thông giáo viên chủ yếu dạy nội dung trong sách giáo khoa và sách bài tập tin học 11, một số giáo viên kết hợp giữa sách giáo khoa trong chương trình nâng cao và sách giáo khoa chương trình cơ bản. Tuy nhiên theo ý kiến của giáo viên thì nội dung dạy lý thuyết trong sách giáo khoa là tương đối đủ, nhưng số lượng bài tập ở chương này trong sách giáo khoa và sách bài tập tin học còn ít so với yêu cầu mục tiêu dạy học của chương bồi dưỡng học sinh giỏi trong nhà trường. Giáo viên cần tham khảo một số tài liệu về bài toán tối ưu.
2.2.2. Về số lượng bài tập:
	- Số lượng bài tập về sử dụng phương pháp quy hoạch động còn ít.
	- Sử dụng một số bài toán tối ưu nhiều.
2.2.3. Về nhận thức và phương pháp giảng dạy của giáo viên:
- Tư tưởng của GV chưa coi trọng phương pháp quy hoạch động, nếu GV sử dụng phương pháp quy hoạch động chỉ là qua loa không dành nhiều thời gian cho HS suy nghĩ, xây dựng lập luận.
- Trang thiết bị trong các nhà trường phổ thông tuy có trang bị nhưng về chất lượng chưa đảm bảo đáp ứng cho việc dạy học của GV.
- Về năng lực và kỹ năng thực hành của GV còn nhiều hạn chế ; một số thuật toán có độ chính xác chưa cao nên để làm được lập trình đôi khi GV phải tự suy nghĩ tìm kiếm và phát hiện lỗi mới thực hiện được. 
 2.2.4. Về phía học sinh :
- Việc học sinh học vật lý ở trên lớp thì học sinh rất thụ động. Chỉ có một số em học khá và say mê học tin học thì tìm tòi mày mò đọc thêm tài liệu để bổ sung kiến thức. Trong khi đó, còn đại đa số thì chỉ trông chờ vào bài giảng của giáo viên
Một số HS lười học lí thuyết, đôi khi chỉ cần dùng câu lệnh, khái niệmđể áp dụng mà chưa kịp hiểu bản chất.
- HS ít có khả năng suy luận logic, chưa có ý thức tự học.
- Khả năng nhận biết các thuật toán còn yếu.
- Học sinh học tốt các môn tự nhiên rất hứng thú đối với môn học này, nhất là những tiết thực hành.
- Môn học rất trực quan và sinh động cho nên học rất chịu khó tìm hiểu và học hỏi thêm. Một số học sinh có khả năng phát triển về lập trình và yêu thích lập trình.
2.3. KHAI THÁC, XÂY DỰNG VÀ SỬ DỤNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG TRONG BỒI DƯỠNG HỌC SINH GIỎI TIN HỌC THPT HIỆN NAY.
2.3.1. Nội dung cơ bản của “phương pháp quy hoạch động”.
	- Hiểu và vận dụng phương pháp quy hoạch động vào giải các bài toán trong chương trình chuyên tin học THPT đặc biệt là các bài toán tối ưu. Giúp học sinh hiểu và vận dụng được phương pháp quy hoạch động vào giải các bài toán tối ưu để học sinh đạt kết quả cao hơn trong kỳ thi học sinh giỏi các cấp.
Bài toán tối ưu gồm có 1 hàm f gọi là hàm mục tiêu hay hàm đánh giá; các hàm g1, g2, , gn cho giá trị logic gọi là hàm ràng buộc. Yêu cầu của bài toán là tìm một cấu hình x thoả mãn tất cả các ràng buộc g1, g2, , gn:gi(x) = TRUE ( i:1 i n) và x là tốt nhất, theo nghĩa không tồn tại một cấu hình y nào khác thoả mãn các hàm ràng buộc mà f(y) tốt hơn f(x). Bài toán tối ưu là bài toán thường có nhiều nghiệm chấp nhận được và mỗi nghiệm có một giá trị đánh giá. Mục tiêu đặt ra là tìm nghiệm tối ưu, đó là nghiệm có giá trị đánh giá lớn nhất hoặc nhỏ nhất (tối ưu). Bài toán tối ưu là bài toán thường có nhiều nghiệm chấp nhận
được và mỗi nghiệm có một giá trị đánh giá. Mục tiêu đặt ra là tìm nghiệm tối ưu, đó là nghiệm có giá trị đánh giá lớn nhất hoặc nhỏ nhất (tối ưu).
- Phương pháp quy hoạch động dùng để giải bài toán tối ưu có bản chất đệ quy, tức là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của một số hữu hạn các bài toán con. 
- Ðối với một số bài toán đệ quy, nguyên lý chia để trị (divide and conquer) thường đóng vai trò chủ đạo trong việc thiết kế thuật toán. Ðể giải quyết một bài toán lớn, ta chia nó thành nhiều bài toán con cùng dạng với nó để có thể giải quyết độc lập. 
- Trong phương án quy hoạch động, nguyên lý chia để trị càng được thể hiện rõ: Khi không biết phải giải quyết những bài toán con nào, ta sẽ đi giải quyết toàn bộ các bài toán con và lưu trữ những lời giải hay đáp số của chúng với mục đích sử dụng lại theo một sự phối hợp nào đó để giải quyết những bài toán tổng quát hơn.
- Ðó chính là điểm khác nhau giữa Quy hoạch động và phép phân giải đệ quy và cũng là nội dung phương pháp quy hoạch động:
+ Phép phân giải đệ quy bắt đầu từ bài toán lớn phân ra thành nhiều bài toán con và đi giải từng bài toán con đó. Việc giải từng bài toán con lại đưa về phép phân ra tiếp thành nhiều bài toán nhỏ hơn và lại đi giải các bài toán nhỏ hơn đó bất kể nó đã được giải hay chưa.
+ Quy hoạch động bắt đầu từ việc giải tất cả các bài toán nhỏ nhất (bài toán cơ sở) để từ đó từng bước giải quyết nhưng bài toán lớn hơn, cho tới khi giải được bài toán lớn nhất (bài toán ban đầu).
- Bài toán giải theo phương pháp quy hoạch động gọi là bài toán quy hoạch động. 
- Công thức phối hợp nghiệm của các bài toán con để có nghiệm của bài toán lớn gọi là công thức truy hồi của quy hoạch động.
- Tập các bài toán có ngay lời giải để từ đó giải quyết các bài toán lớn hơn gọi là cơ sở quy hoạch động.
- Không gian lưu trữ lời giải các bài toán con để tìm cách phối hợp chúng gọi là bảng phương án của quy hoạch động. 
- Trước khi áp dụng phương pháp quy hoạch động ta phải xét xem phương pháp đó có thỏa mãn những yêu cầu dưới đây không:
- Bài toán lớn phải phân rã được thành nhiều bài toán con, mà sự phối hợp lời giải của các bài toán con đó cho ta lời giải của bài toán lớn. 
+ Vì quy hoạch động là đi giải tất cả các bài toán con, nên nếu không đủ không gian vật lý lưu trữ lời giải (bộ nhớ, đĩa, ) để phối hợp chúng thì phương pháp quy hoạch động cũng không thể thực hiện được.
+ Quá trình từ bài toán cơ sở tìm ra lời giải bài toán ban đầu phải qua hữu hạn bước. Các bước cài đặt một chương trình sử dụng quy hoạch động:
+ Giải tất cả các bài toán cơ sở (thông thường rất dễ), lưu các lời giải vào bảng phương án.
+ Dùng công thức truy hồi phối hợp những lời giải của các bài toán nhỏ đã lưu trong bảng phương án để tìm lời giải của các bài toán lớn hơn rồi lưu chúng vào bảng phương án. Cho tới khi bài toán ban đầu tìm được lời giải.
+ Dựa vào bảng phương án, truy vết tìm ra nghiệm tối ưu.
+ Cho tới nay, vẫn chưa có một định lý nào cho biết một cách chính xác những bài toán nào có thể giải quyết hiệu quả bằng quy hoạch động. Tuy nhiên để biết được bài toán có thể giải bằng quy hoạch động hay không, ta có thể đặt câu hỏi:
+ Một nghiệm tối ưu của bài toán lớn có phải là sự phối hợp các nghiệm tối ưu của các bài toán con hay không?
+ Liệu có thể nào lưu trữ được nghiệm các bài toán con dưới một hình thức nào đó để phối hợp tìm được ngiệm bài toán lớn?.
+ Nhìn chung thường các bài toán tối ưu được giải bằng phương pháp truy hồi thường được giải bằng phương pháp quy hoạch động độ phức tạp thuật toán nhỏ hơn.
2.3.2. Các bước cơ bản để giải một bài toán tối ưu bằng quy hoạch động:
Bước 1: Lập công thức truy hồi
Bước 2: Tổ chức dữ liệu và chương trình
Bước 3: Truy vết, tìm nghiệm của bài toán dựa vào bảng phương án
2.3.3. Ví dụ về các bài toán có thể giải bằng phương pháp quy hoạch động:
Bài toán 1: Dãy con đơn điệu tăng
Cho một dãy số nguyên gồm N phần tử a1, a2, a3, ,aN. 
Biết rằng dãy con tăng đơn điệu là 1 dãy a[i1], a[i2], , a[ik] thỏa mãn:
	+ i1< i2 < ik 
	+ a[i1]<a[i2]<a[i3]< <a[ik] 
	 Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?
Dữ liệu: Vào từ file văn bản BAI1.INP
- Dòng 1: Chứa số n (0<N≤ 1000)
- Dòng 2: Chứa n số a1, a2, ,aN đôi một khác nhau và cách nhau ít nhất một dấu cách ( |ai|≤10000)
Kết quả: Ghi ra file văn bản BAI1.OUT
	- Chỉ gồm một dòng ghi độ dài dãy con tăng đơn điệu dài nhất
Ví dụ:
BAI1.INP
BAI1.OUT
6
1 2 5 4 7 3
4
Giải thuật:
	Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a1 đến ai và phần tử cuối cùng là ai. Dãy con đơn điệu tăng dài nhất kết thúc tai ai sẽ được thành lập bằng cách:
	- Kiểm tra xem có bao nhiêu dãy con đơn điệu tăng (các phần tử trong miền từ a1 đến ai-1) mà ta có thể ghép ai vào cuối dãy đó.
	- Chọn dãy con đơn điệu có độ dài lớn nhất để ghép ai vào.
	Ta có công thức quy hoạch động để tính L(i) như sau: 
 	• L(1) = 1. 
	• L(i) = max(1, L(j)+1 với mọi phần tử j: 0 < j < i và aj < ai) 
	Tính L(i) : phần tử đang được xét là ai .Ta tìm đến phần tử aj < ai có L(j) lớn nhất. Khi đó nếu bổ sung ai vào sau dãy con a1...aj ta sẽ được dãy con tăng dần dài nhất xét từ a1...ai.
Chương trình: // độ phức tạp O(n+k)
	Const fi=’bai1.inp’;
 fo=’bai1.out’;
 var a,f:array[1..1000] of integer;
 h, i,j,n,max:integer; tg,cs:string;
 BEGIN
 assign(input,fi);reset(input);
 assign(output,fo');rewrite(output);
 readln(fi,n);
 for i:=1 to n do read(fi,a[i]);
 	 f[1]:=1;
 	 for i:=2 to n do
 	begin
 	 f[i]:=1;
 	for j:=1 to i-1 do
 	if (a[i]>a[j]) and (f[i]<f[j]+1) then f[i]:=f[j]+1;
 	if max<f[i] then max:=f[i];
 	 	end;
 writeln(output,max);
 	close(input);close(output);
 END.
Dạng bài tập áp dụng:
+ Dãy con đơn điệu giảm
+ Bố trí phòng họp
+ Cho thuê máy
+ Dãy tam giác bao nhau
+ Dãy đổi dấu
+ Dãy số WAVIO
+ Xếp các khối đá
Bài toán 2: Tính tổng của dãy số 
Cho một dãy gồm n số nguyên dương A1, A2, ..., An và hai số nguyên x và y (1≤ x≤ y≤ n).
Yêu cầu: Hãy tính tổng các phần tử liên tiếp từ ax  ay
Dữ liệu vào từ file BAI2.INP:
- Dòng 1: ghi 3 số n, x, và y cách nhau bởi ít nhất 1 dấu cách.(1 ≤ n ≤104)
- Dòng 2: ghi n số nguyên A1, A2, ..., An được ghi theo đúng thứ tự cách nhau ít nhất một dấu cách.(|ai| ≤32000).
Dữ liệu ra ghi vào file BAI2.OUT:
- Một dòng ghi một số nguyên là tổng giá trị của các phần tử trong đoạn ax  ay
Ví dụ:
BAI2.INP
BAI2.OUT
10 3 6
-9 5 1 4 6 2 16 5 87 5
13
Giải thuật:
Dùng phương pháp quy hoạch động:
Gọi S[i] là tổng giá trị các phần tử a1, a2, a3, ,ai (1 ≤ i ≤ n)
Ta có công thức quy hoạch động tính S[i] như sau:
S[i]:= S[i-1] +a[i];
Như vậy, việc tính S[n] được thực hiện bằng vòng lặp:
S[0] :=0;
For i:= 1 to n do S[i]:=S[i-1] + a[i];
Kết quả: Tổng các phần tử liên tiếp từ ax đến ay được tính theo công thức:
Sum := S[y] – S[x-1];
Chương trình: // độ phức tạp O(n+k)
 Const fi = ‘bai2.inp’;
 fo = ‘bai2.out’;
 var n,k,i,x,y:longint;
 a:array[1..10000] of integer;
 s:array[0..100000] of int64;
 BEGIN
 Assign(input,fi);reset(input);
 Assign(output,fo);rewrite(output);
 readln(fi,n,x,y);
 s[0]:=0;
 for i:=1 to n do
 begin 
 read(fi,a[i]);
 s[i]:=s[i-1]+a[i];
 end;
 write(fo,s[y]-s[x-1]);
 close(input);close(output);
 END.
Dạng bài tập áp dụng:
+ Dãy con gồm phần tử liên tiếp có tổng lớn nhất chia hết cho K
+ Chia kẹo
+ Điền dấu
+ Market
+ Exptession
Bài toán 3: Tam giác Pascal	
17
1
1
2
1
1
3
1
3
1
6
10
4
10
5
1
1
4
1
5
1
	Tam giác Pascal là một mô hình dùng để đưa ra các hệ số của khai triển nhị thức Newton bậc N (x+1)N.
Ví dụ: trong khai triển (x+1)2 = x2 + 2x +1 có các hệ số là 1 2 1
Trong khai triển (x+1)3 = x3 + 3x2 + 3x + 1 có các hệ số là 1 3 3 1
 Yêu cầu: Hãy tìm các hệ số trong khai triển nhị thức Newton (x + 1)N.
Dữ liệu vào: Cho trong file văn bản BAI31.INP có cấu trúc như sau:
Dòng 1: Ghi số nguyên dương N (1 ≤ N ≤ 100).
Dữ liệu ra: Ghi ra file văn bản BAI31.OUT theo cấu trúc:
Dòng 1: Ghi ra các số nguyên dương lần lượt là các hệ số trong khai triển nhị thức Newton (x + 1)N, các số được ghi cách nhau một dấu cách.
Ví dụ: 
BAI31.INP
BAI31.OUT
5
1 5 10 10 5 1
Giải thuật:
	+ Ta xây dựng mảng hai chiều có kích thước [0..100, 0..101]
	+Ta nhận thấy f[0, 1] = 1 và f[i, 1] = f[i, i+1] = 1 . với mọi i = 1..n
	+ Sử dụng phương pháp quy hoạch động với công thức như sau:
	 	F[i, j] = f[i-1, j-1] + f[i-1,j]
	+kết quả nhận được lưu trữ ở dòng N, cụ thể:
F[N,1], f[N,2], f[N,3], , f[N,N], f[N,N+1]
Chương trình // độ phức tạp O(n2)
 Const fi = ‘bai31.inp’;
 fo = ‘bai31.out’;
Var	i, j, n: longint;
	F: array[0..100, 0..101] of longint;
BEGIN
	Assign(input, fi); reset(input);
	Assign(output,fo); rewrite(output);
	 readln(n);
for i:= 0 to n do f[i,1]:= 1;
 for i:= 1 to n do f[i,i+1]:= 1;
 for i:= 2 to n do 
	 for j:=2 to i do 
 f[i,j]:= f[i-1, j-1] + f[i-1,j];
 for j:= 1 to n+1 do write(f[n,j],’’);
close(input);close(output);
END.
7
8
2
9
3
2
9
5
6
4
5
9
8
4
3
7
1
6
6
8
1
 Tam giác số	
	Cho tam giác số như hình vẽ. Ta định nghĩa một đường đi trong tam giác số là đường đi xuất phát từ hình thoi ở đỉnh tam giác và đi đến được các hình thoi có chung cạnh với nó, đường đi kết thúc khi gặp một hình thoi ở đáy tam giác.
Yêu cầu: Hãy tìm một đườ