Tìm dãy con của một dãy
:confused_smile: Ai làm ơn chỉ giúp tui cách giải các bài tìm dãy con với! Mãi mà tui vẫn chẳng bit làm thế nào? Hix
Vd: Cho n số nguyên a1, a2,…,an. Tìm dãy con của dãy a có tổng bằng s <=40000., n<=200. Mỗi phần tử của dãy a chỉ sử dụng tối đa 1 lần. Dữ liệu vào: Cho từ tệp Daycon.inp có dòng 1 chứa số n và s, dòng 2 chứa n số nguyên của dãy a. Kết quả: Ghi vào tệp Daycon.out dãy tìm được Daycon.inp Daycon.out 5 10 2 3 4 8 1 2 3 4 1 |
Ðề: Hỏi bài
Theo như đề thì dãy con 2 8 cũng là một kết quả đúng không?
Bài yêu cầu tìm nhiều kết quả hay chỉ một? |
Ðề: Tìm dãy con của một dãy
đề chính xác là như thế này cơ các bác ah! :wink_smile:
Input 5 10 2 3 4 8 1 Output 2 3 4 1 |
Ðề: Tìm dãy con của một dãy
2 8
cũng là 1 kết quả đấy bác ah! Em mong các bác chỉ dẫn tận tình cách làm các bài toán dạng như vậy! Em đầu óc tối tăm mãi mà vẫn k biết cách làm Thanks |
Ðề: Tìm dãy con của một dãy
Giải thuật thoạt xuất hiện trong đầu nên chưa chắc là tốt nhất:
1) Xây dựng đồ thị: Xem mỗi phần từ ai của dãy là một đỉnh của đồ thị có hướng. Cạnh của đồ thị aiaj với (i < j). Trọng lượng cạnh là ai. Lưu ý trong quá trình xây dựng đồ thị cần loại bỏ các ai >= s. 2) Áp dụng giải thuật LLoyd để tìm đường đi 2 đỉnh đồ thị. Sau đó in ra đường đi nào có độ dài s-d (với d là đỉnh cuối của đường đi). |
Ðề: Tìm dãy con của một dãy
em cám ơn bác myhanh nhưng thực sự là với đồ thị thì em lại càng mù tịt hơn.
Em nhìn vào chỉ như nhìn bức vách thui. Em chỉ là gà đang tập tọe học lập trình thui mà. Mong các bác pro chỉ giáo :embaressed_smile: em có bài này nữa mong các bác ra tay kíu giúp Đoạn con Cho dãy số nguyên không âm a1, a2, …an. Chia dãy trên thành đoạn con liên tiếp sao cho tổng giá trị các phần tử của các đoạn con đều bằng nhau và số đoạn con là lớn nhất. Dữ liệu vào trong file Doancon.inp có dạng: - Dòng đầu ghi số nguyên dương n là số phần tử có trong dãy (n <= 1000) - Các dòng tiếp theo ghi lần lượt các phần tử thuộc dãy. Dữ liệu ra trong file Doancon.out - Dòng đầu ghi số p, q là số đoạn con và tổng giá trị của mỗi đoạn con. - P dòng tiếp theo mỗi dòng ghi số d và b là chỉ số của phần tử đầu và phần tử kết thúc 1 đoạn con trong dãy đã cho. Ví dụ: Doancon.inp Doancon.out 10 1 3 5 9 7 2 4 1 4 9 5 9 1 3 4 4 5 6 7 9 10 10 |
Ðề: Tìm dãy con của một dãy
Trích:
|
Ðề: Tìm dãy con của một dãy
em cám ơn các bác rất nhìu!
Các bác cho e bít làm thế nào mà các bác lập trình giỏi đc k ah!:tounge_smile: |
Múi giờ GMT +7. Hiện tại là 04:43 PM. |
Website sử dụng phần mềm vBulletin phiên bản 3.6.8
do Công ty TNHH Jelsoft giữ bản quyền từ 2000 - 2024.
Hội CHS Lê Quý Đôn-Long An giữ bản quyền nội dung của website này