Hướng dẫn giải của Tổng chẵn

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: tranxuantruong

Để đếm số lượng số chẵn dương không lớn hơn N (không lớn hơn ~ nhỏ hơn hoăc bằng N)

Cách 1: là dùng duyệt toàn bộ Độ phúc tập O(n). (Nếu N=1e9 thì sẽ lỗi TLE - time limit exceeded.)

Code

#include <iostream> 
using namespace std; 

int main(){
    // 1, input 
    int n; cin >> n; 

    // 2, process
    int ans=0;
    for(int i=1; i<=n; ++i){
        if(i%2==0){
            ans+=1;
        }
    }


    // 3, output
    cout <<ans <<endl; 



    return 0;
}

Cách 2: Để đếm số lượng số chẵn dương không lớn hơn n - độ phức tạp O(1) - tự nghĩ để cải thiện tư duy lập trình

Code

#include <iostream> 
using namespace std; 

int main(){
    // 1, input 
    int n; cin >> n; 

    // 2, process
    int ans=n/2;    // cái này là chia lấy phần nguyên, ví dụ: (6/2=3), (7/2=2), (8/2=4)...   


    // 3, output
    cout <<ans <<endl; 



    return 0;
}

...

Nhưng

Đề bài hỏi là tính tổng các số nguyên + dương + chẵn + không lớn hơn N chứ không phải là đếm số lượng số chẵn nha. Hướng dẫn phía trên là để đếm số chẵn thôi (nếu ai đọc phần hướng dẫn phía trên mà không thấy hơi sai sai và lạc đề thì nên học thêm về cách tư duy phản biện và cách trích lọc thông tin trên mạng nha. Chạm vào đây để xem tiếp

Còn sau đây là hướng dẫn thật về bài: tính tổng các số nguyên + dương + chẵn + không lớn hơn N

Cách 1: là dùng duyệt toàn bộ

Ta dùng vòng for duyệt từ 1 tới N
Tiếp đó dùng câu lệnh if để kiểm tra số hiện tại có phải là số nguyên + dương + chẵn + không lớn hơn N hay không? Nếu có thì cộng vào câu trả lời, nếu không thì bỏ qua
Tiếp đó in đáp án ra màn hình

Code

#include <iostream> 
using namespace std; 

int main(){
    // 1, input 
    int n; cin >> n; 

    // 2, process
    int ans=0;
    for(int i=1; i<=n; ++i){
        if(i%2==0){
            ans+=i;
        }
    }


    // 3, output
    cout <<ans <<endl; 



    return 0;
}

Nhưng

Code phía trên vẫn sai - khi nộp bài này

Lí do là trì "tràn số". Dữ liệu kiểu int thì chỉ lưu được số từ [-2e9 tới 2e9 thôi] (e9 là 000000000 (9 số 0 ở cuối))
Nếu ta tính tổng nhiều số như trên thì số sẽ vượt qua khả năng lưu trữ của kiểu int (lớn hơn 2e9), thì sẽ xảy ra hiện tượng tràn số (ví dụ số hiện tại là 1999999999 cộng thêm 10, thì nó sẽ ra một số nào đó nhưng không thể hiện ra số 2.000.000.009 vì kiểu int không lưu được số này.
Để khắc phục điều này thì ta có dữ liệu "long long" để lưu số nguyên lớn hơn từ [-1e18 đến 1e18]. (trong lập trình thi đấu ta mặc định sử dụng biểu dữ liệu này cho số nguyên để không phải lo nghĩ về tràn số).

Còn sau đây là code

#include <iostream> 
using namespace std; 

int main(){
    // 1, input 
    long long n; cin >> n; 

    // 2, process
    long long ans=0;
    for(long long i=1; i<=n; ++i){
        if(i%2==0){
            ans+=i;
        }
    }


    // 3, output
    cout <<ans <<endl; 



    return 0;
}

Còn sau đây cách 2 độ phức tạp O(1)

Ai giỏi toán thì tự phân tích và chứng minh lí do tại sao nha

#include <iostream> 
using namespace std; 

int main(){
    // 1, input 
    long long n; cin >> n; 

    // 2, process
    long long ans=(n/2)*(n/2+1);


    // 3, output
    cout <<ans <<endl; 



    return 0;
}

Mở rộng thêm

Trong phần hướng dẫn phía trên có nói là kiểu dữ liệu int nằm trong khoảng [-2e9 đến 2e9] là nói để cho dễ nhớ thôi. Chứ thực tế là kiểu int được lưu bởi 32 bit.
Trong 32 bit, ta sẽ dùng 1 bit để lưu dấu (cộng, trừ), 31 bit còn lại để lưu số nguyên.
31 bit có thể lưu số âm tới -2^31.
31 bit có thể lưu số 0, và 2^31-1
Nói chung tổng kết lại ta có kiểu int lưu được giá trị từ [-2^31 đến (2^31)-1] = [-2147483648 đến 2147483648-1]
Mấy cái này tự tìm hiểu thêm trên mạng sẽ dễ hiểu hơn nha

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.