Diviseurs en C++ et bonnes pratiques

Le
Olivier Miakinen
Bonjour,

Ma principale expérience de C++ consiste en la maintenance de programmes
sous Windows avec Visual C++, sans aucune utilisation
de bibliothèque standard. Je voudrais remédier à cela en m'entraînant
sur Linux (avec gcc je suppose). Or il se trouve que j'ai un petit
problème à résoudre, et je pense que ça pourrait être l'occasion, mais
j'aurais besoin d'un peu d'aide au début pour le faire « à la C++ » et
pas avec les méthodes C que j'ai toujours utilisées jusqu'à présent.

Le « début » en question consiste à partir de la suite des nombres de 1
à 200 (dans un vector, je suppose), pour chaque nombre de déterminer la
liste ordonnée de ses diviseurs (dans d'autres vector sans doute), puis
d'écrire sur stdout toutes les décompositions des nombres en produits de
deux facteurs.

Par exemple, cela pourrait donner ceci :
1 : 1×1
2 : 1×2
3 : 1×3
4 : 1×4 2×2

8 : 1×8 2×4
9 : 1×9 3×3
10 : 1×10 2×5

36 : 1×36 2×18 3×12 4×9 6×6

199 : 1×199
200 : 1×200 2×100 4×50 5×40 8×25 10×20

Je ne cherche pas nécessairement à ce qu'on me mâche tout le boulot,
mais déjà, si quelqu'un pouvait m'indiquer où trouver d'une part les
bonnes pratiques C++ et d'autre part s'il existe une bibliothèque de
maths qui gère les décompositions en nombres premiers et les diviseurs,
ça me serait très utile.

Cordialement,
--
Olivier Miakinen
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 5
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Fabien LE LEZ
Le #22645381
On Tue, 05 Oct 2010 01:14:20 +0200, Olivier Miakinen

Le « début » en question consiste à partir de la suite des nombres de 1
à 200 (dans un vector, je suppose), pour chaque nombre de déterminer la
liste ordonnée de ses diviseurs (dans d'autres vector sans doute),



Pourquoi voudrais-tu stocker ces informations, s'il s'agit juste de
les afficher ?

Le problème de ton problème, c'est qu'il est trop trivial pour faire
quelque chose d'intéressant :

#include <iostream>

int main()
{
using std::cout;

for (int n=1; n< 0; ++n)
{
cout << n << " :";
for (int d=1; d*d<=n; ++d)
{
if (n%d==0)
{
cout << " " << d << "×" << (n/d);
}
}
cout << "n";
}
}

J'ai passé pas mal de temps sur les problèmes de projecteuler.net. Ils
sont intéressants d'un point de vue mathématique, mais ils n'aident
pas du tout à acquérir de bons réflexes en C++.

En revanche, réimplémenter la commande Unix "sort" (qui lit un fichier
ligne par ligne, et le régurgite en triant les lignes) pourrait
s'avérer un exercice intéressant.
James Kanze
Le #22645761
On Oct 5, 2:07 am, Fabien LE LEZ
On Tue, 05 Oct 2010 01:14:20 +0200, Olivier Miakinen

En revanche, réimplémenter la commande Unix "sort" (qui lit un fichie r
ligne par ligne, et le régurgite en triant les lignes) pourrait
s'avérer un exercice intéressant.



Si le fichier tiens en mémoire, c'est trivial (std::sort).
Sinon, ça se complique, parce qu'on veut tenir un maximum en
mémoire à la fois, ce qui exclut std::vector (et
std::bad_alloc -- c'est un cas où new(nothrow) s'impose).

Mais à titre d'exercise, peut-être. En fixant le nombre maximum
de lignes (disons 100000) qu'on traite à la fois.

--
James Kanze
Fabien LE LEZ
Le #22646131
On Tue, 5 Oct 2010 00:48:56 -0700 (PDT), James Kanze

Si le fichier tiens en mémoire, c'est trivial (std::sort).



Yep, mais c'est tout de même une introduction aux iostreams, et aux
conteneurs et algorithmes.

Sinon, ça se complique, parce qu'on veut tenir un maximum en
mémoire à la fois, ce qui exclut std::vector



Oui, c'est un peu moins trivial.
Intuitivement, je dirais qu'il vaut mieux utiliser mmap(), histoire de
ne pas recopier une partie du fichier dans le swap.
S'il n'y a pas trop de lignes, on peut stocker en mémoire l'offset de
chaque ligne et ses premiers octets.
Après, évidemment, il faudra concevoir un algorithme pour tirer le
meilleur parti des pages récemment chargées en RAM physique.

(et
std::bad_alloc -- c'est un cas où new(nothrow) s'impose).



Dans quelles conditions un bad_alloc est-il lancé ? Quand l'espace
d'adressage (2 à 3 Go en 32 bits) est plein ?
Olivier Miakinen
Le #22646741
Bonjour,

Le 05/10/2010 03:07, Fabien LE LEZ a écrit :

Le « début » en question consiste à partir de la suite des nombres de 1
à 200 (dans un vector, je suppose), pour chaque nombre de déterminer la
liste ordonnée de ses diviseurs (dans d'autres vector sans doute),



Pourquoi voudrais-tu stocker ces informations, s'il s'agit juste de
les afficher ?



C'est parce qu'il ne s'agit pas « juste » de les afficher ; ceci n'est
que la première partie des traitements à effectuer.


Pour avoir une idée de ce que je cherche à faire, sache qu'il s'agit
d'une énigme mathématique similaire (mais pas identique) à celle qui est
étudiée dans le paragraphe IV 5 de la FAQ de fr.sci.maths :
moi qui avais rédigé cette partie).

Pour ceux qui auraient la flemme de cliquer sur le lien, voici l'énoncé
de l'énigme :

Un prof de maths donne un problème à résoudre à ses deux meilleurs
élèves, Pierre et Sophie. Il donne à Pierre le produit de deux nombres
entiers compris (au sens large) entre 2 et 100, et à Sophie la somme
des deux mêmes nombres, puis il leur demande s'ils peuvent déterminer
quels étaient les nombres de départ.

Pierre: Non, je ne peux pas trouver ces deux nombres.

Sophie: Je le savais.

Pierre: Dans ce cas, je connais les deux nombres.

Sophie: Alors moi aussi.

Sachant que les deux élèves sont d'excellents logiciens et que leurs
quatre déclarations étaient rigoureusement exactes, saurez-vous être
aussi futés qu'eux, et trouver les deux nombres choisis par le
professeur ?

La solution consistait à passer en revue toutes les sommes possibles,
pour chaque somme lister les produits possibles, puis à rechercher les
produits présents dans plusieurs sommes pour éliminer petit à petit les
nombres qui ne conviennent pas. À l'époque j'avais fait un programme en
C pour obtenir ces listes successives.


L'énigme à laquelle je m'attelle maintenant est différente (d'ailleurs
je dois commencer par lister les produits et non les sommes), mais je
n'ai pas envie de l'écrire ici avant de la résoudre moi-même car mon
intention est de la proposer ensuite dans fr.rec.jeux.enigmes. Cela dit,
je peux te l'envoyer en privé si tu es intéressé.


[...]

J'ai passé pas mal de temps sur les problèmes de projecteuler.net. Ils
sont intéressants d'un point de vue mathématique, mais ils n'aident
pas du tout à acquérir de bons réflexes en C++.



Merci, je ne connaissais pas ce site.

En revanche, réimplémenter la commande Unix "sort" (qui lit un fichier
ligne par ligne, et le régurgite en triant les lignes) pourrait
s'avérer un exercice intéressant.



Ah oui, aussi.

Cordialement,
--
Olivier Miakinen
Fabien LE LEZ
Le #22646841
On Tue, 05 Oct 2010 13:22:00 +0200, Olivier Miakinen

je peux te l'envoyer en privé si tu es intéressé.



Effectivement, ce serait sans doute aussi bien. Enfin, envoie surtout
ta méthode de résolution. Mon adresse reply-to
() est fonctionnelle.

À vue de nez, set<> te sera plus utile que vector<>, mais c'est
difficile d'en dire plus tant que je suis dans le vague.
Olivier Miakinen
Le #22647511
Le 05/10/2010 14:01, Fabien LE LEZ a écrit :
On Tue, 05 Oct 2010 13:22:00 +0200, Olivier Miakinen

je peux te l'envoyer en privé si tu es intéressé.



Effectivement, ce serait sans doute aussi bien.



Je vais le faire, mais...

Enfin, envoie surtout
ta méthode de résolution. Mon adresse reply-to
() est fonctionnelle.



... mais pour simplifier les choses, je propose d'en rester à l'énigme
déjà résolue. Le premier avantage est qu'on pourra immédiatement
vérifier que le résultat est correct. En outre, ça me permettra de
m'occuper de l'autre cas tout seul, ce qui devrait être un exercice plus
profitable que de le voir faire par d'autres.

À vue de nez, set<> te sera plus utile que vector<>, mais c'est
difficile d'en dire plus tant que je suis dans le vague.



À vue de nez, en lisant la doc je suis persuadé que tu as raison :

Bien, voici ma méthode de résolution.

####################################################################
1re étape

Lister l'ensemble (« set ») de tous les nombres entiers compris entre
4 et 200. Ce sont les sommes possibles de deux nombres compris entre
2 et 100.

Pour chacune de ces sommes S, lister l'ensemble des produits possibles.
Algo pour une somme S donnée :
pour tout A entier tel que 2 <= A <= S/2, on calcule P = A*(S-A)

Résultat :
4 : 4
5 : 6
6 : 8 9
7 : 10 12
8 : 12 15 16
9 : 14 18 20
10 : 16 21 24 25
11 : 18 24 28 30
12 : 20 27 32 35 36
13 : 22 30 36 40 42
14 : 24 33 40 45 48 49
15 : 26 36 44 50 54 56
16 : 28 39 48 55 60 63 64
17 : 30 42 52 60 66 70 72
...
200 : 396 591 784 ... 9999 10000

####################################################################
2e étape

Extraire (je veux dire conserver) de l'ensemble de données de l'étape 1
les lignes correspondant aux sommes pour lesquels aucun des produits
n'est unique sur l'ensemble des résultats.

Par exemple, on ne garde pas la somme 10 parce que le produit 21
n'appartient à aucune autre somme que 10.

Inversement, on conserve la somme 11 parce que tous ses produits
existent ailleurs :
- le produit 18 appartient aux sommes 9 et 11
- le produit 24 appartient aux sommes 10, 11 et 14
- le produit 28 appartient aux sommes 11 et 16
- le produit 30 appartient aux sommes 11, 13 et 17

Bien sûr, il faut travailler sur une copie plutôt que d'effacer les
lignes au fur et à mesure. Sinon, ayant éliminé la ligne 9 à cause de
son produit 14, on éliminera ensuite à tort la ligne 11 à cause de son
produit 18 qui était dans la ligne 9 !

À l'issue de cette étape, on aura :
11 : 18 24 28 30
17 : 30 42 52 60 66 70 72
23 : 42 60 76 90 102 112 120 126 130 132
27 : 50 72 92 110 126 140 152 162 170 176 180 182
29 : 54 78 100 120 138 154 168 180 190 198 204 208 210
35 : 66 96 124 150 174 196 216 234 250 264 276 286 294 300 304 306
37 : 70 102 132 160 186 210 232 252 270 286 300 312 322 330 336 340
342
41 : 78 114 148 180 210 238 264 288 310 330 348 364 378 390 400 408
414 418 420
47 : 90 132 172 210 246 280 312 342 370 396 420 442 462 480 496 510
522 532 540 546 550 552
53 : 102 150 196 240 282 322 360 396 430 462 492 520 546 570 592 612
630 646 660 672 682 690 696 700 702

####################################################################
3e étape

Supprimer tous les produits qui se trouvent encore dans plusieurs
sommes. Par exemple, les 30 qui sont dans les sommes 11 et 17, les 42
qui sont dans les sommes 17 et 23, etc.

On obtient :
11 : 18 24 28
17 : 52
23 : 76 112 130
27 : 50 92 110 140 152 162 170 176 182
29 : 54 100 138 154 168 190 198 204 208
35 : 96 124 174 216 234 250 276 294 304 306
37 : 160 186 232 252 270 336 340
41 : 114 148 238 288 310 348 364 378 390 400 408 414 418
47 : 172 246 280 370 442 480 496 510 522 532 540 550 552
53 : 240 282 360 430 492 520 570 592 612 630 646 660 672 682 690 696
700 702

####################################################################
4e étape

Supprimer toutes les sommes qui ont conservé plusieurs produits.

On obtient :
17 : 52

... et c'est gagné.


Voilà, merci pour toute aide !

Cordialement,
--
Olivier Miakinen
Olivier Miakinen
Le #22647621
Le 05/10/2010 18:19, je me suis gouré :

####################################################################
1re étape

[...]
Algo pour une somme S donnée :
pour tout A entier tel que 2 <= A <= S/2, on calcule P = A*(S-A)



Il faut bien sûr que S-A soit lui aussi inférieur ou égal à 100.

Donc, sauf erreur : Max(2, S-100) <= A <= S/2

Résultat :
[...]
200 : 396 591 784 ... 9999 10000



200 : 10000

Désolé.
James Kanze
Le #22647611
On Oct 5, 10:05 am, Fabien LE LEZ
On Tue, 5 Oct 2010 00:48:56 -0700 (PDT), James Kanze

>Si le fichier tiens en mémoire, c'est trivial (std::sort).

Yep, mais c'est tout de même une introduction aux iostreams, et aux
conteneurs et algorithmes.



En fait, un niveau encore plus élémentaire que je pensais. En
fait, tu as raison. Pour ça, c'est une très bonne introduction.

>Sinon, ça se complique, parce qu'on veut tenir un maximum en
>mémoire à la fois, ce qui exclut std::vector

Oui, c'est un peu moins trivial.
Intuitivement, je dirais qu'il vaut mieux utiliser mmap(), histoire de
ne pas recopier une partie du fichier dans le swap.



Il faut bien recopier un peu, non ? Si le fichier ne tient pas
en mémoire, tu ne peux pas le mmapper d'un coup non plus. Et
puis, je ne suis pas trop convaincu de l'intérêt de mmap ici.
Tu ne peux pas swapper des lignes directement dans le fichier,
étant donné qu'elles ont des longueurs différentes.

S'il n'y a pas trop de lignes, on peut stocker en mémoire l'offset de
chaque ligne et ses premiers octets.



Avec un seek et une lecture chaque fois que tu veux faire une
comparaison ?

Après, évidemment, il faudra concevoir un algorithme pour tirer le
meilleur parti des pages récemment chargées en RAM physique.

> (et
>std::bad_alloc -- c'est un cas où new(nothrow) s'impose).

Dans quelles conditions un bad_alloc est-il lancé ? Quand l'espace
d'adressage (2 à 3 Go en 32 bits) est plein ?



Quand une allocation échoue. Ici, tu ne veux pas que std::vector
s'ammuse à faire des réallocations (et laissant de la mémoire
que tu ne pourrais pas utiliser par la suite). Or ici, tu veux
réagir à l'échec de l'allocation en triant ce que tu as en
mémoire et en l'écrivant dans un fichier temporaire, pour
récommencer. (Ensuite, évidemment, il faut merger les fichiers
temporaires.)

--
James Kanze
Jean-Marc Bourguet
Le #22647751
James Kanze
On Oct 5, 10:05 am, Fabien LE LEZ > On Tue, 5 Oct 2010 00:48:56 -0700 (PDT), James Kanze
>
> >Si le fichier tiens en mémoire, c'est trivial (std::sort).

> Yep, mais c'est tout de même une introduction aux iostreams, et aux
> conteneurs et algorithmes.

En fait, un niveau encore plus élémentaire que je pensais. En
fait, tu as raison. Pour ça, c'est une très bonne introduction.



J'ai deja pose la question en interview. C'est un bon point de depart pour
discutter des variantes avec une grande variete de niveau de candidats.

A+

--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
James Kanze
Le #22649251
On Oct 5, 6:19 pm, Jean-Marc Bourguet
James Kanze > On Oct 5, 10:05 am, Fabien LE LEZ > > On Tue, 5 Oct 2010 00:48:56 -0700 (PDT), James Kanze
> >
> > >Si le fichier tiens en mémoire, c'est trivial (std::sort).

> > Yep, mais c'est tout de même une introduction aux iostreams, et aux
> > conteneurs et algorithmes.

> En fait, un niveau encore plus élémentaire que je pensais. En
> fait, tu as raison. Pour ça, c'est une très bonne introduction.

J'ai deja pose la question en interview. C'est un bon point
de depart pour discutter des variantes avec une grande variete
de niveau de candidats.



En effet. Je crois que je l'adopterai aussi. Bien que...

Dans l'ensemble, à juger d'après les candidats que j'interviewe
(parfois pour des postes d'assez haut niveau), les connaissances
réeles de C++ sont prèsque toujours minimal. Je ne crois pas
avoir vu un candidat qui aurait énoncé ma solution, ni même
quelque chose de proche. En revanche, il y en a bien eu qui
savait très bien apprendre, une fois renseignés sur ce qu'on
voulait qu'ils apprennent, et qui s'en tirent fort bien une fois
embauchés.

Mais c'est peut-être lié au contexte. Nous récherchons surtout
une maîtrise du calcul numérique, avec des connaissances des
algorithmes de marché, si possible. Le C++ est important, mais
pas primordial. (Et en passant, nous recherchons toujours.)

--
James Kanze
Publicité
Poster une réponse
Anonyme