LeClubInfo / ci-site

algorithmie.md 12.1 KB

title: "Introduction Algorithmie" tags: c algo author: "Benoit 'badetitou' Verhaeghe" license: WTFPL

license_url: http://www.wtfpl.net/

De l'algorithmie au C

Bonjour, Ceci est un petit livre récapitulatif de l'ensemble de ce que l'on à vu en Algorithmie et en C.

Attention. Ceci n'est qu'un récapitulatif. Vous ne pouvez pas prétendre tout savoir avec seulement ces connaissances.

Des exemples ?

Algorithmie

Action ou Fonction

Introduction

L'algorithmie est la partie de la conception où nous devons réfléchir à notre programme avant de le transcrire dans un vrai langage de programmation.

Il est évident que pour créer un programme informatique complexe, le plus simple est de le diviser en plusieurs sous programme simple. C'est ce que nous appelons les actions et les fonctions.

Action

Les actions sont une des manières de diviser son programme. Elle est composé d'un nom, est d'une suite de paramètres.

Action <nom d'action> (paramètres)
|    D   : <Déclaration> {Signification}
|    R   : <Déclaration> {Signification}
|    D/R : <Déclaration> {Signification}
|    VL  : <Déclaration> {Signification}
|    
|    <Corps>
FinAction

L'ensemble des lettres correspondent à l'utilité des paramètres.

  • Données : Information Utilisées
  • Résultats : Informations produites
  • Données/Résultats : Informations modifiées
  • Variables Locales : Informations temporaires au déroulement de l'algorithme

Fonctions

La fonction fonctionne de la même manière qu'une action. Les principales différences sont l'ajout d'un type de retour. L'absence de paramètre de type Résultat ou Données/Résultat.

Fonction <nom d'action> (paramètres) : Type de retour
|    D   : <Déclaration> {Signification}
|    VL  : <Déclaration> {Signification}
|    
|    <Corps>
|
|    Retourner <variable du type indiquer>
FinAction

Les types

Listes des types

Voici une liste non exhaustive des types existant en algorithmie

  • Entier
  • Réel
  • Caractère
  • Chaîne de Caractère
  • Booléen (Vrai ou Faux)
  • Vecteur de "Type" de taille "Entier"
  • Matrice de "Type" de dimensions "Entier","Entier"
  • Structures

Operation de base

Entier, Réel, Caractère, Chaîne de caractère

Ce sont ici les type de base avec lesquels nous allons le plus travailler.

Comme le nom l'indique les variable de type entier permette de stocker un entier dans la mémoire. De même que un réel permet de stocker un réel est une chaîne de caractère un caractère.

Affectation

Prenons A et B deux variable de type Entier. Et C de type Réel.

Pour enregistrer une valeur dans une variable nous utiliserons la notation suivante : A<-9. Je stocke la valeur '9' dans la variable 'A'

Nous pouvons maintenant affecter cette valeur à une autre variable : B<-A

Et si nous faisions C<-B ? Alors C était une variable pour les réel. Elle convertirai 9 en un nombre de type réel.

Que ce passe-t-il si je stocke un Réel dans un Entier ?

Le réel sera tronqué, ça veut dire qu'on enlève tout ce qui a après la virgule.

C<-9.7
B<-C
Afficher B {Affiche '9'}

Le fonctionnement est le même pour les Chaînes de Caractères

Addition..Soustraction..Multiplication..Division..Modulo

Les variables comportant des nombres (Entier, Réel, Caractère (cf : Table ASCII)) supporte l'ensemble des opération ci-dessus. Le modulo étant le reste de la division entière.

ATTENTION : Réel/Entier->Réel ET Entier/Réel->Réel

Opérateur :
+ : Addition
- : Soustraction
/ : Division
* : Multiplication
% : Modulo

Format : A(opérateur)B

Booléen

Les booléen (ou boolean dans la langue de shakespeare) sont des variables pouvant contenir soit VRAI soit FAUX. Il est possible de les combiner via les opération suivante :

  1. ET : VRAI ET FAUX -> FAUX
  2. OU : VRAI OU FAUX -> VRAI

Bref elles respectent l’Algèbre de Boole (logique)

Exemple d'affectation

Une affectation simple.

A<-VRAI

Une affectation par évaluation

B<-5
A<- B<2
Afficher A {Affiche FAUX}
A<- B=5
Afficher A {Affiche VRAI}

Vecteur et matrice

Les vecteurs (ou tableau) ainsi que les matrices (tableau à plusieurs dimension) sont la manière la plus simple de stocker un grand ensemble d'information.

En algorithmie la première case du table est la case 1. La dernière la case n (=correspondant à sa dimension).

Exemples :

Comprendre les Boucles

* Parcours de Tableau

Action affiche_element (v, n) : { Affiche les element 1 à 1 de mon vecteur}
    | D : v Vecteur d'entier de taille n
    | D : n Entier
    | VL: i Entier
    |
    | Pour i de 1 à n Faire
    |   | Afficher v[i]
    | FinPour
    |
FinAction
  • Remplissage de Tableau
Action affiche_element (v, n) : { Affiche les element 1 à 1 de mon vecteur}
    | R : v Vecteur d'entier de taille n
    | D : n Entier
    | VL: i Entier
    |
    | Pour i de 1 à n Faire
    |   | Lire v[i]
    | FinPour
    |
FinAction
  • Parcours de Matrice
Action affiche_element (n,m, Mat) : { Affiche les element 1 à 1 de mon vecteur}
    | D : Mat Matrice d'entier de dimension n,m
    | D : n Entier
    | D : m Entier
    | VL: i Entier
    | VL: j Entier
    |
    | Pour i de 1 à n Faire
    |   | Pour j de 1 à m Faire
    |   |   | Afficher v[i][j]
    |   | FinPour
    | FinPour
    |
FinAction
  • Remplissage de Matrice
Action affiche_element (Mat, n,m) : { Affiche les element 1 à 1 de mon vecteur}
    | D : Mat Matrice d'entier de dimension n,m
    | D : n Entier
    | D : m Entier
    | VL: i Entier
    | VL: j Entier
    |
    | Pour i de 1 à n Faire
    |   | Pour j de 1 à m Faire
    |   |   | Lire Mat[i][j]
    |   | FinPour
    | FinPour
    |
FinAction

Structures

Les structures permettent aux concepteurs de créer leurs propres type, les rendant ainsi plus libre dans la conception et leurs facilitant le travail pour des sujets complexe.

type <ST> = structure
            | <Nom Variable> : <Type>
            | <Nom Variable> : <Type>
            | <Nom Variable> : <Type>
            Fin

Structure de contrôle

Introduction

Il faut toujours avoir à l'esprit que le programmeur est un fainéant. Il a donc naturellement construit des outils pour lui facilité le travail. Certains de ces outils sont sans aucun doutes les structures de contrôle. Elle permette d'utiliser un même programme dans plusieurs cas différent et de simuler l'écriture d'un nombre non calculable de ligne en seulement trois ou quatre.

Alternative

Les alternative permette de tester si une condition est vrai, et dans ce cas, exécuter ou non un certain nombre de commande. En Algorithmie nous appelons ça le SI..Fin SI

Une Condition est en réalité une expression booléenne.

Exemple

Le code suivant affiche "bleu"

A<-1
B<-2
SI (A<B) FAIRE
|   Afficher "bleu"
FinSi

Maintenant avec un booléen

A<-1
B<-2
C<- FAUX
SI (A<B ET C) FAIRE
|   Afficher "bleu"
FinSi

Ici le code n'affiche rien car d'après l'algèbre de Boole VRAI ET FAUX ->FAUX

Boucle

Les boucles sont les structures permettant de répéter plusieurs fois le même code. Elles sont divisé en deux grands groupe. Celle qui "boucle" un nombre de fois définit. Et celle qui continue tant qu'une condition est rempli.

Tant Que

La boucle tant que est celle du deuxième type. Elle entoure du code qui sera effectuer tant que une condition est rempli.

TantQue A<B Faire
|   <code>
FinTantQue

Attention. Vous devez vous assurer que la condition A<B passe à FAUX un moment. Sinon vous créer une boucle infini.

I<-12
TantQue A<B ET I<56Faire
|   <code>
|   I<-I+1
FinTantQue

Pour

La boucle Pour ne doit être utilisé que lorsque vous connaissez exactement le nombre de fois que vous souhaitez répéter le code

B<-1
A<-12
Pour I de B à A Faire
|   Afficher "Je repete du code"
|   Afficher I
|   Afficher fois
FinPour

Le C

Nous supposerons que vous avez déjà lu la partie sur l'Algorithmie. Tout ne sera donc pas décrit ici.

La base

En C tout est fonction. Cela signifie que les Actions n'existent pas. Une action sera donc représenter par une Fonction sans type de retour void

Les fonctions

Une fonction est composé de deux grandes parties.

Tout d'abord le prototype. Il est composé du type de retour, du nom de la fonction et enfin des paramètres.

Puis le corps de la fonction composé de l'ensemble des instruction à exécuter. Le corps est entouré par deux accolade { <coprs> }

La fonction principal appelé au début de l'exécution du programme est le main. Elle accepte deux paramètre qui correspondent au arguments que nous donnerons à notre programme depuis notre shell.

Main

int main(int argc, char* argv[]){ <corps> } ###Exemple fonction

int multiplication (int a, int b){ // Prototype
    return (a*b);                  // Corps de la fonction
}

Nous voyons que les fonctions ce termine par la 'commande' return suivit d'une variable correspondant au type de retour.

Exemple fonction/action

Comme expliqué ci-dessus. En C les actions sont représenté par une fonction sans type de retour;

void hello_world(){
    printf("Hello World !");
}

Instructions

Une instruction est une commande à exécuter en C suivit de ses paramètres entre parenthèses et fini par un ';'.

Type en C

Tout les types peuvent être représenter en C. Mais nous allons diviser les types primitifs et les autres.

Types primitifs

  1. int : Entier
  2. float : Réel (taille normal)
  3. double : Réel (taille plus grande)
  4. char : Caractère.

Exemple

int i, j; // Déclaration de deux variable de type Entier.
i = 3; // Affectation de la valeur 3 à i

Tableau (Vecteur)

Un tableau est déclaré par le type du tableau, suivi de son nom suivit de deux crochets avec la taille du tableau.

En C, et en programmation de manière générale, on commence à compter en 0. La première case du tableau est donc la case 0.

Un tableau de caractère permet donc de représenter une chaîne de caractère.

Exemple

int i[12]; // Déclaration d'un tableau de 12 Entiers
char j[30] = "Bonjour"; // Déclaration d'une chaîne de caractère et son affectation.

Structures

Afin de définir des types plus complexe nous pouvons créer des Structures en C. Une structure peux aussi être composé d'élément étant des structrues.

typedef struct {
    int a;
    double b;
    MaStruct c;
} NomDeMaStructure;

Pointeur :-(

En C les variables peuvent être passé de différente manière au fonction. Nous pouvons donner la valeur de la variable ou son adresse dans la mémoire. C'est ce que l'on appelle les pointeurs.

Pour récupérer l'adresse mémoire d'une variable il suffit d'utiliser l'opérande & avant le nom de la variable. Pour accéder à la place ciblé par un pointeur il faut utiliser l'opérande * placé devant la variable.

Il ne faut pas utiliser les pointeurs pour les tableaux. Un tableau est déjà utilisé comme un pointeur en C

Exemple

Avec pointeur :

void affecte(int *a){
    *a = 2;
}

int main(void){
    int a = 1;
    affecte(&a);
    printf("%d",a); // Affiche 2
    return 0;
}

Sans pointeur :

void affecte(int a){
    a = 2;
}

int main(void){
    int a = 1;
    affecte(a);
    printf("%d",a); // Affiche 1
    return 0;
}

Tableaux :

void rempli(int t[]){
    int a;
    for(a=0;a<12;++a){
        scanf("%d", t[a]);
    }
}

int main(void){
    int t[12];
    rempli(t);
    return 0;
}

C - Structure de contrôle

Les structures de contrôle sont similaire en C et en Algorithmie.

Alternative ... Exemple

int a = 1;
if (a == 1){
    <corps si vrai>
} else if (a == 2) {
    <corps si vrai>
} else {
    <corps si tout le reste est faux>
}

Boucle Pour ... Exemple

int a;
for(a=0;a<12;a++){
    <Corps>
}

Boucle TantQue ... Exemple

int a = 0;
int b = 1;
while (a<b){
    <Corps>
}