Vì vậy, bạn chỉ cần in độ dài của danh sách, không phải danh sách? Điều đó giúp, bởi vì nó đơn giản hóa việc quản lý bộ nhớ (đây là một vấn đề đối với c).
Đây thực sự chỉ là một tìm kiếm được tôn vinh. Tại mỗi điểm bạn cần biết (1) giá trị hiện tại (nếu có); (2) chiều dài hiện tại (nếu có); (3) vị trí trong danh sách; (4) chiều dài lớn nhất được biết. Sử dụng độ dài bằng 0 giúp theo dõi khi bạn không có giá trị hiện tại (vì vậy bạn không cần giá trị ban đầu "ma thuật"). Giá trị trả về phải là độ dài lớn nhất.
Trên mỗi lần đệ quy, bạn có thể bỏ qua số hiện tại hoặc đưa nó vào danh sách (nhưng chỉ khi nó nhỏ hơn giá trị hiện tại).
để mã chỉ là:
#include <stdio.h>
int max(int a, int b) {
return a > b ? a : b;
}
int find(int* data, int total_length, int offset, int previous,
int run_length, int max_length) {
// update max length if it has improved
if (run_length > max_length) max_length = run_length;
// if we are at the end, return max
if (offset == total_length) return max_length;
// if the current value is too small, we cannot include it
if (run_length && data[offset] <= previous)
return find(data, total_length, offset+1, previous, run_length, max_length);
// otherwise, we want the best of either including it or not
return max(
// try including it
find(data, total_length, offset+1, data[offset], run_length+1, max_length),
// try excluding it
find(data, total_length, offset+1, previous, run_length, max_length));
}
// test
int main(int argc, char *argv) {
int data[] = { 88, 1, 22, 3, 34, 6, 54, 9, 19 };
printf("%d\n", find(data, 9, 0, 0, 0, 0));
return 0;
}
rõ ràng điều này là mã khủng khiếp c (không phải vì tôi không sử dụng khởi tạo mảng, mà một ai đó "vui lòng" cố định (mặc dù họ không bận tâm đến việc bỏ phiếu này Câu trả lời - Tôi đoán họ nghĩ rằng tôi có động lực để đăng bài ở đây bằng cách học từ kiến thức sâu về cú pháp C), nhưng vì nó sử dụng ngăn xếp cuộc gọi ở đó sẽ hiệu quả hơn khi sử dụng cấu trúc bộ nhớ riêng biệt).
(Ngoài ra, tôi phải nói, viết một cái gì đó như thế này dễ dàng hơn nhiều như là một hàm đệ quy hơn là làm nó trong một vòng lặp, bởi vì bạn chỉ cần ghi lại những gì bạn muốn xảy ra - nếu bạn có một vòng lặp thì bạn sẽ cần phải lo lắng về việc thay đổi các giá trị và đặt lại chúng và tất cả những điều đó gây rối. Vấn đề là nó lạm dụng stack khủng khiếp).
Tôi không thấy mối quan hệ giữa '88, 1, 22, 3, 34, 6, 54, 9, 19' và sản lượng dự kiến '1,3,6,9,19'. Và '% d: 5' là gì? Đây có phải là bài tập về nhà không? –
Dòng phụ tăng dần lớn nhất (không nhất thiết tiếp giáp) –
... và có lẽ chiều dài của đoạn phụ –