Kết quả 1 đến 10 của 13
-
07-13-2016, 03:32 PM #1Silver member
- Ngày tham gia
- Aug 2015
- Bài viết
- 0
Giải giúp mình bài này bằng Quy Hoạch Động với
Bờm thắng phú ông trong một cuộc đánh cược và buộc phú ông phải đãi rượu. Phú ông bèn bày ra một dãy n chai chứa đầy rượu và nói với bờm rằng có thể uống bao nhiêu tùy ý, nhưng đã chọn chai nào thì uống hết và không được uống ở 3 chai liền nhau bởi đó là điều xui xẻo. Hãy chỉ cho Bờm cách uống được nhiều rượu nhất.
View more random threads:
- Về bài tập pascal
- Tìm nhiều giá trị nhỏ nhất trong một mảng record Pascal
- Bài tập Pascal: Lập chương trình kiểm tra xâu đối xứng và thêm xâu ngắn nhất để nó thành đối xứng
- Nhờ các bác giúp cho lập trình pascal...
- Mn cùng vào đây thảo luận về Pascal :)
- Các hàm thường gặp trong Pascal
- Bài tập Pascal
- Huyện Phước Long tổ chức thành công hội thi môi trường
- Bài tập gỡ mìn
- Bạn nào ở phước long vào đăng kí off tết nhé!
-
07-14-2016, 10:41 AM #2Junior Member
- Ngày tham gia
- Nov 2015
- Bài viết
- 0
Gửi bởi tengiday
-
07-14-2016, 10:44 AM #3Junior Member
- Ngày tham gia
- Aug 2015
- Bài viết
- 0
tengiday bá đạo quá, cái gì cũng biết à [IMG]images/smilies/troll2/xucdong2.gif[/IMG]
-
07-14-2016, 10:50 AM #4Junior Member
- Ngày tham gia
- Dec 2015
- Bài viết
- 0
Thật ra bài này ko cần tới QHĐ, nhưng nếu muốn thì bạn có thể thử cách sau:
F[i] = số lượng chai rượu tối đa Bờm uống đc nếu uống chai thứ i.
Như vậy,
Mã:F[i] = max (F[i - 2] + 1, F[i - 3] + 2)
- Khi chọn chai i và chai i-2 thì ko thể chọn chai i-1.
- Khi chọn chai i và chai i-3 thì phải chọn chai i-1.
- Mình ko dùng F[i-1] vì mình ko chắc có chọn chai i-1 hay không. Với lại, khi chọn chai i-3 thì đã chọn luôn chai i-1 rồi.
Giá trị ban đầu cho mảng F là:
Mã:F[1] = 1, F[2] = 2; F[3] = 2;
Bạn cũng có thể tốn thêm 1 mảng để lưu trữ dấu. Ví dụ như track[i] sẽ lưu i-2 hoặc là i-3 tùy theo hàm max. Bạn lưu ý khi khởi tạo mảng dấu nhé.
Cách ko cần QHĐ: mình sẽ lấy 2 chai liên tiếp, bỏ 1 chai; rồi lấy 2 chai liên tiếp, bỏ 1 chai,... Như vậy, công thức tính số lượng chai rượu tối đa là:
Mã:n div 3 * 2 + n mod 3
Mã:if i mod 3 <> 0
-
07-14-2016, 03:55 PM #5Junior Member
- Ngày tham gia
- Nov 2015
- Bài viết
- 0
[QUOTE="tengiday"]Thật ra bài này ko cần tới QHĐ, nhưng nếu muốn thì bạn có thể thử cách sau:
F[i] = số lượng chai rượu tối đa Bờm uống đc nếu uống chai thứ i.
Như vậy,
Mã:n div 3 * 2 + n mod 3
Mã:if i mod 3 <> 0
</div>
</div>
</div>À mình quên nói là số rượu tính bằng dung tích
Ví dụ
Input:
6
6 10 10 13 10 10
thì Output là: 10 10 10 10
-
07-14-2016, 04:28 PM #6Junior Member
- Ngày tham gia
- Aug 2015
- Bài viết
- 0
Gửi bởi Richard Annowit
Bạn cho mình xem nguyên code nhé, như vậy sẽ dễ biết hơn.
-
07-14-2016, 04:29 PM #7Junior Member
- Ngày tham gia
- Aug 2015
- Bài viết
- 1
Gửi bởi Ihavenothing
-
07-14-2016, 06:47 PM #8Junior Member
- Ngày tham gia
- Nov 2015
- Bài viết
- 0
Gửi bởi Richard Annowit
F[i] = dung tích rượu lớn nhất mà Bờm uống tới chai thứ i. Lưu ý: chai thứ i có thể uống hoặc không uống.
Mình có công thức QHĐ như sau:
Mã:F[i] = max(F[i - 1], F[i - 2] + a[i], F[i - 3] + a[i - 1] + a[i]).
- Uống chai thứ i - 1, nhưng ko uống chai thứ i.
- Uống chai thứ i - 2, ko uống chai thứ i - 1, uống chai thứ i.
- Uống chai thứ i - 3, ko uống chai thứ i - 2, uống chai thứ i - 1, uống chai thứ i.
Khởi tạo mảng F:
Mã:F[1] = a[1], F[2] = a[1] + a[2], F[3] = max(a[1] + a[2], a[1] + a[3], a[2] + a[3]).
Mình viết cho bạn 1 đoạn duyệt ngược mảng F chừng nào phần tử còn lớn hơn 3 nhé.
Mã:t := n; while (t > 3) do begin if (f[t] = f[t - 1]) then begin write(a[t - 1], ' '); t := t - 1; end else if (f[t] = f[t - 3] + a[t - 1] + a[t]) then begin write(a[t], ' ', a[t - 1], ' '); t := t - 3; end else if (f[t] = f[t - 2] + a[t]) then begin write(a[t], ' '); t := t - 2; end; end;
Input:
6
3 2 1 4 5 6
Output:
6 5 2 3
Input:
6
6 1 5 3 2 1
Output:
1 3 5 6
(lưu ý 2 output trên ra 2 kết quả dung tích rượu khác nhau 16 vs 15, mặc dù đều là cùng 6 số).
Những trường hợp đặc biệt như n = 1, 2, 3 thì bạn nhớ xử lý nhé.
-
07-14-2016, 07:04 PM #9Junior Member
- Ngày tham gia
- Aug 2015
- Bài viết
- 0
[QUOTE="tengiday"]Như vậy thì giải bài này hơi khác tí xíu nhé.
F[i] = dung tích rượu lớn nhất mà Bờm uống tới chai thứ i. Lưu ý: chai thứ i có thể uống hoặc không uống.
Mình có công thức QHĐ như sau:
Mã:t := n - 1; while (t > 3) do begin if (f[t] = f[t - 1]) then begin write(a[t - 1], ' '); t := t - 1; end else if (f[t] = f[t - 3] + a[t - 1] + a[t]) then begin write(a[t], ' ', a[t - 1], ' '); t := t - 3; end else if (f[t] = f[t - 2] + a[t]) then begin write(a[t], ' '); t := t - 2; end; end;
Input:
6
3 2 1 4 5 6
Output:
6 5 2 3
Input:
6
6 1 5 3 2 1
Output:
1 3 5 6
(lưu ý 2 output trên ra 2 kết quả dung tích rượu khác nhau 16 vs 15, mặc dù đều là cùng 6 số).
Những trường hợp đặc biệt như n = 1, 2, 3 thì bạn nhớ xử lý nhé.</div>
</div>
</div>
</div>Mình làm được rồi, cảm ơn bạn nha!!! Bạn nhiệt tình giúp đỡ thật.
Nhưng mà bạn ơi
Mã:F[i] = max(F[i - 1], F[i - 2] + a[i], F[i - 3] + a[i - 1] + a[i]).
Mã:f[i]:=max(f[i-3]+a[i-1]+a[i],f[i-2]+a[i])
-
07-14-2016, 07:41 PM #10Junior Member
- Ngày tham gia
- Nov 2015
- Bài viết
- 0
1) Bạn cho mình biết gọi (định nghĩa) mảng f là gì và khởi tạo giá trị như thế nào và kết quả được đọc từ đâu để mình xem. Bạn thử test này xem nhé:
Input:
6
3 2 1 4 15 2
Output:
15 4 2 3
Tổng max phải là 24. Mình nghĩ bạn nên build mảng F trước, chắc chắn nó đúng rồi hãy nghĩ tới duyệt ngược sau.
2) Mình có sửa lại là t := n. Tại mình chuyển từ C++ sang Pascal cho nên phải đổi index của mảng.
Những sản phẩm được thanh lý và tái sử dụng không chỉ mang lại lợi ích kinh tế mà còn giúp tạo ra một môi trường sống xanh, sạch đẹp. Sự tiến bộ và phát triển của xã hội không đến mà không có những...
Tái sinh tài nguyên: Đóng góp của...