29.2 Floyd Uorshall algoritmi Informatika sohasida Floyd-Uorshall algoritmi (Floyd algoritmi, Roy-Uorshall algoritmi, Roy-Floyd algoritmi yoki WFI algoritmi deb ham ataladi) ijobiy yoki manfiy qirrali yo'naltirilgan og'irlikli grafikdagi eng qisqa yo'llarni topish uchun algoritmdir. og'irliklar (lekin salbiy tsikllarsiz). Algoritmning bitta bajarilishi barcha cho'qqilar juftligi orasidagi eng qisqa yo'llarning uzunligini (yig'indisi og'irliklarini) topadi. Garchi u yo'llarning tafsilotlarini o'zi qaytarmasa ham, algoritmga oddiy o'zgartirishlar bilan yo'llarni qayta qurish mumkin. Algoritm versiyalari, shuningdek, {\displaystyle R}R munosabatining tranzitiv yopilishini yoki (Schulze ovoz berish tizimi bilan bog'liq holda) vaznli grafikdagi barcha cho'qqi juftlari orasidagi eng keng yo'llarni topish uchun ishlatilishi mumkin.
30.1 Fibonachchi algoritmi Matematik nuqtai nazardan Fibonachchi ketma-ketligi deganda quyidagi shartlarni bajaruvchi ketma-ketlikka aytiladi:
F(n) = F(n-1) + F(n-2) va F(0) = 0, F(1) = 1
Ta’rif: Har bir hadi o’zidan oldingi ikkita hadning yig’indisiga teng bo’lgan ketma-ketlik Fibonachchi ketma-ketligi deyiladi. Bunda boshlang’ish ikkita had ko’pincha 0 va 1 deb olinadi. Lekin, ixtiyoriy ikkita son boshlang’ish had sifatida olinishi ham mumkin.
(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … sonlari Fibonachchi ketma-ketligining dastlabki hadlari hisoblanadi.
Berilgan atamalar to'plami uchun Fibonachchi seriyasini topishimiz mumkin bo'lgan turli xil algoritmlar yoki usullar mavjud. Eng keng tarqalgan usullar quyidagilardir:
1. Rekursiyadan foydalanish
2. Rekursiyadan foydalanmasdan yoki Dinamik dasturlashdan foydalanmasdan
3. DPda fazoni optimallashtirilgan usul
Procedure Recursive_Fibonacci(n)
int f0, f1
f0 := 0
f1 := 1
if(n <= 1):
return n
return Recursive_Fibonacci(n-1) + Recursive_Fibonacci(n-2)
END Recursive_Fibonacci
