Bài toán giai thừa

[Hoc cao]

Đề 2010

Xét hàm tính giai thừa bằng giải thuật đệ quy như sau:
{

if (n==0) return 1;

else

return n*giaithua(n-1);

}
a. Viết công thức đệ quy tính thời gian thực hiện chương trình con (hàm).
b. Tính độ phức tạp của thuật toán chứa chương trình con. 

Xin mời mọi người cho ý kiến!

[Hoc cao]

rattonwing:

vừa vặn giải thuật này mới dùng để viết tool, cái này trên mạng có thể sẽ ghi độ phức tạp vì nó quá common nhưng thử sức xem sao.

khi n=0 ta đc O(1)

khi vừa thả n vào hàm factorial để chạy thì lại đc O(1)

ta đc O(n+1), ngắt râu ria đi mình còn O(n)

là kết quả câu b, còn công thức rõ ràng thì chịu ko bít viết :-P

giải thuật này nguyên thủy chỗ xét đk là:

if (n==0 || n==1) return 1;

làm vậy mình sẽ giảm đc 1 vòng đệ quy khi n>0

Mình cũng đã viết cái tool để tính C, P, n! chờ ngày up lên host đến lúc thi móc di động có gprs ra tính nếu ko có máy tính ( ngặt nỗi mình ko có cả 2 T_T)

ngoài 3 phép tính đó bạn nào nhắc mình nhớ thêm để viết nốt

và đáp án bài này tìm đc ở trang:

http://stackoverflow.com/questions/2327244/complexity-of-recursive-factorial-program

 

Từ: Hoc cao <it_cao...@yahoo.com.vn>
Đến: "caoh...@googlegroups.com" <caoh...@googlegroups.com>
Đã gửi 20:01 Thứ Hai, 3 tháng 10 2011
Chủ đề: Bài toán giai thừa

[Tran Minh Hung]

Tôi vừa đọc được cái nay nên đưa len cho moi người xem.

Xét hàm tính giai thừa viết bằng giải thuật đệ quy như sau:

      FUNCTION Giai_thua(n:Integer): Integer;

         BEGIN

             IF n=0 then Giai_thua :=1

             ELSE Giai_thua := n* Giai_thua(n-1);

         END;

Gọi T(n) là thời gian thực hiện việc tính n giai thừa, thì T(n-1) là thời gian thực hiện việc tính n-1 giai thừa. Trong trường hợp n = 0 thì chương trình chỉ thực hiện một lệnh gán Giai_thua:=1, nên tốn O(1), do đó ta có T(0) = C1. Trong trường hợp n>0 chương trình phải gọi đệ quy Giai_thua(n-1), việc gọi đệ quy này tốn T(n-1), sau khi có kết quả của việc gọi đệ quy, chương trình phải nhân kết quả đó với n và gán cho Giai_thua. Thời gian để thực hiện phép nhân và phép gán là một hằng C2. Vậy ta có

T(n) = C1 nếu n=0 hay T(n)= (n-1)+ C2 nêu n>0

Ðây là phương trình đệ quy để tính thời gian thực hiện của chương trình đệ quy Giai_thua.

2011/10/3 Hoc cao <it_cao...@yahoo.com.vn>

--
                  Trần Minh Hùng
Truong Cao dang Phat thanh-Truyen hinh II

Trung tâm đào tạo nghề công nghệ cao

                     Giám đốc

           tranh...@gmail.com
          hung...@yahoo.com.vn
          tranh...@hotmail.com
       

[Hoc cao]

Chào anh,

Anh có thể gửi cho mọi người tài liệu đó để tham khảo không?

Cám ơn anh nhiều!

---

Từ: Tran Minh Hung <tranh...@gmail.com>
Đến: caoh...@googlegroups.com
Đã gửi 15:08 Thứ Tư, 5 tháng 10 2011
Chủ đề: Re: Bài toán giai thừa

[Silverwolf]

Công thức của anh Hùng đưa ra là đúng rồi đó. Bây giờ mình làm câu b
nhé

Tức là giải PT: T(n) = C1 khi n=0 và T(n) = T(n-1)+C2 khi n>0

Ta có:
T(n) = T(n-1) + C2
= (T(n-2) + C2) + C2 = T(n-2) + 2C2
= T(n-i) + iC2

PT kết thúc khi n-i = 0 hay n = i

=> T(n) = T(0) + nC2 = C1 + nC2

Theo quy tắc Big-O thì độ phức tạp của thuật toán là O(C1+nC2)=O(n)

[Hoc cao]

bravo bạn Silverwolf!

sau khi dò lại 4 lần đoạn sau mình đã rõ, cách giải thích chính thống vầy mình ko có, mà ko có thì chắc mất điểm phần này, đa tạ!

T(n) = C1 khi n=0

= T(n-i) + iC2

PT kết thúc khi n-i = 0 hay n = i

=> T(n) = T(0) + nC2

Từ: Silverwolf <ton...@gmail.com>
Đến: Cao Học <caoh...@googlegroups.com>
Đã gửi 20:44 Thứ Tư, 5 tháng 10 2011
Chủ đề: Re: Về: Bài toán giai thừa