Thiết kế thuật toán và chương trình theo mô đun cho bài toán
Thiết kế thuật toán và chương trình theo mô đun cho bài toán sau.
Một công ti du lịch có n địa điểm tham quan được đánh số theo thứ tự 0, 1, 2, ...n – 1. Công ti này luôn tổ chức các tour du lịch đi lần lượt từ vị trí 0, 1, 2,... và kết thúc tại vị trí cuối cùng n − 1. Để thuận tiện cho việc quảng bá du lịch công ti đã lấy ý kiến khách hàng đánh giá bằng điểm số cho từng địa điểm du lịch trên, các đánh giá có thể là các số dương, 0 hoặc số âm bất kì. Sổ lớn hơn 0 biểu thị đánh giá tốt, số nhỏ hơn 0 biểu thị đánh giá xấu về địa điểm đó. Mỗi khách hàng sẽ gửi lên công ti du lịch bảng đánh giá của mình, được biểu thị bằng một dãy n số, ví dụ như sau:
1, -3, 4, 10, 0, -5, -8, 2, -1, 7, 2
Công ti du lịch hứa sẽ tổ chức một tour riêng cho mỗi khách hàng, bảo đảm sự hài lòng cao nhất của khách hàng. Tour du lịch riêng của khách hàng sẽ là một dãy các vị trí liên tục các địa điểm, ví dụ từ vị trí i đến j, tức là xuất phát từ i, khách hàng sẽ lần lượt đi qua các vị trí i, i + 1, i + 2,... và kết thúc tại j. Công ti du lịch bảo đảm rằng tổng các đánh giá của khách hàng trên tour riêng của mình là lớn nhất.
Em hãy giúp công ti du lịch thiết lập tour du lịch tối ưu cho khách hàng nếu biết trước các đánh giá của khách hàng đó.
Quảng cáo
Giả sử dữ liệu đầu vào là đánh giá của khách hàng được cho trong tệp văn bản "dulich.inp", ví dụ tệp có dạng sau:
Chương trình có thể như sau:
1 fi = "dulich.inp"
2 def NhapDL(fi):
3 f = open(fi)
4 A = [int(x) for x in f.readline().split()]
5 return A
6
7 def DiemDG(A,i,j):
8 S = 0
9 for k in range(i, j+1):
10 S = S + A[k]
11 return S
12
13 def findMAX(A):
14 n = len(A)
15 imax = 0
16 jmax = 0
17 vmax = A[0]
18 for i in range(n):
19 for j in range(i,n):
20 if vmax < DiemDG(A,i,j):
21 imax = i
22 jmax = j
23 vmax = DiemDG(A,i,j)
24 return imax,jmax
25
26 def Thongbao(i,j):
27 print("Lịch trình du lịch tối ưu của quý khách là từ địa điểm",i,"đến địa điểm",j)
28
29 # Chương trình chính
30 A = NhapDL(fi)
31 imax,jmax = findMAX(A)
32 Thongbao(imax,jmax)
Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí
>> 2K8 Chú ý! Lộ Trình Sun 2026 - 3IN1 - 1 lộ trình ôn 3 kì thi (Luyện thi 26+ TN THPT, 90+ ĐGNL HN, 900+ ĐGNL HCM, 70+ ĐGTD - Click xem ngay) tại Tuyensinh247.com.Đầy đủ theo 3 đầu sách, Thầy Cô giáo giỏi, luyện thi theo 3 giai đoạn: Nền tảng lớp 12, Luyện thi chuyên sâu, Luyện đề đủ dạng đáp ứng mọi kì thi.
 |
 |
 |
 |
 |
 |
 |
 |
Hỗ trợ - Hướng dẫn
-
024.7300.7989
-
1800.6947
(Thời gian hỗ trợ từ 7h đến 22h)
Email: lienhe@tuyensinh247.com
