›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 6: Thực hiệu thuật toán Euclid bằng đệ qui - Đào Nam Anh

pdf 21 trang ngocly 2800
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 6: Thực hiệu thuật toán Euclid bằng đệ qui - Đào Nam Anh", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_bai_6_thuc_hieu_thu.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 6: Thực hiệu thuật toán Euclid bằng đệ qui - Đào Nam Anh

  1. DATA STRUCTURE AND ALGORITHM Recursive Euclid Algorithm CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Thực hiệu thuật toán Euclid bằng đệ qui Dr. Dao Nam Anh Data Structure and Algorithm 1
  2. Resource - Reference Slides adapted from Robert Sedgewick, and Kevin Wayne. Major Reference: • Robert Sedgewick, and Kevin Wayne, “Algorithms” Princeton University, 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley Data Structure and Algorithm 2
  3. Recursive Euclid Algorithm Tìm ước số chung lớn nhất của hai số nguyên public class Euclid { public static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } public static void main(String[] args) { int p = Integer.parseInt(args[0]); int q = Integer.parseInt(args[1]); System.out.println(gcd(p, q)); } } Data Structure and Algorithm 3
  4. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 4
  5. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 5
  6. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 6
  7. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { 1272 = 216 5 + 192 if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 7
  8. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 8
  9. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 9
  10. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 192, q = 24 gcd(192, 24) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 10
  11. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 192, q = 24 gcd(192, 24) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 11
  12. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 192, q = 24 gcd(192, 24) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 12
  13. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 192, q = 24 gcd(192, 24) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); p = 24, q = 0 } gcd(24, 0) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 13
  14. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 192, q = 24 gcd(192, 24) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); p = 24, q = 0 } gcd(24, 0) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 14
  15. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 192, q = 24 gcd(192, 24) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); p = 24, q = 0 } 24 gcd(24, 0) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } Data Structure and Algorithm 15
  16. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 192, q = 24 gcd(192, 24) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } 24 Data Structure and Algorithm 16
  17. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 192, q = 24 24 gcd(192, 24) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } 24 Data Structure and Algorithm 17
  18. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } 24 Data Structure and Algorithm 18
  19. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } p = 216, q = 192 24 gcd(216, 192) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } 24 Data Structure and Algorithm 19
  20. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } 24 Data Structure and Algorithm 20
  21. p = 1272, q = 216 gcd(1272, 216) environment static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); }24 public class Euclid { public static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } public static void main(String[] args) { int p = Integer.parseInt(args[0]); int q = Integer.parseInt(args[241]); System.out.println(gcd(p, q)); } 24 } % java Euclid 1272 216 24 Data Structure and Algorithm 21