← Level 3 · Đọc hiểu & Tình huống FE
Thuật toán & giả mã Tình huống đọc hiểu Độ khó: Nâng cao Thời gian dự kiến: Khoảng 5 phút Cấp độ phù hợp: FE Level 3 (môn B)

Tính ước chung lớn nhất bằng thuật toán Euclid

Thuật toán Euclid tính hiệu quả ước chung lớn nhất (GCD) của hai số nguyên. Đoạn giả mã dưới đây triển khai ý tưởng này theo cách đệ quy.

○ kiểu số nguyên: gcd(số nguyên: a, số nguyên: b)
  if (b bằng 0) then
    return a
  else
    return gcd(b, a mod b)
  endif

Từ khóa

最大公約数さいだいこうやくすうước chung lớn nhất 剰余じょうよsố dư (mod)

Câu hỏi

1

Khi gọi gcd(48, 18), giá trị nào được trả về?

Lựa chọn

  1. 2
  2. 6
  3. 9
  4. 18
Xem giải thích

Chuỗi gọi là gcd(48,18)→gcd(18,12)→gcd(12,6)→gcd(6,0), cuối cùng trả về 6.

2

Trong quá trình tính gcd(48, 18), hàm gcd được gọi tổng cộng bao nhiêu lần (tính cả lần gọi đầu tiên)?

Lựa chọn

  1. 2 lần
  2. 3 lần
  3. 4 lần
  4. 5 lần
Xem giải thích

Chuỗi gcd(48,18)→gcd(18,12)→gcd(12,6)→gcd(6,0) tổng cộng 4 lần gọi.

3

Việc trả về a khi b bằng 0 đóng vai trò gì trong hàm đệ quy này?

Lựa chọn

  1. Điều kiện dừng (base case) để chấm dứt đệ quy
  2. Bước tạo ra vòng lặp vô hạn
  3. Bước sửa lỗi tính toán
  4. Bước hoán đổi giá trị a và b
Xem giải thích

Khi b bằng 0, đây là điều kiện dừng (base case) chấm dứt việc gọi đệ quy tiếp và trả về giá trị a hiện tại làm kết quả cuối cùng.

Đăng nhập để lưu kết quả

Bạn có thể đọc miễn phí nội dung, câu hỏi và giải thích. Hãy đăng nhập để lưu kết quả và đưa vào hàng ôn tập cùng phân tích điểm yếu.

Đăng nhập để lưu