Bài 9.4: Ước chung lớn nhất và bội chung nhỏ nhất trong C++

Chào mừng trở lại với series blog C++ của FullhouseDev! Trong bài học hôm nay, chúng ta sẽ cùng nhau tìm hiểu về hai khái niệm quen thuộc trong toán học nhưng cực kỳ hữu ích trong lập trình: Ước chung lớn nhất (ƯCLN) hay Greatest Common Divisor (GCD) và Bội chung nhỏ nhất (BCNN) hay Least Common Multiple (LCM).

Tại sao chúng ta cần quan tâm đến UCLN và BCNN trong lập trình? Chúng xuất hiện ở nhiều nơi hơn bạn nghĩ đấy! Từ việc tối giản phân số, giải các bài toán số học, cho đến các vấn đề liên quan đến lịch trình, đồng bộ hóa hay thậm chí trong các thuật toán mã hóa. C++ cung cấp cho chúng ta nhiều cách để tính toán hai giá trị này, từ việc tự cài đặt các thuật toán cơ bản đến sử dụng các hàm có sẵn cực kỳ tiện lợi.

Hãy cùng đi sâu vào chi tiết nhé!

1. Ước chung lớn nhất (ƯCLN / GCD)

Ước chung lớn nhất của hai hay nhiều số nguyên dương là số nguyên dương lớn nhất mà là ước của tất cả các số đó. Ký hiệu: UCLN(a, b) hoặc GCD(a, b).

Ví dụ:

  • Ước của 12 là: 1, 2, 3, 4, 6, 12
  • Ước của 18 là: 1, 2, 3, 6, 9, 18
  • Các ước chung của 12 và 18 là: 1, 2, 3, 6
  • Ước chung lớn nhất của 12 và 18 là: 6. Vậy UCLN(12, 18) = 6.
Các phương pháp tìm UCLN
Phương pháp 1: Duyệt từ số nhỏ nhất trở xuống (Naive Approach)

Đây là cách tiếp cận đơn giản và dễ hiểu nhất. Ta biết rằng UCLN của hai số a và b không thể lớn hơn số nhỏ hơn trong hai số đó. Vì vậy, ta có thể bắt đầu duyệt từ min(a, b) xuống 1. Số đầu tiên mà chia hết cho cả a và b chính là UCLN.

Hãy xem code minh họa:

#include <iostream>
#include <algorithm> // Cần cho min

// Hàm tìm UCLN bằng cách duyệt
int find_gcd_naive(int a, int b) {
    // Đảm bảo a và b là số dương
    a = abs(a);
    b = abs(b);

    if (a == 0) return b; // UCLN(0, b) = |b|
    if (b == 0) return a; // UCLN(a, 0) = |a|

    int min_val = min(a, b);
    for (int i = min_val; i >= 1; --i) {
        if (a % i == 0 && b % i == 0) {
            return i; // Tìm thấy ước chung lớn nhất đầu tiên
        }
    }
    return 1; // Trường hợp duy nhất còn lại là UCLN(a,b)=1 (nếu a, b > 0 và không có ước chung nào khác)
}

int main() {
    int num1 = 48, num2 = 18;
    cout << "UCLN cua " << num1 << " va " << num2 << " la: " << find_gcd_naive(num1, num2) << endl;

    num1 = 7; num2 = 13;
    cout << "UCLN cua " << num1 << " va " << num2 << " la: " << find_gcd_naive(num1, num2) << endl;

    return 0;
}

Giải thích:

  • Hàm find_gcd_naive nhận hai số nguyên a và b.
  • Chúng ta sử dụng abs() để làm việc với giá trị tuyệt đối, đảm bảo xử lý cả số âm (mặc dù định nghĩa chuẩn thường là với số dương).
  • Kiểm tra trường hợp đặc biệt khi một trong hai số là 0. UCLN của một số và 0 là giá trị tuyệt đối của chính số đó.
  • Tìm giá trị nhỏ nhất giữa a và b bằng min.
  • Vòng lặp for bắt đầu từ min_val giảm dần về 1.
  • Điều kiện a % i == 0 && b % i == 0 kiểm tra xem i có phải là ước chung của cả a và b hay không.
  • Ngay khi tìm thấy số i thỏa mãn điều kiện này, đó chính là UCLN lớn nhất, và chúng ta trả về i.
  • Nếu vòng lặp kết thúc (chỉ xảy ra khi min_val ban đầu là 0, hoặc khi a và b là 0), hàm sẽ trả về 1 (trường hợp a=b=0 sẽ trả về 0 ở kiểm tra ban đầu, trường hợp a,b > 0 nhưng không tìm thấy ước chung nào khác ngoài 1).

Phương pháp này đơn giản nhưng không hiệu quả lắm với các số lớn vì nó có thể cần duyệt qua rất nhiều số.

Phương pháp 2: Thuật toán Euclid (Euclidean Algorithm)

Đây là thuật toán cổ điển và hiệu quả nhất để tìm UCLN. Nguyên lý của thuật toán dựa trên tính chất sau:

UCLN(a, b) = UCLN(b, a mod b) (với a > b, và a mod b là số dư khi chia a cho b)

Thuật toán lặp đi lặp lại việc thay thế cặp số (a, b) bằng cặp (b, a mod b) cho đến khi số thứ hai bằng 0. Khi đó, số thứ nhất chính là UCLN.

Ví dụ: Tìm UCLN(48, 18)

  1. UCLN(48, 18) = UCLN(18, 48 mod 18) = UCLN(18, 12)
  2. UCLN(18, 12) = UCLN(12, 18 mod 12) = UCLN(12, 6)
  3. UCLN(12, 6) = UCLN(6, 12 mod 6) = UCLN(6, 0)
  4. Số thứ hai bằng 0, vậy UCLN là số thứ nhất: 6.

Thuật toán Euclid có thể được cài đặt bằng đệ quy hoặc lặp.

Cài đặt đệ quy:

#include <iostream>
#include <numeric> // Cần cho gcd nếu bạn muốn so sánh hoặc sử dụng

// Hàm tìm UCLN bằng thuật toán Euclid (đệ quy)
int find_gcd_recursive(int a, int b) {
    // Đảm bảo a và b là số dương cho thuật toán cơ bản
    a = abs(a);
    b = abs(b);

    if (b == 0) {
        return a; // Trường hợp dừng: UCLN(a, 0) = |a|
    }
    // Bước đệ quy: UCLN(a, b) = UCLN(b, a % b)
    return find_gcd_recursive(b, a % b);
}

int main() {
    int num1 = 48, num2 = 18;
    cout << "UCLN (de quy) cua " << num1 << " va " << num2 << " la: " << find_gcd_recursive(num1, num2) << endl;

    num1 = 101, num2 = 103;
    cout << "UCLN (de quy) cua " << num1 << " va " << num2 << " la: " << find_gcd_recursive(num1, num2) << endl;

    return 0;
}

Giải thích:

  • Hàm đệ quy find_gcd_recursive cũng xử lý giá trị tuyệt đối và trường hợp b == 0.
  • Trường hợp cơ sở (base case) của đệ quy là khi b bằng 0, ta trả về a.
  • Trường hợp đệ quy (recursive step) là gọi lại hàm với cặp số mới (b, a % b). Quá trình này tiếp diễn cho đến khi đạt được trường hợp cơ sở.

Cài đặt lặp (phi đệ quy):

#include <iostream>
#include <numeric>

// Hàm tìm UCLN bằng thuật toán Euclid (lặp)
int find_gcd_iterative(int a, int b) {
    // Đảm bảo a và b là số dương
    a = abs(a);
    b = abs(b);

    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a; // Khi b = 0, a chính là UCLN
}

int main() {
    int num1 = 48, num2 = 18;
    cout << "UCLN (lap) cua " << num1 << " va " << num2 << " la: " << find_gcd_iterative(num1, num2) << endl;

    num1 = 25, num2 = 5;
    cout << "UCLN (lap) cua " << num1 << " va " << num2 << " la: " << find_gcd_iterative(num1, num2) << endl;

    return 0;
}

Giải thích:

  • Hàm find_gcd_iterative sử dụng vòng lặp while.
  • Vòng lặp tiếp tục chừng nào b còn khác 0.
  • Bên trong vòng lặp, ta lưu giá trị hiện tại của b vào biến tạm temp.
  • Cập nhật b thành số dư của a chia cho b (a % b).
  • Cập nhật a thành giá trị cũ của b (lưu trong temp).
  • Quá trình này tương đương với bước đệ quy nhưng không sử dụng stack call.
  • Khi vòng lặp kết thúc (b bằng 0), giá trị cuối cùng của a chính là UCLN.

Thuật toán Euclid (dù là đệ quy hay lặp) nhanh hơn đáng kể so với phương pháp duyệt đơn giản, đặc biệt với các số lớn.

Phương pháp 3: Sử dụng gcd (Từ C++17)

May mắn thay, từ chuẩn C++17, thư viện chuẩn đã cung cấp sẵn hàm gcd trong header <numeric>. Đây là cách nên dùng nếu bạn làm việc với C++17 trở lên vì nó đã được tối ưu hóa và kiểm tra kỹ lưỡng.

#include <iostream>
#include <numeric> // Cần cho gcd

int main() {
    int num1 = 48, num2 = 18;
    // Sử dụng gcd
    cout << "UCLN (gcd) cua " << num1 << " va " << num2 << " la: " << gcd(num1, num2) << endl;

    num1 = 100, num2 = 75;
    cout << "UCLN (gcd) cua " << num1 << " va " << num2 << " la: " << gcd(num1, num2) << endl;

    num1 = -12, num2 = 18; // gcd xử lý số âm theo quy tắc UCLN(a, b) = UCLN(|a|, |b|)
    cout << "UCLN (gcd) cua " << num1 << " va " << num2 << " la: " << gcd(num1, num2) << endl;

    return 0;
}

Giải thích:

  • Chỉ cần #include <numeric> và gọi gcd(a, b).
  • Hàm này tự động xử lý các trường hợp số âm và số 0 theo định nghĩa chuẩn (UCLN của a và b là UCLN của |a| và |b|).
  • Đây là cách ngắn gọn, an toàn và hiệu quả nhất để tìm UCLN trong C++ hiện đại.

2. Bội chung nhỏ nhất (BCNN / LCM)

Bội chung nhỏ nhất của hai hay nhiều số nguyên dương là số nguyên dương nhỏ nhất (khác 0) mà là bội của tất cả các số đó. Ký hiệu: BCNN(a, b) hoặc LCM(a, b).

Ví dụ:

  • Bội dương của 12 là: 12, 24, 36, 48, 60, 72, ...
  • Bội dương của 18 là: 18, 36, 54, 72, ...
  • Các bội chung dương của 12 và 18 là: 36, 72, ...
  • Bội chung nhỏ nhất của 12 và 18 là: 36. Vậy BCNN(12, 18) = 36.
Mối liên hệ giữa UCLN và BCNN

Có một công thức rất hữu ích liên kết UCLN và BCNN của hai số nguyên dương a và b:

UCLN(a, b) * BCNN(a, b) = |a * b|

Từ công thức này, ta có thể dễ dàng tính BCNN nếu đã biết UCLN:

BCNN(a, b) = (|a * b|) / UCLN(a, b)

Đây là phương pháp phổ biến nhất để tìm BCNN vì chúng ta đã có các thuật toán hiệu quả để tìm UCLN.

Lưu ý quan trọng: Khi tính (a * b) / UCLN(a, b), nếu a và b là các số rất lớn, tích a * b có thể bị tràn số (integer overflow) trước khi kịp chia cho UCLN. Để tránh điều này, một cách an toàn hơn là thực hiện phép chia trước phép nhân:

BCNN(a, b) = (|a| / UCLN(a, b)) * |b|

Hoặc tương đương BCNN(a, b) = (|b| / UCLN(a, b)) * |a|.

Hãy xem code minh họa sử dụng công thức này và giả sử chúng ta đã có hàm tính UCLN (ví dụ: gcd).

#include <iostream>
#include <numeric> // Cần cho gcd
#include <cmath>   // Cần cho abs

// Hàm tìm BCNN sử dụng mối liên hệ với UCLN
long long find_lcm(long long a, long long b) {
    // BCNN của bất kỳ số nào với 0 là 0 theo định nghĩa chuẩn
    if (a == 0 || b == 0) {
        return 0;
    }

    // Sử dụng công thức BCNN(a, b) = (|a| * |b|) / UCLN(a, b)
    // Để tránh tràn số, nên tính (|a| / UCLN(a, b)) * |b|
    long long abs_a = abs(a);
    long long abs_b = abs(b);

    // Tìm UCLN của |a| và |b|
    long long gcd_val = gcd(abs_a, abs_b);

    // Tính BCNN bằng công thức an toàn hơn để tránh tràn số
    // abs_a / gcd_val không bao giờ lẻ, và kết quả luôn là số nguyên.
    return (abs_a / gcd_val) * abs_b;
}

int main() {
    long long num1 = 12, num2 = 18;
    cout << "BCNN cua " << num1 << " va " << num2 << " la: " << find_lcm(num1, num2) << endl;

    num1 = 21, num2 = 6;
    cout << "BCNN cua " << num1 << " va " << num2 << " la: " << find_lcm(num1, num2) << endl;

    num1 = 1000000, num2 = 1000001; // Các số lớn để minh họa
    cout << "BCNN cua " << num1 << " va " << num2 << " la: " << find_lcm(num1, num2) << endl;

    num1 = -12, num2 = 18; // BCNN của a và b là BCNN của |a| và |b|
    cout << "BCNN cua " << num1 << " va " << num2 << " la: " << find_lcm(num1, num2) << endl;

    return 0;
}

Giải thích:

  • Hàm find_lcm nhận hai số a và b. Chúng ta sử dụng long long để có thể làm việc với các giá trị BCNN lớn hơn.
  • Trường hợp đặc biệt: BCNN của bất kỳ số nào với 0 là 0.
  • Lấy giá trị tuyệt đối của a và b để đảm bảo làm việc với số dương.
  • Sử dụng gcd để tìm UCLN của giá trị tuyệt đối của a và b.
  • Tính BCNN bằng công thức (|a| / UCLN(|a|, |b|)) * |b|. Công thức này an toàn hơn vì phép chia |a| / UCLN(|a|, |b|) luôn cho kết quả là một số nguyên và thường nhỏ hơn |a|, giúp giảm nguy cơ tràn số khi nhân với |b|.
Phương pháp 2: Sử dụng lcm (Từ C++17)

Tương tự như UCLN, C++17 cũng cung cấp sẵn hàm lcm trong header <numeric>.

#include <iostream>
#include <numeric> // Cần cho lcm

int main() {
    long long num1 = 12, num2 = 18;
    // Sử dụng lcm
    cout << "BCNN (lcm) cua " << num1 << " va " << num2 << " la: " << lcm(num1, num2) << endl;

    num1 = 21, num2 = 6;
    cout << "BCNN (lcm) cua " << num1 << " va " << num2 << " la: " << lcm(num1, num2) << endl;

    num1 = 1000000, num2 = 1000001;
    cout << "BCNN (lcm) cua " << num1 << " va " << num2 << " la: " << lcm(num1, num2) << endl;

    num1 = -12, num2 = 18; // lcm xử lý số âm theo quy tắc BCNN(a, b) = BCNN(|a|, |b|)
    cout << "BCNN (lcm) cua " << num1 << " va " << num2 << " la: " << lcm(num1, num2) << endl;

    num1 = 0; num2 = 5; // lcm(a, 0) = 0
    cout << "BCNN (lcm) cua " << num1 << " va " << num2 << " la: " << lcm(num1, num2) << endl;

    return 0;
}

Giải thích:

  • Chỉ cần #include <numeric> và gọi lcm(a, b).
  • Hàm này cũng tự động xử lý số âm và số 0 theo định nghĩa chuẩn (BCNN của a và b là BCNN của |a| và |b|, và BCNN của bất kỳ số nào với 0 là 0).
  • Tương tự như gcd, lcm là cách ngắn gọn, an toàn và hiệu quả nhất để tìm BCNN trong C++17 trở lên.

3. Ứng dụng trong thực tế

UCLN và BCNN tuy là khái niệm toán học cơ bản nhưng có nhiều ứng dụng thực tế trong lập trình:

  • Tối giản phân số: Chia tử số và mẫu số cho UCLN của chúng. Ví dụ: Phân số 12/18, UCLN(12, 18) = 6. Chia cả tử và mẫu cho 6 được 2/3.
  • Tìm mẫu số chung nhỏ nhất (LCD - Least Common Denominator): Khi cộng hoặc trừ phân số, BCNN của các mẫu số chính là mẫu số chung nhỏ nhất.
  • Bài toán lịch trình/Chu kỳ: Tìm thời điểm tiếp theo hai sự kiện lặp lại sẽ xảy ra đồng thời. Nếu sự kiện A lặp sau mỗi T_a đơn vị thời gian và sự kiện B lặp sau mỗi T_b đơn vị thời gian, chúng sẽ lặp lại đồng thời sau mỗi BCNN(T_a, T_b) đơn vị thời gian.
  • Trong các thuật toán lý thuyết số: UCLN và BCNN là nền tảng cho nhiều thuật toán phức tạp hơn.

Việc hiểu rõ UCLN, BCNN và cách tính toán chúng hiệu quả sẽ giúp bạn giải quyết nhiều vấn đề lập trình một cách thanh lịch và tối ưu hơn.

#include <iostream>
#include <numeric>

// Ví dụ ứng dụng: Tối giản phân số
struct Fraction {
    int numerator;   // Tử số
    int denominator; // Mẫu số

    void simplify() {
        // Đảm bảo mẫu số dương
        if (denominator < 0) {
            numerator = -numerator;
            denominator = -denominator;
        }
        // Tìm UCLN của tử và mẫu (lấy giá trị tuyệt đối của tử)
        int common_divisor = gcd(abs(numerator), denominator);

        // Chia cả tử và mẫu cho UCLN
        numerator /= common_divisor;
        denominator /= common_divisor;
    }
};

int main() {
    Fraction frac = {12, 18};
    cout << "Phan so goc: " << frac.numerator << "/" << frac.denominator << endl;
    frac.simplify();
    cout << "Phan so sau khi toi gian: " << frac.numerator << "/" << frac.denominator << endl;

    Fraction frac2 = {-24, 36};
     cout << "Phan so goc: " << frac2.numerator << "/" << frac2.denominator << endl;
    frac2.simplify();
    cout << "Phan so sau khi toi gian: " << frac2.numerator << "/" << frac2.denominator << endl;

    Fraction frac3 = {15, -25};
     cout << "Phan so goc: " << frac3.numerator << "/" << frac3.denominator << endl;
    frac3.simplify();
    cout << "Phan so sau khi toi gian: " << frac3.numerator << "/" << frac3.denominator << endl;

    return 0;
}

Giải thích:

  • Struct Fraction lưu tử số và mẫu số.
  • Hàm simplify() đầu tiên đảm bảo mẫu số là dương bằng cách đổi dấu cả tử và mẫu nếu cần.
  • Sau đó, nó tính UCLN của giá trị tuyệt đối của tử số và mẫu số bằng gcd. Lấy giá trị tuyệt đối của tử là quan trọng vì UCLN chỉ định nghĩa cho số dương, nhưng tử số có thể âm.
  • Cuối cùng, cả tử số và mẫu số được chia cho UCLN để tối giản phân số.

Đây chỉ là một ví dụ đơn giản, nhưng nó cho thấy cách UCLN có thể được áp dụng trực tiếp vào một vấn đề lập trình phổ biến.

Bài tập ví dụ: C++ Bài 4.B3: Kê chân bàn

Thấy chân bàn bị gập ghềnh nên Hiếu lấy một tờ giấy lần lượt gấp đôi lại nhiều lần để kê chân bàn. Giả sử tờ giấy có bề dày là \(n\) thì sau lần gấp đôi thứ nhất bề dày là \(2n\) , sau lần gấp đôi thứ \(2\) là \(4n\), lần thứ \(3\) là \(8n\),...

Nếu khoảng gập ghềnh là \(b\) thì Hiếu cần gấp đôi giấy bao nhiêu lần để kê chân bàn ít bị gập ghềnh nhất?

INPUT FORMAT

Dòng đầu tiên chứa hai giá trị \(n,b\) \((1 \leq a, b \leq 10^9)\).

OUTPUT FORMAT

Ví dụ 1:

Input
1 4
Ouput
2

Ví dụ 2:

Input
2 5
Output
1

Giải thích ví dụ mẫu:

  • Ví dụ 1:

    • Input: 1 4
    • Giải thích: Sau 2 lần gấp đôi, bề dày giấy là 4, đủ để kê chân bàn có khoảng gập ghềnh là 4.

  • Ví dụ 2:

    • Input: 2 5
    • Giải thích: Sau 1 lần gấp đôi, bề dày giấy là 4, đủ để kê chân bàn có khoảng gập ghềnh là 5.

<br>

1. Phân tích bài toán:

  • Bạn bắt đầu với một tờ giấy có bề dày ban đầu là n.
  • Mỗi lần gấp đôi, bề dày tăng gấp đôi.
  • Sau k lần gấp, bề dày sẽ là n * 2^k.
  • Khoảng gập ghềnh cần kê là b.
  • Mục tiêu là tìm số lần gấp k ít nhất sao cho bề dày sau khi gấp (n * 2^k) đủ để kê, tức là n * 2^k >= b.
  • Các giá trị n và b có thể lên tới 10^9, nên cần sử dụng kiểu dữ liệu có thể chứa được các giá trị lớn.

2. Xác định phương pháp giải:

Bài toán yêu cầu tìm số lần gấp k nhỏ nhất để đạt được một điều kiện (n * 2^k >= b). Bề dày tăng theo lũy thừa của 2, đây là một sự tăng trưởng nhanh chóng. Ta có thể mô phỏng trực tiếp quá trình gấp giấy.

Bắt đầu từ 0 lần gấp, kiểm tra bề dày. Nếu chưa đủ, tăng số lần gấp lên 1 và tính bề dày mới (gấp đôi bề dày hiện tại), rồi kiểm tra lại. Lặp lại quá trình này cho đến khi bề dày đủ để kê (>= b).

3. Hướng dẫn các bước thực hiện (không code hoàn chỉnh):

  • Bước 1: Đọc dữ liệu đầu vào.

    • Đọc hai số nguyên n và b.
    • Vì n và b có thể lớn (10^9), và bề dày sau khi gấp có thể vượt quá int, hãy sử dụng kiểu dữ liệu long long cho n và b, cũng như biến lưu trữ bề dày hiện tại.

  • Bước 2: Khởi tạo.

    • Khởi tạo một biến để lưu trữ số lần gấp hiện tại, bắt đầu từ 0.
    • Khởi tạo một biến để lưu trữ bề dày hiện tại, bắt đầu bằng giá trị n đọc từ input. Đảm bảo biến này cũng là long long.

  • Bước 3: Lặp và kiểm tra.

    • Sử dụng một vòng lặp (ví dụ: while) để tiếp tục quá trình gấp giấy chừng nào bề dày hiện tại còn nhỏ hơn khoảng gập ghềnh b.
    • Điều kiện của vòng lặp sẽ là: bề dày hiện tại < b.

  • Bước 4: Cập nhật trong mỗi lần lặp.

    • Bên trong vòng lặp (khi bề dày chưa đủ):
      • Tăng số lần gấp hiện tại lên 1.
      • Nhân đôi bề dày hiện tại. bề dày hiện tại = bề dày hiện tại * 2; hoặc bề dày hiện tại *= 2;.

  • Bước 5: Kết thúc và xuất kết quả.

    • Khi vòng lặp kết thúc, điều đó có nghĩa là bề dày hiện tại đã đạt hoặc vượt quá b.
    • Số lần gấp tại thời điểm vòng lặp dừng lại chính là số lần gấp tối thiểu cần thiết.
    • In ra giá trị của biến đếm số lần gấp.

4. Lưu ý khi triển khai bằng C++:

  • Sử dụng thư viện <iostream> cho việc nhập/xuất chuẩn (cin, cout).
  • Khai báo biến n, b, biến lưu bề dày hiện tại với kiểu long long. Biến đếm số lần gấp có thể là int vì số lần gấp sẽ không quá lớn (logarit cơ số 2 của 10^9 * 10^9 không quá lớn, khoảng 60), nhưng dùng long long cũng an toàn.
  • Đảm bảo phép nhân bề dày hiện tại với 2 không bị tràn số bằng cách sử dụng long long.

Ví dụ minh họa cách suy nghĩ (không phải code):

Input: n=2, b=5

  1. n=2, b=5.
  2. folds = 0, current_thickness = 2.
  3. Kiểm tra current_thickness < b: 2 < 5 -> True.
  4. Vào vòng lặp:
    • folds = 1.
    • current_thickness = 2 * 2 = 4.
  5. Kiểm tra current_thickness < b: 4 < 5 -> True.
  6. Vào vòng lặp:
    • folds = 2.
    • current_thickness = 4 * 2 = 8.
  7. Kiểm tra current_thickness < b: 8 < 5 -> False.
  8. Vòng lặp kết thúc.
  9. In ra folds, là 2.

Lưu ý về Ví dụ 2 trong đề bài: Ví dụ 2 trong đề bài (Input: 2 5, Output: 1) mâu thuẫn với quy tắc "bề dày >= b" và cách hoạt động của Ví dụ 1 (Input: 1 4, Output: 2, nơi bề dày 4 >= 4). Dựa trên mô tả bài toán "bề dày là \(n\) thì sau lần gấp đôi thứ nhất bề dày là \(2n\)..." và mục tiêu "kê chân bàn ít bị gập ghềnh nhất" (ngầm hiểu là cần đủ bề dày), giải pháp n * 2^k >= b là cách hiểu hợp lý nhất cho một bài tập lập trình cơ bản. Rất có thể ví dụ 2 có sai sót trong đề bài hoặc phần giải thích. Hãy code theo logic n * 2^k >= b.

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

Comments

There are no comments at the moment.