الرئيسية › الدروس › الخوارزميات التراجعية

المتتاليات التراجعية وFibonacci والعدد الذهبي ومثلث باسكال

الفصل 22 · باك علوم الإعلامية

كل حدّ نحسبوه من اللي قبلو: المتتاليات، Fibonacci، العدد الذهبي، مثلث باسكال.

دروس هذا الفصل

المتتاليات التراجعية
Fibonacci والعدد الذهبي
مثلث باسكال

الدرس 22.1 : المتتاليات التراجعية

10 دقيقة

متتالية تراجعية من الدرجة 1 تعطي حدّ أوّل U0، وبعد قاعدة باش نتعدّاو من حدّ للّي بعدو: مثلا U(n) = 2 × U(n − 1) + 1. باش نحسبو U(n)، نبداو من U0 ونطبّقو القاعدة n مرّات.

متغيّر واحد u يكفي: u ← 2 × u + 1 تعوّض الحدّ القديم بالجديد.
كان لازم نخلّيو الحدود الكل، نحطّوهم في tableau: U[i] ← 2 × U[i − 1] + 1.

نصيحة : الـ boucle Pour i de 1 à n تطبّق القاعدة n مرّات بالضبط: بعدها، u تساوي U(n).

بـ Python

حدود U(n) = 2 × U(n − 1) + 1، بـ U0 = 1.

n = int(input())
u = 1
print("U0 =", u)
for i in range(1, n + 1):
    u = 2 * u + 1
    print("U" + str(i), "=", u)

بـ algorithme

convch(i) تلصق نومرو الحدّ في الاسم U.

Algorithme Suite
Début
  Lire(n)
  u ← 1
  Ecrire("U0 = ", u)
  Pour i de 1 à n Faire
    u ← 2 * u + 1
    Ecrire("U" + convch(i), " = ", u)
  FinPour
Fin

TDO
Objet | Type/Nature
n, u, i | Entier

الدرس 22.2 : Fibonacci والعدد الذهبي

11 دقيقة

متتالية Fibonacci من الدرجة 2: كل حدّ هو مجموع الزوز اللي قبلو. F0 = 0، F1 = 1، وبعد F(n) = F(n − 1) + F(n − 2): 0، 1، 1، 2، 3، 5، 8، 13…

لازم نخلّيو زوز متغيّرات، a (قبل الأخير) و b (الأخير).
في كل دورة: c ← a + b، وبعد a ← b و b ← c (بالترتيب هذا).

النسبة F(n) / F(n − 1) تقرب لـ العدد الذهبي φ = 1.6180339… نوقفو كي زوز نسب متتاليين يختلفو بأقل من eps.

انتبه : كان تكتب a ← b وبعد b ← a + b، تستعمل a الجديد: النتيجة غالطة. عدّي بـ c.

بـ Python

أوّل n حدود متاع Fibonacci (n ≥ 2).

n = int(input())
a = 0
b = 1
print(a)
print(b)
for i in range(2, n):
    c = a + b
    a = b
    b = c
    print(c)

بـ algorithme

ثلاثة متغيّرات، وترتيب الـ affectations مهم.

Algorithme Fibonacci
Début
  Lire(n)
  a ← 0
  b ← 1
  Ecrire(a)
  Ecrire(b)
  Pour i de 2 à n - 1 Faire
    c ← a + b
    a ← b
    b ← c
    Ecrire(c)
  FinPour
Fin

TDO
Objet | Type/Nature
n, a, b, c, i | Entier

الدرس 22.3 : مثلث باسكال

11 دقيقة

مثلث باسكال يحطّ المعاملات C(n, p) في matrice: السطر i فيه C(i, 0)، C(i, 1)، …، C(i, i). كل خانة هي مجموع الخانة اللي فوقها واللي فوقها على اليسار: M[i, j] ← M[i − 1, j] + M[i − 1, j − 1]. العمود الأول والقطر يساويو 1.

نصيحة : هي تراجعية من الدرجة 1 على الأسطر: كل سطر نحسبوه من اللي قبلو.

بـ Python

أوّل n أسطر من المثلث (الـ indices من 0 في Python).

n = int(input())
M = [[0] * n for i in range(n)]
for i in range(n):
    M[i][0] = 1
    M[i][i] = 1
    for j in range(1, i):
        M[i][j] = M[i - 1][j] + M[i - 1][j - 1]
for i in range(n):
    ligne = ""
    for j in range(i + 1):
        ligne = ligne + str(M[i][j]) + " "
    print(ligne)

بـ algorithme

في الـ algorithme، الأسطر والأعمدة من 1 لـ n.

Algorithme Pascal
Début
  Lire(n)
  Pour i de 1 à n Faire
    M[i, 1] ← 1
    M[i, i] ← 1
    Pour j de 2 à i - 1 Faire
      M[i, j] ← M[i - 1, j] + M[i - 1, j - 1]
    FinPour
  FinPour
  Pour i de 1 à n Faire
    ligne ← ""
    Pour j de 1 à i Faire
      ligne ← ligne + convch(M[i, j]) + " "
    FinPour
    Ecrire(ligne)
  FinPour
Fin

TDO
Objet | Type/Nature
M | Matrice de 20 lignes et 20 colonnes d'entiers
n, i, j | Entier
ligne | Chaîne

تدرّب مجانًا

كل درس فيه 3 تمارين مجانية مع تلميحات باش تطبّق الفصل هذا مع هنّيبوت.

افتح الفصل في Mission Carthage جرّب في الكومبيلاتور أونلاين

← الفصل اللي قبل : العودية (Récursivité) · الفصل اللي بعد : الملفات (Fichiers) →

كل الفصول · شوف فروض 2 تكنولوجيا المصلّحة

الدروس كتبناها لـ Mission Carthage على أساس البرنامج الرسمي. الأستاذ متاعك يبقى المرجع.