tailieunhanh - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG I: THUẬT TOÁN_4

Thuật toán Euclide được viết dưới dạng giả mã như sau: procedure ƯCLN (a,b: positive integers) x := a y := b while y 0 begin r := x mod y x := y y := r end {UCLN (a,b) là x} | CHƯƠNG I THUẬT TOÁN Thuật toán Euclide được viết dưới dạng giả mã như sau procedure ƯCLN a b positive integers x a y b while y 0 begin r x mod y x y y r end UCLN a b là x Trong thuật toán trên các giá trị ban đầu của x và y tương ứng là a và b. Ở mỗi giai đoạn của thủ tục x được thay bằng y và y được thay bằng x mod y. Quá trình này được lặp lại chừng nào y 0. Thuật toán sẽ ngừng khi y 0 và giá trị của x ở điểm này đó là số dư khác không cuối cùng trong thủ tục cũng chính là ước chung lớn nhất của a và b. . Biểu diễn các số nguyên Mệnh đề 3 Cho b là một số nguyên dương lớn hơn 1. Khi đó nếu n là một số nguyên dương nó có thể được biểu diễn một cách duy nhất dưới dạng n akbk ak-1bk 1 . aib a0. Ở đây k là một số tự nhiên a0 a1 . ak là các số tự nhiên nhỏ hơn b và ak 0. Biểu diễn của n được cho trong Mệnh đề 3 được gọi là khai triển của n theo cơ số b ký hiệu là akak-1. a1a0 b. Bây giờ ta sẽ mô tả thuật toán xây dựng khai triển cơ số b của số nguyên n bất kỳ. Trước hết ta chia n cho b để được thương và số dư tức là n bq0 a0 0 a0 b. Số dư ao chính là chữ số đứng bên phải cùng trong khai triển cơ số b của n. Tiếp theo chia q0 cho b ta được q0 bq1 a1 0 a1 b. Số dư a1 chính là chữ số thứ hai tính từ bên phải trong khai triển cơ số b của n. Tiếp tục quá trình này bằng cách liên tiếp chia các thương cho b ta sẽ được các chữ số tiếp theo trong khai triển cơ số b của n là các số dư tương ứng. Quá trình này sẽ kết thúc khi ta nhận được một thương bằng 0. Thí dụ 7 Tìm khai triển cơ số 8 của 12345 10. 12345 1 1543 7 192 0 24 0 3 3. Do đó 12345 10 30071 8. Đoạn giả mã sau biểu diễn thuật toán tìm khai triển cơ số b của số nguyên n. procedure khai triển theo cơ số b n positive integer q n k 0 while q 0 begin ak q mod b q b k k 1 end . Thuật toán cho các phép tính số nguyên Các thuật toán thực hiện các phép tính với những số nguyên khi dùng các khai triển nhị phân của chúng là cực kỳ quan trọng trong .