Gandirea algoritmica

Problema căutării
Există şi cazul care, pentru o aceeaşi problem putem prezenta două soluţii, în care una este mai rapidă ca alta. De pildă, fie un şir de numere natural oarecare, de exemplu 4,2,10,1,8,15,7. Vream să testăm dacă un număr dat (să zicem numărul 8) se află în această secvenţă sau nu.

O astfel de căutare, prin parcurgerea de a stânga la dreapta a întregii secvenţe de numere, până se găseşte numărul dorit sau se epuiează toate elementele din secvenţă, se numeşte căutarea secvenţială. Dacă avem un şir S de n elemente (notat S[i..n]), atunci căutarea secvenţială a lui x în S se descrie prin:

Căutare_secventială(x,S[1. .n]) înseamnă
Început
  Fie elemental_curent = primul_element;
  Atăt timp cât (elemental_curent <> x) si (poziţia elementului current <= poziţia ultimului element (n)) execută   Început     Dacă elemental_curent = x atunci mesaj ("găsit")     Altfel treci la următorul element   Sfârşit Sfârşit.

În continuare să presupunem că numerele erau deja ordonate crescător 1, 2, 4, 7, 8, 10, 15. în acest caz particular, căutarea secvenţială a unui număr cum este 8 nu este prea eficientă, deoarece 8 se află în a doua jumătate a secvenţei, deci ar fi de preferat să nu-1 căutăm în prima jumătate. Acest procedeu este mai rapid:
• Dacă numărul din mijloc este mai mic decât numărul căutat, atunci căutăm a doua jumătate;
• Dacă numărul din mijloc este mai mare ca numărul căutat, atunci căutăm în prima jumătate;
• Dacă numărul din mijloc este egal cu numărul căutat, înseamnă că am găsit numărul în cauză şi trebuie să oprim căutarea.
Căutarea înjumătăţea aleasă se face tot la fel, deci se va înjumătăţi şi această zonă…

Procedeul anterior se numeşte căutare binară, deoarece, de fiecare dată, o secvenţă de numere este divizată în două jumătăţi. Putem descrie căutarea binară a unui număr x într-o secvenţă S[i..n] astfel.

Căutarea_binară(x,S[i..n]) înseamnă
Început
  Stabileşte elemental_eurent ca fiind elemental din mijlocul secvenţei;
  Daca n=1 atunci
    Dacă x = elemental_curent atunci mesaj (“găsit”)
    Altfel mesaj(“negăsit”)
  Altfel
    Început
      Împarte secvenţa în cele două jumătăţi (S[i..mijloc] si S[mijloc+i..n]);
      Dacă elemental_curent = x atunci mesaj (“găsit”)
    Altfel
      Dacă elemental_curent < x atunci Căutare_binară (x,S[mijloc+1..n]) Altfel căutarea_binară(x,S[1..mijloc])
    Sfârşit
Sfârşit.

Problema intrării într-un cabinet medical
Dacă un om vrea să intre pentru consult la un medic, atunci, mai întâi va bate la uşă: dacă medicul răspunde prin „poftim!”, atunci va intra, atlfel va aştepta până când pacientul dinăuntru va ieşi; abia după ce cabinetul va fi liber, va intra.

Intrare_la_medic înseamnă
  Început
    Bate la_uşă;
    Dacă răspunsul = “poftim!” atunci
      Întră_în_cabinet;
    Altfel
      Început
        Atât timp cât cabinetul_este_ocupat_de_alt_pacient execută
          Citeste_un_ziar;
      Sfârşit
Sfârşit.

O intrucţiune compusă este formată dintr-o secvenţă de intrucţiuni, încadrate de cuvinte început şi sfârşit, care pot conţine, la rândul lor, blocuri de alternativă şi repetiţie.
Programarea este tehnica realizării de algoritmi descrişi prin proceduri şi programe. Ea devine o artă, atunci când se folosesc cele trei elemente de structurate şi se numeşte programare structurată. Pentru a vedea ce ar însemna programare nestructurată, să reconsiderăm procedura de intrare în cabinetul medical:

Intare_la_medic înseamnă
Început
  Bate_la_uşă;
  Dacă răspunsul = “poftim!” atunci intră_în_cabinet;
  Altfel Început
    Atât timp cât cabinetul_este_ocupat_de_alt_pacient execută
      Citeste_un_ziar;
    Întră_în_cabinet
  Sfârşit
Sfârşit.

Leave a Reply

Your email address will not be published. Required fields are marked *

seven − 5 =

Time limit is exhausted. Please reload CAPTCHA.