Algorithmes de NSI

def generer_liste_alea(n,maxi):
    return [random.randint(0,maxi) for i in range(n)]

def tri_selection(L):
    for i in range(len(L)-1):
        mini=i #indice
        for j in range(i+1,len(L)):
            if L[j]<L[mini]:
                mini=j
        if mini!=i:
            L[i],L[mini]=L[mini],L[i]
    return L

Liste des algorithmes à connaître en Spécialité NSI :

• Calcul de la moyenne d’une liste d’entiers

def moyenne(L):
    somme=0
    for elm in L:
        somme=somme+elm
    return somme/len(L)

• Calcul du quotient et du reste de la division euclidienne, sans faire de division :

def divisionEuclidienne(a,b):
    r=a
    q=0
    while r>=b:
        r=r-b
        q=q+1
    return (q,r)

• Comptage de l’occurrence d’un élément dans une liste

def compte(tab,valeur):
    cpt=0
    for elm in tab:
        if elm==valeur:
            cpt=cpt+1
    return cpt

• Recherche du maximum d’une liste ou de l’indice du maximum d’une liste donnée

L=[randint(0,100) for i in range(10)]

def rechercheMaxi(L):
    indiceMaxi=0
    for i in range(len(L)):
        if L[i]>L[indiceMaxi]:
            indiceMaxi=i
    return L[indiceMaxi],indiceMaxi

• Recherche du minimum d’une liste ou de l’indice du minimum d’une liste donnée

def rechercheMini(L):
    indiceMini=0
    for i in range(len(L)):
        if L[i]<L[indiceMini]:
            indiceMini=i
    return L[indiceMini],indiceMini

• Recherche dichotomique d’un élément dans une liste triée

def rechercheIndiceDicho(elm, T):
    #@pre T est une liste d'entier triée contenant l'élément cherché
    assert elm in T,"elm absent dans T"
    g = 0
    d = len(T)-1
    while g <= d:
        m = (g+d)//2
        if T[m] == elm :
            return m
        if T[m] < elm :
            g = m+1
        else :
            d = m-1

• Parcours d’une matrice :
  • Comptage : parcours total de la matrice
    • Recherche d’un élément avec un «return» qui stoppe le parcours total pendant la boucle for
• Tri par sélection d’une liste d’entiers :

def tri_selection(L):
    for i in range(len(L)-1):
        mini=i #indice
        for j in range(i+1,len(L)):
            if L[j]<L[mini]:
                mini=j
        if mini!=i:
            L[i],L[mini]=L[mini],L[i]
    return L

• Tri par insertion d’une liste d’entiers

from random import *
T=[randint(0,100) for i in range(10)]

def triParInsertion(T):
    n=len(T)
    for i in range(1,n):
        j=i
        x=T[i]
        while (j>0) and (T[j-1]>x):
            T[j]=T[j-1]
            j=j-1
        T[j]=x
    return T

• Recherche du zéro d’une fonction par dichotomie, dans un intervalle [a,b] donné
• Calcul de la valeur du nième terme d’une suite donnée, définie par une formule de récurrence ou par une formule explicite
• Calcul du rang k tel que Un>k
• Algorithme des k plus proches voisins