Kiểm tra khả năng chia tập N số tự nhiên đầu tiên thành hai tập có hiệu tổng bằng D trong C++

Trong bài toán này, chúng ta được cho hai số nguyên N và D. Nhiệm vụ là kiểm tra xem có thể chia tập các N số tự nhiên đầu tiên thành hai tập sao cho hiệu của tổng hai tập bằng D hay không.

Hãy xem ví dụ sau để hiểu rõ bài toán:

Đầu vào – N=5, D=3

Đầu ra – Có

Giải thích –

Từ các số 1, 2, 3, 4, 5. Ta có thể tạo hai tập: tập1 = {1, 2, 3} và tập2 = {4, 5}, hiệu tổng = 3. {4+5} - {1+2+3} = 9 - 6 = 3

Để giải bài toán này, ta sử dụng một số tính toán toán học.

Ta biết tổng của tất cả các số bằng tổng các phần tử của hai tập:

Công thức tổng N số tự nhiên đầu tiên:

sum(s1) + sum(s2) = (n*(n+1))/2. Theo đề bài, sum(s1) - sum(s2) = D

Cộng hai phương trình ta được:

2*sum(s1) = ((n*(n+1))/2) + D

Nếu điều kiện này đúng (vế phải là số chẵn) thì mới có nghiệm.

Ví dụ minh họa

Chương trình triển khai giải pháp:

#include <iostream> using namespace std; bool isSetPossible(int N, int D) {    int set = (N * (N + 1)) / 2 + D;    return (set % 2 == 0); } int main() {    int N = 10;    int D = 7;    cout<<"Tạo hai tập từ "<<N<<" số tự nhiên đầu tiên với hiệu "<<D<<" là ";    isSetPossible(N, D)?cout<<"khả thi":cout<<"không khả thi";    return 0; }

Kết quả

Tạo hai tập từ 10 số tự nhiên đầu tiên với hiệu 7 là khả thi