Taqsimlangan algoritmlar va tizimlar

Dinamik dasturlash misoli Fibonachchi ketma-ketligini 5-songacha topamiz. Fibonachchi seriyasi - bu har bir raqam oldingi ikkitasining yig'indisi bo'lgan raqamlar ketma-ketligi. Masalan, 0,1,1, 2, 3. Bu erda har bir raqam oldingi ikkita raqamning yig'indisidir. Fibonachchi raqamlari quyidagi butun qatordagi raqamlardir. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. Matematik nuqtai nazardan, Fibonachchi raqamlarining Fn ketma-ketligi takrorlanish munosabati bilan aniqlanadi.
Dastur kodi
# Botir Narziyev
# 30.04.2022
# Taqsimlangan algoritmlar va tizimlar
# Fibonachchi sonlari
nterms = int(input("Fibonachchi sonlari uzunligini kiriting? "))
n1, n2 = 0, 1
count = 0
if nterms <= 0:
print("Iltimos, musbat son kiriting")
elif nterms == 1:
print("Fibonachchi ketma-ketligigacha",nterms,":")
print(n1)
else:
print("Fibonachchi ketma-ketligi:")
while count < nterms:
print(n1)
nth = n1 + n2
n1 = n2
n2 = nth
count += 1
1-rasm Dastur natijasi


Topshiriq
F n ni qaytaruvchi int fib(int n) funksiyasini yozing . Misol uchun, agar n = 0 bo'lsa, u holda fib() 0 ni qaytarishi kerak. Agar n = 1 bo'lsa, u 1 ni qaytarishi kerak. n > 1 uchun F n-1 + F n-2 ni qaytarishi kerak. n = 9 uchun Chiqish: 34

1-usul (Rekursiyadan foydalanish) To'g'ridan-to'g'ri rekursiv amalga oshirish matematik takrorlanish munosabati bo'lgan oddiy usul keltirilgan.

2-rasm. Rekursiv funksiyadan foydalanib yozilgan dastur va uning natijasi

2-usul (Dinamik dasturlashdan foydalanish) Biz hozirgacha hisoblangan Fibonachchi raqamlarini saqlash orqali 1-usulda bajarilgan takroriy ishlardan qochishimiz mumkin.

3-rasm. Dinamik dasturlashdan foydalanib yozilgan dastur va uning natijasi
3-usul (optimallashtirilgan) Biz oldingi ikkita raqamni saqlash orqali 2- usulda foydalanilgan maydonni optimallashtirishimiz mumkin, chunki bu keyingi Fibonachchi raqamini ketma-ket olishimiz uchun kerak bo'lgan yagona narsa.


4-rasm. Dinamik dasturlashdan (optimallashgan)foydalanib yozilgan dastur va uning natijasi