LH Quảng cáo: lazijsc@gmail.com

Bài tập  /  Bài đang cần trả lời

Cho một dãy số nguyên N ( 2 <= N <= 100), và một dãy số nguyên ai ( 0 < ai < 100)

Cho một dãy <!--[if gte msEquation 12]>N<!--[endif]-->  các số nguyên, tìm dãy con dài nhất từ dãy đã cho sao cho trị tuyệt đối của bất kì <!--[if gte msEquation 12]-->2<!--[endif]-->  phần tử nào đều nhỏ hơn hoặc bằng <!--[if gte msEquation 12]-->1<!--[endif]--> .

Dữ liệu vào: Vào từ tệp văn bản subarr.inp có dạng:

·     Dòng đầu ghi số nguyên N, trong đó: <!--[if gte msEquation 12]>2≤n≤100<!--[endif]-->

·     Dòng thứ hai ghi <!--[if gte msEquation 12]>N<!--[endif]-->  số nguyên <!--[if gte msEquation 12]-->ai<!--[endif]-->  trong đó <!--[if gte msEquation 12]-->0<ai<100<!--[endif]-->

Kết quả: In ra tệp văn bản subarr.out một số nguyên: số phần tử của dãy con dài nhất tìm được.

Ví dụ:

subarr.inp

subarr.out

Giải thích

 

9

1 1 2 2 4 4 5 5 5

5

Dãy thỏa mãn là {1,1,2,2} và {4,4,5,5,5} vì giữa hai phần tử bất kì hơn kém nhau không quá 1 đơn vị. Dãy 2 dài hơn, có 5 phần tử.

 

6

4 6 5 3 3 1

3

Chỉ có 1 dãy thỏa mãn và dài nhất là {4,3,3}

 

6

1 2 2 3 1 2

5

Dãy thỏa mãn là {1,2,2,1,2} có 5 phần tử.


help mình c++!
1 trả lời
Hỏi chi tiết
37
Tham khảo câu trả lời từ Trợ lý ảo Lazi
Để giải bài toán tìm dãy con dài nhất từ một dãy số nguyên sao cho trị tuyệt đối của bất kỳ hai phần tử nào đều nhỏ hơn hoặc bằng 1, bạn có thể sử dụng một phương pháp đơn giản với sự kết hợp của vòng lặp và điều kiện kiểm tra.

Dưới đây là mã C++ để thực hiện điều này:

```cpp
#include
#include
#include
#include

int main() {
std::ifstream input("subarr.inp");
std::ofstream output("subarr.out");

int N;
input >> N;

std::vector a(N);
for (int i = 0; i < N; i++) {
input >> a[i];
}

int maxLength = 1; // Độ dài lớn nhất
for (int i = 0; i < N; i++) {
int currentLength = 1; // Độ dài hiện tại
for (int j = i + 1; j < N; j++) {
if (std::abs(a[j] - a[i]) <= 1) {
currentLength++;
} else {
break; // Nếu không thỏa mãn điều kiện, dừng
}
}
maxLength = std::max(maxLength, currentLength);
}

output << maxLength << std::endl;

return 0;
}
```

### Giải thích mã:
1. **Đọc dữ liệu**: Chương trình mở tệp `subarr.inp`, đọc số nguyên `N`, sau đó đọc các phần tử của mảng `a`.
2. **Tìm dãy con dài nhất**:
- Sử dụng hai vòng lặp: vòng lặp bên ngoài xác định phần tử bắt đầu, vòng lặp bên trong kiểm tra các phần tử tiếp theo để xem liệu chúng có thỏa mãn điều kiện độ lệch không lớn hơn 1.
- Nếu có, tăng biến `currentLength`. Nếu không, dừng vòng lặp ngay lập tức.
3. **Cập nhật độ dài lớn nhất**: Sau mỗi vòng lặp bên ngoài, so sánh và cập nhật độ dài lớn nhất tìm thấy.
4. **Ghi kết quả**: Kết quả được ghi ra tệp `subarr.out`.

### Lưu ý:
- Đảm bảo rằng tệp `subarr.inp` tồn tại trong cùng thư mục với tệp thực thi.
- Bài toán này có độ phức tạp O(N^2) do sử dụng hai vòng lặp, điều này là chấp nhận được cho N ≤ 100.
0
0
Thu Phươngg
20/11 20:23:55

def soln(): with open('subarr.inp', 'r') as f: N = int(f.readline().strip()) a = [int(x) for x in f.readline().strip().split()]

dp = [1] * N for i in range(1, N): for j in range(i): if abs(a[i] - a[j]) <= 1: dp[i] = max(dp[i], dp[j] + 1) with open('subarr.out', 'w') as f: f.write(str(max(dp)))

soln()

Mở khóa để xem toàn bộ nội dung trả lời

(?)
Bạn đã đạt đến giới hạn của mình. Bằng cách Đăng ký tài khoản, bạn có thể xem toàn bộ nội dung trả lời
Cải thiện điểm số của bạn bằng cách đăng ký tài khoản Lazi.
Xem toàn bộ các câu trả lời, chat trực tiếp 1:1 với đội ngũ Gia sư Lazi bằng cách Đăng nhập tài khoản ngay bây giờ
Tôi đã có tài khoản? Đăng nhập

Bạn hỏi - Lazi trả lời

Bạn muốn biết điều gì?

GỬI CÂU HỎI
Học tập không giới hạn cùng học sinh cả nước và AI, sôi động, tích cực, trải nghiệm
Bài tập liên quan
Bài tập Lập trình Lớp 8 mới nhất
Trắc nghiệm Lập trình Lớp 8 mới nhất

Hôm nay bạn thế nào? Hãy nhấp vào một lựa chọn, nếu may mắn bạn sẽ được tặng 50.000 xu từ Lazi

Vui Buồn Bình thường

Học ngoại ngữ với Flashcard

×
Trợ lý ảo Trợ lý ảo
×
Gia sư Lazi Gia sư