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

Lập trình C++: Cho dãy n gồm số nguyên dương a1; a2;...; an (a1 ≤ 10^6)

lập trình c++: Cho dãy n gồm số nguyên dương a1; a2;...; an (a1≤ 10^6).

Yêu cầu: Đếm số lượng cặp (hai phần tử) có tổng là một số chẵn.

Dữ liệu: cho từ tệp văn bản DEMCAP.INP dòng đầu chứa số nguyên dương n (n ≤ 10^18), dòng tiếp theo ghi n số nguyên dương a1, a2, .: an, mỗi số cách nhau một dấu cách trống.

Kết quả: ghi ra tệp văn DEMCAP.OUT số cặp đếm được 
1 trả lời
Hỏi chi tiết
141
Tham khảo câu trả lời từ Trợ lý ảo Lazi
Để giải bài toán này, chúng ta cần xác định số lượng cặp các phần tử trong dãy số mà tổng của chúng là một số chẵn. Khái niệm cơ bản là:

- Tổng của hai số chẵn là chẵn.
- Tổng của hai số lẻ là chẵn.
- Tổng của một số chẵn và một số lẻ là lẻ.

Do đó, để tìm số cặp có tổng chẵn, chúng ta chỉ cần đếm số lượng số chẵn và số lượng số lẻ trong dãy. Số cặp có tổng chẵn sẽ được tính bằng công thức:

\[
\text{số cặp} = C(chẵn, 2) + C(lẻ, 2)
\]

Trong đó \(C(x, 2)\) là số cách chọn 2 trong x, được tính bằng công thức \(C(x, 2) = \frac{x \cdot (x-1)}{2}\).

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

```cpp
#include
#include
#include

int main() {
std::ifstream infile("DEMCAP.INP");
std::ofstream outfile("DEMCAP.OUT");

int n;
infile >> n;

// Kiểm tra điều kiện n
if (n <= 0) {
outfile << 0 << std::endl;
return 0;
}

int countEven = 0;
int countOdd = 0;
int number;

for (int i = 0; i < n; i++) {
infile >> number;
if (number % 2 == 0) {
countEven++;
} else {
countOdd++;
}
}

// Cách chọn 2 số chẵn
long long pairsEven = static_cast(countEven) * (countEven - 1) / 2;
// Cách chọn 2 số lẻ
long long pairsOdd = static_cast(countOdd) * (countOdd - 1) / 2;

long long totalPairs = pairsEven + pairsOdd;

outfile << totalPairs << std::endl;

infile.close();
outfile.close();

return 0;
}
```

### Giải thích mã

1. **Đọc dữ liệu từ tệp**: Chúng ta mở tệp `DEMCAP.INP` để đọc n (số lượng phần tử) và các phần tử trong dãy.
2. **Đếm số chẵn và số lẻ**: Sử dụng vòng lặp để kiểm tra mỗi số nếu số đó chẵn hay lẻ và tăng các biến `countEven` và `countOdd` tương ứng.
3. **Tính số cặp**: Dựa vào công thức trên để tính số cặp số chẵn và số cặp số lẻ.
4. **Ghi kết quả**: Kết quả được ghi vào tệp `DEMCAP.OUT`.

### Lưu ý
- Đảm bảo rằng n không quá lớn để tránh quá tải bộ nhớ; mã này không tối ưu cho n lên tới \(10^{18}\). Trong thực tế, do giới hạn bộ nhớ, chúng ta không thể lưu trữ quá nhiều số nguyên cùng một lúc. Do đó, khi n vượt quá 10 triệu, ta cần điều chỉnh cách nhập để tính toán trực tiếp mà không lưu trữ từng số.
0
0
Nguyen Thuan
10/08 16:38:57

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 ký 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

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

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