[Shell Script] Thuật toán tìm ước chung lớn nhất

Trong bài viết này, chúng ta sẽ cùng nhau khám phá thuật toán tìm ước chung lớn nhất và học cách triển khai nó bằng ngôn ngữ lập trình Shell Script.

Xem thêm:

• Tính tổng n số hạng đầu tiên của dãy Fibonacci shellscript
• Kiểm tra số nguyên tố đối xứng shell script

1. Bài toán

Bài toán: Tính UCLN(a, b), a và b được truyền vào dưới dạng tham số

2. Phân tích bài toán tìm ước chung lớn nhất shellscript

1. Trong hàm ucln:
   • Hai tham số a và b được truyền vào hàm.
   • Kiểm tra nếu một trong hai số a hoặc b bằng 0, thì hiển thị tổng của cả hai số là UCLN của chúng.
   • Nếu cả a và b đều lớn hơn 0, thực hiện vòng lặp while để tìm UCLN bằng thuật toán Euclid:
     • Trong mỗi vòng lặp, kiểm tra xem a có lớn hơn b không. Nếu có, trừ b từ a, ngược lại, trừ a từ b.
     • Lặp lại cho đến khi a và b bằng nhau. Lúc này, a (hoặc b) chính là UCLN của a và b.
   • Cuối cùng, script sẽ hiển thị UCLN của a và b.
2. Phần chính của script:
   • Hiển thị thông báo để yêu cầu người dùng nhập số a.
   • Đọc giá trị a từ người dùng.
   • Hiển thị thông báo để yêu cầu người dùng nhập số b.
   • Đọc giá trị b từ người dùng.
3. Cuối cùng, gọi hàm ucln với đối số num1 và num2 là giá trị của a và b đã được nhập từ người dùng. Hàm này sẽ tính và hiển thị UCLN của a và b.

3. Code tìm ucln(a,b) shellscript

#!/bin/bash

ucln () {
 
 a=$1
 b=$2
 
 if [ $a -eq 0 -o $b -eq 0 ]
 then
  echo "Uoc chung lon nhat la: `expr $a + $b`"
  
 else
  while [ $a != $b ]
  do
     if [ $a -gt $b ]
     then
     	a=`expr $a - $b`
     else
     	b=`expr $b - $a`
     fi
     
  done
  
  echo "Uoc chung lon nhat la: $a"
   
 fi
}

echo "Nhap a:"
read num1
 
echo "Nhap b:"
read num2

ucln $num1 $num2

4. Kết quả

Ngoài ra, bạn có thể thử các bộ test sau:

Dưới đây là một số bộ test cho mã shell script tính ước chung lớn nhất (UCLN) của hai số a và b:

Bộ test 1:

• Nhập a = 12
• Nhập b = 18
• Kết quả đầu ra: “Uoc chung lon nhat la: 6”

Bộ test 2:

• Nhập a = 25
• Nhập b = 35
• Kết quả đầu ra: “Uoc chung lon nhat la: 5”

Bộ test 3:

• Nhập a = 7
• Nhập b = 11
• Kết quả đầu ra: “Uoc chung lon nhat la: 1”

Bộ test 4:

• Nhập a = 0
• Nhập b = 10
• Kết quả đầu ra: “Uoc chung lon nhat la: 10”

Bộ test 5:

• Nhập a = 30
• Nhập b = 45
• Kết quả đầu ra: “Uoc chung lon nhat la: 15”

Bộ test 6:

• Nhập a = 17
• Nhập b = 19
• Kết quả đầu ra: “Uoc chung lon nhat la: 1”

Bộ test 7:

• Nhập a = 12
• Nhập b = 0
• Kết quả đầu ra: “Uoc chung lon nhat la: 12”

Bộ test 8:

• Nhập a = -5
• Nhập b = 8 (làm cho người dùng nhập lại cho đến khi a và b là số dương)
• Tiếp theo, nhập a = 15
• Nhập b = 0 (làm cho người dùng nhập lại cho đến khi b là số dương)
• Kết quả đầu ra: “Uoc chung lon nhat la: 15”

Trong bài viết này, chúng ta đã cùng nhau tìm hiểu về thuật toán tìm ước chung lớn nhất (GCD) và cách triển khai nó bằng ngôn ngữ lập trình Shell Script. Cảm ơn bạn đã đọc bài viết này trên ttnguyen.net và hẹn gặp lại trong những bài viết khác của quản trị linux!

Bài viết liên quan:

mảng trong Shell Script

các hàm trong shell