Đếm cặp số nguyên không âm phân biệt (x, y) thỏa bất đẳng thức x*x + y*y < n trong C++

Chúng ta được cho một số nguyên dương N. Mục tiêu là đếm các cặp số nguyên không âm phân biệt thỏa mãn bất đẳng thức: x*x + y*y < N.

Chúng ta sẽ bắt đầu từ x=0 đến x² < N và y=0 đến y² < N. Nếu bất kỳ x² + y² < N, tăng số cặp.

Ví dụ

Đầu vào

n = 4

Đầu ra

cặp phân biệt = 4

Giải thích − Các cặp sẽ là (0,0), (1,1), (0,1), (1,0). Tất cả thỏa mãn bất đẳng thức x² + y² < 4.

Đầu vào

n = 2

Đầu ra

cặp phân biệt = 3

Giải thích − Các cặp sẽ là (0,0), (0,1), (1,0). Tất cả thỏa mãn bất đẳng thức x² + y² < 2.

Phương pháp sử dụng trong chương trình dưới đây

• Số nguyên N lưu số nguyên dương.
• Hàm countPairs(int n) nhận n làm đầu vào và trả về số cặp số nguyên không âm phân biệt thỏa mãn bất đẳng thức: x² + y² < n.
• Biến count lưu số cặp như vậy, khởi tạo 0.
• Bắt đầu từ i=0 đến i² < n và vòng lặp khác j=0 đến j² < n.
• Nếu i² + j² < n thì tăng count.
• Trả về count cuối cùng làm kết quả.

Ví dụ mã nguồn

#include <iostream> 
using namespace std; 

int countPairs(int n) { 
    int count = 0; 
    for (int i = 0; i * i < n; i++) 
        for (int j = 0; j * j < n; j++) // x*x + y*y < n
            if (i * i + j * j < n) 
                count++; 
    return count; 
} 

int main() { 
    int N = 4; 
    cout << "Số cặp số nguyên không âm phân biệt: " 
         << countPairs(N); 
    return 0; 
}

Kết quả

Số cặp số nguyên không âm phân biệt: 4