K54A3 - Students of A3
December 2016
MonTueWedThuFriSatSun
   1234
567891011
12131415161718
19202122232425
262728293031 

Calendar Calendar


Thuật toán đệ quy+Bài chữa bài tập về nha

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by nguyendnhat on Sun 04 Apr 2010, 1:16 am

Đệ quy là gì?
Đề quy như mình nhìn vào 2 cái gương gương kia sẽ chứa gường đối diện và trong anh trong gương ấy lại có chính gương này cứ thế vô hạn
Thuật toán đệ quy cũng thế nhưng khác ở chổ nó có điểm dừng là như kiểu mà khi nào thì gương kia không chứa gương này nữa hoặc là cho ra kết quả gì đấy (Thấy 1 bóng ma trong gương chẳng hạn :D)
nói khó hiêu nhỉ :D
Thôi ta vào thuật toán đệ quy luôn nha
để làm 1 bài toán theo tính đệ quy thì cần phải xác định 2 phân
1) Phần neo phần này có thể tính 1 cách đễ dàng không phải suy nghĩ nhiều phần neo rất quan trọng có phần neo mình mới tính được phần trên và phần neo thì xác định tính dừng của bài toán
2) Phần đệ quy khi mình không thể tính được như phần neo thì ta phân thành các bài toán con rồi giải các bài toán con ấy gộp các bài toán con lại với nhau thì được kết quả

Bây giờ mình giải bài Fibonacci (viết đúng không nhỉ :D) nha

function fibonacci (x,n)
if n<=1 then
return 1;
endif
fibonacci = fibonacci (n-1)+fibonacci (n-2);
endfunction

hic khó hiểu quá nhỉ?
mình giải thích nha
Đầu tiên là nguồn gốc
Fibonacci đã mô tả dãy các tổ tiên của một con ong đực như sau : (Loài ong có thể thụ tinh đơn tính hoặc lưỡng tính). Giả sử rằng:

* Nếu một trứng ong thụ tinh bởi chính con ong cái nó nở thành một con ong đực
* Tuy nhiên, nếu một trứng thụ tinh bởi một ong đực nó nở thành một con ong cái.
* Như vậy một con ong đực sẽ luôn có một mẹ, và một con ong cái sẽ có cả bố và mẹ.

Ta bắt đầu tính số các con ong tổ tiên của một con ong đực. Xét một con ong đực ở thế hệ thứ n.

* Trước một đời, thế hệ n-1: Con ong đực chỉ có một mẹ (1 ong cái).
* Trước hai đời, thế hệ n-2: Con ong cái đời n-1 có 2 bố mẹ, một ong bố (đực) và một ong mẹ (cái)(2 con ong: 1 đực+ 1 cái)) .
* Trước ba đời, thế hệ n-3: Con ong cái thế hệ n-2 lại có hai bố mẹ, một ong bố (đực) và một mẹ (cái), và con đực thế hệ n-2 có một mẹ (3 con ong :1 ong đực + 2 ong cái)
* Trước bốn đời,thế hệ n-4: Hai con cái, mỗi con có 2 cha, mẹ và mỗi con đực có một mẹ (5 con ong: 2 ong đực 3 ong cái)

Tiếp tục quá trình này ta sẽ có một dãy số Fibonacci.

mình chép từ Wikipedia đó
không cần xem đâu thực ra không quan trọng lắm :D
bây giờ là các giải của nó
chúng ta giả sử n=5
[You must be registered and logged in to see this image.]
chúng ta sẽ thấy là khi tính 1 giá trị thì nó luôn luôn mang về giá trị phần neo
nói nhiều quá rồi nếu ai không hiêu thì cứ post lên nha mình sẽ giải thích lại cặn kẽ hơn giờ phải làm việc khác rồi Ngủ :D

nguyendnhat

Tổng số bài gửi : 70
thanks : 0
Join date : 31/03/2010
Age : 25
Đến từ : Nghệ An

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by nguyendnhat on Sun 04 Apr 2010, 1:19 am

Ơ xin lỗi mọi người nha chèn ảnh không đúng kĩ thuật :D <a target='_blank' title='ImageShack - Image And Video Hosting' href='http://img688.imageshack.us/i/fibonacci.jpg/'><img src='http://img688.imageshack.us/img688/8440/fibonacci.jpg' border='0'/></a>

nguyendnhat

Tổng số bài gửi : 70
thanks : 0
Join date : 31/03/2010
Age : 25
Đến từ : Nghệ An

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by nguyendnhat on Sun 04 Apr 2010, 1:21 am

lại sai nữa rồi hic thương mình quá
[You must be registered and logged in to see this image.]

nguyendnhat

Tổng số bài gửi : 70
thanks : 0
Join date : 31/03/2010
Age : 25
Đến từ : Nghệ An

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by nam91 on Sun 04 Apr 2010, 9:10 pm

bác nhật cham chỉ thế,e phục bác quá .yêu cầu a admin cho bác nhật làm mode khu vực này nhé

nam91
Super Moderator
Super Moderator

Tổng số bài gửi : 406
thanks : 2
Join date : 03/02/2010
Age : 25
Đến từ : hà nội

Xem lý lịch thành viên

Về Đầu Trang Go down

hế hế a nhật nhà ta chăm chỉ quá đúng là thành viên n0.1 k54 SITclub ồ zé :d:d

Bài gửi by boconganhtronggio on Mon 05 Apr 2010, 5:50 pm


boconganhtronggio

Tổng số bài gửi : 82
thanks : 0
Join date : 05/04/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by kieutrang on Mon 05 Apr 2010, 6:09 pm

Ngưỡng mộ. Lần sau tiếp tục nhá

kieutrang

Tổng số bài gửi : 33
thanks : 0
Join date : 23/03/2010
Age : 24
Đến từ : Thanh Hóa vô đối

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by taday on Thu 08 Apr 2010, 12:29 am

này
bác Nhật ơi
thế f(0) thì vẫn ghi ra bằng 1 à
cái này có vẻ không hợp lí nha
theo tôi thì hàm sẽ là
function fibonacci
if n=o return 0;
if n=1 return 1;
else
fibonacci = fibonacci(n-1)+ fibonacci(n-2)
end function
ok

taday

Tổng số bài gửi : 46
thanks : 1
Join date : 04/04/2010
Age : 25
Đến từ : Bắc Giang

Xem lý lịch thành viên http://vn.360plus.yahoo.com/tuandvlgbg/

Về Đầu Trang Go down

Re: Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by nguyendnhat on Thu 08 Apr 2010, 12:31 am

Vẩn đúng mà tớ đã viết là n<=1 thì nó bao hàm cả n=0 và n=1 luôn
không phải làm 2 if cho dài làm cánh của cậu cũng được không sao cả

nguyendnhat

Tổng số bài gửi : 70
thanks : 0
Join date : 31/03/2010
Age : 25
Đến từ : Nghệ An

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by boconganhtronggio on Wed 14 Apr 2010, 11:47 pm

tớ thấy bạn taday nói đúng mà phải có 2 if chứ, với lại cái đối số trong phần tên hàm ý " function fibonaxi(x,n)" làm j có x, x có phải đối số trong hàm này đâu, chỉ có n thui theo t nghĩ là "function fibonaxi(n)"
bác nhật giải thích hộ e cái

boconganhtronggio

Tổng số bài gửi : 82
thanks : 0
Join date : 05/04/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by buithiphuong on Wed 21 Apr 2010, 10:51 pm

đồng chí Nhật rất đáng được tuyên dương

buithiphuong

Tổng số bài gửi : 30
thanks : 0
Join date : 19/04/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

Re: Thuật toán đệ quy+Bài chữa bài tập về nha

Bài gửi by Sponsored content Today at 6:30 pm


Sponsored content


Về Đầu Trang Go down

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết