QHDONG-Hay.DOC
- 0 / 0
-
Nguồn:
Người gửi: Trần Chí Thu (trang riêng)
Ngày gửi: 22h:30' 24-04-2009
Dung lượng: 83.0 KB
Số lượt tải: 279
Người gửi: Trần Chí Thu (trang riêng)
Ngày gửi: 22h:30' 24-04-2009
Dung lượng: 83.0 KB
Số lượt tải: 279
Số lượt thích:
0 người
Qui hoạch động
A - Phần đề bài
Bài 1 :
Cho N số nguyên dương (0Tìm trong dãy đã cho một dãy con Ai1, Ai2, .... , Aik thoả mãn các điều kiện :
a) Ai j ( Ai j+1
b) ij ( i j+1
c) k lớn nhất
Dữ liệu vào : File BL1.INP có cấu trúc như sau :
Dòng thứ nhất ghi số N
Các dòng tiếp theo của nó chứa dãy A1, A2 , ... , An mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
Dữ liệu ra : File BL1.OUT có cấu trúc như sau :
Dòng thứ nhất ghi số k
Các dòng tiếp theo chứa k số Ai1, Ai2, .... , Aik mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
File Input
12
6 12 8 11 3 4 1 7 5 9 10 2
File Output
3 4 7 9 10
Bài 2 :
Cho 2 số nguyên dương M,N (0Dữ liệu vào : File BL1.INP có cấu trúc như sau :
Dòng thứ nhất ghi số N ,M
Các dòng tiếp theo của nó chứa dãy A1, A2 , ... , AN và B1, B2 , ... , B M mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
Dữ liệu ra : File BL1.OUT có cấu trúc như sau :
Dòng thứ nhất ghi số k
Các dòng tiếp theo chứa k số còn lại của 1 dãy nào đó , mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
File Input
8 12
0 0 9 2 3 7 3 1
4 4 0 5 0 9 0 3 10 4 8 3
File Output
5
0 0 9 3 3
Bài 3 : ( Di chuyển từ Tây sang Đông )
Cho hình chữ nhật MxN ô vuông ,mỗi ô chứa một số nguyên
Bài : ( Bài Mã vạch )
Cho bộ 3 số (N,M,K) nguyên không âm (N<=100,M,K<=33) . Người ta định nghĩa mỗi bộ 3 số trên ứng với 1 mã là một xâu kí tự dạng nhị phân thoả mãn :
+ Chứa đúng N chữ số
+ Các chữ số 0 liền nhau hoặc các chữ số 1 liền nhau gọi là 1 vạch , phải có đúng M vạch
+ Số chữ số trong 1 vạch gọi là độ rộng của vạch . Độ rộng tối đa của vạch là K
+ Vạch đầu tiên của mã phải là vạch gồm các chữ số 1.
Lập trình thực hiện các yêu cầu sau :
1) Lấy dữ liệu từ File ‘MV.INP’ tổ chức như sau :
- Dòng đầu là 3 số N,M,K
- Dòng thứ 2 là số p
- P dòng tiếp theo : mỗi dòng là một mã M i (0< i2) Thông tin ra gửi vào File ‘MV.OUT’ :
- Dòng đầu là số nêu tổng số mã của bộ mã (N,M,K)
- Tiếp theo gồm p dòng , mỗi dòng ghi 1 số là vị trí của mã M i trong tự điển xếp tăng các mã của bộ mã (N,M,K) .
Thí dụ
File ‘MV.INP’
7 4 3
6
1110100
1101100
1001000
1000100
1101110
1110110
File ‘MV.OUT’
16 15
12
3
1
13
16
Bài 1 : Tìm dãy con tăng dài nhất :
Cho mảng A(N) . Cần xoá ít nhất một số phần tử của dãy này sao cho các phần tử còn lại tạo thành dãy tăng nghiêm ngặt . Ta xây dựng mảng T(N) và mảng D(N) với ý nghĩa :
+ T[i] là chỉ số j ( trong mảng A ) của phần tử đứng trước phần tử có chỉ số i (trong mảng A ) khi xét dãy kết quả .
+ D[i] là độ dài của dãy kết quả khi bài toán trên mảng A(N) mới được xét từ phần tử 1 đến phần tử i ( Nghiã là ta tạm giải bài toán với kích
A - Phần đề bài
Bài 1 :
Cho N số nguyên dương (0
a) Ai j ( Ai j+1
b) ij ( i j+1
c) k lớn nhất
Dữ liệu vào : File BL1.INP có cấu trúc như sau :
Dòng thứ nhất ghi số N
Các dòng tiếp theo của nó chứa dãy A1, A2 , ... , An mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
Dữ liệu ra : File BL1.OUT có cấu trúc như sau :
Dòng thứ nhất ghi số k
Các dòng tiếp theo chứa k số Ai1, Ai2, .... , Aik mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
File Input
12
6 12 8 11 3 4 1 7 5 9 10 2
File Output
3 4 7 9 10
Bài 2 :
Cho 2 số nguyên dương M,N (0
Dòng thứ nhất ghi số N ,M
Các dòng tiếp theo của nó chứa dãy A1, A2 , ... , AN và B1, B2 , ... , B M mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
Dữ liệu ra : File BL1.OUT có cấu trúc như sau :
Dòng thứ nhất ghi số k
Các dòng tiếp theo chứa k số còn lại của 1 dãy nào đó , mỗi dòng không quá 10 số , các số cách nhau ít nhất một dấu cách .
File Input
8 12
0 0 9 2 3 7 3 1
4 4 0 5 0 9 0 3 10 4 8 3
File Output
5
0 0 9 3 3
Bài 3 : ( Di chuyển từ Tây sang Đông )
Cho hình chữ nhật MxN ô vuông ,mỗi ô chứa một số nguyên
Bài : ( Bài Mã vạch )
Cho bộ 3 số (N,M,K) nguyên không âm (N<=100,M,K<=33) . Người ta định nghĩa mỗi bộ 3 số trên ứng với 1 mã là một xâu kí tự dạng nhị phân thoả mãn :
+ Chứa đúng N chữ số
+ Các chữ số 0 liền nhau hoặc các chữ số 1 liền nhau gọi là 1 vạch , phải có đúng M vạch
+ Số chữ số trong 1 vạch gọi là độ rộng của vạch . Độ rộng tối đa của vạch là K
+ Vạch đầu tiên của mã phải là vạch gồm các chữ số 1.
Lập trình thực hiện các yêu cầu sau :
1) Lấy dữ liệu từ File ‘MV.INP’ tổ chức như sau :
- Dòng đầu là 3 số N,M,K
- Dòng thứ 2 là số p
- P dòng tiếp theo : mỗi dòng là một mã M i (0< i
- Dòng đầu là số nêu tổng số mã của bộ mã (N,M,K)
- Tiếp theo gồm p dòng , mỗi dòng ghi 1 số là vị trí của mã M i trong tự điển xếp tăng các mã của bộ mã (N,M,K) .
Thí dụ
File ‘MV.INP’
7 4 3
6
1110100
1101100
1001000
1000100
1101110
1110110
File ‘MV.OUT’
16 15
12
3
1
13
16
Bài 1 : Tìm dãy con tăng dài nhất :
Cho mảng A(N) . Cần xoá ít nhất một số phần tử của dãy này sao cho các phần tử còn lại tạo thành dãy tăng nghiêm ngặt . Ta xây dựng mảng T(N) và mảng D(N) với ý nghĩa :
+ T[i] là chỉ số j ( trong mảng A ) của phần tử đứng trước phần tử có chỉ số i (trong mảng A ) khi xét dãy kết quả .
+ D[i] là độ dài của dãy kết quả khi bài toán trên mảng A(N) mới được xét từ phần tử 1 đến phần tử i ( Nghiã là ta tạm giải bài toán với kích
Các Ý Kiến