Discussion :

[Mandyy]

Bonjour à tous,

Je viens demander un peu d'aide sur un exercice.

Il me semble que c'est ok pour la question 1 par contre je ne comprends pas la question 2, même en ayant retourné dans ma tête tous les sens possibles.

Voici l'énoncé, merci par avance

[Obsidian]

Bonjour et bienvenue,

Il me semble que c'est ok pour la question 1 par contre je ne comprends pas la question 2, même en ayant retourné dans ma tête tous les sens possibles.

Ce n'est pas très difficile : une fonction récursive est une fonction qui fait référence à elle-même (et dans un programme informatique, c'est une fonction qui se rappelle elle-même). Dans la version itérative (avec boucle), tu examines une valeur et si ce n'est pas la bonne, tu te rabats sur les valeurs situées au dessus (de la valeur examinée exclue jusqu'à la fin de la table) ou au dessous (du début de la table jusqu'à la valeur examinée exclue) et tu cibles une nouvelle valeur dans cette plage au tour de boucle suivant.

Dans la version récursive, il te suffit de renvoyer la valeur examinée si c'est la bonne, ou la valeur de retour d'un appel à ta fonction sur la nouvelle plage dans le cas contraire. Le fait que ta fonction se rappelle elle-même va provoquer une sorte de « mise en abîme » dans laquelle ta fonction va se rappeler en cascade, jusqu'à ce que la condition d'arrêt soit atteinte (valeur trouvée ou plage restante réduite à l'ensemble nul).

[Mandyy]

Bonjour Obsidian et merci pour ta réponse,

Ton explication est très claire concernant les fonctions récursives, en fait je vois ce qu'est une fonction récursive et j'ai pu aussi comparer par analogie avec l'exemple très courant de la factorielle.
Mais ton explication m'aide j'ai l'impression car ca recadre pas mal les choses.

Ici ce qui me gênait, c'etait vraiment le sens de la question, pour moi ce n'etait pas clair.
Dans la première question, c'était très clair: je dois renvoyer le rang de x si il appartient au tableau.

Là je n'étais pas sure de ce que je devais renvoyer.

Autre chose, au début il parle d'un tableau trié mais pour ce que l'on fait ça n'a pas de sens puisque si le tableau est trié, on connait déjà le rang du x que l'on cherche, pire on a même pas à chercher x, à par dans le cas où on ne connait pas la taille du tableau et que x est grand.
Qu'en penses tu?

[Obsidian]

Bonjour,

… en fait je vois ce qu'est une fonction récursive et j'ai pu aussi comparer par analogie avec l'exemple très courant de la factorielle. Mais ton explication m'aide j'ai l'impression car ca recadre pas mal les choses. Ici ce qui me gênait, c'etait vraiment le sens de la question, pour moi ce n'etait pas clair.

C'est bien l'impression que j'en avais aussi à la lecture de ton message. Du coup, toute la subtilité consistait à exprimer cela sans révéler la solution.

Là je n'étais pas sure de ce que je devais renvoyer.

Effectivement : il faut faire une fonction qui rende exactement le même service, mais en suivant une approche récursive plutôt qu'itérative pour y arriver.

Autre chose, au début il parle d'un tableau trié mais pour ce que l'on fait ça n'a pas de sens puisque si le tableau est trié, on connait déjà le rang du x que l'on cherche, pire on a même pas à chercher x, à par dans le cas où on ne connait pas la taille du tableau et que x est grand. Qu'en penses tu?

C'est une excellente remarque mais attention, il y a une subtilité : le tableau doit être trié (suivant un ordre donc), mais rien ne dit qu'il doit être complet ! Si tu dois chercher l'existence du nombre « 7 » dans la suite [ 1, 3, 5, 8, 25, 32, 42, 78, 104 ] par exemple, rien ne te permet d'affirmer à l'avance que le chiffre s'y trouve. Par contre, le fait qu'elle soit triée et que l'on sache qu'elle contient neuf termes te permet de conclure d'emblée que tu auras forcément la réponse en un maximum de quatre tentatives.

[transgohan]

et que l'on sache qu'elle contient neuf termes te permet de conclure d'emblée que tu auras forcément la réponse en un maximum de quatre tentatives.

Oh c'est vil de voir de la dichotomie pour un problème aussi simple.

[Obsidian]

Oh c'est vil de voir de la dichotomie pour un problème aussi simple.

Pourquoi donc ?

[Mandyy]

Bonjour,



C'est bien l'impression que j'en avais aussi à la lecture de ton message. Du coup, toute la subtilité consistait à exprimer cela sans révéler la solution.



Effectivement : il faut faire une fonction qui rende exactement le même service, mais en suivant une approche récursive plutôt qu'itérative pour y arriver.



C'est une excellente remarque mais attention, il y a une subtilité : le tableau doit être trié (suivant un ordre donc), mais rien ne dit qu'il doit être complet ! Si tu dois chercher l'existence du nombre « 7 » dans la suite [ 1, 3, 5, 8, 25, 32, 42, 78, 104 ] par exemple, rien ne te permet d'affirmer à l'avance que le chiffre s'y trouve. Par contre, le fait qu'elle soit triée et que l'on sache qu'elle contient neuf termes te permet de conclure d'emblée que tu auras forcément la réponse en un maximum de quatre tentatives.

Bonjour bis!

Merci pour ton retour,

Bien vu pour le fait que le tri ne soit pas complet! Je n'y avais pas du tout pensé!

J'ai "fait" l'exercice en entier, c'est dommage car pour la dernière question j'ai une "conflicting type error" mais je n'arrive pas à voir ce qui pose problème
J'ai pensé à mettre le prototype avant le main.
Quoi qu'il en soit, ma fonction me parait très longue, j'ai un peu peur d'être à côté de la plaque ^^
Si je comprends bien il faut renvoyer l intersection entre le segment [min, max] et le segment [idx_lower, idx_upper]
La fonction binary_search retourne un int qui correspond à l'indice du x recherché.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
 
void slice(int *array, int size, int min, int max, int *idx_lower, int *idx_upper){
 
	int a = binary_search(array,min);
	int b = binary_search(array, max);
 
	if(*idx_lower < a && b < *idx_upper){
 
		size = b-a;
		for(int i = 0; i<size; i++){
			printf("%d\n", array[a] + i );
 
		}
	}
	else if(a > *idx_lower && b > *idx_upper){
 
		size = *idx_upper - a;
		for(int i = 0; i<size; i++){
			printf("%d\n", array[a] + i);
		}
	}
	else if(a < *idx_lower && b > *idx_upper){
		size = *idx_upper - *idx_lower;
		for(int i = 0; i<size; i++){
			printf("%d\n", array[*idx_lower] + i);
		}
	}else{
		size = b - *idx_lower;
		for(int i = 0; i<size; i++){
			printf("%d\n", array[*idx_lower] + i);
		}
 
 
	}
 
}

[Obsidian]

« Re, »

Bien vu pour le fait que le tri ne soit pas complet! Je n'y avais pas du tout pensé!

Oui mais justement : c'est une excellente chose d'être arrivée seule — et avant d'écrire la première ligne de code — à la conclusion que le problème est sans objet en l'absence de cette possibilité !

Quoi qu'il en soit, ma fonction me parait très longue, j'ai un peu peur d'être à côté de la plaque ^^
Si je comprends bien il faut renvoyer l intersection entre le segment [min, max] et le segment [idx_lower, idx_upper]

Pas tout-à-fait : il s'agit cette fois non plus de restreindre la recherche à un élément mais à une plage, plage dont tous les éléments sont compris entre minimum et un maximum. Donc en fait, ici, min et max ne changent jamais (ce sont les consignes initiales), et idx_lower et idx_upper sont les bornes de ta plage, qui au départ délimitent le tableau entier puis se rapprochent peu à peu jusqu'à cerner parfaitement la zone qui nous intéresse.

En fait, il s'agit simplement de mener deux binary_search en parallèle, une sur chaque borne. C'est aussi une manière utile d'exploiter le résultat de cette recherche si l'élément lui-même n'est pas trouvé. Il faudra juste penser à vérifier sur quel élément on se trouvait si on atteint l'ensemble nul (l'élément censé précéder la valeur cherchée ou censé la suivre) et comparer cela avec les consignes min et max pour être sûr de ne pas se tromper de borne finale.