Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

 C Discussion :

Multiple dans un tableau


Sujet :

C

  1. #1
    Membre à l'essai
    Femme Profil pro
    Étudiant
    Inscrit en
    décembre 2019
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : décembre 2019
    Messages : 32
    Points : 11
    Points
    11
    Par défaut Multiple dans un tableau
    Bonsoir, j'ai essayé de faire cet exercice sauf que sa me renvoie false et je ne comprend pas pourquoi merci d'avance :
    Nom : Capture d’écran 2020-01-11 à 20.48.19.png
Affichages : 110
Taille : 494,2 Ko

    Pour la première question pour le tableau trié avec une complexité O(n) j'ai fais ça;
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    bool Tabmul(int T[],int n){
                   int s=1 ;
                   int cpt=0;
                   int i=0;
                         while( i<n){
                                  if(s*T[0] == T[i]){
                                         cpt=cpt+1;
                                         s=s+1;
                                         i=i+1;}
                    i=i+1;}
    if(cpt==n){
       return true;}
    return false;}
    Pour la 2eme question tableau non trié avec une complexité O(n)

    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
    int mintab(int T[],int n){
        min=T[0];
       for(int i=1;i<n;i++){
             if(min >T[i]){
                  min=T[i];}
    }
    return min;}
    bool Tabmul(int T[],int n){
    int cpt=0;
    int s=1;
                  for(int i=0;i<n;i++){
                       if(s*mintab(T,n)==T[i]){
                                  cpt=cpt+1;
                                  i=0;
                                  s=s+1;}
    }
    if(cpt==n){
    return true;}
    return false;}
    aidez moi s'il vous plait merci

  2. #2
    Expert éminent
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    3 168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 3 168
    Points : 7 071
    Points
    7 071
    Par défaut
    Je ne sais plus quoi te dire

    Déjà en quoi c'est du C++ ? c'est un mystère
    C'est tellement du C, tellement du procédural qu'il n'y a rien qui justifie les tableaux std::array/ std::vector


    Et pour ton code : en l'indentant correctement, tu voies directement le problème. L'incrément qui fait un "+2"
    Mais en plus c'est quoi tous ces valeurs qui ne servent à rien entre un incrément de boucle i, un compteur de multiple s et un compteur de multiples trouvés cpt tu ne sens pas la redondance. Non ... rien
    Et ce return tout moisi tu ne sais donc pas que dans un retour booléen, on peut mettre une expression booléenne. Non ... sérieux

    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
    bool Tabmul(int tab[], size_t tab_size) {
        bool is_mult;
     
        if (tab_size > 1) {
            size_t mult;
            int first=(*tab);
     
            for(mult=2, ++tab; ((mult <= tab_size) && ((*tab) == static_cast<int>(mult * first))); ++tab, ++mult) {
                printf("Tabmul - debug : multiple %d and %d (first: %d) - %lu\n", static_cast<int>(mult * first), (*tab), first, mult);
            }
     
            is_mult = (mult > tab_size);
     
            printf("Tabmul - debug : nb multiples %lu\n", (mult - 2));
        } else {
            is_mult = false;
        }
     
        return is_mult;
    }
    Et pour la question 2, oui, tu fais 2 parcours, donc tu as une complexité linéaire

  3. #3
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    7 774
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 7 774
    Points : 21 022
    Points
    21 022
    Billets dans le blog
    1
    Par défaut
    Salut

    Citation Envoyé par foetus Voir le message
    Déjà en quoi c'est du C++ ? c'est un mystère
    C'est tellement du C, tellement du procédural qu'il n'y a rien qui justifie les tableaux std::array
    Hé, on est dans le fofo C ici... (ou alors un modo a déplacé le topic depuis ton post )

    Citation Envoyé par foetus Voir le message
    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
    bool Tabmul(int tab[], size_t tab_size) {
        bool is_mult;
     
        if (tab_size > 1) {
            size_t mult;
            int first=(*tab);
     
            for(mult=2, ++tab; ((mult <= tab_size) && ((*tab) == static_cast<int>(mult * first))); ++tab, ++mult) {
                printf("Tabmul - debug : multiple %d and %d (first: %d) - %lu\n", static_cast<int>(mult * first), (*tab), first, mult);
            }
     
            is_mult = (mult > tab_size);
     
            printf("Tabmul - debug : nb multiples %lu\n", (mult - 2));
        } else {
            is_mult = false;
        }
     
        return is_mult;
    }
    Très beau code et très certainement 100% fonctionnel. Mais voilà, ici on fait du C, pas du C++

    Citation Envoyé par Marwaa45 Voir le message
    Citation Envoyé par foetus Voir le message
    Et ce return tout moisi tu ne sais donc pas que dans un retour booléen, on peut mettre une expression booléenne. Non ... sérieux
    C'est vrai qu'écrire if (truc) return true; else return false; alors qu'il est tellement plus évident d'écrire directement return truc est un peu moyen...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  4. #4
    Expert éminent
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    3 168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 3 168
    Points : 7 071
    Points
    7 071
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    Hé, on est dans le fofo C ici... (ou alors un modo a déplacé le topic depuis ton post )
    C'est le 3-4ième sujet de @Marwaa45 qu'elle poste dans le forum C++, avec des tableaux et des listes chaînées ... mais c'est du pur C avec que des pointeurs et des tableaux à la C.
    Surtout qu'avec les listes chaînées, j'ai montré du code avec des classes ... mais rien.

    Apparemment c'est son prof ... mais apparemment


    Citation Envoyé par Sve@r Voir le message
    Très beau code et très certainement 100% fonctionnel. Mais voilà, ici on fait du C, pas du C++
    Il y a juste les cast à changer/ supprimer et le type bool à remplacer par un unsigned char.
    D'ailleurs comme elle utilise des tableaux à la C, j'ai fait un déplacement pointeur ... juste pour l'embêter parce qu'elle code en C++ avec un C [très] très scolaire

    Le code est là pour montrer qu'on le fait en 2 lignes et 2 variables

  5. #5
    Expert éminent
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    3 168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 3 168
    Points : 7 071
    Points
    7 071
    Par défaut
    Je reviens sur ce que j'ai dit , parce que si tu veux faire du C++, tu peux coder avec la notion de classe, de foncteur, d'itérateurs et un chouïa de la bibliothèque STL.

    Code fait à l'arrache :
    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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    #include <algorithm>
    #include <iostream>
    #include <vector>
     
    #include <cstdlib>
     
     
    class c_test {
    public:
     
        c_test(int input_first) { reset(input_first); }
     
    public:
     
        void reset(int input_first) { first=input_first; count=1; }
     
        bool operator() (int one_value) {
    //      std::cout << "debug - c_test::operator() : multiple " << static_cast<int>(count * first) << " and " << one_value << " (first: " << first << ") - " << count << std::endl;
     
            ++count;
     
            return (one_value != static_cast<int>(count * first));
        }
     
    private:
     
        int first;
        size_t count;
    };
     
     
    void display_result(const std::vector<int>& tab, const std::vector<int>::iterator& result_it, const std::string& begin) {
        if (tab.size() > 1) {
            std::vector<int>::const_iterator it = tab.begin();
     
            std::cout << begin << " [" << (*it);
     
            for(++it; (it != tab.end()); ++it) {
                std::cout << ' ' << (*it);
            }
     
            std::cout << "] is_mult " << ((result_it == tab.end())? "true": "false") << std::endl;
        } else {
            std::cout << begin << " size < 2" << std::endl;
        }
    }
     
     
    int main (int argc, char** argv)
    {
        std::vector<int> tab;
        tab.reserve(8);
        tab.push_back( 3);
        tab.push_back( 6);
        tab.push_back( 9);
        tab.push_back(12);
        tab.push_back(15);
        tab.push_back(18);
        tab.push_back(21);
     
    //  Test 1 - 7 elements, all multiples
        c_test one_test( tab[0] );
     
        std::vector<int>::iterator result_it = std::find_if((tab.begin() + 1), tab.end(), one_test);
     
        display_result(tab, result_it, "main - tab");
     
    //  Test 2 - 8 elements, all multiples
        one_test.reset( tab[0] );
     
        tab.push_back(24);
     
        result_it = std::find_if((tab.begin() + 1), tab.end(), one_test);
     
        display_result(tab, result_it, "main - tab");
     
    //  Test 3 - 8 elements, one error
        tab[4] = 17;
     
        one_test.reset( tab[0] );
     
        result_it = std::find_if((tab.begin() + 1), tab.end(), one_test);
     
        display_result(tab, result_it, "main - tab");
     
     
        return EXIT_SUCCESS;
    }

  6. #6
    Membre éclairé
    Homme Profil pro
    Programmeur du dimanche
    Inscrit en
    août 2017
    Messages
    227
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Programmeur du dimanche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2017
    Messages : 227
    Points : 742
    Points
    742
    Par défaut
    foetus, ça ne sert à rien de montrer du code C++ idiomatique à quelqu'un qui est en train d'apprendre des bases d'algorithmique et de programmation en C.
    Sur Youtube je suis "Le prof des cavernes"
    https://www.youtube.com/channel/UCSz...bYl_pSNMv_zerQ

  7. #7
    Expert éminent
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    3 168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 3 168
    Points : 7 071
    Points
    7 071
    Par défaut
    Citation Envoyé par Jamatronic Voir le message
    foetus, ça ne sert à rien de montrer du code C++ idiomatique à quelqu'un qui est en train d'apprendre des bases d'algorithmique et de programmation en C.
    Si tu n'as pas compris que le sujet a été déplacé de la section C++ à la section C parce qu'un modérateur a remarqué que @Marwaa45 poste des sujets C dans la section C++.

    Au lieu de me moinser, demande à @Marwaa45 si ces sujets sont du C ou du C++. Moi cela fait 2 semaines que je lui demande sans succès


    Citation Envoyé par foetus Voir le message
    Et pour la question 2, oui, tu fais 2 parcours, donc tu as une complexité linéaire
    Je reviens aussi sur cela. Parce que si le tableau n'est pas trié, il faut prouver que les nombres sont des multiples du plus petit nombre. Ce point est facile

    Mais il ne faut pas de trous : ce sont les premiers multiples. Et sur ce point je ne sais pas
    Je me demande comme ce sont les premiers multiples, s'il ne faut pas juste prouver que la somme des diviseurs doit être égale à la somme de (n - 1) n premiers entiers (*)
    Et dans ce cas (s'il fonctionne), ton algo est linéaire en temps et constant en espace.

    Sinon, il faudra trier ton tableau, utiliser un tableau qui va contenir des booléens (la case n veut dire "n est un diviseur ou pas"), ...


    *: @Sve@r a raison, il faut compter le plus petit nombre, mais lui a toujours comme diviseur 1.
    Ensuite diviseur ou quotient , j'ai recherché sur Internet le terme, mais sans trop de réussite et sans être convaincu

  8. #8
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    7 774
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 7 774
    Points : 21 022
    Points
    21 022
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par foetus Voir le message
    Je me demande comme ce sont les premiers multiples, s'il ne faut pas juste prouver que la somme des diviseurs doit être égale à la somme de (n - 1) premiers entiers.
    Je pense que ce serait plutôt "la somme des quotients" qui serait égale à la somme de "n" premiers entiers (et avec évidemment obligation des restes à 0). Avec par exemple 3, 6, 9 (même en non trié), t'auras 1, 2 et 3 qui donnera une somme de 6. Et ça reste linéaire...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  9. #9
    Membre chevronné
    Avatar de sambia39
    Homme Profil pro
    No Comment
    Inscrit en
    mai 2010
    Messages
    492
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loiret (Centre)

    Informations professionnelles :
    Activité : No Comment
    Secteur : High Tech - Matériel informatique

    Informations forums :
    Inscription : mai 2010
    Messages : 492
    Points : 1 806
    Points
    1 806
    Par défaut
    Bonjour ;
    Il y a un truc qui me chiffonne. Je ne comprends pas pourquoi il y a implémentation d'algorithme sachant qu'il est spécifié dans l'énoncer de fournir la complexité ; cela sous-entend de quel type de complexité, s'agit-il ; chose qui ne s'obtient pas avec un booléen ou un langage de programmation. D'ailleurs ; un algorithme doit être décrit avec une notation totalement indépendante d'un langage de programmation (en clair pas de langage de programmation C ou C++ ou autres) car en utilisant cette dernière (langage de programmation C ou C++) on procède à une implémentation de l'algorithme qui veut tout simplement dire que l'on procède à l'écriture du programme. Et si l'on par du postulat que le tableau est trié et que l'on prend compte de sa complexité dès le départ; l'exercice 1 doit probablement avoir une complexité : O(log n) (chose à vérifier, car dit à la louche basé sur la recherche dans un tableau trié) ?
    Celui qui peut, agit. Celui qui ne peut pas, enseigne.
    Il y a deux sortes de savants: les spécialistes, qui connaissent tout sur rien,
    et les philosophes, qui ne connaissent rien sur tout.
    George Bernard Shaw

  10. #10
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    7 774
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 7 774
    Points : 21 022
    Points
    21 022
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par sambia39 Voir le message
    sachant qu'il est spécifié dans l'énoncer de fournir la complexité ; cela sous-entend de quel type de complexité, s'agit-il ; chose qui ne s'obtient pas avec un booléen
    Le booléen c'est juste le résultat de l'algorithme qui doit donner "tableau multiple" ou "tableau pas multiple"

    Citation Envoyé par sambia39 Voir le message
    ou un langage de programmation.
    Généralement dans l'apprentissage, les deux vont de pair. On apprend à la fois à résoudre un problème à l'aide d'ordres spécifiques qui, comme par hasard, ont une symbolique super proche du langage dans lequel on doit écrire. Parce qu'écrire i <- i + 1 ou i=i+1 ça ne change pas vraiment l'apprentissage de l'algorithme et ça apprend en même temps le C (ou tout autre langage qui accepte ce type d'instruction)

    Citation Envoyé par sambia39 Voir le message
    D'ailleurs ; un algorithme doit être décrit avec une notation totalement indépendante d'un langage de programmation (en clair pas de langage de programmation C ou C++ ou autres) car en utilisant cette dernière (langage de programmation C ou C++) on procède à une implémentation de l'algorithme qui veut tout simplement dire que l'on procède à l'écriture du programme.
    Idem ci-dessus. C'est bien joli d'avoir des principes "l'algorithme doit être indépendant du langage" mais parfois il faut aussi savoir prendre en compte les réalités de la vie (ça coûte cher les heures de prof !!!). Même la logique doit laisser la place à la physique (Spock dans Star Trek VI, Terre Inconnue)

    Citation Envoyé par sambia39 Voir le message
    l'exercice 1 doit probablement avoir une complexité : O(log n) (chose à vérifier, car dit à la louche basé sur la recherche dans un tableau trié) ?
    Pas certain. La recherche du plus petit élément dans un tableau trié est effectivement en O(log n) mais ensuite il faut quand-même parcourir tout le tableau une fois entière pour regarder si les éléments sont bien des multiples du plus petit. Donc O(n)...
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  11. #11
    Expert confirmé
    Avatar de Pyramidev
    Homme Profil pro
    Développeur
    Inscrit en
    avril 2016
    Messages
    1 037
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur

    Informations forums :
    Inscription : avril 2016
    Messages : 1 037
    Points : 4 438
    Points
    4 438
    Par défaut
    Bonjour,

    Citation Envoyé par Marwaa45 Voir le message
    Bonsoir, j'ai essayé de faire cet exercice sauf que sa me renvoie false et je ne comprend pas pourquoi merci d'avance :
    [...]
    Pour la 2eme question tableau non trié avec une complexité O(n)

    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
    int mintab(int T[],int n){
        min=T[0];
       for(int i=1;i<n;i++){
             if(min >T[i]){
                  min=T[i];}
    }
    return min;}
    bool Tabmul(int T[],int n){
    int cpt=0;
    int s=1;
                  for(int i=0;i<n;i++){
                       if(s*mintab(T,n)==T[i]){
                                  cpt=cpt+1;
                                  i=0;
                                  s=s+1;}
    }
    if(cpt==n){
    return true;}
    return false;}
    aidez moi s'il vous plait merci
    Ce code ne fonctionne pas, car il part du principe que les éléments sont triés. Il ne faut pas seulement chercher le minimum dans tout le tableau. Il faut aussi changer ton code qui croit que s*mintab(T,n)==T[i] avec s croissant.
    Si tu réfléchis à comment se comporte ton algo avec l'exemple 15 5 10 20 de l'exercice, tu devrais vite voir pourquoi il ne marche pas. Si tu ne le vois pas encore, tu peux t'aider en ajoutant des printf dans le code.

    Une fois que tu auras compris pourquoi ça ne marche pas, tu pourras essayer de concevoir un autre algo. Alors, si tu bloques encore, tu pourras nous redemander de l'aide.

    Pour implémenter cet algo sans faire de tri, il y a une manière simple avec une complexité quadratique.
    J'ai aussi trouvé une manière plus astucieuse avec une complexité linéaire, mais qui nécessite une allocation dynamique.

    Citation Envoyé par Sve@r Voir le message
    Je pense que ce serait plutôt "la somme des quotients" qui serait égale à la somme de "n" premiers entiers (et avec évidemment obligation des restes à 0). Avec par exemple 3, 6, 9 (même en non trié), t'auras 1, 2 et 3 qui donnera une somme de 6. Et ça reste linéaire...
    Cette astuce-là ne marche pas. Par exemple, pour le tableau 15 5 15 15, si tu divises les éléments par 5, tu auras 3 1 3 3. La somme est 10 qui vaut bien 1+2+3+4, mais le tableau 15 5 15 15 n'est pas un tableau de multiples au sens de l'exercice.

  12. #12
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    février 2006
    Messages
    7 774
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : février 2006
    Messages : 7 774
    Points : 21 022
    Points
    21 022
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Pyramidev Voir le message
    Cette astuce-là ne marche pas. Par exemple, pour le tableau 15 5 15 15, si tu divises les éléments par 5, tu auras 3 1 3 3. La somme est 10 qui vaut bien 1+2+3+4, mais le tableau 15 5 15 15 n'est pas un tableau de multiples au sens de l'exercice.
    Bien vu
    On peut rajouter "et aucun élément égal à aucun autre" qui élimine alors cette situation (et toute autre analogue) mais ça explose la complexité
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site

  13. #13
    Expert éminent
    Homme Profil pro
    Analyste/ Programmeur
    Inscrit en
    juillet 2013
    Messages
    3 168
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Analyste/ Programmeur

    Informations forums :
    Inscription : juillet 2013
    Messages : 3 168
    Points : 7 071
    Points
    7 071
    Par défaut
    @Pyramidev Justement je parlais de prouver parce que je n'avais pas trouvé de chausse-trapes ... et je n'ai pas pensé aux doublons
    Mais la probabilité que "la somme des diviseurs/ quotients est égale à la somme des n premiers entiers mais que les diviseurs/ quotients ne se suivent pas" doit être très faible : cela peut se tenter

    Citation Envoyé par Sve@r Voir le message
    On peut rajouter "et aucun élément égal à aucun autre" qui élimine alors cette situation (et toute autre analogue) mais ça explose la complexité
    Pas forcément

    Je parlais d'un "tableau qui va contenir des booléens (la case n veut dire "n est un diviseur ou pas")" et c'est peut-être 1 solution pour avoir une complexité linéaire.
    Ce tableau a la même taille que le tableau de valeurs/ multiples et est initialisé à "false" (sauf le premier, mais c'est anecdotique)

    Exemple 1 : avec [15, 5, 10, 20]
    Initialisation : tab_verif [true, false, false, false]
    Le plus petit est 5 (1 parcours)
    15 = 5 * 3 -> tab_verif [2 (3 - 1)] = true
    05 = 5 * 1 -> tab_verif [0 (1 - 1)] = true // déjà fait
    10 = 5 * 2 -> tab_verif [1 (2 - 1)] = true
    20 = 5 * 4 -> tab_verif [3 (4 - 1)] = true

    À la fin tab_verif [true, true, true, true], avec 1 parcours, on remarque que toutes les cases sont vraies : tous des multiples

    Évidement, si la valeur n'est pas un multiple (la reste de la division est différent de 0), alors on arrête l'algo.


    Exemple 2 : avec [2, 4, 8]
    Initialisation : tab_verif [true, false, false]
    Le plus petit est 2 (1 parcours)
    2 = 2 * 1 -> tab_verif [0 (1 - 1)] = true // déjà fait
    4 = 2 * 2 -> tab_verif [1 (2 - 1)] = true
    8 = 2 * 4 -> mais 3 (4 - 1) est hors tableau, on ne fait rien // peut-être qu'on peut arrêter l'algo ici, on sait qu'il manquera 1 multiple

    À la fin tab_verif [true, true, false], avec 1 parcours, on remarque qu'1 case est à faux : il manque 6 (2 * (2 + 1))


    Exemple 3 : avec [15, 5, 15, 15]
    Initialisation : tab_verif [true, false, false, false]
    Le plus petit est 5 (1 parcours)
    15 = 5 * 3 -> tab_verif [2 (3 - 1)] = true
    05 = 5 * 1 -> tab_verif [0 (1 - 1)] = true // déjà fait
    15 = 5 * 3 -> mais la case 2 (3 - 1) est déjà à vraie donc on a un doublon

Discussions similaires

  1. [JavaScript] Suppression des multiples dans un tableau (array) alphanumérique
    Par danielhagnoul dans le forum Contribuez
    Réponses: 0
    Dernier message: 07/06/2011, 12h40
  2. valeur xml et multiplication dans un tableau
    Par frexville dans le forum Langage
    Réponses: 4
    Dernier message: 27/09/2010, 14h51
  3. Réponses: 5
    Dernier message: 17/07/2008, 10h18
  4. checkbox multiple dans un tableau
    Par yviii dans le forum Général JavaScript
    Réponses: 1
    Dernier message: 21/06/2007, 17h40
  5. [DDE]selection multiple dans un tableau Excel
    Par NewbiePower dans le forum VBA Access
    Réponses: 9
    Dernier message: 23/03/2007, 14h08

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo