Chuyển tới nội dung chính
Z

Trình trực quan hóa thuật toán Euclid (GCD)

Thuật toán Euclid dạng hoạt họa — tính GCD của hai số theo từng bước với phép rút gọn (a, b) → (b, a mod b). Chạy ngay trong trình duyệt.

Miễn phí Không cần đăng ký Chạy trên trình duyệt Tôn trọng riêng tư Updated

/

Mã giả

Run an operation to see its steps.

Cách dùng

  1. 1 Nhập hai số cách nhau bằng dấu phẩy (ví dụ: 48, 36) rồi nhấn Tính GCD.
  2. 2 Theo dõi từng bước thay (a, b) bằng (b, a mod b) cho đến khi b bằng 0.
  3. 3 Khi b bằng 0, a chính là ước chung lớn nhất.
  4. 4 Dùng Random để lấy một cặp số mới, hoặc thực hiện từng phép chia một.

Vì sao dùng công cụ này

  • Xem thuật toán Euclid — một trong những thuật toán lâu đời nhất của toán học — hoạt động trực tiếp.
  • Hiểu vì sao gcd(a, b) = gcd(b, a mod b) và vì sao thuật toán kết thúc rất nhanh.
  • Quan sát các giá trị giảm theo cấp số logarit cho đến khi một số về 0.
  • Chạy hoàn toàn trong trình duyệt của bạn. Không cần đăng ký, không upload dữ liệu.

Câu hỏi thường gặp

Thuật toán Euclid là gì?

Một phương pháp tính ước chung lớn nhất (GCD) của hai số nguyên bằng cách liên tục thay số lớn hơn bằng phần dư khi chia nó cho số nhỏ hơn, cho đến khi phần dư bằng 0.

Độ phức tạp thời gian của thuật toán Euclid là gì?

O(log min(a, b)) — số bước tỉ lệ với số chữ số, đó là lý do thuật toán cực kỳ nhanh ngay cả với các số rất lớn.

Vì sao gcd(a, b) = gcd(b, a mod b)?

Bất kỳ ước chung nào của a và b cũng chia hết a mod b (và ngược lại), nên tập hợp các ước chung — và do đó ước chung lớn nhất — không đổi qua phép thay thế này.

GCD được dùng để làm gì?

Rút gọn phân số, số học modulo, thuật toán Euclid mở rộng (nghịch đảo modulo, RSA), và tính bội chung nhỏ nhất qua công thức lcm(a,b) = a·b / gcd(a,b).

Trình trực quan hóa thuật toán Euclid (GCD) là gì?

Trình trực quan hóa thuật toán Euclid mô phỏng cách tìm GCD của hai số nguyên bằng cách liên tục thay cặp (a, b) bằng (b, a mod b) cho đến khi b đạt 0 — lúc đó a chính là ước chung lớn nhất.

Tính năng

Step-by-step animation

Watch each division-and-remainder step until the remainder hits zero.

Complexity

Time: O(log min(a, b)) division steps. Space: O(1).

100% private

Runs entirely in your browser — nothing is uploaded.

Ví dụ

Input

gcd(48, 18)

Output

48 = 2·18 + 12; 18 = 1·12 + 6; 12 = 2·6 + 0 → GCD = 6

Trường hợp sử dụng

  1. 1

    Reduce fractions

    Use the GCD to simplify a fraction to lowest terms.

  2. 2

    Understand the algorithm

    See why remainders shrink quickly, giving logarithmic steps.

  3. 3

    Number theory basics

    Learn the foundation for modular arithmetic and RSA.

Tóm tắt

Zerethon's Euclidean algorithm visualizer animates finding the greatest common divisor of two integers in your browser, repeatedly replacing the larger number with the remainder of dividing it by the smaller until the remainder is zero. It runs in O(log min(a, b)) division steps with O(1) space — one of the oldest algorithms still in use (Euclid's Elements, ~300 BC).

Danh mục
Thuật toán
Giá
Miễn phí
Quyền riêng tư
Chạy trên trình duyệt
Đăng ký
Không cần

References

Quyền riêng tư

Dữ liệu của bạn không bao giờ rời khỏi trình duyệt trừ khi được nêu rõ. Trình trực quan hóa thuật toán Euclid (GCD) chạy hoàn toàn phía client — không tải lên máy chủ, không ghi log, không theo dõi dữ liệu bạn nhập.

Mới làm quen? Đọc giải thích từng bước kèm phân tích Big-O: Tìm hiểu Number Theory →

So sánh

LCM vs GCD

Công cụ liên quan

Trình mô phỏng Bubble Sort

Mô phỏng bubble sort có hoạt ảnh với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và pseudocode. Chạy hoàn toàn trong trình duyệt của bạn.

Mở công cụ

Trình trực quan hóa Insertion Sort

Insertion Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.

Mở công cụ

Trình trực quan hóa Selection Sort

Selection Sort hoạt hình với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt của bạn.

Mở công cụ

Trình trực quan hóa Merge Sort

Mô phỏng merge sort có hoạt ảnh với điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/ghi trực tiếp và mã giả (pseudocode). Chạy hoàn toàn trên trình duyệt.

Mở công cụ

Xây dựng, chia sẻ và phát triển trên Zerethon Social

Đăng ký miễn phí. Kiếm điểm, sưu tầm thành tựu và kết nối với nhà sáng tạo khắp thế giới.

Đăng ký miễn phí