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 ?

[transgohan]

Oh bah j'ai cherché trop loin alors... Il n'y avait aucune subtilité dans ton message.
J'en suis déçu vu la teneur de la discussion jusque là. Rembourser !!!!!

Je croyais que tu voulais dire qu'avec un tableau de 9 valeurs on pouvait trouver n'importe laquelle en 4 lecture maximum.
Ce qui ne peut se faire qu'avec de la dichotomie.

Parce que du coup si tu as le tableau suivant : [ 1, 2, 3, 4, 5, 6, 7, 78, 104 ]
Tu ne la trouveras pas en moins de 4 lectures sans dichotomie.

[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]

Je croyais que tu voulais dire qu'avec un tableau de 9 valeurs on pouvait trouver n'importe laquelle en 4 lecture maximum.
Ce qui ne peut se faire qu'avec de la dichotomie. Parce que du coup si tu as le tableau suivant : [ 1, 2, 3, 4, 5, 6, 7, 78, 104 ]
Tu ne la trouveras pas en moins de 4 lectures sans dichotomie.

Tout-à-fait, mais c'est bien l'objet de l'exercice : regarde l'énoncé donné en pièce jointe du premier commentaire…

La PO avait juste des difficultés à concevoir la version récursive de la fonction en question.

[transgohan]

Il faut vraiment que j'apprenne à lire les énoncés moi...

[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.

[Mandyy]

Tout d'abord merci pour tes encouragements

Oui comme c'est une fonction void elle ne renvoie rien, je voulais dire cerner l'intersection sus-mentionnée dans mon précédent commentaire, en espérant ( car je n'ai pas encore vérifié ), que faire un printf dans cette fonction ne compte pas comme renvoyer qqch.

Ce qui m'ennuie je te l'avoue c'est de ne pas avoir compris l'énoncé en fait.
Je pensais que dans l'idéal, une fois que le programme compile et fonctionne pour les cas où "tout se passe bien", il aurait fallu le compléter en prenant en compte qu'un utilisateur distrait pourrait prendre min qui soit plus grand que max, des idx_lower ou idx_upper qui soit hors tableau etc...
Je pensais donc devoir dans un premier temps faire une fonction qui gère les différents intervalles.

Si j'avais pu interpréter comme tu l'as fait, que min et max sont fixés et que idx_lower (resp idx_upper) part du début (resp de la fin) du tableau ça m'aurait facilité la tâche.
Cependant c'est plutôt logique du coup de faire appel aux fonctions définies plus tôt dans l'exercice, c'est aussi pour cela que je trouvais mon code suspect ^^ normalement on se sert tôt ou tard des premières questions.

Je vais donc reprendre mon code, mais je ne vois quand même pas pourquoi le compilateur me met conflicting type error :



Dans tous les cas merci pour ton temps Obsidian

[Obsidian]

Oui comme c'est une fonction void elle ne renvoie rien, je voulais dire cerner l'intersection sus-mentionnée dans mon précédent commentaire, en espérant ( car je n'ai pas encore vérifié ), que faire un printf dans cette fonction ne compte pas comme renvoyer qqch.

Non, non, ne t'inquiète pas. Par « valeur de retour », on entend la valeur qui est renvoyée par la fonction en fin de calcul, ce qui, mathématiquement, correspond en fait à la valeur de la fonction elle-même, dans le sens où l'on dit bien que « cos(0) vaut 1 » et non que « cos(0) renvoie 1 ». C'est pourtant bien ce qui va se passer dans les faits mais il s'agit en fait d'une valeur renvoyée en sortie par une procédure à qui l'on a confié ce calcul, soit pour être exact : « déterminer la valeur du cosinus de zéro ».

Un programme qui est appelé par un autre, au sein d'un même logiciel, et qui permet à cet autre programme de poursuivre son déroulement là où il s'était arrêté pour passer la main s'appelle un « sous-programme ». C'était déjà très fréquent en BASIC, par exemple. En langage C, les notions de fonction et de sous-programme sont confondues, mais ce n'est pas toujours le cas.

Le fait de provoquer un effet qui n'est pas directement lié à l'évaluation de la fonction (au calcul de sa valeur) est appelé « effet de bord ». Ça peut être volontaire (écrire quelque chose à l'écran) ou involontaire et contrariant : on utilise généralement le terme pour parler d'un bug induit par la mise en place d'une chose sans rapport avec ce qu'elle perturbe.

Une fonction sans effet de bord et ne dépendant pas non plus de l'état extérieur s'appelle une fonction pure. À ne pas confondre avec « fonction virtuelle pure » qui est une terminologie du C++. La page Wikipédia en question est également à prendre avec des pincettes car elle ne précise pas si une fonction qui utilise des variables statiques (donc propres à la fonction quand même) peut être quand même considérée comme pure.

Je pensais que dans l'idéal, une fois que le programme compile et fonctionne pour les cas où "tout se passe bien", il aurait fallu le compléter en prenant en compte qu'un utilisateur distrait pourrait prendre min qui soit plus grand que max, des idx_lower ou idx_upper qui soit hors tableau etc...
Je pensais donc devoir dans un premier temps faire une fonction qui gère les différents intervalles.

Absolument, et c'est très important en informatique mais d'une part, comme tu le dis, ce n'est pas l'objet de l'exercice (qui t'occupe déjà bien assez comme ça et de l'autre, c'est une tâche qui devra faire l'objet d'une fonction distincte : en gros, tu considères tout ce qui provient de l'extérieur de ton programme comme potentiellement malfaisant et tout ce qui est à l'intérieur comme sûr et tu ne t'en soucies plus. Donc, tu vas faire une fonction dédiée dont la tâche consistera à acquérir des données de l'extérieur et à les vérifier (voire les rejeter si nécessaire). À son issue, ce qui restera sera considéré comme fiable.

Si j'avais pu interpréter comme tu l'as fait, que min et max sont fixés et que idx_lower (resp idx_upper) part du début (resp de la fin) du tableau ça m'aurait facilité la tâche.

Ça, c'est de l'entraînement et malheureusement, au moins 75% des difficultés que tu vas rencontrer autant dans le domaine scolaire que professionnel va être dû à des informations mal formulées. Effectivement, c'est mieux si on le sait à l'avance et pas une fois que l'on a raté ses partiels. Tu verras aussi qu'il est très difficile de synthétiser soi-même ses propres connaissances (d'où les exposés, présentations, oraux et compagnie…).

Dans le cas qui nous intéresse, c'est tout de suite plus clair quand on comprend que « idx_ » signifie « index ». Mais là encore, il faut avoir fait un peu d'informatique sur la durée pour que cela
vienne naturellement et sans y réfléchir.

Cependant c'est plutôt logique du coup de faire appel aux fonctions définies plus tôt dans l'exercice, c'est aussi pour cela que je trouvais mon code suspect ^^ normalement on se sert tôt ou tard des premières questions. Je vais donc reprendre mon code, mais je ne vois quand même pas pourquoi le compilateur me met conflicting type error :

Ça veut dire « conflit de types ». C'est parce que tu redéfinis la même fonction (« slice ») avec des types différents, donc le compilateur ne sait pas quelle version est la bonne (et de toutes façons, en C, il ne doit y en avoir qu'une). Et par « type », on entend non seulement le type de la fonction elle-même (donc, en fait, celui de sa valeur de retour) mais également celui de ses paramètres. Et s'il t'accuse de les avoir modifiés, c'est parce qu'en fait, tu as bien spécifiés les étoiles « * » des pointeurs idx_lower et idx_upper en définissant ta fonction (à la ligne 55) mais que tu avais oublié de les mettre dans son prototype (ligne 7).

Dans tous les cas merci pour ton temps Obsidian

Avec plaisir.

[Mandyy]

Merci pour ton message,

Dans le cas qui nous intéresse, c'est tout de suite plus clair quand on comprend que « idx_ » signifie « index ». Mais là encore, il faut avoir fait un peu d'informatique sur la durée pour que cela
vienne naturellement et sans y réfléchir.

Pour le coup, j'avais assez rapidement fait le lien entre l et idx_lower donc index l , puis u et idx_upper. C'est bien une des seules choses où je n'ai pas été confuse

Ça veut dire « conflit de types ». C'est parce que tu redéfinis la même fonction (« slice ») avec des types différents, donc le compilateur ne sait pas quelle version est la bonne (et de toutes façons, en C, il ne doit y en avoir qu'une). Et par « type », on entend non seulement le type de la fonction elle-même (donc, en fait, celui de sa valeur de retour) mais également celui de ses paramètres. Et s'il t'accuse de les avoir modifiés, c'est parce qu'en fait, tu as bien spécifiés les étoiles « * » des pointeurs idx_lower et idx_upper en définissant ta fonction (à la ligne 55) mais que tu avais oublié de les mettre dans son prototype (ligne 7).

Bien vu! Car même en me relisant plusieurs fois je n'avais pas fait attention, effectivement j'avais oublié les * dans le prototype.

La dernière chose qui me perturbe dans cette fonction slice c'est la nécessité du int size en paramètre, est-ce juste pour éviter d'avoir à créer une variable temporaire dans le corps de la fonction?

Voici mon code pour cette fonction slice: ( peut importe ce que rentrera l'utilisateur comme "size" je le récupère pour m'en servir de la sorte )

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 
void slice(int *array, int size, int min, int max, int *idx_lower, int *idx_upper){
 
	size = binary_search(array, max) - binary_search(array,min);
 
	for(int i = 0; i<size ; i++){
 
		printf("%d\n", array[binary_search(array,min)] + i );
 
 
	}
}

[Sve@r]

La dernière chose qui me perturbe dans cette fonction slice c'est la nécessité du int size en paramètre

Bonjour

Voici deux tableaux: int tA[]={1, 2, 3}; int tB[]={1, 2, 3, 4, 5, 6, 7}.
Si tu veux créer une fonction "afficheTab()" qui affichera indifféremment (selon celui des deux tableaux que tu lui passes en paramètre) tA ou tB (ou éventuellement tout autre tableau d'ints quelconque), comment la fonction "afficheTab()" saura où s'arrêter dans sa boucle d'affichage ?

est-ce juste pour éviter d'avoir à créer une variable temporaire dans le corps de la fonction?

Non. Et au contraire il vaut toujours mieux privilégier les variables locales aux paramètres qui complexifient justement le code. Dans mon "afficheTab()" du dessus il y aura fatalement un size_t i indice de boucle qui sera local et qui n'a certainement pas besoin d'arriver de l'extérieur comme paramètre.
Les paramètres ce sont les informations que la fonction n'a pas, et qu'elle ne peut pas retrouver par elle-même ; et dont elle a besoin pour produire son résultat. Les variables locales sont les outils qu'elle peut créer elle-même pour faire son travail.