quy hoạch động

silverbullet2k3

Học sinh mới
Thành viên
4 Tháng hai 2018
4
5
6
21
Nam Định
Trần Dăng Ninh
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

BÀI TẬP TẾT
DÃY SỐ Tên chương trình: NUM25.??? Steve trực nhật vì vậy hôm nay bạn đến trường sớm, giặt khăn lau bảng và xóa bảng. Đang xóa bỗng Steve nhận thấy dãy số mà mình đã xóa một phần khá đặc biệt, phần đầu của nó là:
1 2 3 2 3 4 3 4 5 4 5 6 5 6 7
Đáng tiếc, phần còn lại của dãy đã bị xóa mất rồi! Cuối cùng Steve cũng xóa sạch bảng trước khi trống vào lớp vang lên, nhưng dãy số trên vẫn cứ lởn vởn mãi trong đầu. Buổi tối, khi lên giường ngủ, Steve lại nghĩ về dãy số này. Steve nhận thấy số 1 xuất hiện một lần trong dãy, số 2 xuất hiện 2 lần và lần đầu tiên - ở vị trí thứ 2, số 3 xuất hiện 3 lần và lần đầu tiên - ở vị trí thứ 3, nhưng số 4 thì lần đầu tiên xuất hiện không ở vị trí thứ tư! Tổng quát hơn, sốk sẽ xuất hiện lần đầu ở vị trí thứ mấy trong dãy? Ví dụ k = 5 thì vị trí xuất hiện sẽ là . . . vàSteve mơ màng thiếp đi trong giấc ngủ, chỉ còn kịp tự an ủi: “Có thể mình sẽ có một giấc mơ đẹpvà nhìn thấy được vị trí xuất hiện lần đầu tiên của k, nhưng …” Bạn có thể giúp Steve có được giấc mơ đẹp của mình hay không? Nếu được thì đừng tiếc sức, vì không phải lúc nào ta cũng có dịp giúp đỡ bạn mình đâu!Yêu cầu: Cho số nguyên k. Hãy xác định vị trí xuất hiện lần đầu của nó trong dãy số trên.Dữ liệu: Vào từ file văn bản NUM25.INP gồm một dòng chứa số nguyên k (1 ≤ k ≤ 109).Kết quả: Đưa ra file văn bản NUM25.OUT vị trí tìm được.XÂU CON CHUNG Tên chương trình: SUBST.??? Cho hai xâu s và t. Nói xâu t chứa s nếu tồn tại một xâu con các ký tự liên tiếp nhau của t bằng s. Ví dụ, với t = ‘ABRACADABRA’, nó sẽ chứa các xâu ‘ABRA’, ‘RAC’, ‘D’, ‘ACADABRA’,‘ABRACADABRA’, nhưng không chứa xâu ‘ABRC’. Xâu bất kỳ luôn luôn được coi là chứa xâu rỗng. Hai xâu X = ‘ABRACADABRA’ và Y = ‘ECADADABRBCRDARA’ cùng chứa các xâu ‘CA’,‘CADA’, ‘ADABR’ và xâu rỗng. Đó là các xâu con chung cùng được X và Y chứa. Trong số cácxâu con này, xâu ‘ADABR’ có độ dài lớn nhất (bằng 5).Yêu cầu: Cho hai xâu X và Y chỉ chứa các ký tự la tinh in hoa, mỗi xâu có độ dài trong phạm vi từ 1 đến 4000. Hãy xác định độ dài lớn nhất của xâu con chung cùng được X và Y chứa.Dữ liệu: Vào từ file văn bản SUBST.INP: Dòng thứ nhất chứa xâu X, Dòng thứ 2 chứa xâu Y.Kết quả: Đưa ra file văn bản SUBST.OUT một số nguyên – độ dài lớn nhất tìm được.ĐỌC SÁCH Tên chương trình: BOOK.??? Steve rất yêu thích môn số học. Vì vậy khi đọc sách thường đếm và tính tổng số lượng các chữ số của số trang và dựa vào kết quả tính ra được mình đã đọc đến trang nào. Lần này cuốn truyện in hơi đặc biệt: từ trang thứ tư trở đi mới có số trang. Trang này được đánh số là 4, trang tiếp theo – 5, . . . Số lượng chữ số Steve tính được là (1 ≤ ≤ 10 000). Bạn có biết là Steve đã đọc được đến trang nào không?: Cho số nguyên . Hãy xác định số của trang đã được đọc.: Vào từ file văn bản BOOK.INP gồm một dòng chứa số nguyên .: Đưa ra file văn bản BOOK.OUT một số nguyên – số trang.CANDY.???Bà của Steve là một nhà toán học đầy nhiệt huyết và bà thường làm đau đầu Steve bằng các câuđố hoặc trò chơi toán học. Lần này bà viết một dãy gồm số nguyên dương, mỗi số không vượt quá 106.Đưa nó cho Steve, bà nói: ”Cháu chọn 2 số bất kỳ trong dãy,(gọi 2 số đó là và ), chọn sốnguyên tố sao cho chia hết cho . Sau đó xóa và thay nó bằng , xóa đi và thay nóbằng . Cháu có thể làm như vậy bao nhiêu lần cũng được, chừng nào còn thấy thích. Khi nàodừng, cháu sẽ nhận được số kẹo bằng ước số chung lớn nhất của tất cả các số trong dãy”.Dĩ nhiên, Steve rất thích kẹo và muốn làm sao để nhận được nhiều kẹo nhất. Như vậy cần tính sốlần thực hiện biến đổi và sau đó – tính số kẹo sẽ được nhận.: Cho và dãy số nguyên dương. Hãy xác định số kẹo tối đa mà Steve có thể nhậnđược và số lần biến đổi cần thực hiện.: Vào từ file văn bản CANDY.INP: Dòng đầu tiên chứa số nguyên , Dòng thứ 2 chứa số nguyên dương.: Đưa ra file văn bản CANDY.OUT trên một dòng hai số nguyên: số kẹo tối đa và sốbước biến đổi. Dựa trên trò chơi dân gian nhảy lò cò, Bờm nghĩ ra một trò chơi mới như sau:Trò chơi được mô tả trên bảng gồm R dòng và C cột (2 ≤ ≤ 100, 2 ≤ ≤ 100), các dòngđược đánh số từ trên xuống dưới bắt đầu từ 1, các cột đánh số từ trái sang phải bắt đầu từ 1, giao của dòng i cột j là ô (i,j), trên mỗi ô (i,j) được gán nhãn là một số nguyên trong phạm vi từ1 … (1<=K<=R*C). Mỗi người chơi ban đầu đứng ở vị trí ô (1,1) và di chuyển xuống ô (R,C) của bảng bằng một dãy các bước nhảy thỏa mãn các điều kiện sau: 1. Chỉ nhảy đến ô có nhãn khác ô đang đứng. 2. Ô nhảy đến có chỉ số dòng lớn hơn ô đang đứng. 3. Ô nhảy đến có chỉ số cột lớn hơn ô đang đứng. Bờm rất thích thú với trò chơi này nhưng vẫn còn một thắc mắc: có bao nhiêu cách nhảy thỏamãn để di chuyển từ ô (1,1) đến ô (, ).: bạn hãy viết chương trình giúp Bờm trả lời câu hỏi đó?vào cho trong tệp - dòng 1 chứa 3 số , , - R dòng sau, mỗi dòng chứa số, mỗi số trong phạm vi từ 1 … .đưa ra tệp một số duy nhất là số cách di chuyển khác nhau thỏa mãn yêu cầu, kết quả có thể rất lớn chỉ cần đưa ra theo modul 109 + 7n n

mấy bạn giúp mình 2 bài cuối nha, đây hơi kém quy hoạch động
 

Tạ Đặng Vĩnh Phúc

Cựu Trưởng nhóm Toán
Thành viên
10 Tháng mười một 2013
1,559
2,715
386
26
Cần Thơ
Đại học Cần Thơ
Xin lỗi nhưng nữa post đề CP bạn mô tả lại công việc cần làm được rồi không cần hết cái đề đâu nhé: Quy hoạch động thì tích góp kinh nghiệm từ từ thôi chớ chia nhỏ bài toán và xài CTDL nào không phải ngày 1 ngày 2 mà có thể nhận xét được
 
Top Bottom