Sujet Précédent Sujet Suivant

Calcul par dichotomie

Fermé
davidhazak Messages postés 3 Date d'inscription lundi 4 mai 2015 Statut Membre Dernière intervention 4 mai 2015 - 4 mai 2015 à 13:54
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 - 4 mai 2015 à 22:00
Bonjour,
j'ai un tableau sur c#composer de 0 et de 1
1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
je dois afficher le tableau et dire combien il y a de 1 en utilisant un code avec un algorithme de dichotomie.
merci de votre aide a tous.
A voir également:

4 réponses

Réponse 1 / 4
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 931
4 mai 2015 à 14:58
Bonjour, on ne fait pas le travail pour les autres ici, on aide à débloquer un problème.
Il faut donc commencer par nous montrer le code qui pose problème en utilisant icic comment utiliser la coloration syntaxique.
Préciser quelles lignes beugue, quel est le message d'erreur?

D'autre part, il s'agit surement d'un exercice (parce que sinon y'a la méthode count...), ce qui implique que ton prof veut te faire travailler un truc précis, or nous ne sommes pas ton prof et nous ne suivons pas ton cour, donc difficile pour nous de savoir ou ton prof veut t'amener à réfléchir.

Pour rappel
https://www.commentcamarche.net/infos/25899-demander-de-l-aide-pour-vos-exercices-sur-ccm/
0
Réponse 2 / 4
davidhazak Messages postés 3 Date d'inscription lundi 4 mai 2015 Statut Membre Dernière intervention 4 mai 2015
Modifié par Whismeril le 4/05/2015 à 18:29
ok j'ai bien compris mais
1) je ne savais pas qu'il y avait cette charte
2) j'ai bien lue la charte et aider n'est pas interdit
3) si je demande l'aide c'est que j'ai réfléchis et que je suis coincer
4)répondre moins agressivement n'est pas interdit
et qu'on soit bien je n'ai jamais demander que l'on fasse l'exercice a ma place j'ai demander de l'aide .
voici ou je suis arriver si quelqu'un peut m'aider a continuer merci a vous
voici le code que j'ai écrit: 
   public static int BinarySearch(int[]array,int number)
        {
             array = new int[] { 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
             number = 1;
            int left = 0, middle, right = array.Length - 1;
            while (left>=right)
            {
                middle = (left + right) / 2;
                if (number==array[middle]&&array[middle+1]==0)
                {
                    int one=middle; 
                }
                else if(number>array[middle])
                {
                    right = middle - 1;
                }
                else
                {
                    left = middle + 1;
                }
               
            }
            return -1;
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 931
4 mai 2015 à 18:13
2) j'ai bien lue la charte et aider n'est pas interdit
et donc tu as bien compris comment on utilise la coloration syntaxique, ha ben non, je vais donc corriger pour toi.

je n'ai jamais demander que l'on fasse l'exercice a ma place j'ai demander de l'aide
non tu as dit : j'ai ça à faire, et rien d'autre, donc ouvert à toute interprétations, dans le doute je suis intervenu.
Je ne pense pas avoir été agressif, mais formel. Après personne n'est parfait.

D'autre part tu n'as toujours pas précisé le langage, et de ce que j'en vois ça pourrait être du C++, du C# ou du java, par défaut je mets la coloration du C++
0
Réponse 3 / 4
davidhazak Messages postés 3 Date d'inscription lundi 4 mai 2015 Statut Membre Dernière intervention 4 mai 2015
4 mai 2015 à 18:27
ok le langage c'est c# et si tu peux m'aider ce serais gentil merci de ton aide
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 931
Modifié par Whismeril le 4/05/2015 à 18:49
Au temps pour moi, tu vais posté dans le bon forum
0
Réponse 4 / 4
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 931
4 mai 2015 à 21:47
Alors ton tableau est trié, l'idée est donc de trouver "rapidement", c'est à dire en moins d'itérations que le nombre de cases dans ton tableau ou est la limite entre 0 et 1

Etape 1 Right dernier index du tableau, Left Premier et Middle la moitié, jusque là OK

Tu regardes la valeur à l'index Middle (dans un premier temps, pas celui d'après)
S'il vaut Number alors tu dois aller "plus loin" left prend la valeur de middle
Dans le cas contraire, il faut aller "moins loin" right prend la valeur de middle

Si left = right tu es à la frontière, et tu pourras déterminer le nombre de 1 en fonction de l'index donc on sort de la boucle, dans le cas contraire on retourne à l'étape 1.

Une fois sorti de la boucle on retourne le nombre de 1 en fonction de la valeur de left
0
Whismeril Messages postés 19028 Date d'inscription mardi 11 mars 2003 Statut Non membre Dernière intervention 24 avril 2024 931
4 mai 2015 à 22:00
Ha je viens de tester, ça boucle à l'infini si right et left se retrouvent à deux valeur consécutives, middle étant un int il est tronqué et du coup left ne change pas.
Il faut donc affecter middle + 1 à left ou middle -1 à right.
0