الرئيسية › الدروس › البحث في tableau

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

1. البحث المتتالي (séquentielle)
2. البحث الثنائي (dichotomique)
3. عدّ وتعداد المرّات

الدرس 15.1 : البحث المتتالي (séquentielle)

9 دقيقة

الـ recherche séquentielle تشوف الخانات وحدة بوحدة، من البداية، حتى تلقى القيمة ولا توصل لآخر الـ tableau. تخدم على أي tableau، مرتّب ولا لا.

• نتقدّمو ما دمنا ما وصلناش للآخر و الخانة موش هي: Tant que (i ≤ n) et (T[i] ≠ x).
• بعد الـ boucle، كان i ≤ n، القيمة تلقات في البلاصة i. وإلا موش موجودة.

انتبه : ترتيب الزوز tests مهم: نثبّتو i ≤ n قبل ما نقراو T[i]، وإلا نقراو خانة موش موجودة.

نصيحة : بـ Tant que، الـ boucle توقف وحدها كيف نلقاو: ما يلزمش break في Python.

بـ Python

في Python الخانة الأولى هي 0: نكتبو الرتبة i + 1 باش نحكيو كيما في القسم (الأول، الثاني…).

t = [12, 7, 19, 4, 7]
n = len(t)
x = int(input())
i = 0
while i < n and t[i] != x:
    i = i + 1
if i < n:
    print("Trouvé au rang", i + 1)
else:
    print("Introuvable")

بـ algorithme

في الـ algorithme، الخانات من 1 لـ n: الرتبة هي i مباشرة.

Algorithme RechercheSeq
Début
  T[1] ← 12
  T[2] ← 7
  T[3] ← 19
  T[4] ← 4
  T[5] ← 7
  n ← 5
  Lire(x)
  i ← 1
  Tant que (i ≤ n) et (T[i] ≠ x) Faire
    i ← i + 1
  FinTantQue
  Si i ≤ n Alors
    Ecrire("Trouvé au rang ", i)
  Sinon
    Ecrire("Introuvable")
  FinSi
Fin

TDO
Objet | Type/Nature
T | Tableau de 5 Entiers
n, x, i | Entier

الدرس 15.2 : البحث الثنائي (dichotomique)

11 دقيقة

كي يكون الـ tableau مرتّب، نجمو نلوّجو أسرع برشا. الـ recherche dichotomique تشوف الخانة اللي في الوسط: كان هي القيمة، كمّلنا؛ كان القيمة اللي نلوّجو عليها أصغر، نخلّيو النص اليسار؛ وإلا النص اليمين. في كل دورة، منطقة البحث تتقسم على زوز.

• زوز حدود: inf (بداية المنطقة) و sup (آخر المنطقة).
• الوسط: m ← (inf + sup) div 2.
• كان x < T[m] إذن sup ← m - 1، وإلا inf ← m + 1.
• نوقفو كي نلقاو، ولا كي inf > sup (المنطقة فارغة).

انتبه : الـ recherche dichotomique تخدم كان على tableau مرتّب. على tableau مخلّط، تنجم تقول « ما لقيتش » والقيمة موجودة.

نصيحة : لـ 1000 خانة مرتّبة، الـ séquentielle تنجم تعمل 1000 مقارنة؛ الـ dichotomique تعمل 10 على الأكثر.

بـ Python

الـ tableau مرتّب. المتغيّر trouve يوقّف الـ boucle من غير break.

t = [3, 8, 11, 15, 20, 26, 31]
x = int(input())
inf = 0
sup = len(t) - 1
trouve = False
while inf <= sup and not trouve:
    m = (inf + sup) // 2
    if t[m] == x:
        trouve = True
    elif x < t[m]:
        sup = m - 1
    else:
        inf = m + 1
if trouve:
    print(x, "existe")
else:
    print(x, "n'existe pas")

بـ algorithme

نفس الـ algorithme بالخانات من 1 لـ 7.

Algorithme Dichotomie
Début
  T[1] ← 3
  T[2] ← 8
  T[3] ← 11
  T[4] ← 15
  T[5] ← 20
  T[6] ← 26
  T[7] ← 31
  Lire(x)
  inf ← 1
  sup ← 7
  trouve ← Faux
  Tant que (inf ≤ sup) et (Non trouve) Faire
    m ← (inf + sup) div 2
    Si T[m] = x Alors
      trouve ← Vrai
    Sinon Si x < T[m] Alors
      sup ← m - 1
    Sinon
      inf ← m + 1
    FinSi
  FinTantQue
  Si trouve Alors
    Ecrire(x, " existe")
  Sinon
    Ecrire(x, " n'existe pas")
  FinSi
Fin

TDO
Objet | Type/Nature
T | Tableau de 7 Entiers
x, inf, sup, m | Entier
trouve | Booléen

الدرس 15.3 : عدّ وتعداد المرّات

8 دقيقة

ساعات ما نوقفوش في أول مرّة نلقاو: نحبّو نعرفو قدّاش من مرّة تظهر القيمة (الـ fréquence، ولا عدد الـ occurrences)، ولا كل البلايص متاعها. وقتها نمرّو على الـ tableau الكل بـ boucle Pour.

• الـ fréquence: compteur nb ← 0، يزيد في كل خانة تساوي x.
• البلايص: نكتبو i في كل خانة تساوي x.

نصيحة : اختار الـ boucle حسب السؤال: Tant que لـ « موجودة ولا لا؟ » (نجمو نوقفو بكري)، Pour لـ « قدّاش؟ » (لازم نشوفو كل شيء).

بـ Python

نعدّو النقاط اللي تساوي النقطة اللي قريناها.

notes = [12, 15, 12, 9, 12, 15]
x = int(input())
nb = 0
for i in range(len(notes)):
    if notes[i] == x:
        nb = nb + 1
print("La note", x, "apparaît", nb, "fois")

بـ algorithme

boucle Pour على الـ 6 خانات، و compteur.

Algorithme Frequence
Début
  T[1] ← 12
  T[2] ← 15
  T[3] ← 12
  T[4] ← 9
  T[5] ← 12
  T[6] ← 15
  Lire(x)
  nb ← 0
  Pour i de 1 à 6 Faire
    Si T[i] = x Alors
      nb ← nb + 1
    FinSi
  FinPour
  Ecrire("La note ", x, " apparaît ", nb, " fois")
Fin

TDO
Objet | Type/Nature
T | Tableau de 6 Entiers
x, nb, i | Entier

تدرّب مجانًا

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

← الفصل اللي قبل : الفرز (Les tris) · الفصل اللي بعد : الحساب (Arithmétique) →

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

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