[Chia để Trị] Tính Lũy Thừa A^n - Writes - Dạy Nhau Học

Có thể bạn quan tâm

sharewritesalgorithm nhatlonggunz (nhatlonggunz) March 30, 2016, 6:35pm #1 Giờ rảnh được chút, làm thêm một bài nữa về một thuật toán cơ bản: tính lũy thừa an bằng phương pháp chia để trị. Chắc mọi người đa số hay dùng vòng lặp nhỉ (cứ ừ đại đi), bây giờ đổi gió xíu nhéVào luôn vấn đề, như mọi người đã biết, an được tính bằng cách nhân n lần số a (nói vậy cho gọn đi) Mình lấy ví dụ:

a8 = a . a . a . a . a . a . a . a (8 chữ a lận nhé)

Ta nhận thấy rằng có thể chia nửa cái phép tính trên kia ra, như thế này:

a8 = a4 + 4 = a4 . a4

trong đó, a4 có thể được tính:

a4 = a2 . a2

Lại một lần nữa chia nhỏ :

a2 = a1 . a1 = a . a

Đến đây ra có thể dễ dàng đưa ra a (a cùng n là input của bài toán này).

Vậy ta nhận ra được phần base case của thuật đệ quy ở đây (hay nhiều sách tiếng Việt gọi là phần neo ấy, mình học trên Khan nên đọc quen rồi) chính là khi số mũ đưa về 1, ta có thể đưa thẳng ra giá trị a

Từ đó ta suy ra cách giải quyết bài toán thế này: chia nhỏ số mũ n ra cho đến khi n = 1

Vậy hàm pow với tham số : int pow(int a, int n) Sẽ có phần base case:Thế còn recursive case (phần đệ quy) ? Thì theo như ví dụ ở trên, ta có công thức:

an = an/2 . an/2

Chuyển ra code:Thế nhưng nếu n là một số lẻ thì sao? Ví dụ như n = 3:

a5 = a . a . a . a . a (1) Thì trong trường hợp này, n/2 sẽ bằng 5/2 = 2 (do n kiểu int nên số sẽ tự bỏ đi phần thập phân) (1) = a2 . a2 . a do là số lẻ nên khi khi mod 2 (chia lấy dư) thì số dư sẽ luôn luôn là 1 => Với n là số lẻ, khi chia ra sẽ luôn thừa một số a

Vậy ta suy ra công thức:

an = an/2 . an/2 với n là số lẻ

hay chuyển ra code:Tổng hợp lại công thức tổng quát:

an =

an/2 * an/2 nếu n chẵn

an/2 * an/2 * a nếu n lẻ

Và cuối cùng là code, dài dòng lê thê lắm rồi:Thế nhưng, ta lại thấy code trên có 1 điểm không tốt, đó chính là trong phần đệ quy, hàm pow được tính 2 lần trong khi chúng giống hệt nhau:Vậy ta sẽ gán chúng vào một biến, như thế thì sẽ đỡ phải tính lại thêm 1 lần:Code ngắn gọn hơn xíu:Cập nhật:

Dùng vòng for(i=0->n): dpt=O(n)

Dùng chia để trị: T(n)= T(n/2)+O(1) => dpt=O(logn)

=> Dùng phương pháp chia để trị nhanh hơn là dùng vòng lặpKết thúc bài

chưa có kinh nghiệm nên viết bài có vẻ lê thê quá, mọi người thông cảm

14 LikesHỏi về thuật toán lấy số dư của phép chia một lũy thừa cho 1 số nhỏGiải thích đơn giản về thuật toán tính lũy thừa nhanhCheck lỗi giúp code in ra tất cả các số nguyên tố có N chữ số và tổng các chữ số đúng bằng S cho trước nhatlonggunz (nhatlonggunz) April 30, 2015, 10:03am #2 À đúng rồi anh @Gio , anh xem giùm em độ phức tạp khi sử dụng cách này so với khi dùng vòng lặp với. Để em bổ sung vô cho mọi người có cái nhìn trực quan3 Likes nguyenchiemminhvu (NCMV) April 30, 2015, 10:48am #3 số mũ lẻ tính có chính xác không? Gio (Gió) April 30, 2015, 10:56am #4

Dùng vòng for(i=0->n): dpt=O(n)

Dùng chia để trị: T(n)= T(n/2)+O(1) => dpt=O(logn)

1 Like nhatlonggunz (nhatlonggunz) April 30, 2015, 11:26am #5 Vậy cái này lâu hơn hay nhanh hơn hả anh, em chưa học log nên cũng không biết nhiều Gio (Gió) April 30, 2015, 11:32am #6 Tất nhiên là O(logn) sẽ nhanh hơn.p/s: log_a(b)=x <=> a^x=b viết log(n) <=> log_2(n) VD: log(16)=42 Likes nhatlonggunz (nhatlonggunz) April 30, 2015, 11:38am #7 Cám ơn anh

Bữa em học bên Khan một chút về logab = x mà thấy nước ta toàn viết log(n), thấy ngộ ngộ, đâu mất phần base (em không biets nó gọi là gì nữa, logab người ta đọc là log base a of b) Cám ơn anh

thanhmssl10 (TP) April 30, 2015, 12:12pm #8 @nhatlonggunz với anh @Gio nghiên cứu viết tut tính độ phức tạp thật toán đê, muốn tính cho bằng anh em mà không biết tính

nhatlonggunz (nhatlonggunz) April 30, 2015, 12:15pm #9 Bên Khan có dạy mà em chưa học, để khi nảo rảnh em vừa học vừa dịch luôn thử.1 Like thanhmssl10 (TP) April 30, 2015, 1:33pm #10

Mà cái độ phức tạp này ý nghĩa thực tế thế nào nhỉ, nhìn nó rất Toán, không biết có tính được ra tốc độ chạy code không nhatlonggunz (nhatlonggunz) April 30, 2015, 12:22pm #11 Theo em hiểu sơ sơ (không học nhưng cũng lướt lướt) thì cái đó tính thời gian chạy của thuật toán (ví dụ cho i lặp từ 1 đến n, mỗi lần lặp là 1 bước, n lần lặp là n bước), space (gọi thế nào cho chuẩn nhỉ, chắc là khoảng tài nguyên sử dụng), rồi còn 1 cái nữa là gì ấy em không biết.Và theo em nhìn qua thì đúng là nó

rất Toán

1 Like yuh (Huy) April 30, 2015, 1:14pm #12

Mà cái độ phức tạp này ý nghĩa thực tế thế nào nhỉ, nhìn nó rất Toán, không khiết có tính được ra tốc độ chạy code không

tính độ phức tạp này đâu có gì khó đâu

mà “độ phức tạp” với “tốc độ chạy code” (thời gian) là khác nhau

2 Likes thanhmssl10 (TP) April 30, 2015, 1:37pm #13 Thể nó tính được gì ạ ?

nhatlonggunz (nhatlonggunz) April 30, 2015, 1:38pm #14 Có lẽ là số bước ?20 char thanhmssl10 (TP) April 30, 2015, 1:40pm #15 Log hay lẻ lắm, số bước thì chắc phải nguyên chứ nhỉ

nhatlonggunz (nhatlonggunz) April 30, 2015, 1:43pm #16 Em đang viết bài về vụ này, có lẽ trong nay mai sẽ được thôi. Cái này rắc rối quá, đọc đi đọc lại nãy giờ. Giờ phải viết làm sao cho người ta hiểu.1 Like thanhmssl10 (TP) April 30, 2015, 1:47pm #17 A, anh tìm được tài liệu tiếng việt rồi, nhưng cái này phải biết giới hạn (lim: 1 khái niệm toán nhá, lớp 12 học), nhatlonggunz (nhatlonggunz) April 30, 2015, 1:49pm #18 Em đang làm bài về Asymptotic Notation (tiệm cận), không biết nó có liên quan đến độ phức tạp (complexity không) Gio (Gió) April 30, 2015, 1:50pm #19 Cái này mang tính học thuật quá. Nói chung là ước lượng thời gian chạy: O lớn, o nhỏ, Omega… nói chung là để tính thời gian chạy trong TH tốt, xấu, trung bình…1 Like Gio (Gió) April 30, 2015, 1:53pm #20 Thực ra là làm tròn lên, nhưng khi làm tròn nó chỉ dc cộng 1 số 0<=c< 1 nên bị bỏ qua.1 Likenext page →