DSA oddiy algoritm

Fibonachchi sonlari

Fibonachchi sonlari algoritmlar bilan tanishtirish uchun juda qulay, shuning uchun davom etishdan oldin Fibonachchi sonlari haqida qisqacha ma’lumot beramiz.

Fibonachchi sonlari Fibonachchi nomi bilan tanilgan XIII asr italyan matematigi sharafiga nomlangan.

Dastlabki ikkita Fibonachchi soni 0 va 1 ga teng, keyingi Fibonachchi soni esa har doim oldingi ikkita sonning yig‘indisiga teng bo‘ladi, shunday qilib 0, 1, 1, 2, 3, 5, 8, 13, 21, ... ketma-ketligini hosil qilamiz.

Ushbu darslikda sikllar va rekursiyadan ko‘p foydalaniladi. Shuning uchun davom etishdan oldin sikllar yordamida dasturlash va rekursiya yordamida dasturlash o‘rtasidagi farqni oddiy tarzda ko‘rish uchun Fibonachchi sonlarini hosil qiluvchi algoritmning uch xil versiyasini amalga oshiraylik.

Fibonachchi sonlari algoritmi

Fibonachchi sonini hosil qilish uchun oldingi ikkita Fibonachchi sonini qo‘shish kifoya.

Fibonachchi sonlari algoritm nima ekanini ko‘rsatishning yaxshi usulidir. Keyingi sonni qanday topish tamoyilini bilamiz, shuning uchun imkon qadar ko‘p Fibonachchi sonlarini hosil qiladigan algoritm yozishimiz mumkin.

Quyida dastlabki 20 ta Fibonachchi sonini hosil qilish algoritmi keltirilgan.

Sikllar va rekursiya

Sikllar va rekursiya o‘rtasidagi farqni ko‘rsatish uchun Fibonachchi sonlarini topish yechimlarini uch xil usulda amalga oshiramiz:

1. Yuqoridagi Fibonachchi algoritmini for sikli yordamida amalga oshirish.
2. Yuqoridagi Fibonachchi algoritmini rekursiya yordamida amalga oshirish.
3. Rekursiya yordamida \(n\)-Fibonachchi sonini topish.

1. For sikli yordamida amalga oshirish

Dasturlashdan oldin kod nimalarni o‘z ichiga olishi yoki nima qilishi kerakligini ro‘yxat qilib olish foydali bo‘lishi mumkin:

• Oldingi ikkita Fibonachchi sonini saqlash uchun ikkita o‘zgaruvchi
• 18 marta bajariladigan for sikli
• Oldingi ikkitasini qo‘shib, yangi Fibonachchi sonlarini hosil qilish
• Yangi Fibonachchi sonini chiqarish
• Oldingi ikkita Fibonachchi sonini saqlovchi o‘zgaruvchilarni yangilash

Yuqoridagi ro‘yxatdan foydalansak, dasturni yozish osonroq bo‘ladi:

prev2 = 0
prev1 = 1

print(prev2)
print(prev1)
for fibo in range(18):
    newFibo = prev1 + prev2
    print(newFibo)
    prev2 = prev1
    prev1 = newFibo

2. Rekursiya yordamida amalga oshirish

Rekursiya — funksiyaning o‘zini o‘zi chaqirishi.

Fibonachchi algoritmini amalga oshirish uchun yuqoridagi kod misolidagi narsalarning aksariyati kerak bo‘ladi, ammo for siklini rekursiya bilan almashtirishimiz lozim.

For siklini rekursiya bilan almashtirish uchun kodning katta qismini funksiya ichiga joylashtirishimiz kerak, shuningdek, hosil qilingan Fibonachchi sonlari soni 19 dan kichik yoki unga teng bo‘lgunicha yangi Fibonachchi sonini hosil qilish uchun funksiya o‘zini o‘zi chaqirishi kerak.

Kodimiz quyidagicha ko‘rinadi:

print(0)
print(1)
count = 2

def fibonacci(prev1, prev2):
    global count
    if count <= 19:
        newFibo = prev1 + prev2
        print(newFibo)
        prev2 = prev1
        prev1 = newFibo
        count += 1
        fibonacci(prev1, prev2)
    else:
        return

fibonacci(1,0)

3. Rekursiya yordamida \(n\)-Fibonachchi sonini topish

\(n\)-Fibonachchi sonini topish uchun \(n\)-Fibonachchi sonining matematik formulasiga asoslangan kod yozishimiz mumkin:

\[F(n) = F(n-1) + F(n-2) \]

Bu shunchaki, masalan, 10-Fibonachchi soni 9- va 8-Fibonachchi sonlarining yig‘indisiga teng ekanini anglatadi.

Bu g‘oyani rekursiya bilan qo‘llaganda, \(n\) 1 dan kichik yoki unga teng bo‘lgunicha funksiyaga o‘zini o‘zi chaqirishga imkon berishimiz mumkin. Agar \(n \le 1\) bo‘lsa, bu kod bajarilishi dastlabki ikkita Fibonachchi sonidan biriga — 1 yoki 0 ga yetib kelganini bildiradi.

Kod quyidagicha ko‘rinadi:

def F(n):
    if n <= 1:
        return n
    else:
        return F(n - 1) + F(n - 2)

print(F(19))

E’tibor bering, bu rekursiv metod o‘zini bir marta emas, ikki marta chaqiradi. Bu dasturning kompyuterimizda amalda qanday ishlashiga juda katta ta’sir qiladi. Biz olmoqchi bo‘lgan Fibonachchi sonining tartib raqamini oshirganimizda hisoblashlar soni keskin ortib ketadi. Aniqrog‘i, kerakli Fibonachchi sonining tartib raqamini bittaga oshirgan sari funksiya chaqiruvlari soni ikki baravar ko‘payadi.

\(F(5)\) uchun funksiya chaqiruvlari soniga bir nazar tashlang:

Kodni yaxshiroq tushunish uchun quyida rekursiv funksiya chaqiruvlari qiymatlarni qanday qaytarishi va natijada \(F(5)\) to‘g‘ri qiymatni qaytarishi ko‘rsatilgan:

Bu yerda ikkita muhim narsaga e’tibor bering: funksiya chaqiruvlari soni va funksiyaning bir xil argumentlar bilan necha marta chaqirilishi.

Shunday qilib, kod qiziqarli bo‘lsa va rekursiya qanday ishlashini ko‘rsatsa-da, uning amalda bajarilishi katta Fibonachchi sonlarini hosil qilishda foydalanish uchun juda sekin va samarasiz.

Xulosa

Davom etishdan oldin shu paytgacha ko‘rganlarimizni ko‘rib chiqaylik:

• Algoritmni turli usullarda va turli dasturlash tillarida amalga oshirish mumkin.
• Rekursiya va sikllar — algoritmlarni amalga oshirish uchun foydalanish mumkin bo‘lgan ikki xil dasturlash usuli.

Endi biz ko‘rib chiqadigan birinchi ma’lumotlar tuzilmasi — massivga o‘tish vaqti keldi.

Davom etish uchun "Keyingi" tugmasini bosing.

print(0)
print(1)
count = 2

def fibonacci(prev1, prev2):
    global count
    if count <= 19:
        newFibo = prev1 + prev2
        print(newFibo)
        prev2 = prev1
        prev1 = newFibo
        count += 1
        (prev1, prev2)
    else:
        return

fibonacci(1,0)