Home Home » Pascal nâng cao » Bài tập chuyên đề Quy hoạch động

Bài tập chuyên đề Quy hoạch động

Thứ Bảy, 29 tháng 7, 2017
Bài 1: Bài toán Tính tổng của dãy số                                                SUM.PAS
          Cho dãy số nguyên gồm n phần tử a1, a2, …, an  (1 £ n £ 105) và hai số nguyên dương p và q (1 £ p £ q £ n).
Yêu cầu: Hãy tính tổng của các phần tử liên tiếp từ  ap … aq  bằng phương pháp quy hoạch động (lập bảng phương án).
Dữ liệu vào: Ghi trong file văn bản SUM.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương n và k, hai số được ghi cách nhau một dấu cách.
- Dòng 2: Ghi n số nguyên a1, a2, …, an, các số được ghi cách nhau ít nhất một dấu cách (-32000 £ ai £ 32000).
- Dòng thứ i trong k dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương pi và qi, hai số được ghi cách nhau một dấu cách (1 £ pi £ qi £ n).
Dữ liệu ra: Ghi ra file văn bản SUM.OUT theo cấu trúc như sau:
- Dữ liệu được ghi trên k dòng: Dòng thứ i ghi một số nguyên là tổng giá trị của các phần tử trong đoạn pi..qi
Ví dụ:

SUM.INP
SUM.OUT
5  3
2  9  -3   5   8
1  5
2  3
4  4

21
6
5



Bài 2: TRIANGLE NUMBER (Tam giác số)                          TRIANNUM.PAS

          
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 đường đi trong tam giác số sao cho tổng giá trị của các ô trong đường đi có giá trị lớn nhất.
Dữ liệu vào: Cho trong file văn bản TRIANNUM.INP có cấu trúc như sau:
Dòng 1: Ghi số nguyên dương N là số hàng của tam giác (1 ≤ N ≤ 100).
Dòng thư i trong N dòng tiếp theo: Ghi i số nguyên dương lần lượt là giá trị của các ô trên dòng thứ i tưng ứng trong tam giác (Các số có giá trị không quá 32000). Các số được ghi cách nhau một dấu cách.
Dữ liệu ra: Ghi ra file văn bản TRIANNUM.OUT theo cấu trúc:
Dòng 1: Ghi ra số nguyên dương S là tổng giá trị của đường đi tìm được.
Ví dụ:

TRIANNUM.INP
TRIANNUM.OUT
6
7
2  8
5  9  3
4  6  9   2
7  8  5   6   6
1  3  4   9   8   1
48


Bài 3: Bài toán Thỏ nhặt cà rốt             CARROT.PAS


Các con thú nuôi trong chuồng ở vườn bách thú thường ít có điều kiện vận động. Điều này vừa có hại cho sức khỏe của thú nuôi, vừa làm giảm hứng thú của khách tham quan. Để khắc phục điều đó, Ban giám đốc cho đặt một cái thang có n bậc trong chuồng thỏ. Đến giờ cho ăn người ta đặt cà rốt - thứ khoái khẩu nhất của thỏ, lên bậc trên cùng của thang. Thỏ phải nhảy theo các bậc thang để lấy cà rốt. Mỗi bước nhảy thỏ có thể vượt được k bậc (1 ≤ k ≤ n ≤ 300). Có thể có nhiều cách nhảy để lấy cà rốt. Hai cách nhảy gọi là khác nhau nếu tồn tại một bậc thỏ tới được ở một cách nhảy và bị bỏ qua ở cách kia. Ví dụ, với n = 4 và k = 3 có tất cả 7 cách lấy cà rốt khác nhau: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1.
Yêu cầu: Cho k và n. Hãy xác định số cách khác nhau thỏ có thể thực hiện để lấy cà rốt.
Dữ liệu vào: Ghi trong file văn bản CARROT.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương t là số lượng cặp k và n (1 ≤ t ≤ 50).
- Dòng thứ i trong t dòng tiếp theo: Mỗi dòng ghi 2 số nguyên k và n.
Dữ liệu ra: Ghi ra file văn bản CARROT.OUT, kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên.
Ví dụ:
CARROT.INP

CARROT.OUT
3
1 3
2 7
3 10

1
21
274

Bài 4:  Bài toán " con kiến".                     FOOD.PAS

Trên một sân hình chữ nhật MxN, được chia thành các ô vuông đơn vị, mỗi ô chứa một lượng thức ăn. Một con kiến xuất phát từ ô (1,1) muốn đi qua sân để đến dòng thứ M. Con kiến chỉ có thể đi theo một dòng chia nhỏ trên sân ứng với một dòng của bảng chữ nhật hoặc đi theo trên một cột của sân. Hãy chỉ ra đường đi giúp con kiến có được nhiều thức ăn nhất.
Dữ liệu vào: Từ tệp FOOD.INP với cấu trúc sau
-         Dòng 1 gồm 2 giá trị M, N được viết cách nhau bởi dấu  cách
-         M dòng tiếp theo mỗi dòng chứa N giá trị viết cách nhau bởi dấu cách.
Dữ liệu ra: Ghi vào tệp FOOD.OUT, một số nguyên duy nhất thể hiện giá trị lớn nhất mà con kiến có thể ăn để đi đến được hàng thứ M.
Ví dụ:

FOOD.INP
FOOD.OUT
3 5
7 3 8 1 5
8 8 3 14 1
6 15 19 1 1
45

Bài 5: Bài toán ″Sa mạc ″.           SAMAC.PAS

Một bãi sa mạc có dạng hình chữ nhật MxN. Mỗi ô vuông đơn vị trên sa mạc có một độ cao nào đó. Một người muốn đi từ bờ đầu này sang bờ cuối cùng bên kia. Người đó chỉ có thể đi từ ô đang đứng tới một ô mới theo hướng thẳng đứng chéo trái hoặc chéo phải. Giả thiết rằng người đó không được vượt ra hai mép trái và phải của sa mạc.

Hãy tìm đường đi sao cho người đó phải vượt qua quãng đường ngắn nhất. Mỗi lần đi từ một ô sang ô mới tiếp theo người đó phải đi hết quãng đường bằng độ chênh cao giữa hai ô đó.

Dữ liệu vào: Từ tệp SAMAC.INP với cấu trúc sau
-         Dòng 1 gồm 2 giá trị M, N được viết cách nhau bởi dấu  cách
-         M dòng tiếp theo mỗi dòng chứa N giá trị viết cách nhau bởi dấu cách.
Dữ liệu ra: Ghi vào tệp SAMAC.OUT, một số nguyên duy nhất thể hiện giá trị nhỏ nhất của đường đi để người đó vượt qua được sa mạc (đến được hàng thứ M).
Ví dụ:

SAMAC.INP
SAMAC.OUT
5 5
3 3 8 1 5
8 7 3 14 1
6 7 18 1 1
20 20 17 23 24
31 20 27 10 6
12

Bài 6: Vận may       vanmay.pas
Một người may mắn gặp được một ma trận kim cương gồm MxN ô. Giá trị A[i,j] (A[i,j] là một số nguyên dương) là trọng lượng kim cương có ở ô trên dòng i cột j. Người này chỉ được xuất phát từ 1 ô ở mép bên trái của ma trận và di chuyển sang mép bên phải. Từ ô (i,j) người này chỉ có thể di chuyển sang 1 trong 3 ô (i-1,j+1), (i,j+1) và (i+1,j+1). Di chuyển qua ô nào thì người đó được phép mang theo lượng kim cương ở ô đó. Em hay giúp người này di chuyển theo hướng đi nào để có thể nhận được nhiều kim cương nhất.
Dữ liệu vào: từ tệp văn bản vanmay.inp với cấu trúc sau
- dòng 1 ghi 2 số M, N (0<=M,N<=5000) cách nhau một khoảng trắng
- M dòng tiếp theo mỗi dòng ghi N số nguyên của ma trận( các số nguyên có giới hạn 10^9).
Dữ liệu ra: tệp văn bản vanmay.out, ghi tổng số kim cương có thể có được.
ví dụ
vanmay.inp
vanmay.out
3 3
1 5 13
3 8 14
4 6 13

26

 Bài 7: Day wavio         wavio.pas
Dãy số Wavio là dãy số nguyên thỏa mãn các tính chất : các phần tử đầu sắp xếp thành 1 dãy

 tăng dần đến 1 phần tử đỉnh sau đó giảm dần. Ví dụ dãy số 1 2 3 4 5 2 1 là 1 dãy Wavio độ dài 7. Cho 1 dãy gồm N số nguyên (N ≤ 1000), hãy chỉ ra một dãy con Wavio có độ dài lớn nhất trích ra từ dãy đó.

Dữ liệu vào: từ tệp wavio.inp có cấu trúc

 – Dòng đầu ghi số n.

 – Dòng thứ hai ghi n số Ai là giá trị phần tử thứ i của dãy (Ai ≤ 1000).
Dữ liệu ra: ghi vào tệp wavio.out 1 số nguyên duy nhất là độ dài của dãy wavio dài nhất.
Ví dụ:
WAVIO.INP
WAVIO.OUT
5
2 1 4 3 5
3


Bài 8: Dãy con có tổng lớn nhất                  TONGMAX.PAS
Cho dãy A gồm n phần tử (1<n<1000) số nguyên dương a[1..n]. Hãy tìm dãy con đơn điệu tăng dần có tổng lớn nhất.
Dữ liệu vào: từ tệp tong.inp có cấu trúc
-          Dòng đầu ghi số n
-          Dòng tiếp theo ghi n số nguyên dương cách nhau bởi dấu cách trống thể hiện n phần tử trong dãy A.
Dữ liệu ra: ghi vào tệp tong.out 1 số nguyên duy nhất thể hiện tổng lớn nhất của dãy con.

 Ví dụ
TONG.INP
TONG.OUT
5
1 100 7 9 99
116
5
1 200 7 9 99
201


Bài 9: Dãy con dài nhất có tổng chia hết cho k                     SUBSEQ.PAS
Cho dãy A gồm n phần tử (1<n<1000) số nguyên dương a[1..n]. Hãy tìm dãy con đơn điệu tăng dần dài nhất có tổng chia hết cho k.
Dữ liệu vào: từ tệp SUBSEQ.INP có cấu trúc
-          Dòng đầu ghi số n và k
-          Dòng tiếp theo ghi n số nguyên dương a[1],a[2],…cách nhau bởi dấu cách trống thể hiện n phần tử trong dãy A.
Dữ liệu ra: ghi vào tệp SUBSEQ.OUT 1 số nguyên duy nhất thể hiện độ dài lớn nhất của dãy con chia hết cho k.

 Ví dụ
SUBSEQ.INP
SUBSEQ.OUT
5 17
1 100 7 9 99
3

Bài 10: Dãy đổi dấu DAYDOIDAU.PAS

Cho dãy a1, a2,…, an (N ≤ 1000, ai ≤ 1000). Hãy tìm dãy con  đổi dấu dài nhất của dãy  đó. Dãy con đổi dấu ai1, ai2, …, aik phải thoả mãn các điều kiện sau:

·         ai1 < ai2 > ai3 <… hoặc ai1 > ai2 < ai3 > …

·         các chỉ số phải cách nhau ít nhất L: i2 – i1 ≥ L, i3 – i2 ≥ L….

·         chênh lệch giữa 2 phần tử liên tiếp nhỏ hơn U: |ai1 – ai2|≤U, |ai2 – ai3| ≤ U…

Input :
– Dòng đầu tiên ghi ba số n, l, u.
– Dòng thứ hai ghi n số là các phần tử của dãy A.
Output :
– Ghi độ dài lớn nhất của dãy con đổi dấu.

Ví dụ

DAYDOIDAU.INP
DAYDOIDAU.OUT
5 2 2
5 4 3 2 4
3


var fi,fo:text;

a,f,p:array[1..10000] of integer;

n,l,u,i,j,k:integer;

function max(a,b:integer):integer;

begin

  if a>b then max:=a else max:=b;

end;

begin

  assign(fi,'daydoidau.inp'); reset(fi);

  assign(fo,'daydoidau.out'); rewrite(fo);

  readln(fi,n,l,u);

  for i:=1 to n do read(fi,a[i]);

  close(fi);

 f[1]:=1;   p[1]:=1;  k:=f[1];

  for i:=2 to n do

    begin

      f[i]:=1;  p[i]:=1;

      for j:=1 to i-1 do

      if abs(a[i]-a[j])<=u then

      begin

         if (a[i]>a[j]) and (i-j>=l) and (f[i]<p[j]+1) then f[i]:=p[j]+1;

         if (a[i]<a[j]) and (i-j>=l) and (p[i]<f[j]+1) then p[i]:=f[j]+1;

      end;

      if (k<f[i]) or (k < p[i]) then k:=max(f[i],p[i]);

    end;

    write(fo,k);

    close(fo);
  end.
 Bài 11: Trò chơi với băng số      BANGSO.PAS




Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm n ô vuông, đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi một số nguyên dương ai, i = 1, 2, ..., n. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô i1, i2, ..., ik. Khi đó điểm số mà người chơi đạt được sẽ là:


•   ai1 - ai2 + ... + (-1)k-1aik

Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.

Dữ liệu vào: Từ tệp bangso.inp với cấu trúc sau:

•   Dòng đầu tiên chứa số nguyên dương n ( n ≤ 106 ) là số lượng ô của băng số;

•   Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an ( ai ≤ 104, i = 1, 2, ..., n ) ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Dữ liệu ra: Ghi kết quả vào tệp bangso.out

•   Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.



Ví dụ:
bangso.inp
bangso.out
7
4 9 2 4 1 3 7
17


Gọi F[i,1] là số điểm lớn nhất có thể đạt được khi xét tới ô thứ i và ô cuối cùng mang dấu ‘+’, tương tự F[i,2] là số điểm lớn nhất có thể đạt được khi xét tới ô thứ i và ô cuối cùng mang dấu ‘-’ ta thấy:
F[i,1]=Max(F[i-1,2]+a[i],F[i-1,1]).
F[i,2]=Max(F[i-1,1]-a[i],F[i-1,2]).

code 1
Var i,j,n:longint;
    A:array[0..1000001] Of Longint;
    F:array[0..1000001,1..2] Of int64;
    fi,fo:text;

Function Max(a,b:Longint):Longint;
Begin
 If a>b then max:=a else max:=b;
 End;
BEGIN
 assign(fi,'bangso.inp'); reset(fi);
 assign(fo,'bangso.out'); rewrite(fo);
  Readln(fi,n);
  For i:=1 to n do read(fi,a[i]);
  F[0,1]:=0;
  F[0,2]:=0;
  For i:=1 to n do
       begin
           F[i,1]:=Max(F[i-1,1],F[i-1,2]+A[i]);
           F[i,2]:=Max(F[i-1,2],F[i-1,1]-A[i]);
       end;
  Writeln(fo,Max(F[n,1],F[n,2]));
close(fi); close(fo);
end.

Bài 12: VCOWFLIX - Đi xem phim


Nông dân John đang đưa các con bò của anh ta đi xem phim! Xe tải của anh ta thì có sức chứa có hạn thôi, là C (100 <= C <= 5000) kg, anh ta muốn đưa 1 số con bò đi xem phim sao cho tổng khối lượng của đống bò này là lớn nhất, đồng thời xe tải của anh ta vẫn chịu được.
Cho N (1 <= N <= 16) con bò và khối lượng W_i của từng con, hãy cho biết khối lượng bò lớn nhất mà John có thể đưa đi xem phim là bao nhiêu.

Dữ liệu vào: từ tệp COW.INP

  • Dòng 1: 2 số nguyên cách nhau bởi dấu cách: C và N
  • Dòng 2..N+1: Dòng i+1 chứa 1 số nguyên: W_i

Kết quả ra: ghi vào tệp COW.OUT

1 số nguyên duy nhất thể hiện khối lượng bò lớn nhất mà john đưa đi xem phim

Ví dụ

COW.INP
COW.OUT
259 5
81
58
42
33
61
242







 






Chia sẻ bài viết
Bài liên quan

Comments[ 0 ]


Đăng nhận xét