El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Implementació d'Algorismes

Següent ►
►

En aquest tema, explorarem com implementar algorismes en ALGOL. Aprendrem a traduir algorismes comuns en codi ALGOL, i veurem exemples pràctics que ens ajudaran a comprendre millor com treballar amb aquesta llengua de programació.

Objectius del Tema

  • Comprendre la importància dels algorismes en la programació.
  • Aprendre a implementar algorismes bàsics en ALGOL.
  • Practicar la traducció d'algorismes a codi ALGOL.
  • Resoldre problemes comuns utilitzant algorismes.

Contingut

  1. Què és un Algorisme?
  2. Algorismes de Cerca
    • Cerca Lineal
    • Cerca Binària
  3. Algorismes d'Ordenació
    • Ordenació per Bombolla
    • Ordenació per Inserció
  4. Algorismes de Divisió i Conquesta
    • Quicksort
  5. Exercicis Pràctics
  6. Conclusió

Què és un Algorisme?

Un algorisme és una seqüència finita de passos ben definits que resolen un problema o completen una tasca. Els algorismes són fonamentals en la programació perquè proporcionen una manera estructurada de resoldre problemes.

Algorismes de Cerca

Cerca Lineal

La cerca lineal és un algorisme senzill que busca un element en una llista recorrent-la seqüencialment fins a trobar l'element desitjat o arribar al final de la llista.

Exemple de Cerca Lineal en ALGOL

begin
  integer array A[1:10];
  integer i, n, key, pos;
  boolean found;

  A := (3, 5, 7, 9, 11, 13, 15, 17, 19, 21);
  n := 10;
  key := 15;
  found := false;
  pos := 0;

  for i := 1 step 1 until n do
    if A[i] = key then
      found := true;
      pos := i;
      exit;
    fi;
  od;

  if found then
    print("Element trobat a la posició: ", pos);
  else
    print("Element no trobat");
  fi;
end;

Explicació

  • Declarem un array A amb 10 elements.
  • Inicialitzem n amb la longitud de l'array i key amb l'element que volem buscar.
  • Utilitzem un bucle for per recórrer l'array.
  • Si trobem l'element, actualitzem found a true i guardem la posició.
  • Sortim del bucle amb exit i imprimim el resultat.

Cerca Binària

La cerca binària és un algorisme eficient per buscar un element en una llista ordenada dividint repetidament la llista a la meitat.

Exemple de Cerca Binària en ALGOL

begin
  integer array A[1:10];
  integer low, high, mid, key;
  boolean found;

  A := (3, 5, 7, 9, 11, 13, 15, 17, 19, 21);
  low := 1;
  high := 10;
  key := 15;
  found := false;

  while low <= high do
    mid := (low + high) div 2;
    if A[mid] = key then
      found := true;
      exit;
    elif A[mid] < key then
      low := mid + 1;
    else
      high := mid - 1;
    fi;
  od;

  if found then
    print("Element trobat a la posició: ", mid);
  else
    print("Element no trobat");
  fi;
end;

Explicació

  • Declarem un array A amb 10 elements ordenats.
  • Inicialitzem low i high amb els extrems de l'array i key amb l'element que volem buscar.
  • Utilitzem un bucle while per dividir l'array a la meitat.
  • Si trobem l'element, actualitzem found a true i sortim del bucle.
  • Imprimim el resultat.

Algorismes d'Ordenació

Ordenació per Bombolla

L'ordenació per bombolla és un algorisme senzill que ordena una llista comparant i intercanviant elements adjacents repetidament.

Exemple d'Ordenació per Bombolla en ALGOL

begin
  integer array A[1:10];
  integer i, j, n, temp;

  A := (21, 19, 17, 15, 13, 11, 9, 7, 5, 3);
  n := 10;

  for i := 1 step 1 until n-1 do
    for j := 1 step 1 until n-i do
      if A[j] > A[j+1] then
        temp := A[j];
        A[j] := A[j+1];
        A[j+1] := temp;
      fi;
    od;
  od;

  print("Array ordenat: ", A);
end;

Explicació

  • Declarem un array A amb 10 elements desordenats.
  • Utilitzem dos bucles for per comparar i intercanviar elements adjacents.
  • Imprimim l'array ordenat.

Ordenació per Inserció

L'ordenació per inserció és un algorisme que construeix l'array ordenat un element a la vegada, inserint cada nou element en la seva posició correcta.

Exemple d'Ordenació per Inserció en ALGOL

begin
  integer array A[1:10];
  integer i, j, n, key;

  A := (21, 19, 17, 15, 13, 11, 9, 7, 5, 3);
  n := 10;

  for i := 2 step 1 until n do
    key := A[i];
    j := i - 1;
    while j > 0 and A[j] > key do
      A[j+1] := A[j];
      j := j - 1;
    od;
    A[j+1] := key;
  od;

  print("Array ordenat: ", A);
end;

Explicació

  • Declarem un array A amb 10 elements desordenats.
  • Utilitzem un bucle for per recórrer l'array.
  • Inserim cada element en la seva posició correcta utilitzant un bucle while.
  • Imprimim l'array ordenat.

Algorismes de Divisió i Conquesta

Quicksort

Quicksort és un algorisme d'ordenació eficient que utilitza la tècnica de divisió i conquesta per ordenar una llista.

Exemple de Quicksort en ALGOL

procedure quicksort(A, low, high);
  integer array A;
  integer low, high;

  begin
    integer pivot, i, j, temp;

    if low < high then
      pivot := A[low];
      i := low;
      j := high;

      while i < j do
        while A[i] <= pivot and i < high do
          i := i + 1;
        od;
        while A[j] > pivot do
          j := j - 1;
        od;
        if i < j then
          temp := A[i];
          A[i] := A[j];
          A[j] := temp;
        fi;
      od;

      A[low] := A[j];
      A[j] := pivot;

      quicksort(A, low, j-1);
      quicksort(A, j+1, high);
    fi;
  end;

begin
  integer array A[1:10];
  integer n;

  A := (21, 19, 17, 15, 13, 11, 9, 7, 5, 3);
  n := 10;

  quicksort(A, 1, n);

  print("Array ordenat: ", A);
end;

Explicació

  • Definim una funció quicksort que ordena l'array A utilitzant la tècnica de divisió i conquesta.
  • Utilitzem un pivot per dividir l'array en dues parts.
  • Ordenem recursivament les dues parts.
  • Imprimim l'array ordenat.

Exercicis Pràctics

Exercici 1: Cerca Lineal

Implementa una funció que realitzi una cerca lineal en un array de nombres enters i retorni la posició de l'element buscat.

Exercici 2: Ordenació per Bombolla

Implementa una funció que ordeni un array de nombres enters utilitzant l'algorisme d'ordenació per bombolla.

Exercici 3: Quicksort

Implementa una funció que ordeni un array de nombres enters utilitzant l'algorisme Quicksort.

Conclusió

En aquest tema, hem après a implementar diversos algorismes en ALGOL, incloent algorismes de cerca, ordenació i divisió i conquesta. Hem vist exemples pràctics i hem practicat la traducció d'algorismes a codi ALGOL. Aquests coneixements són fonamentals per resoldre problemes de programació de manera eficient.

En el següent tema, explorarem la construcció d'un compilador simple en ALGOL, aplicant els coneixements adquirits fins ara.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats