Khóa học CTDL và GT

Bài 1.5. Bài tập tổng hợp về độ phức tạp và vòng lặp

Chào mừng bạn quay trở lại với series blog về Cấu trúc dữ liệu và Giải thuật của chúng ta! Sau khi đã tìm hiểu về độ phức tạp thuật toán (Algorithmic Complexity) và ký hiệu Big O ở các bài trước, đã đến lúc chúng ta xắn tay áo lên và áp dụng kiến thức này vào việc phân tích các đoạn code thực tế.

Phần lớn thời gian chạy của một chương trình thường nằm ở các cấu trúc lặp đi lặp lại như vòng lặp (for, while, do-while). Vì vậy, việc hiểu rõ cách các vòng lặp ảnh hưởng đến độ phức tạp là cực kỳ quan trọng. Bài viết này sẽ tập trung vào việc phân tích độ phức tạp của các đoạn code chứa vòng lặp, thông qua nhiều ví dụ C++ chi tiết.

Hãy cùng bắt đầu nhé!

Nhắc lại nhanh: Tại sao phải quan tâm đến độ phức tạp?

Nhớ lại từ các bài trước, độ phức tạp thuật toán cho chúng ta biết hiệu suất của một thuật toán thay đổi như thế nào khi kích thước dữ liệu đầu vào (n) tăng lên. Chúng ta thường quan tâm đến:

• Độ phức tạp thời gian (Time Complexity): Số bước tính toán mà thuật toán cần thực hiện.
• Độ phức tạp không gian (Space Complexity): Lượng bộ nhớ mà thuật toán cần sử dụng.

Và Big O Notation (O(...)) giúp chúng ta mô tả tốc độ tăng trưởng của tài nguyên (thời gian hoặc không gian) cần thiết ở trường hợp xấu nhất (worst-case), bỏ qua các hằng số và các số hạng bậc thấp.

Trong bài này, chúng ta sẽ tập trung chủ yếu vào Độ phức tạp thời gian vì nó bị ảnh hưởng rõ rệt bởi các vòng lặp.

Phân tích độ phức tạp của các cấu trúc vòng lặp cơ bản

Nguyên tắc chung khi phân tích vòng lặp là: Độ phức tạp của một vòng lặp xấp xỉ bằng (Số lần lặp) nhân với (Độ phức tạp của công việc bên trong mỗi lần lặp).

Các công việc bên trong vòng lặp mà chỉ mất một lượng thời gian cố định (không phụ thuộc vào n) được coi là có độ phức tạp O(1) (hằng số).

1. Vòng lặp đơn - Độ phức tạp O(n)

Đây là trường hợp phổ biến nhất. Một vòng lặp for hoặc while chạy từ 1 đến n (hoặc từ 0 đến n-1, hoặc bất kỳ khoảng cố định nào tỉ lệ với n).

Ví dụ 1.1:

#include <iostream>

void example1(int n) {
    // Vòng lặp chạy n lần
    for (int i = 0; i < n; ++i) {
        // Công việc bên trong vòng lặp: in ra một số (O(1))
        std::cout << i << std::endl;
    }
}

int main() {
    example1(10); // Gọi với n = 10
    example1(100); // Gọi với n = 100
    return 0;
}

Giải thích:

• Biến đầu vào là n.
• Vòng lặp for bắt đầu từ i = 0 và kết thúc khi i đạt n. Tổng cộng, vòng lặp sẽ thực hiện n lần lặp.
• Bên trong vòng lặp, câu lệnh std::cout << i << std::endl; là một thao tác đơn giản, mất một lượng thời gian cố định, không phụ thuộc vào n. Do đó, nó có độ phức tạp O(1).
• Tổng độ phức tạp: (Số lần lặp) (Độ phức tạp bên trong) = `n O(1) = O(n)`.

Đây là độ phức tạp tuyến tính (linear). Thời gian chạy tăng tỉ lệ thuận với kích thước đầu vào.

2. Vòng lặp đơn với bước nhảy không phải 1 - Vẫn là O(n)

Nếu vòng lặp tăng (hoặc giảm) biến đếm một lượng hằng số khác 1, độ phức tạp vẫn là O(n).

Ví dụ 1.2:

#include <iostream>

void example2(int n) {
    // Vòng lặp chạy từ 0 đến n, nhưng bước nhảy là 2
    for (int i = 0; i < n; i += 2) {
        // Công việc bên trong là O(1)
        std::cout << i << std::endl;
    }
}

int main() {
    example2(10); // Gọi với n = 10
    example2(100); // Gọi với n = 100
    return 0;
}

Giải thích:

• Vòng lặp bắt đầu từ i = 0 và tăng i thêm 2 sau mỗi lần lặp.
• Vòng lặp sẽ thực hiện khoảng n / 2 lần lặp.
• Công việc bên trong vẫn là O(1).
• Tổng độ phức tạp: (n / 2) * O(1).
• Trong ký hiệu Big O, chúng ta bỏ qua hằng số (như / 2). Do đó, độ phức tạp vẫn là O(n).

Tương tự, vòng lặp chạy từ n về 0 với bước nhảy 1 (for (int i = n; i > 0; --i)) cũng có độ phức tạp O(n).

3. Vòng lặp lồng nhau - Độ phức tạp O(n^2)

Khi một vòng lặp nằm bên trong một vòng lặp khác, độ phức tạp sẽ là tích của số lần lặp của các vòng lặp đó. Trường hợp kinh điển là hai vòng lặp lồng nhau, mỗi vòng lặp chạy n lần.

Ví dụ 1.3:

#include <iostream>

void example3(int n) {
    // Vòng lặp ngoài chạy n lần
    for (int i = 0; i < n; ++i) {
        // Vòng lặp trong chạy n lần cho MỖI lần của vòng lặp ngoài
        for (int j = 0; j < n; ++j) {
            // Công việc bên trong là O(1)
            std::cout << "(" << i << "," << j << ") ";
        }
        std::cout << std::endl; // O(1)
    }
}

int main() {
    example3(3); // Gọi với n = 3
    example3(10); // Gọi với n = 10
    return 0;
}

Giải thích:

• Vòng lặp ngoài chạy n lần (với i từ 0 đến n-1).
• Đối với mỗi giá trị của i trong vòng lặp ngoài, vòng lặp trong chạy n lần (với j từ 0 đến n-1).
• Tổng số lần công việc bên trong (std::cout << "(" << i << "," << j << ") ";) được thực hiện là n * n = n^2.
• Công việc bên trong vòng lặp lồng nhau là O(1).
• Tổng độ phức tạp: n * n * O(1) = O(n^2).

Đây là độ phức tạp bậc hai (quadratic). Thời gian chạy tăng rất nhanh khi n tăng.

4. Vòng lặp lồng nhau với giới hạn phụ thuộc - Vẫn thường là O(n^2)

Đôi khi, giới hạn của vòng lặp trong lại phụ thuộc vào biến đếm của vòng lặp ngoài.

Ví dụ 1.4:

#include <iostream>

void example4(int n) {
    // Vòng lặp ngoài chạy n lần
    for (int i = 0; i < n; ++i) {
        // Vòng lặp trong chạy từ 0 đến i (hoặc i+1 lần)
        for (int j = 0; j <= i; ++j) {
             // Công việc bên trong là O(1)
            std::cout << "(" << i << "," << j << ") ";
        }
        std::cout << std::endl; // O(1)
    }
}

int main() {
    example4(3); // Gọi với n = 3
    example4(10); // Gọi với n = 10
    return 0;
}

Giải thích:

• Vòng lặp ngoài chạy n lần.
• Vòng lặp trong chạy:
  • Khi i = 0, j chạy 1 lần.
  • Khi i = 1, j chạy 2 lần.
  • Khi i = 2, j chạy 3 lần.
  • ...
  • Khi i = n-1, j chạy n lần.
• Tổng số lần công việc bên trong được thực hiện là 1 + 2 + 3 + ... + n.
• Tổng này là một cấp số cộng, có công thức là n * (n + 1) / 2.
• n * (n + 1) / 2 = (n^2 + n) / 2 = 0.5 * n^2 + 0.5 * n.
• Trong ký hiệu Big O, chúng ta bỏ qua hằng số (0.5) và các số hạng bậc thấp (0.5 * n). Số hạng bậc cao nhất là n^2.
• Do đó, độ phức tạp là O(n^2).

Mặc dù số lần lặp có vẻ ít hơn O(n^2) thuần túy (chỉ bằng một nửa), tốc độ tăng trưởng của nó vẫn là bậc hai.

5. Vòng lặp với bước nhảy nhân/chia - Độ phức tạp O(log n)

Khi biến đếm của vòng lặp không tăng/giảm một lượng cố định, mà được nhân hoặc chia cho một hằng số lớn hơn 1 sau mỗi lần lặp, chúng ta thường gặp độ phức tạp logarit (logarithmic).

Ví dụ 1.5:

#include <iostream>

void example5(int n) {
    // Bắt đầu với i = 1, nhân i với 2 sau mỗi lần lặp cho đến khi i >= n
    for (int i = 1; i < n; i *= 2) {
        // Công việc bên trong là O(1)
        std::cout << i << std::endl;
    }
}

int main() {
    example5(10); // 1, 2, 4, 8 -> 4 lần lặp
    example5(100); // 1, 2, 4, 8, 16, 32, 64 -> 7 lần lặp
    example5(1000); // 1, 2, 4, ..., 512 -> 10 lần lặp
    return 0;
}

Giải thích:

• Biến i bắt đầu từ 1 và được nhân đôi sau mỗi lần lặp.
• Chúng ta muốn biết cần bao nhiêu lần lặp (k) để i đạt đến hoặc vượt quá n. Tức là, tìm k sao cho 1 * 2^k >= n.
• Giải phương trình này theo k: 2^k >= n => log2(2^k) >= log2(n) => k >= log2(n).
• Số lần lặp xấp xỉ log2(n).
• Công việc bên trong là O(1).
• Tổng độ phức tạp: log2(n) * O(1) = O(log n).

Cơ số của logarit không quan trọng trong ký hiệu Big O (vì log_b(n) = log_a(n) / log_a(b), và 1 / log_a(b) là một hằng số). Do đó, O(log2(n)) hay O(log10(n)) đều được viết là O(log n).

Vòng lặp chia cho 2 cũng cho độ phức tạp O(log n).

Ví dụ 1.6:

#include <iostream>

void example6(int n) {
    // Bắt đầu với i = n, chia i cho 2 sau mỗi lần lặp cho đến khi i <= 1
    for (int i = n; i > 1; i /= 2) {
        // Công việc bên trong là O(1)
        std::cout << i << std::endl;
    }
}

int main() {
    example6(10); // 10, 5, 2 -> 3 lần lặp
    example6(100); // 100, 50, 25, 12, 6, 3 -> 6 lần lặp
    example6(1000); // 1000, 500, ..., 3 -> 9 lần lặp
    return 0;
}

Giải thích:

• Biến i bắt đầu từ n và bị chia đôi sau mỗi lần lặp.
• Chúng ta cần tìm k sao cho n / 2^k <= 1.
• Giải: n <= 2^k => log2(n) <= k.
• Số lần lặp xấp xỉ log2(n).
• Độ phức tạp là O(log n).

Độ phức tạp logarit là rất hiệu quả, đặc biệt với n lớn, vì thời gian chạy tăng rất chậm so với kích thước đầu vào.

6. Vòng lặp chạy số lần cố định - Độ phức tạp O(1)

Nếu số lần lặp của một vòng lặp không phụ thuộc vào kích thước đầu vào n mà là một hằng số (ví dụ: luôn chạy 10 lần, luôn chạy 5 lần), thì độ phức tạp của vòng lặp đó là O(1).

Ví dụ 1.7:

#include <iostream>

void example7(int n) { // n là đầu vào, nhưng không ảnh hưởng đến số lần lặp
    // Vòng lặp này luôn chạy 5 lần, bất kể giá trị của n
    for (int i = 0; i < 5; ++i) {
        // Công việc bên trong là O(1)
        std::cout << "Lap thu: " << i << std::endl;
    }
    // Các phép toán O(1) khác
    int x = n * 2;
    std::cout << "Gia tri cua x: " << x << std::endl;
}

int main() {
    example7(10);
    example7(1000);
    return 0;
}

Giải thích:

• Vòng lặp for chạy từ i = 0 đến i = 4, tức là luôn thực hiện 5 lần lặp.
• Số lần lặp này là một hằng số, không thay đổi khi n thay đổi.
• Công việc bên trong vòng lặp là O(1).
• Tổng độ phức tạp của vòng lặp: 5 * O(1) = O(5).
• Trong ký hiệu Big O, chúng ta bỏ qua hằng số. Do đó, độ phức tạp của vòng lặp này là O(1).
• Các câu lệnh khác trong hàm (int x = n * 2;, std::cout << ...;) cũng là O(1).
• Tổng độ phức tạp của hàm là O(1) + O(1) + O(1) = O(1).

Độ phức tạp hằng số (constant) là hiệu quả nhất, vì thời gian chạy không thay đổi theo kích thước đầu vào.

Phân tích độ phức tạp của các cấu trúc kết hợp

Thường thì code không chỉ có một vòng lặp đơn lẻ mà là sự kết hợp của nhiều cấu trúc khác nhau.

7. Các vòng lặp chạy nối tiếp nhau

Nếu có hai hoặc nhiều vòng lặp chạy nối tiếp nhau, độ phức tạp tổng thể sẽ là độ phức tạp của vòng lặp chiếm ưu thế nhất (có bậc cao nhất).

Ví dụ 1.8:

#include <iostream>

void example8(int n) {
    // Vòng lặp 1: O(n)
    for (int i = 0; i < n; ++i) {
        std::cout << "Vong lap 1: " << i << std::endl; // O(1)
    }

    // Vòng lặp 2: O(n^2)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << "Vong lap 2: (" << i << "," << j << ")" << std::endl; // O(1)
        }
    }

    // Vòng lặp 3: O(log n)
    for (int i = 1; i < n; i *= 2) {
        std::cout << "Vong lap 3: " << i << std::endl; // O(1)
    }
}

int main() {
    example8(10);
    return 0;
}

Giải thích:

• Vòng lặp 1 có độ phức tạp O(n).
• Vòng lặp 2 có độ phức tạp O(n^2).
• Vòng lặp 3 có độ phức tạp O(log n).
• Khi các cấu trúc chạy nối tiếp, tổng độ phức tạp là tổng của độ phức tạp của từng phần: O(n) + O(n^2) + O(log n).
• Trong ký hiệu Big O, chúng ta chỉ giữ lại số hạng có bậc cao nhất. Ở đây, n^2 tăng nhanh hơn n và log n rất nhiều.
• Do đó, độ phức tạp tổng thể là O(n^2).

Nguyên tắc là: O(A) + O(B) = O(max(A, B)) trong thế giới Big O.

8. Cấu trúc điều kiện (if/else)

Các câu lệnh điều kiện (if, else if, else) bản thân chúng có độ phức tạp O(1). Tuy nhiên, chúng ảnh hưởng đến những đoạn code nào được thực thi. Khi phân tích độ phức tạp của code có điều kiện, chúng ta thường xem xét trường hợp xấu nhất (worst-case).

Ví dụ 1.9:

#include <iostream>

void example9(int n) {
    if (n > 100) {
        // Khối lệnh 1: Có một vòng lặp O(n)
        for (int i = 0; i < n; ++i) {
            std::cout << "Trong IF: " << i << std::endl; // O(1)
        }
    } else {
        // Khối lệnh 2: Có một vòng lặp O(n^2)
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                 std::cout << "Trong ELSE: (" << i << "," << j << ")" << std::endl; // O(1)
            }
        }
    }
}

int main() {
    example9(50); // n = 50, thực thi khối ELSE -> O(50^2)
    example9(200); // n = 200, thực thi khối IF -> O(200)
    return 0;
}

Giải thích:

• Câu lệnh if (n > 100) là O(1).
• Nếu điều kiện n > 100 đúng, code trong khối if sẽ chạy. Khối này chứa một vòng lặp O(n).
• Nếu điều kiện n > 100 sai (tức là n <= 100), code trong khối else sẽ chạy. Khối này chứa hai vòng lặp lồng nhau O(n^2).
• Để tìm độ phức tạp trường hợp xấu nhất của hàm example9, chúng ta xem xét nhánh nào tốn thời gian nhiều nhất khi n đủ lớn.
• So sánh O(n) và O(n^2). Rõ ràng, O(n^2) tăng trưởng nhanh hơn và là trường hợp xấu nhất.
• Do đó, độ phức tạp của hàm example9 là O(n^2).

9. Vòng lặp với công việc bên trong phức tạp hơn O(1)

Đôi khi, công việc bên trong một vòng lặp không phải là O(1) mà lại chứa các cấu trúc phức tạp hơn, như một vòng lặp khác, hoặc một lời gọi hàm có độ phức tạp nhất định.

Ví dụ 1.10:

#include <iostream>

// Giả sử hàm này có độ phức tạp O(log k), với k là đầu vào
void some_log_function(int k) {
    for (int i = 1; i < k; i *= 2) {
        // Công việc O(1)
        // std::cout << "  Log func step: " << i << std::endl;
    }
}

void example10(int n) {
    // Vòng lặp ngoài chạy n lần
    for (int i = 0; i < n; ++i) {
        // Công việc bên trong: Gọi some_log_function với đầu vào n
        some_log_function(n);
    }
}

int main() {
    example10(10);
    example10(100);
    return 0;
}

Giải thích:

• Hàm some_log_function(k) có độ phức tạp O(log k) (như đã phân tích ở Ví dụ 1.5, với biến k thay cho n).
• Trong hàm example10, vòng lặp for (int i = 0; i < n; ++i) chạy n lần.
• Bên trong mỗi lần lặp của vòng lặp ngoài, chúng ta gọi hàm some_log_function(n). Lời gọi hàm này có độ phức tạp O(log n) (vì đầu vào là n).
• Tổng độ phức tạp: (Số lần lặp vòng ngoài) * (Độ phức tạp bên trong vòng ngoài).
• Tổng độ phức tạp = n * O(log n) = O(n log n).

Đây là độ phức tạp n log n. Nó phổ biến trong nhiều thuật toán sắp xếp hiệu quả như Merge Sort hay Quick Sort (dù chúng sử dụng đệ quy, nhưng ý tưởng về việc xử lý n phần tử với mỗi phần tử tốn chi phí logarit thì tương đồng).

Tóm tắt các quy tắc phân tích vòng lặp:

1. Vòng lặp đơn: Nếu vòng lặp chạy k lần và công việc bên trong là O(F), độ phức tạp là O(k * F). Nếu k tỉ lệ thuận với n, nó là O(n * F). Nếu F là O(1), nó là O(n).
2. Vòng lặp với bước nhảy hằng số: i += c (với c là hằng số > 0) vẫn cho ra O(n) nếu chạy đến n.
3. Vòng lặp với bước nhảy nhân/chia: i *= c hoặc i /= c (với c là hằng số > 1) thường cho ra O(log n) nếu chạy đến/từ n.
4. Vòng lặp lồng nhau: Độ phức tạp là tích của độ phức tạp của các vòng lặp. Vòng lặp n lần bên trong vòng lặp n lần cho ra O(n * n) = O(n^2). Vòng lặp n lần bên trong vòng lặp log n lần cho ra O(n * log n).
5. Vòng lặp chạy nối tiếp: Cộng độ phức tạp của từng vòng lặp và lấy số hạng bậc cao nhất. O(A) + O(B) = O(max(A, B)).
6. Công việc bên trong vòng lặp: Phân tích độ phức tạp của toàn bộ khối code bên trong vòng lặp trước khi nhân với số lần lặp của vòng lặp đó.
7. Cấu trúc điều kiện: Phân tích từng nhánh và lấy độ phức tạp của nhánh tốn thời gian nhất (trường hợp xấu nhất).

Bài tập thực hành (Hãy thử tự phân tích trước khi nhìn vào đáp án!)

Hãy phân tích độ phức tạp thời gian cho các đoạn code C++ sau, với n là kích thước đầu vào:

Bài tập 1:

void practice1(int n) {
    for (int i = 0; i < 10; ++i) {
        std::cout << i << std::endl;
    }
    for (int j = 0; j < n; ++j) {
        std::cout << j << std::endl;
    }
}

Bài tập 2:

void practice2(int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            std::cout << "(" << i << "," << j << ")" << std::endl;
        }
    }
}

Bài tập 3:

void practice3(int n) {
    if (n % 2 == 0) {
        for (int i = 0; i < n * 2; ++i) {
            std::cout << "Chan: " << i << std::endl;
        }
    } else {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                std::cout << "Le: (" << i << "," << j << ")" << std::endl;
            }
        }
    }
}

Bài tập 4:

void practice4(int n) {
    for (int i = 0; i < n; ++i) {
        // Loop inside depends on i
        for (int j = 1; j < 100; j++) { // This inner loop runs a fixed number of times!
             std::cout << i * j << std::endl;
        }
    }
}

Bài tập 5:

void practice5(int n) {
    int count = 0;
    for (int i = n; i > 0; i /= 3) {
        for (int j = 0; j < n; ++j) {
            count++;
        }
    }
}

Đáp án và giải thích:

Bài tập 1:

• Vòng lặp đầu tiên chạy cố định 10 lần. Độ phức tạp O(1).
• Vòng lặp thứ hai chạy n lần. Độ phức tạp O(n).
• Hai vòng lặp chạy nối tiếp. Tổng độ phức tạp = O(1) + O(n).
• Số hạng bậc cao nhất là O(n).
• Đáp án: O(n)

Bài tập 2:

• Vòng lặp ngoài chạy n lần (từ i = 0 đến n-1).
• Vòng lặp trong chạy từ j = i đến n-1.
  • Khi i = 0, j chạy n lần.
  • Khi i = 1, j chạy n-1 lần.
  • Khi i = 2, j chạy n-2 lần.
  • ...
  • Khi i = n-1, j chạy 1 lần.
• Tổng số lần lặp của vòng trong là n + (n-1) + (n-2) + ... + 1.
• Tổng này bằng n * (n + 1) / 2.
• n * (n + 1) / 2 = 0.5 * n^2 + 0.5 * n.
• Số hạng bậc cao nhất là n^2.
• Đáp án: O(n^2)

Bài tập 3:

• Cấu trúc điều kiện if/else bản thân là O(1).
• Nhánh if: Chứa một vòng lặp chạy n * 2 lần. Độ phức tạp O(n * 2) = O(n).
• Nhánh else: Chứa hai vòng lặp lồng nhau, mỗi vòng chạy n lần. Độ phức tạp O(n * n) = O(n^2).
• Trường hợp xấu nhất là nhánh else chạy khi n đủ lớn (hoặc khi n <= 100 theo điều kiện cụ thể này, nhưng khi phân tích Big O, chúng ta quan tâm hành vi khi n tăng trưởng). So sánh O(n) và O(n^2), O(n^2) là bậc cao hơn.
• Đáp án: O(n^2)

Bài tập 4:

• Vòng lặp ngoài chạy n lần (từ i = 0 đến n-1).
• Vòng lặp trong chạy từ j = 1 đến 99. Vòng lặp này luôn chạy 99 lần, bất kể giá trị của n hay i. Độ phức tạp của vòng lặp trong là O(1) (vì 99 là hằng số).
• Công việc bên trong vòng lặp ngoài là vòng lặp trong O(1).
• Tổng độ phức tạp = (Số lần lặp vòng ngoài) (Độ phức tạp bên trong) = `n O(1) = O(n)`.
• Đáp án: O(n)

Bài tập 5:

• Vòng lặp ngoài: Biến i bắt đầu từ n và chia cho 3 sau mỗi lần lặp (i /= 3). Vòng lặp này chạy đến khi i không còn lớn hơn 0. Số lần lặp là khoảng log3(n). Độ phức tạp O(log n).
• Vòng lặp trong: Biến j chạy từ 0 đến n-1. Vòng lặp này chạy n lần. Độ phức tạp O(n).
• Vòng lặp trong chạy bên trong vòng lặp ngoài.
• Tổng độ phức tạp = (Số lần lặp vòng ngoài) (Độ phức tạp vòng trong) = `O(log n) O(n) = O(n log n)`.
• Đáp án: O(n log n)

Bài tập ví dụ:

Tìm tính chẵn lẻ

Trong một buổi học phép thuật, FullHouse Dev gặp Alice - một cô bé đang tìm hiểu về số chẵn và số lẻ. Để giúp Alice hiểu rõ hơn về khái niệm này, FullHouse Dev đã đưa ra một bài toán thú vị về phép XOR và tính chất chẵn lẻ của kết quả.

Bài toán

Alice có hai số nguyên \(L\) và \(R\). Gọi \(X\) là số được tạo ra bằng cách thực hiện phép XOR tất cả các số trong đoạn từ \(L\) đến \(R\) (bao gồm cả \(L\) và \(R\)). Nhiệm vụ của bạn là giúp Alice xác định \(X\) là số chẵn hay số lẻ.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(L\) và \(R\)

OUTPUT FORMAT:

• In ra "even" nếu số \(X\) là số chẵn, ngược lại in ra "odd" (không có dấu ngoặc kép)

Ràng buộc:

• \(1 \leq L \leq R \leq 10^{12}\)

Ví dụ

INPUT

3 5

OUTPUT

even

Giải thích

• Với \(L = 3\) và \(R = 5\)
• \(X = (3 \oplus 4 \oplus 5)\) trong đó \(\oplus\) là phép toán XOR
• \(X = 2\)
• Vì \(X\) là số chẵn nên kết quả là "even" Tuyệt vời! Bài toán này kiểm tra khả năng suy luận về tính chất của phép XOR và các mẫu số học. Dưới đây là hướng dẫn giải ngắn gọn bằng C++:

1. Tính chất quan trọng: Parity (tính chẵn lẻ) của một số chỉ phụ thuộc vào bit cuối cùng (least significant bit - LSB) của nó. Phép XOR của nhiều số A1 ^ A2 ^ ... ^ An sẽ có LSB bằng (LSB của A1) ^ (LSB của A2) ^ ... ^ (LSB của An).

2. Bài toán con: Do đó, bài toán gốc tương đương với việc tìm parity của (L%2) ^ ((L+1)%2) ^ ... ^ (R%2).

3. Mẫu Parity: Dãy parity của các số nguyên liên tiếp là 0, 1, 0, 1, ... Điều này lặp lại sau mỗi 2 số.

4. XOR tổng Parity từ 1 đến N: Hãy quan sát kết quả của (1%2) ^ (2%2) ^ ... ^ (N%2) dựa trên N:

   • N=1: 1 -> 1
   • N=2: 1 ^ 0 -> 1
   • N=3: 1 ^ 0 ^ 1 -> 0
   • N=4: 1 ^ 0 ^ 1 ^ 0 -> 0
   • N=5: 1 ^ 0 ^ 1 ^ 0 ^ 1 -> 1
   • N=6: 1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 0 -> 1
   • N=7: 1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 0 ^ 1 -> 0
   • N=8: 1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 0 ^ 1 ^ 0 -> 0

   Bạn có thể thấy kết quả chỉ phụ thuộc vào N % 4. Xây dựng một hàm trả về kết quả này dựa trên N % 4.

5. XOR tổng Parity từ L đến R: Sử dụng tính chất XOR: XOR[L..R] = XOR[1..R] ^ XOR[1..L-1]. Áp dụng kết quả từ bước 4 để tính XOR tổng parity từ 1 đến R và từ 1 đến L-1.

6. Kết quả cuối cùng: XOR hai kết quả từ bước 5. Nếu kết quả là 0, tổng XOR ban đầu là chẵn ("even"). Nếu kết quả là 1, tổng XOR ban đầu là lẻ ("odd").

7. Lưu ý kiểu dữ liệu: Vì L và R có thể rất lớn (đến 10^12), bạn cần sử dụng kiểu dữ liệu 64-bit (ví dụ: long long trong C++) để đọc và xử lý L, R và các phép tính với chúng.

Làm thêm nhiều bài tập miễn phí tại đây