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

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