Introducció
En aquest tema, introduirem els conceptes fonamentals dels algorismes. Un algorisme és una seqüència finita de passos ben definits que resolen un problema o realitzen una tasca específica. Els algorismes són essencials en la programació i la computació, ja que proporcionen les instruccions necessàries per a que els ordinadors puguin executar tasques de manera eficient.
Objectius
- Entendre què és un algorisme.
- Conèixer les propietats dels algorismes.
- Aprendre a representar algorismes.
- Veure exemples pràctics d'algorismes senzills.
Què és un Algorisme?
Un algorisme és una sèrie de passos o instruccions que es segueixen per resoldre un problema específic. Els algorismes poden ser simples, com una recepta de cuina, o molt complexos, com els que s'utilitzen en la criptografia.
Propietats dels Algorismes
Un bon algorisme ha de tenir les següents propietats:
- Finitud: L'algorisme ha de tenir un nombre finit de passos.
- Definitud: Cada pas de l'algorisme ha de ser clar i no ambigu.
- Entrada: L'algorisme ha de tenir zero o més entrades.
- Sortida: L'algorisme ha de produir una o més sortides.
- Eficàcia: Cada pas de l'algorisme ha de ser realitzable en un temps finit.
Representació d'Algorismes
Els algorismes es poden representar de diverses maneres, incloent:
- Pseudocodi: Una representació textual que utilitza una combinació de llenguatge natural i elements de programació.
- Diagrames de flux: Representacions gràfiques que mostren el flux de control de l'algorisme.
- Codi font: La implementació de l'algorisme en un llenguatge de programació específic.
Exemple de Pseudocodi
A continuació, es mostra un exemple de pseudocodi per a un algorisme que calcula la suma dels primers n nombres naturals:
Algorisme SumaPrimerNombres
Entrada: Un nombre enter n
Sortida: La suma dels primers n nombres naturals
Inici
suma ← 0
per i de 1 a n fer
suma ← suma + i
fi per
retornar suma
FiExemple de Diagrama de Flux
A continuació, es mostra el diagrama de flux corresponent a l'algorisme anterior:
Inici | v suma ← 0 | v i ← 1 | v i ≤ n? ---- No ----> Fi | Sí | v suma ← suma + i | v i ← i + 1 | v Torna a i ≤ n?
Exemples Pràctics
Exemple 1: Algorisme de Cerca Lineal
L'algorisme de cerca lineal busca un element en una llista recorrent-la seqüencialment fins a trobar l'element o arribar al final de la llista.
Pseudocodi:
Algorisme CercaLineal
Entrada: Una llista de n elements, un element x a cercar
Sortida: La posició de x en la llista o -1 si no es troba
Inici
per i de 0 a n-1 fer
si llista[i] = x llavors
retornar i
fi si
fi per
retornar -1
FiBloc de codi en Python:
def cerca_lineal(llista, x):
for i in range(len(llista)):
if llista[i] == x:
return i
return -1
# Exemple d'ús
llista = [2, 4, 6, 8, 10]
x = 6
resultat = cerca_lineal(llista, x)
print(f'Element trobat a la posició: {resultat}') # Sortida: Element trobat a la posició: 2Exemple 2: Algorisme de Cerca Binària
L'algorisme de cerca binària busca un element en una llista ordenada dividint repetidament la llista en meitats fins a trobar l'element o determinar que no està present.
Pseudocodi:
Algorisme CercaBinaria
Entrada: Una llista ordenada de n elements, un element x a cercar
Sortida: La posició de x en la llista o -1 si no es troba
Inici
esquerra ← 0
dreta ← n - 1
mentre esquerra ≤ dreta fer
mig ← (esquerra + dreta) / 2
si llista[mig] = x llavors
retornar mig
si no si llista[mig] < x llavors
esquerra ← mig + 1
si no
dreta ← mig - 1
fi mentre
retornar -1
FiBloc de codi en Python:
def cerca_binaria(llista, x):
esquerra, dreta = 0, len(llista) - 1
while esquerra <= dreta:
mig = (esquerra + dreta) // 2
if llista[mig] == x:
return mig
elif llista[mig] < x:
esquerra = mig + 1
else:
dreta = mig - 1
return -1
# Exemple d'ús
llista = [2, 4, 6, 8, 10]
x = 6
resultat = cerca_binaria(llista, x)
print(f'Element trobat a la posició: {resultat}') # Sortida: Element trobat a la posició: 2Exercicis Pràctics
Exercici 1: Algorisme de Suma de Nombres
Escriu un algorisme que calculi la suma dels primers n nombres parells.
Solució:
Pseudocodi:
Algorisme SumaPrimerNombresParells
Entrada: Un nombre enter n
Sortida: La suma dels primers n nombres parells
Inici
suma ← 0
per i de 1 a n fer
suma ← suma + 2 * i
fi per
retornar suma
FiBloc de codi en Python:
def suma_parells(n):
suma = 0
for i in range(1, n + 1):
suma += 2 * i
return suma
# Exemple d'ús
n = 5
resultat = suma_parells(n)
print(f'La suma dels primers {n} nombres parells és: {resultat}') # Sortida: La suma dels primers 5 nombres parells és: 30Exercici 2: Algorisme de Factorial
Escriu un algorisme que calculi el factorial d'un nombre n.
Solució:
Pseudocodi:
Algorisme Factorial
Entrada: Un nombre enter n
Sortida: El factorial de n
Inici
factorial ← 1
per i de 1 a n fer
factorial ← factorial * i
fi per
retornar factorial
FiBloc de codi en Python:
def factorial(n):
factorial = 1
for i in range(1, n + 1):
factorial *= i
return factorial
# Exemple d'ús
n = 5
resultat = factorial(n)
print(f'El factorial de {n} és: {resultat}') # Sortida: El factorial de 5 és: 120Resum
En aquest tema, hem après què és un algorisme i quines són les seves propietats fonamentals. Hem vist com representar algorismes utilitzant pseudocodi i diagrames de flux, i hem treballat amb exemples pràctics com la cerca lineal i la cerca binària. També hem practicat amb exercicis per reforçar els conceptes apresos. En el següent tema, explorarem els diferents tipus d'algorismes.
Curs d'Anàlisi i Disseny d'Algorismes
Mòdul 1: Introducció als Algorismes
Mòdul 2: Anàlisi d'Algorismes
- Anàlisi de Complexitat Temporal
- Anàlisi de Complexitat Espacial
- Cases de Complexitat: Millor, Pitjor i Promig
Mòdul 3: Estratègies de Disseny d'Algorismes
Mòdul 4: Algorismes Clàssics
- Cerca Binària
- Ordenació per Inserció
- Ordenació per Mescla (Merge Sort)
- Ordenació Ràpida (Quick Sort)
- Algorisme de Dijkstra
- Algorisme de Floyd-Warshall