Dichotomie simple et étagée

Bonjour tlm ;

Je suis debutant en programmation, je cherche l'algorithme et le programme en C de la dichotomie simple et étagée pour la recherche d'une valeur dans un tableau.

Meci a vous !

En gros tu veux le beurre et l'argent du beurre :aie:

Réalise ton algo (ou voir le forum algo) ensuite tu pourras retranscrire cela en C et à partir de là on pourra plus t'aider.

Je peux d'ore et déja dire que ton programme va au moins ressembler à cela :

Code:

---

1 2 3 4

int main () { return 0; }

---

;)

Citation:

---

Envoyé par hegros

En gros tu veux le beurre et l'argent du beurre :aie:

Réalise ton algo (ou voir le forum algo) ensuite tu pourras retranscrire cela en C et à partir de là on pourra plus t'aider.

Je peux d'ore et déja dire que ton programme va au moins ressembler à cela :

Code:

---

1 2 3 4

int main () { return 0; }

---

;)

---

Plutôt à cela, non?

Code:

---

1 2 3 4

int main (void) { return 0; }

---

Thierry

J'ai l'algo de la dichotomie simple, je peut continuer ?


//déclarations
entier : début, milieu, fin, val
Tnb [0..100] : Tableau d'entier

//initialisation
début <- 0
fin <- 100

//Question
Répéter
Afficher "Valeur recherchée?"
Saisir val
Jusqu'à début<=val et val<=fin

//Boucle de recherche
Répéter

//Calcul du milieu
milieu = arrondiàl'unité((début+fin)/2)

//Conditions et affectations
Si val > Tnb[milieu] alors

début <- milieu + 1

Sinon

Si val=Tnb[milieu] alors

début <- milieu
fin <- milieu

Sinon

fin <- milieu - 1

Finsi

Finsi

jusqu'à début=fin

//Affichage du résultat
Afficher "La valeur est ", val

Superbe si tu es sûr de ton algo il te faut le retranscrire.

Par exemple

Entier : debut,fin,val
Tnb [0..100] : Tableau d'entier

se transforme en

Code:

---

1 2	int debut,fin,val; int Tnb[100];

---

Ensuite tes Répéter jusqu'a se transforme en do while
Tes Si en if etc etc etc

Tu as essayé de le retranscrire en C pour voir ce que ca donne ?

Citation:

---

Envoyé par mujigka

Plutôt à cela, non?

Code:

---

1 2 3 4

int main (void) { return 0; }

---

Thierry

---

Tant qu'a faire alors je dirais plutot :

Code:

---

1 2 3 4

#include <stdlib.h> int main(int argc,char**argv) { return EXIT_SUCCESS; }

---

Citation:

---

Envoyé par hegros

Tant qu'a faire alors je dirais plutot :

Code:

---

1 2 3 4

#include <stdlib.h> int main(int argc,char**argv) { return EXIT_SUCCESS; }

---

---

Equivalent, sauf que les paramètres argc et argv sont inutiles, car pas utilisés. Je rappelle que int main() engendre un comportement indéterminé.

Thierry

Citation:

---

Envoyé par mujigka

Equivalent, sauf que les paramètres argc et argv sont inutiles, car pas utilisés. Je rappelle que int main() engendre un comportement indéterminé.

Thierry

---

Je ne sais pas d'où tu tiens cela (la norme surement :roll: ) mais tu peux toujours essayé de relever le défi de me montrer 1 et 1 seul comportement "bizaroide" en utilisant ce proto.

Tiens d'ailleurs rapporte nous où tu as lu cela dans la norme ou dans la spécification que ce proto engendre un comportement indeterminé.

Bon courage :mrgreen:

Salut,
C'est pas plus simple si tu fait un truc dans le genre ca :

int i;
for (i = 0; i < strlen(TonTable); i++)
{
if (TonTable[i] == CeQueTuCherches)
{
// La tu met le code a éxécuter si il la trouver
}
}

Citation:

---

Envoyé par wikipierre

Salut,
C'est pas plus simple si tu fait un truc dans le genre ca :

int i;
for (i = 0; i < strlen(TonTable); i++)
{
if (TonTable[i] == CeQueTuCherches)
{
// La tu met le code a éxécuter si il la trouver
}
}

---

1) il VEUT faire de la recherche dychotomique

2) strlen(Table) ne marche QUE pour une chaine.

3) si tu as 25 Millions d'enregistrements, un peu dur de faire une boucle comme ça....


:roll:

Citation:

---

Envoyé par hegros

Je ne sais pas d'où tu tiens cela (la norme surement :roll: )

---

Oui, la norme

Citation:

---

Envoyé par hegros

mais tu peux toujours essayé de relever le défi de me montrer 1 et 1 seul comportement "bizaroide" en utilisant ce proto.

---

A quoi bon? int main(void), ça me va, ça ne mange pas d'pain, et c'est conforme. Mais tout cela est évidamment hors sujet.

EDIT: Et puis, int main() n'est précisément pas un prototype au sens du langage C.

Thierry

Citation:

---

Envoyé par mujigka

Oui, la norme

A quoi bon? int main(void), ça me va, ça ne mange pas d'pain, et c'est conforme. Mais tout cela est évidamment hors sujet.

Thierry

---

Certe.Cependant ca peut être intéressant que tu nous rapportes ce que dit exactement la norme à ce sujet (j'imagine que tu as le document sous la main sinon pour une prochaine fois peut être)

Citation:

---

Envoyé par hegros

Certe.Cependant ca peut être intéressant que tu nous rapportes ce que dit exactement la norme à ce sujet (j'imagine que tu as le document sous la main sinon pour une prochaine fois peut être)

---

ISO/IEC 9899:TC2 section 5.1.2.2.1:

Citation:

---

The function called at program startup is named main. The implementation declares no
prototype for this function. It shall be defined with a return type of int and with no
parameters:
int main(void) { /* ... */ }
or with two parameters (referred to here as argc and argv, though any names may be
used, as they are local to the function in which they are declared):
int main(int argc, char *argv[]) { /* ... */ }
or equivalent;9) or in some other implementation-defined manner.

---

L'important ici est que no parameter se note en C main(void) et non main() qui signifie "nombre indetermine d'arguments de types indetermines".

Citation:

---

Envoyé par hegros

Certe.Cependant ca peut être intéressant que tu nous rapportes ce que dit exactement la norme à ce sujet (j'imagine que tu as le document sous la main sinon pour une prochaine fois peut être)

---

<HS>

Citation:

---

Envoyé par norme du langage C

5.1.2.2.1 Program startup
The function called at program startup is named main. The implementation
prototype for this function. It shall be defined with a return type of
parameters:
int main(void) { /* ... */ }
or with two parameters (referred to here as argc and argv, though
used, as they are local to the function in which they are declared):
int main(int argc, char *argv[]) { /* ... */
or equivalent;9) or in some other implementation-defined manner.

---

La norme ne faisant mention que de ces deux formes, toutes les autres correspondent à un comportement indéterminé et dépendant de la plateforme.

Pour le comportement bizarre:

Code:

---

1 2 3 4 5 6

#include <stdlib.h>   int main() { return EXIT_SUCCESS; }

---

compilé avec gcc avec des réglages relativement courants:

Code:

---

gcc -Wstrict-prototypes -Werror main.c

---

donne une erreur de compilation.
</HS>

Thierry

Citation:

---

Envoyé par mujigka

Pour le comportement bizarre:
Code :

#include <stdlib.h> int main() { return EXIT_SUCCESS; }


compilé avec gcc avec des réglages relativement courants:
Code :

gcc -Wstrict-prototypes -Werror main.c

donne une erreur de compilation.

---

Quand on parle de comportement indeterminé c'est lié à l'execution du programme pas à sa compilation.

fflush(stdin) ne pose aucun probléme à la compilation par contre à l'execution son comportement est indeterminé.

En effet, mais les warnings sont un bon indices pour en débusquer certains, aussi ignorer un warning est déconseillé...

Citation:

---

Envoyé par Médinoc

En effet, mais les warnings sont un bon indices pour en débusquer certains, aussi ignorer un warning est déconseillé...

---

Le warning des arguments argc et argv est complétement superflu.

Mais tant qu'a faire si on ne les utilise pas c'est vrai autant mettre void.Mais la norme n'est pas trés bavarde sur ce sujet...

Citation:

---

Envoyé par mujigka

Equivalent, sauf que les paramètres argc et argv sont inutiles, car pas utilisés. Je rappelle que int main() engendre un comportement indéterminé.

---

Non.

Ca signifie que le nombre et le type de paramètres n'est pas défini, ce dont on se tape tant que personne n'appelle main(). Or appeler main() est une pratique peu recommandable (interdite en C++).

Code:

---

1 2 3 4

int main() { }

---

est donc acceptable et sans danger, même si

Code:

---

1 2 3 4

int main(void) { }

---

est plus cohérent avec le reste du code qui utilise des prototypes.