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.

[foetus]

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

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

[Sve@r]

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

[sambia39]

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é) ?

[Sve@r]

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"

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)

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)

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

[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