Discussion :

[Marwaa45]

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

[foetus]

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

[Sve@r]

Salut

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 )

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

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

[foetus]

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

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

[foetus]

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;
}

[Jamatronic]

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.

[Pyramidev]

Bonjour,

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.

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.

[Sve@r]

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é

[foetus]

@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

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