Exercices sur les algorithmes de recherche

Écrivez une fonction qui renvoie la plus petite valeur d’un tableau non trié de N cases. Quelle est la complexité de cet algorithme ?

Correction

FONCTION MIN(↕t: TABLEAU ENTIER, N: ENTIER)
VARIABLE i: ENTIER
VARIABLE val <- +∞

POUR i DE 0 À N-1:
    SI val > t[i]:
       val <- t[i]
    FIN SI
FIN POUR

RETOURNER val
FIN FONCTION

def MIN(t, n):
    r = float("infinity")
    for i in range(0, n):
        if t[i] < r:
            r = t[i]
    return r

#include <limits.h>
int MIN(int t[], int n) {
    int val = INT_MAX;
    for( int i = 0; i<n; i++ ) {
        if( t[i] < val )
            val = t[i];
    }
    return val;
}

Écrivez une fonction qui renvoie la plus petite valeur d’un tableau croissant de N cases. Quelle est la complexité de cet algorithme ?

Correction

FONCTION MIN_TRI(↕t: TABLEAU ENTIER, N: ENTIER)
    RETOURNER t[0]
FIN FONCTION

def MIN_SORT(t, n):
    return t[0]

int MIN(int t[], int n) {
    return t[0];
}

Écrivez une fonction qui compte le nombre de fois que se trouve une valeur dans un tableau croissant de N cases.
- Astuce: quid si la valeur est plus grande que la plus grande valeur du tableau ?

Correction

FONCTION COUNT(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
    VARIABLE i, cpt: ENTIER
    cpt <- 0

    TANT QUE t[i] <= val ET val <= t[N-1]:
        SI val = t[i]:
           cpt <- cpt + 1
        FIN SI
        i <- i+1
    FIN POUR
    RETOURNER cpt
FIN FONCTION

def COUNT(t, n, val):
    cpt = 0
    i = 0
    while t[i] <= val and val <= t[n-1]:
        if val == t[i]:
            cpt = cpt +1
        i = i +1
    return cpt

int COUNT(int t[], int n, int val) {
    int cpt = 0;
    while( t[i] <= val && val <= t[n-1] ) {
        if( val == t[i] )
            cpt++;
    }
    return cpt;
}

Écrivez une fonction qui renvoie l’indice de la case dans laquelle se trouve une valeur d’un tableau non trié de N cases. Si la valeur n’est pas présente, renvoyer la valeur -1.

Correction

FONCTION FIND(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
VARIABLE i: ENTIER

POUR i DE 0 À N-1:
    SI val = t[i]:
       RETOURNER i
    FIN SI
FIN POUR

RETOURNER -1
FIN FONCTION

def FIND(t, n, val):
    for i in range(0, n):
        return i
    return -1

int FIND(int t[], int n, int val) {
    for( int i=0; i<n; i++) {
        if( val == t[i] )
            return i;
    }
    return -1;
}

Écrivez une fonction qui renvoie l’indice de la case dans laquelle se trouve une valeur dans un tableau croissant de N cases. Si la valeur n’est pas présente, renvoyer la valeur -1. Pour cet exercice, utiliser la recherche linéaire. Quelle est la complexité de cet algorithme ?

Correction

FONCTION FIND_LINEAR_ORDERED(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
    VARIABLE i: ENTIER
    i <- 0
    TANT QUE i < N ET t[i] <= val
        SI val = t[i]:
           RETOURNER i
        i <- i + 1
    FIN TANT QUE
    RETOURNER -1
FIN FONCTION

def FIND_LINEAR_ORDERED(t, n, val):
    i = 0
    while i < n t[i] <= val:
        if val = t[i]
            return i
        i++
    return -1

int FIND_LINEAR_ORDERED(int t[], int n, int val) {
    int i = 0;
    while( i < n && t[i] <= val ) {
        if( val == t[i] )
            return i;
        i++;
    }
    return -1;
}

Écrivez une fonction qui renvoie l’indice de la case dans laquelle se trouve une valeur dans un tableau croissant de N cases. Si la valeur n’est pas présente, renvoyer la valeur -1. Pour cet exercice, utiliser la recherche dichotomique. Quelle est la complexité de cet algorithme ?

Correction

FONCTION FIND_DICHOTOMIC(↕t: TABLEAU ENTIER, N: ENTIER, val: ENTIER)
    VARIABLE g, d, c: ENTIER
    g <- 0
    d <- N-1

    RÉPÉTER
        c = (g+d)/2
        SI t[c] == val:
            RETOURNER c
        SINON SI t[c] < val:
            g = c+1
        SINON SI:
            d = c-1;
        FIN SI
    TANT QUE ( g < d )
    RETOURNER -1
FIN FONCTION

def FIND_DICHOTOMIC(t, n, val):
    g = 0
    d = n-1
    while g < d:
        c = (g+d)/2
        if t[c] == val:
            return c
        elif t[c] < val:
            g = c+1
        else:
            d = c-1
    return -1

int FIND_DICHOTOMIC(int t[], int n, int val) {
    int c;
    int g = 0;
    int d = n-1;
    do {
        c = (g+d)/2;
        if( t[c] == val )
            return c;
        else if( t[c] < val )
            g = c+1;
        else
            d = c-1;
    } while( g < d );
    return -1;
}

Exercices sur les algorithmes de recherche

Leave A Reply Annuler la réponse.

Login with your site account

Register a new account