Giả sử, có n số nhóm sinh viên đang đợi để từ trường đại học trở về nhà bằng xe buýt của trường đại học. Trong mỗi nhóm học sinh có m số học sinh. Các nhóm sinh viên muốn di chuyển bằng xe buýt mà không bị tách rời. Họ lên xe buýt nếu và chỉ khi tất cả các thành viên trong nhóm của họ có thể lên xe buýt. Ngoài ra, một nhóm không lên xe buýt nếu nhóm trước của họ chưa lên xe buýt hoặc đã đến điểm đến của họ. Nếu được cung cấp số nhóm và số học sinh của mỗi nhóm, chúng ta phải tìm kích thước của xe buýt để xe buýt có thể chở tất cả các nhóm và mỗi khi xe buýt bắt đầu từ trường đại học không còn chỗ trống. trên xe buýt.
Vì vậy, nếu đầu vào là nhóm hoặc gr_no =[3, 4, 2, 2, 1, 4, 3, 5], thì đầu ra sẽ là [12, 24].
Nếu kích thước xe buýt là 12, nó có thể chứa các nhóm 1 - 5 trong chuyến đi đầu tiên và các nhóm còn lại trong chuyến đi thứ hai.
Nếu kích thước xe buýt là 24, nó có thể chứa tất cả các nhóm và chỉ vận chuyển chúng trong một chuyến đi.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một function factor_ret (). Điều này sẽ mất n
- đối với tôi trong phạm vi (0 đến n ^ 0,5), thực hiện
- nếu n mod i giống 0, thì
- thêm một bộ giá trị (i, giá trị sàn của (n / i)) vào output_list
- nếu n mod i giống 0, thì
- sắp xếp danh sách output_list
- trả về output_list dưới dạng một tập hợp
- đối với tôi trong phạm vi (0 đến n ^ 0,5), thực hiện
- Bây giờ, hãy thực hiện các bước sau -
- total:=một danh sách mới chứa mục gr_no [0]
- đối với tôi trong phạm vi từ 1 đến kích thước là gr_no, hãy thực hiện
- chèn tổng số [i - 1] + gr_no [i] vào cuối tổng số
- b_sizes:=một danh sách mới
- đối với mỗi kích thước trong factor_ret (tổng của danh sách (gr_no)), hãy thực hiện
- temp_list:=một danh sách mới từ tất cả các phần tử khác 0 trong tổng số
- chỉ mục:=1
- chỉ báo:=True
- đối với mỗi điểm trong temp_list, hãy thực hiện
- nếu điểm không giống với chỉ số size *, thì
- chỉ báo:=Sai
- ra khỏi vòng lặp
- index:=index + 1
- nếu điểm không giống với chỉ số size *, thì
- nếu chỉ báo là True, thì
- chèn kích thước vào cuối b_sizes
- trả về kích thước b_size
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
from functools import reduce def solve(gr_no): total = [gr_no[0]] for i in range(1, len(gr_no)): total.append(total[i - 1] + gr_no[i]) b_sizes = [] for size in factor_ret(sum(gr_no)): temp_list = list(filter(lambda x : x % size == 0, total)) index = 1 indicator = True for point in temp_list: if point != size * index: indicator = False break index += 1 if indicator: b_sizes.append(size) return b_sizes def factor_ret(n): return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))) print(solve([3, 4, 2, 2, 1, 4, 3, 5]))
Đầu vào
[3, 4, 2, 2, 1, 4, 3, 5]
Đầu ra
[12, 24]