[Thuật toán] Rút gọn phân số

Đề bài: Nhập vào tử số, mẫu số. In ra phân số rút gọn ở dạng tối giản

Ý tưởng

  • Tìm ước chung lớn nhất
  • Chia tử số, mẫu số cho ước chung lớn nhất
  • Case đặc biệt:
    • Dấu âm ở mẫu số -> đẩy lên tử số
    • Tử số chia hết cho mẫu số

Tìm ước chung lớn nhất

Sử dụng đệ quy để tìm:

  • Nếu a chia hết cho b -> trả về số b
  • Nếu a không chia hết cho b -> tìm ước chung của (b, b%a)

Code

package main
import "fmt"
func ucln(a int, b int) int {
if a%b == 0 {
return b
}
return ucln(b, a%b)
}
func main() {
// Tử và mẫu nhập vào. Chỗ này mình mock luôn cho ngắn
tu := 10
mau := 15
if tu % mau == 0 {
fmt.Println(tu/mau)
return
}
uc := ucln(tu, mau)
tu = tu / uc
mau = mau / uc
if mau < 0 {
mau *= 1
tu *= 1
}
fmt.Printf("%v/%v", tu, mau)
}
view raw rutgon.go hosted with ❤ by GitHub

Cảm ơn bạn vì đã đọc bài ^^

Trả lời

Điền thông tin vào ô dưới đây hoặc nhấn vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google photo

Bạn đang bình luận bằng tài khoản Google Đăng xuất /  Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất /  Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất /  Thay đổi )

Connecting to %s