Réponses aux exercices

Réponse à l'exercice 1

Q1

6 Il suffit de suivre l'évolution des différentes variables:

Elle affecte donc 0 aux variables A,B et C.

Réponse à l'exercice 2

Q1

6

Elle affecte 9 à X, Y et Z.

Réponse à l'exercice 3

Q1

7

Réponse à l'exercice 4

Q1

7

Néanmoins, cela ne marche que parce que les variables sont de type Entier. Ça ne marcherait pas avec des variables de type Caractère.

Réponse à l'exercice 5

Q1

7

Réponse à l'exercice 6

Q1

7

Réponse à l'exercice 7

Q1

7

Réponse à l'exercice 8

Q1

7

Réponse à l'exercice 9

Q1

7

Réponse à l'exercice 10

Q1

8 $A = {3}$, $B = {3}$, $C = {9}$

Q2

$A = {0}$, $B = {1}$, $C = {3}$

Q3

$A = {-4}$, $B = {-3}$, $C = {-12}$

Q4

$A = {9}$, $B = {9}$, $C = {9}$

Q5

$A = {11}$, $B = {11}$, $C = {100}$

Réponse à l'exercice 11

Q1

8

Réponse à l'exercice 12

Q1

9

Réponse à l'exercice 13

Q1

10

Réponse à l'exercice 14

Q1

13

Q2

int calcul_somme(int n) {
  int i, j, somme = 0;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= i; j++) {
      somme = somme + i + j;
    }
  }
  return (somme);
}

Réponse à l'exercice 15

Q1

13

Q2

int calcul_Fibonnacci_iteratif_simple(int n)
{
  int tab[100];
  int i = 2;

  if (n <= 0)
    return -1;
  tab[0] = 1;
  tab[1] = 1;
  for (i = 2; i <= n; i++) {
    tab[i] = tab[i - 1] + tab[i - 2];
  }
  return (tab[n]);
}

Réponse à l'exercice 16

Q1

13

Q2

int calcul_Fibonnacci_iteratif_ruse(int n)
{
  int tab[3];
  int i = 2;

  if (n <= 0)
    return -1;
  if (n <= 1)
    return 1;
  tab[2] = 1;
  tab[1] = 1;
  tab[0] = tab[1] + tab[2];
  for (i = 3; i <= n; i++) {
    tab[2] = tab[1];
    tab[1] = tab[0];
    tab[0] = tab[1] + tab[2];
  }
  return (tab[0]);
}

Réponse à l'exercice 17

Q1

13

Q2

int calcul_Fibonnacci_recursif(int n)
{
  int res = 0;

  if (n == 0)
    return 1;
  if (n == 1)
    return 1;
  res = calcul_Fibonnacci_recursif(n-1) + calcul_Fibonnacci_recursif(n-2);
  return (res);
}

Réponse à l'exercice 18

Q1

14

$f(n)$	$g(n)$	$f=\ensuremath{\mathcal{O}}\xspace (g)$	$g=\ensuremath{\mathcal{O}}\xspace (f)$	$f=o(g)$	$g = o(f)$	$f=\Theta(g)$
$n+1$	$n^4+3n -2$	Vrai	Faux	Faux	Vrai	Faux
$n+4$	$4n$	Vrai	Vrai	Faux	Faux	Vrai
$\frac{1}{10}n^3 + 100n^2 +10000$	$n^3$	Vrai	Vrai	Faux	Faux	Vrai
$2^{n+1}$	$2^n$	Vrai	Vrai	Faux	Faux	Vrai
$2^{2n}$	$2^n$	Faux	Vrai	Vrai	Faux	Faux
$(n+a)^b$	$n^b$	Vrai	Vrai	Faux	Faux	Vrai
$n^n$	$n!$	Faux	Vrai	Vrai	Faux	Faux
$2^n$	$n!$	Vrai	Faux	Faux	Vrai	Faux
$n$ si $n\equiv0[2]$ et 1 sinon	$n$	Vrai	Faux	Faux	Faux	Faux

Réponse à l'exercice 19

Q1

17

Q2

void affiche_tableau(int *tab, int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf("Tab[%d]=%d\n",i,tab[i])
  }
}

Réponse à l'exercice 20

Q1

17

Q2

void affiche_tableau(int *tab, int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf("Tab[%d]=%d\n",i,tab[i])
  }
}

Réponse à l'exercice 21

Q1

17

Q2

void lire_tableau(int *tab, int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf("Tab[%d]= ?\n",i);
    scanf("%d",&(tab[i]));
  }
}

Réponse à l'exercice 22

Q1

17

Réponse à l'exercice 23

Q1

17 Soit $\mathcal{A}$ UN algorithme qui résout le problème du MAX. Appliquons $\mathcal{A}$ à $[t[1]; t[2]; \dots ; t[n]]$, où $t[1]$ est le plus grand élément du tableau. Cet algo renvoie donc $t[1]$. On montre par l'absurde que tout élément qui n'est pas le maximum est comparé au moins une fois à un élément plus grand que lui : supposons que $t[2]$ ne soit pas comparé à plus grand que lui. Alors en appliquant $\mathcal{A}$ sur l entrée $[t[1]; t[1] + 1; t[3]; \dots ; t[n]]$, on ne va pas changer le déroulement précédent de l'algorithme et la réponse retournée est incorrecte, ce qui contredit l'hypothèse de départ. Comme il y a n-1 éléments qui ne sont pas le maximum, il y a au moins $n-1$ comparaisons.

Réponse à l'exercice 24

Q1

17

Réponse à l'exercice 25

Q1

26118

Q2

Il est facile de compter le nombre d'opérations nécessaires. À chaque itération, on démarre à l'élément $tab(i)$ et on le compare successivement à $tab(i+1),tab(i+2), \dots,tab(n)$. On fait donc $n-i$ comparaisons. On commence avec $i=1$ et on finit avec $i=n-1$. Donc on fait $(n-1)+(n-2)+\dots+2+1=n(n-1)/2$ comparaisons, et $n-1$ échanges. Le tri par sélection fait donc de l'ordre de $n^2$ comparaisons.

Q3

void tri_selection_sans_copie(int* tab,int taille){
  int i,j,x,ind_min;
  for(i=0;i<taille-1;i++){
    ind_min=i;
    for(j=i+1;j<taille;j++){
      if(tab[j]<tab[ind_min]){
       ind_min=j;
      }
    }
    x=tab[i];
    tab[i]=tab[ind_min];
    tab[ind_min]=x;
  }
}

Réponse à l'exercice 27

Q1

19

Q2

On peut compter aussi trés facilement le nombre d'opérations et se rendre compte qu'il s'agit d'un tri en $\Theta(n^2)$ comparaisons et $\ensuremath{\mathcal{O}}\xspace (n^2)$ échanges (si par exemple le tableau est donné en ordre strictement décroissant).

Q3

void tri_bulle(int* tab,int taille){
  int i,j,x;
  for(i=1;i<=taille-1;i++){
    for(j=0;j<taille-i;j++){
      if(tab[j]>tab[j+1]){
       x=tab[j];
       tab[j]=tab[j+1];
       tab[j+1]=x;
      }
    }
  }
}

Réponse à l'exercice 28

Q1

21

Q2

Q3

Q4

Q5

Une première méthode peu efficace...

Et une seconde bien plus efficace.

Q6

Q7

Réponse à l'exercice 29

Q1

26

Q2

Q3

Q4

On utilise bien sûr la fonction définie comme ci...

Réponse à l'exercice 30

Q1

26

Q2