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
    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 :


    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
    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
    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
    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
    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é
    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 développeur des cavernes"
    https://www.youtube.com/channel/UCSz...bYl_pSNMv_zerQ

  7. #7
    Expert éminent
    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
    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é
    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
    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é
    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
    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
    @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

###raw>template_hook.ano_emploi###