Vous n'êtes pas identifié(e).
L'icône rouge permet de télécharger chaque page du wiki visitée au format PDF et la grise au format ODT →
Ceci est une ancienne révision du document !
Soit une chaîne de caractères terminée par un caractère '.'.
Donnez l'algorithme d'un programme qui compte la longueur de cette chaîne (“.” non compris).
chaine de caractères —→| calcul des caractères de la chaîne |—> nombre de lettres de la phrase
CONSTANTE point = '.' // caractère d'arrêt nbremax = 100 // nombre max de caractères TYPE chaîne tableau[taille] de caractères VARIABLES taille_phrase : entier // taille réelle de la chaîne de caractère entrée'' i : entier // indice de parcours de la phrase nombre_lettre // Nombre d'occurrence de la lettre cherchée
chainedecaractère | nombredelettre |
---|---|
“.” | 0 |
“a.” | 1 |
“ab.” | 2 |
(C'est la notice d'utilisation de la procédure pour le programme qui utilisera cette procédure.)
L'interface de procédure (procédure décrite en pseudo-langage)
procédure compterchainedecaractère (entrée chainedecaractère : chaine sortie nombredecaractère : entier) //compterchainedecaractère : compte le nombre de caractère de la chaîne //chainedecaractère : suite de plusieurs caractères éventuellement espace d'espace et terminée par un point //nombredecaractère : nombre de caractère qui ont été" rentrés
chainedecaractère
: nom du paramètre
chaine
: c'est le type tableau créé pour le paramètre “chainedecaractère ”
nombredecaractère
: c'est le nom de la variable de sortie qui aura pour valeur le résultat (elle est de type prédéfini “entier”.)
CONSTANTES point = '.' // caractère d'arrêt nbremax = 100 // nombre max de caractères TYPES chaine = tableau [n] caractere VARIABLES chainedecaractere : chaine nombredelettre : entier PROCEDURES procédure compterchainedecaractère (entrée chainedecaractère : chaine ; sortie nombredecaractère : entier) //compterchainedecaractère : compte le nombre de caractère de la chaîne //chainedecaractère : suite de plusieurs caractères éventuellement espace d'espace et terminée par un point //nombredecaractère : nombre de caractère qui ont été" rentrés début écrire ('entrez une phrase') lire (chainedecaractère) compterchainedecaractère (chainedecaractère, nombredelettre) écrire ('le nombre de caractère est', nombredelettre) fin
procédure compterchainedecaractère (ENTREE chainedecaractère : chaine ; SORTIE nombredecaractère : entier) // entrée et sortie sont des mots réservés //compterchainedecaractère : compte le nombre de caractère de la chaîne //chainedecaractère : suite de plusieurs caractères éventuellement espace d'espace et terminée par un point //nombredecaractère : nombre de caractère qui ont été" rentrés i : entier //indice début i := 1 tantque chainedecaractere [i] <> point faire i := i + 1 fintantque nombredecaractère := i-1 fin
Rechercher si deux lettres choisies par l'utilisateur sont dans une phrase entrée par l'utilisateur.
schéma procédure | | phrase ----------->|cherche si deux |------> si caractère1 ET caractère2 sont dans la phrase et successifs | | alors terminateur |lettres succ | deuxlettres = VRAIE caractère 1 ------->| dans | caractère 2 ------> | cette phrase |
CONSTANTES\\ terminateur = '.' // caractère d'arrêt\\ TYPES\\ chainetableau tableau[MAX] caractère\\ VARIABLES\\ phrase : caractère\\ car1 : caractère\\ car2 : caractère\\ nbr : entier\\
phrase | terminateur | caractère1 | caractère2 | nombre |
---|---|---|---|---|
blablobli. | '.' | “l” | “r” | 0 |
bonjour. | '.' | “b” | “.” | 0 |
blablo. | '.' | “b” | “l” | 2 |
blablobli. | '.' | “b” | “l” | 3 |
vérifier si une phrase contient deux lettres
PROCEDURE
procédure DeuxLettresID ( entrée phrase : chainetableau ;\\ sortie nbreoccurrence : entier )\\ // CompterDeuxLettres : procédure qui recherche deux lettres successives et définies extérieurement dans une phrase terminée par un point\\ // phrase : phrase saisie par l'utilisateur\\ //nbreoccurrence : décompte du nombre d'occurrence de mot contenant deux lettres successives\\
chainetableau
: c'est le type créé
CONSTANTES max = 100 TYPES chaine tableau[MAX] caractère VARIABLES phrase : chaine lettre 1 : caractère lettre 2 : caractère nbreoccurrence : entier début écrire ("entrez une phrase terminée par un point") lire (phrase) écrire ("entrez une première lettre") lire (lettre 1) écrire ("entrez une deuxième lettre") lire (lettre 2) DeuxLettresID ( entrée phrase : chainetableau , sortie nbreoccurrence : entier ) écrire ("le nombre d'occurrences des lettres choisies dans la phrase donnée est", nbreoccurrence") fin
CompterDeuxLettres( lettre phrase chaine entrée car1 : caractère car2 : caractère FIN : caractère sortie occurrence : entier VARIABLE i : entier occurrence : 0 début i := 1 occurrence := 0 tantque (phrase [i] <> FIN) si (phrase[i] = car1) si (phrase [i + 1] = car2 occurrence + 1 finsi finsi i := i + 1 fintantque fin
Procédure pour déterminer si une chaîne de caractère terminée par un point est un palindrome.
chaîne. —> | recherche palindrome | —> palindr : booléen (Vrai ou FAUX)
i (indice ->) 1 2 3 4 5 | 6 |... | MAX ---------------------------------- | L | A | V | A | L | . | j (indice <-|.| )
'.' | c'est un palindrome |
'a.' | c'est un palindrome |
'aa.' | c'est un palindrome |
'aba.' | c'est un palindrome |
'acb' | ce n'est pas un palindrome |
'aacba.' | ce n'est pas un palindrome |
'aacab | ce n'est pas un palindrome |
CONSTANTES taille =80 //nombre max de caractères de la chaîne carterm ='.' // caractère terminaleur de la chaîne TYPE chaine =tableau[taille] de caractères // type crée pour contenir une liste VARIABLES phrase : chaine // phrase où une symétrie est recherchée i : entier // j : entier // indice de parcours de la phrase depuis la fin.
procédure cherchePalinPoint(entrée texte : chaine, entrée sortie ind1 : entier, ind2 : entier) // Cette procédure permet de dire si une chaine de caractère terminée par un point est un palindrome. // ind1 : c'est l'indice de parcours du texte par le début // ind2 : c'est l'indice de parcours du texte par la fin
CONSTANTES constante MAX =80 //nombre max de caractères de la chaîne (Pour pouvoir créer le type chaine, car un tableau est toujours de taille fixe. constante FIN ='.' // caractère terminaleur de la chaîne (Un tableau peut ne pas être tout rempli) TYPES Type chaine =tableau[MAX] de caractères // type crée pour contenir une liste VARIABLES variable possPalin : chaine // phrase où une symétrie est recherchée variable indiceDeb : entier // variable indiceFin : entier // indice de parcours de la phrase depuis la fin. PROCEDURES procédure cherchePalinPoint(entrée texte : chaine, entrée sortie ind1 : entier, ind2 : entier sortie result : booléen) // Cette procédure permet de dire si une chaine de caractère terminée par un point est un palindrome. // ind1 : c'est l'indice de parcours du texte par le début // ind2 : c'est l'indice de parcours du texte par la fin Début // Saisie de la phrase : ECRIRE ('Entrez votre phrase et n'oubliez pas de la terminer par un point.' LIRE(phrase) indiceDeb := possPalin[1] indiceFin := possPalin[MAX-1] result := booléen // Recherche d'un palindrome fini par un point : cherchePalinPoint(entrée possPalin:chaine , entrée/sortie ind1:entier, entrée/sortie ind2:entier, sortie result:bool) SI result = VRAI ECRIRE('La phrase', possPalin 'est un palindrome.') SINON ECRIRE('La phrase', possPalin 'n'est pas un palindrome.') FINSI Fin
procédure cherchePalinPoint(entrée texte : chaine, entrée sortie ind1 : entier, ind2 : entier sortie result: booléen) // Cette procédure permet de dire si une chaine de caractère terminée par un point est un palindrome. // ind1 : c'est l'indice de parcours du texte par le début // ind2 : c'est l'indice de parcours du texte par la fin CONSTANTE MAX : 80 TYPE chaine = tableau[MAX] de caractères VARIABLES i : entier j : entier palindrome : booléen TERM : '.' : caractère début i := chaine[1] j := chaine[TERM - 1] SI chaine[i] < chaine[j] ALORS palindrome := VRAI TQ (i < j) ET (chaine[i] = chaine[j]) i := i + 1 j := j - 1 FinTQ SINON palindrome := FAUX FINSI fin
| | liste désordonnée de chiffre---> | |----> liste ordonnés par ordre croissant | |
Entrée sortie ------------------------------------ rien rien 5 0 5293741 123479
CONSTANTES constante MAX = 80 TYPES table =Tableau[MAX] de entiers VARIABLES variable chiffresDesordo : table //Table d'entiers désordonnés variable nbrchiffre : entier // Nombres de chiffres variable taille : entiers // Taille de la table de chiffres désordonnés en entrée // et ordonnée en sortie
CONSTANTES constante MAX = 80 TYPES table =Tableau[MAX] de entiers VARIABLES variable chiffresDesordo : table //Table d'entiers désordonnés variable nbrchiffre : entier // Nombres de chiffres variable taille : entiers // Taille de la table de chiffres désordonnés en entrée // et ordonnée en sortie PROCEDURES procédure saisie procédure triBulle procédure affichage Début saisie(chiffresDesordo, nbrchiffre, taille) // appel de la procédure saisie triBulle(chiffresDesordo, taille) // appelle de la procédure triBulle affichage(chiffreOrdonnés, taille) // appelle de la procédure affichage Fin
Procédure tribulle ( entrée taille : entier entrée/sortie chiffresDesordo : table entrée/sortie chiffreOrdonnés : table) // **la procédure du tri des bulles** permet de ranger une chaîne de chiffres //désordonnés en ordre croissant. // **chiffresDesordo** est la liste de chiffres désordonnés rentrée par l'utilisateur ainsi que la liste de chiffres triés en sortie. // **taille** est le nombre de chiffres rentrés par l'utilisateur. // **invert** est vrai quand il y a eu inversion
variable i : entier // indice de parcours du tableau. cible : entier // variable permettant l'inversion de 2 entiers dans le tableau. invert : booléen // Permet de déterminé s'il y a ou non inversion Début // parcours jusqu'à qu'il n'y est plus aucune inversion. i := 1 invert := FAUX Répéter Tantque ( i < taille ) faire SI table[i] > table[ i + 1 ] ALORS // si l'entier "1 " du tableau //est supérieur à l'entier "2" // suivant dans le tableau alors. cible = table[1] table[1] = table[i + 1] table[i+1] = cible invert := VRAI Finsi i := i + 1 // incrémentation pour passer aux entiers suivants. Fintantque Jusquà invert = faux Fin
//exo: tri par remontée des bulles I] Procédure "remplir" Procédure remplir ( sortie tab_désordonné : les_chiffres_donnés, sortie tableau_donné : entier ) // La procédure remplir permet de récupérer les données saisies par l'utilisateur. // les_chiffres_donnés : c'est la table de chiffres rentrés par l'utilisateur. // taille_tableau_donné : c'est la taille de la table. Variables taille_finale : entier // nombre de tous les chiffres rentrés par l'utilisateur. chiffre_donnés : entier // les chiffres rentrés par l'utilisateur pour mettre //quelque chose dans la tableau //(l'utilisateur ne rentre pas forcément 80 chiffres) Début // l'utilisateur rentre la taille de la table d'entier et ses valeurs. Répéter Ecrire ( 'Quel sera le nombre de nombres à trier?' ) // taille du tableau à trier //( sup à 0 , // non égal à 1, // stric inf à 80) Lire ( taille_finale ) Jusquà ( taille_finale >= 0 ) et ( taille_finale < = MAX ) Ecrire ( "Vous allez entrer", taille_finale, "chiffres" ) // remplir le tableau chiffre_donnés := 1 // initialisation l'utilisateur n'a pas encore donné ses chiffres à trier Tantque ( chiffre_donnés <= taille_finale ) Faire Ecrire ( 'Veuillez donner un autre entier" ) // on demande ensuite les entiers à l'utilisateur // pour chaque case du tableau. Lire ( taille_finale [ chiffre_donnés ] ) chiffre_donnés := chiffre_donnés + 1 // Incrémentation pour mettre les autres //entiers dans le tableau. Fintantque Fin /////////////////////////////////////////////////////////////////////// II] procédure "afficher" Procédure affichage ( entrée table_utilisateur : listechiffre, entrée taille_table : entier ) // La procédure permet l'affichage du tableau de chiffre de l'utilisateur et le tableau trié // table_utilisateur est la table de chiffre rentré par l'utilisateur. //listechiffre est le type crée (un tableau) // taille_table définie la taille de la table. Variables nombre_chiffre_affichage : entier // compte le nombre de chiffres rentré par l'utilisateur. Début nombre_chiffre_affichage := 1 Tantque ( nombre_chiffre_affichage <= taille_tableaffichage ) Faire Ecrire ( ",liste_chiffre, [",nombre_chiffre_affichage," ] = ",taille_table [nombre_chiffre_affichage] ) nombre_chiffre_affichage := nombre_chiffre_affichage + 1 Fintantque Fin
VOIR les tris :http://axiomcafe.fr/tri-dans-un-tableau
// recherche dichotomique GENERALITE méthode de recherche par dichotomie : exemple i | a | b | c | d | e | ...| j i = début j = fin milieu = tab(i[1] + i[n]) / 2 si cible > milieu alors cible est à chercher sur tab[milieu][j] si cible < milieu alors cible est à chercher sur tab[i][j] ///////////////////////// 1) Analyse du problème : deux programmes : 1) crée la table de prénom 2) chercher un prenom dans la table entrée Faire_table sortie prénom cherché --------------------------------------------------------------------------------------------------------- | enregistre | | les prénoms | et numérote |-> une table | résultat : prénom dans la table | les prénoms | de prenoms numérotés | ou | entrés | (max 10) | pas dans la table ---------------------------------------------------------------------------------------------------------- //////////////////////////////////////////////////////////////////// PROGRAMME crée la table de prénom et enregister le prenom recherché ///////////////////////////////////////////////////////////////////// On sait que la taille de la table de prénom est égale au nombre de prénoms entrés CONSTANTES nombre_de_prenom = 10 // taille max de la table taille_prenom = 15 // taille max d'un prenom TYPE prenom =tableau[nombre_de_prenom] de caractère table =tableau[nombre_de_prenom] de prenom VARIABLES i : entier // compteur de prénoms entrée nombre_de_prenom : entier // Nombre de prenoms entrés par l'utilisateur table_prenom : table de prenom prenom : prenom // prénom cherché resultat : entier début i := 0 // Pas encore de prénom entrés écrire("combien de prenom ?") lire(nombre_de_prenom) TANTQUE ( i < nombre_de_prenom ) FAIRE i := i + 1 écrire(Entrez un prénom, svp.) lire( table_prenom[i] ) FINTANTQUE // enregistrer le prénom à chercher ecrire(Pour quel nom voulez-vous l'indice ?) lire(prenom) //appel procédure cherche_prenom chercher_prenom(table , nombre_de_prenom, prenom , resultat) SI resultat = 0 ALORS écrire ("Le prénom n'est pas dans la liste") SINON écrire ("Le prénom est dans la table au n° ", resultat) fin ////////////////////////////////////////////////////////////////////// Programme chercher le prénom ///////////////////////////////////////////////////////////////////// VARIABLES indice_début : entier // Début de table de prénom indice_fin : entier // fin de la table de prénom indice_moyen : entier // milieu de la table de prénom TYPE prenom =tableau[nombre_de_prenom] de caractère table =tableau[nombre_de_prenom] de prenom procédure chercher_prenom(entrée tableEnregistrée :table entrée taille :entier entrée prenom_cherché :prenom sortie indice : entier) // taille c'est place du prénom par rapport à la taille totale de la table de prénom // cible c'est le n° du prenom dans la table de prénom début indice_début := 1 indice_fin := taille cible := (indice_début + indice_fin) DIV 2 TANTQUE (indice_début < indice_fin) ET (table [cible] <> prenom_cherché) FAIRE SI tableEnregistrée[cible] > prenom_cherché ALORS indice_fin = cible - 1 //du milieu à la fin de la table de prénom SINON indice_début := cible + 1 //du début jusqu'au milieu de la table de prénom FINSI cible := (indice_début + indice_fin) DIV 2 FINTANTQUE SI (indice_début > indice_fin ) OU ( table [cible] <> prenom_cherché) ALORS cible := 0 FINSI fin