_tutos/algorithmie.md

---
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 ? ](https://drive.google.com/open?id=0Bxnrqy9eZ2mXYWxpRnpQSXM0VHc)
# 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](http://www.asciitable.com/))) 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)](https://www.wikiwand.com/fr/Alg%C3%A8bre_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](structure_de_controle.md)
*
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](les_types.md).
### 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>
}
```