Curriculum and Labs for Engineering Education

cancel
Showing results for 
Search instead for 
Did you mean: 

Challenge mathématique #34 : La constante de Champernowne

Nouveau défi pour le mois de Juin

Comme pour tous les autres challenges, un gagnant ! ce mois ci encore le Livre LabVIEW de chez Dunod de plus de 400 pages

Pour participer il suffit de créer un petit VI LabVIEW nommé Challenge 34_votre speudo.vi et de me l'envoyer à emmanuel.roset@ni.com avant le 30 juin.

Pensez à participer à la communauté pour partager vos soucis ou expériences sur ce défi et de poster un "code envoyé" pour être sur que les filtres emails me permettent d'oublier personne

Le gagnant sera sélectionné au hasard parmi les VI fonctionnels (je doute pas qu'il y en aura beaucoup)

Voici le défi :

La constante de Champernowne est un nombre compris entre 0 et 1, dont le développement décimal est obtenu en écrivant successivement les nombre entiers. Elle commence ainsi :

0,12345678910111213141515171819202122...

Numérotons les chiffres situés après la virgule. Le chiffre 1 est 1, le chiffre 9 est 9, le chiffre 10 est 1 et le chiffre 11 est 0, le chiffre 12 est 1, etc...


Deux entiers n1 et n2 sont donnés en entrée de ce problème. Vous devez donner la somme des chiffres n1 à n2 inclus.


Par exemple, si n1=11 et n2=21, il faut sommer ces chiffres :


        0 , 12345678910111213141516171819202122 ...

                                                         |                     |

                      11        21

La réponse à donner serait alors : 0 + 1 + 1 + 1 + 2 + 1 + 3 + 1 + 4 + 1 + 5 = 20

Donc deux entrées n1 et n2 et une sortie S sur le VI (le type qui vous convient)

Pas de limite sur longueur de la constante (au dela de 19 chiffres après la virgule)

n2 < 10e6

N'hésitez pas à poster des questions

Bon défi

Emmanuel


Comments
Cisco
Active Participant
Active Participant
on

Code envoyé!

Francis M
Olivier_L
Active Participant
Active Participant
on

code envoyé

Olivier L. | Certified LabVIEW Developer


didje007
Active Participant
Active Participant
on

code envoyé

MaherHAMDI
Member
Member
on

Code envoyé !!

Bilsix
NI Employee (retired)
on

Code envoyé !

Bilsix.
David-K
Member
Member
on

Code envoyé

PhilB58
Active Participant
Active Participant
on

Code envoyé

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

Bonjour Emmanuel,

faut-il gérer pour n2 > à la limite d'un I32 (ou d'un U32) ?

par exemple :

n1 = 5.000.000.000  et  n2 = 5.000.000.850

autrement dit :

Les codes qui ne sont valides que pour n2 =< à la limite d'un I32 sont-ils acceptés ? (ou pas)

PhilB58
Active Participant
Active Participant
on

Bonjour Ouadji,

N1 et N2 en entiers signés, ça n'a pas beaucoup de sens à mon avis, donc U32 conviendrait bien.

Ensuite, même si la constante de Champernowne est infinie puisqu'il est toujours possible d'ajouter des décimales à l'infini, définir N1 et N2 dans des valeurs de 5.000.000.000 n'a pas beaucoup de sens non plus.

Je pense que le but du VI demandé dans ce challenge n'est pas là, la contrainte de 19 chiffres après la virgule impose juste une certaine approche autre qu'arithmétique .

Bonne programmation.

emmanuel-fr
Member
Member
on

Bonjour,

En effet, la constante peut facilement dépasser les 19 chiffres après la virgule comme dans l'exemple donné sinon ca sert à par grand chose. Donc arithmétiquement ce n'est simplement pas possible, il faut un algorithme de décomposition de la constante.

Maintenant, le but du challenge n'est pas cette fois de repartir sur un piège de dépassement. On va limiter les valeurs de n2 à des valeurs gérables facilement par des I32 ou U32.

D'ailleurs, n2 sera inférieur à 10e6 pour se focaliser sur un algorithme simple mais efficace.

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

@ PhilB58 :

Je suis d'accord concernant le I32 ... n1 et/ou n2 négatif(s) n'a pas de sens, nous sommes d'accord.

Ceci dit, le fait d'utiliser un I32 n'induit pas obligatoirement que l'on puisse entrer un nombre négatif

Il suffit de limiter aux nombres >=0 dans : Properties / Data Entry / minimum.

Alors pourquoi utiliser un I32 ?

Pour éviter des conversions à gauche et à droite pour entrer sur les fonctions LV, index array, array subset, etc...

définir N1 et N2 dans des valeurs de 5.000.000.000 n'a pas beaucoup de sens non plus.

Ah bon ? et pourquoi cela n'aurait-il pas beaucoup de sens ??

La constante de Champernowne étant infinie ....

je ne vois pas (du tout) pourquoi un n1-n2 de l'ordre de 5e9 aurait "moins de sens" qu'un n1-n2 de 11 et 21.

@ Emmanauel :

On va limiter les valeurs de n2 à des valeurs gérables facilement par des I32 ou U32.

n2 sera inférieur à 10e6 pour se focaliser sur un algorithme simple mais efficace


ok, compris.

bonne journée à toutes et tous.

PhilB58
Active Participant
Active Participant
on

C'était juste un avis, pas une critique!

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

pas de soucis Phil (réellement aucun)      (ceci dit, tu peux critiquer)

mais le fait que cela " avait peu de sens pour 5e9 " ...

cela m'a étonné, je me suis demandé pourquoi tu disais cela (tout simplement)

et si on échangeait un résultat ou deux ... histoire de "voir" si on est sur la bonne route ?

par exemple n1=100.000  et  n2=100.100 ... S? .. cela intéresse-t-il de "vérifier entre nous" ?    (ou pas)

PhilB58
Active Participant
Active Participant
on

Je n'ai pas de soucis, je trouvais juste que si ton code fonctionne avec 11 et 21 pour n1 et n2, il doit fonctionner avec d'autres valeurs, même très grandes (sans oublier d'en tenir compte pour la représentation parce que U8, ça va coincé ).

Pour la réponse à ta question, je trouve 266 !

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

@ Phil :

" parce que un U8, ça va coincer " ... ... élémentaire mon cher Watson 

266 ... idem, je confirme.

emmanuel-fr
Member
Member
on

Bien vu Ouadji, tous les codes ne passent pas le test du 100.000 alors qu'ils passent le 11,21 car optimisés pour cela

Pour info, vous avez tous les deux raison

Olivier_L
Active Participant
Active Participant
on

Le mien aussi passe, à 266 😄

Olivier L. | Certified LabVIEW Developer


MaherHAMDI
Member
Member
on

Mon deuxième code passe bien le test (si on change la représenation de l'indicateur S) :!

Olivier_L
Active Participant
Active Participant
on

Pendant mon dev, j'avais remarqué une potentielle erreur dans le cas où n1 et n2 inférieurs à 10.

Et bien sûr, la prise en compte du n1>n2, sait-on jamais...

Olivier L. | Certified LabVIEW Developer


ouadji
Trusted Enthusiast
Trusted Enthusiast
on

et celui-ci :

oui, je sais, c'est au dessus de 10e6 ... juste pour le plaisir 

n1 : 1.000.000.000

n2 : 1.000.001.000

S = 4248

qui peut me confirmer (ou pas) ? ... allez, on croise les doigts 

@ Olivier_L :" Et bien sûr, la prise en compte du n1>n2, sait-on jamais "

oui, j'ai prévu aussi ... histoire "d'être propre" 

Olivier_L
Active Participant
Active Participant
on

Bon, après une rectification de mon VI qui m'emmenait en saturation mémoire,

je confirme S= 4248 😉

Olivier L. | Certified LabVIEW Developer


ouadji
Trusted Enthusiast
Trusted Enthusiast
on

Bonjour Olivier,

pas assez de mémoire ... c'était le piège avec 1e9 

Tu confirmes 4248, ok, super.

Bonne journée à tous.

ouadji
Trusted Enthusiast
Trusted Enthusiast
on
Bilsix
NI Employee (retired)
on

J'ai de mon côté aussi un problème de mémoire pour des chiffres de l'ordre du milliard, comme Olivier_L, mais je ne sais comment résoudre le problème...
Comment vous y êtes vous pris pour éviter ça ? Une piste ?

Bilsix.
ouadji
Trusted Enthusiast
Trusted Enthusiast
on

@ Bilsix : une piste ?

Est-il réellement nécessaire de construire la chaîne complète des décimales ?

Bilsix
NI Employee (retired)
on

On est d'accord ouadji, mais cela ne résoud pas le cas où n1 = 2 et n2 = 1.000.000.003 par exemple !
Sauf si...

Je vais tester un petit truc et je reviens vers toi !

Bilsix.
ouadji
Trusted Enthusiast
Trusted Enthusiast
on

@Bilsix : " mais cela ne résoud pas le cas où n1 = 2 et n2 = 1.000.000.003 par exemple "

Si tu veux résoudre le cas que tu mentionnes : (sans avoir de soucis de mémoire)

Une fois que tu es arrivé au début de la "fenêtre" (n1), idem, il ne faut pas construire toute la chaine (n1-n2), mais procéder au fur et à mesure. En fait, tu ne construis aucune chaine (ni aucun Tableau). Tu commences ton addition à n1b =< n1 et tu la termines à n2b >= n2. Pour terminer il faudra retirer de l'addition finale les parties excédentaire (n1 - n1b) et/ou (n2b - n2). Du début à la fin, tu n'auras concaténer aucune chaine et tu n'auras construit aucun Tableau.

Olivier_L
Active Participant
Active Participant
on

Du début à la fin, tu n'auras concaténer aucune chaine et tu n'auras construit aucun Tableau.

Pour ma part, je ne suis pas allé aussi loin que toi dans l'optimisation Ouadji.

Notamment parce que je n'aime pas les maths et que je n'avais pas envie de me prendre la tête à réfléchir à ces valeurs de n1b et n2b.

Donc j'ai fait de la concaténation de chaines, mais effectivement, il faut éviter les tableaux pour ne pas avoir de problèmes de mémoire.A vrai dire, avec la concaténation de chaines, on arrivera effectivement à une saturation mémoire à un moment, mais la demande d'origine étant n2<10e6, il ne devrait pas y avoir trop de soucis.

Pour info, avec les valeurs de Bilsix de 2 et 1.000.000.003, je trouve 4.366.712.394 ^^

Olivier L. | Certified LabVIEW Developer


ouadji
Trusted Enthusiast
Trusted Enthusiast
on

@ Olivier :

le filou ...  un U64 en sortie 

je confirme : n1 = 2 , n2 = 1.000.000.003  >>  S = 4.366.712.394  (j'ai le même résultat)

Sebastien_D
Member
Member
on

Code envoyé !

didje007
Active Participant
Active Participant
on

Toutes vos discussion m'ont fait me repencher sur mon code et je me suis rendu compte qu'il ne fonctionnait que pour le cas particulier 11 et 21.

Concernant l'optimisation que tu proposes ouadji, elle n'est pas nécessaire avec la consigne n2<10e6 c'est pourquoi je ne l'avais pas intégré au début.

Mais c'est toujours intéressant de se poser des questions sur les limites d'un code surtout quand l'algo est aussi simple que peut l'être celui ci.

Donc Nouveau Code envoyé!

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

@ didje : " Concernant l'optimisation que tu proposes ouadji ..."

une autre ...

Il n'est pas nécessaire de "balayer" l'ensemble des nombres pour trouver celui qui est pointé par n1.

Il existe 9 nombres de 1 digit (1>9) ... 90 pour 2 digits (10>99) ... 900 pour 3 digits (100>999) ... etc

Quelle que soit la taille de n1, il est donc possible de calculer directement sur quel nombre n1 pointe,

ainsi que la position "dans" ce nombre ... soit le "point d'entrée" à partir duquel l'addition commence.

"c'est toujours intéressant de se poser des questions sur les limites d'un code"  super vrai !

"surtout quand l'algo est aussi simple" ... humm, réellement "aussi simple" ? 

bonne journée à toutes et tous.

beno72
Member
Member
on

code envoyé

Didier_Bleses
Member
Member
on

Code envoyé

Nico_EMC
Member
Member
on

Code envoyé (un peu tardif ce mois-ci)

Alice_M
Member
Member
on

Code envoyé

Pierre-Alexis
Member
Member
on

Eh bien voici mon code pour ce premier défi, je n'en avais pas connaissance auparavant! C'est ludique et rapide, parfait pour la pause!

Ingénieur Instrumentation Michelin
Certifié CLD
emmanuel-fr
Member
Member
on

Petit update des codes recus dans ma boite à ce jour.

15 compétiteurs . Vérifiez que vous êtes dans la liste et que je ne vous ai pas manqué dans les emails. Merci !

Bientot la fin du mois...

1 - Challenge34_cisco.vi
2 - Challenge 34_LABONNE V3.vi
3c - Challenge  34_Didje 007_2.vi
4A et B - Challenge 34_MaherHAMDI-V2.vi
5 - Challenge_34_Bilsix.vi
6 - Challenge 34_Evad_I.vi
7 - Challenge 34_PhilB58.vi
8c Challenge 34_ouadji_code_final.zip
9 - Challenge 34_Jules1403.vi
10 - CH34_Sebastien_D.zip
11 - Challenge34_beno72.vi
12 - Challenge 34_Didier_Bleses
13 - Challenge34_NICO_EMC.vi
14 _Alice_M_ch34.vi
15 - Challenge 34_Pierre-Alexis.vi
ALoa
Member
Member
on

Code envoyé

emmanuel-fr
Member
Member
on

Il est temps de cloturer les réponses au challenge 34.

Voici le tableau des nominés pour le prix et le résultat des valeurs de test

Le tirage au sort se fera sur la première boule du loto de samedi 2 juillet. Il y a 15 candidats donc en x3 chacun aura 3 boules de 1 à 45 sur les 49. Si la première boule est entre 46 et 49 alors on prend la 2e etc... bonne chance pour le Livre LabVIEW et merci pour votre participation !

Publications des codes réponses très bientôt en bas de l'énoncé (en pièce jointe)

Numéro de tirageOrdre d'arrivée des codes et pseudosTest (100 000 ; 100 100) = 266Test (1 ; 1e6) = 4176766
1         1 - Challenge34_cisco.viOK

OK
2         2 - Challenge 34_LABONNE V3.viOK

OK
3         3c - Challenge  34_Didje 007_2.viOK

OK
4         5 - Challenge_34_Bilsix.viOK

OK
5         6 - Challenge 34_Evad_I.viOK

OK
6        7 - Challenge 34_PhilB58.viOK

OK
7        8c Challenge 34_ouadji_code_final.zipOK

OK
8        10 - CH34_Sebastien_D.zipOK

OK
9        11 - Challenge34_beno72.viOK

OK
10        12 - Challenge 34_Didier_BlesesOK

OK
11        13 - Challenge34_NICO_EMC.viOK

OK
12        14 _Alice_M_ch34.viOK

OK
13        15 - Challenge 34_Pierre-Alexis.viOK

OK
14        17 - Challenge 34_JFI.viOK

OK
15        18 - Challenge 34_vdparter.viOK

OK







4A et B - Challenge 34_MaherHAMDI-V2.viLimité 40 decimales
Impossible

9 - Challenge 34_Jules1403.vi264

4176765

16 - Challenge34_ALoa.vi264

4176765
PhilB58
Active Participant
Active Participant
on

Qui est l'heureux élu???

emmanuel-fr
Member
Member
on

Exact, 

Voici le résulat du loto de samedi 2 :

SAMEDI  02/07/20168243117165

La première boule à être tombée est le 8 ! je regardais en plus

Donc cela donne le 3e de notre liste

Le gagnant est Didje 007 !!

Bravo

PhilB58
Active Participant
Active Participant
on

Bravo Didje 007
Hmmm, comme un air d'agent secret de sa majesté, sans doute qu'il a des tuyaux pour faire sortir la bonne boule du Lotto, ... s'il pouvait nous donner les boules du prochain tirage, on serait tous gagnant

Sebastien_D
Member
Member
on

Grosse déception pour moi qui étais certain d'avoir gagné en regardant le loto samedi...

Apparemment il y avait deux interprétations au règlement et j'ai cru la mauvaise.

Alice_M
Member
Member
on

Bonjour,

Excuse moi Emmanuel, mais je n'avais pas compris la règle comme ça en lisant ton post.

J'avais compris que la liste serait parcourue trois fois de suite, avec chacun son numéro.

Par exemple, pour la première personne sur la liste, les numéros attribués seraient le 1, 16 et 31.

Je ne sais pas si je suis la seule à avoir compris les choses ainsi, et du coup pour moi le gagnant était Sebastien_D.

Bravo à didje, toutefois

Olivier_L
Active Participant
Active Participant
on

Personnellement, j'avais bien compris que j'avais les boules de 4 à 6, mais ma boule n'est sortie qu'en dernière, cette grosse faignasse ^^

Félicitations à Didje!!

Et bravo à tous pour vos codes fonctionnels!!

Olivier L. | Certified LabVIEW Developer


Bilsix
NI Employee (retired)
on

Salut à tous !
Je m'étais aussi fait avoir, je pensais à la méthode "1, 16, 31" et non "1, 2, 3". Attends voir Olivier, te plains pas, la mienne n'est même pas sortie !! ^^
Est-il possible d'avoir accès aux codes fonctionnels Emmanuel ? Mon code était limité au milliard il me semble, mais je sais que d'autres ont réussi à contourner ce problème...

Bilsix.
emmanuel-fr
Member
Member
on

Désolé, je reconfirme. J'utilise ce même principe de N boules par numéro de candidat à chaque fois pour remplir le maximum de valeurs jusqu'à 49 afin d'éviter principalement que nous ayons a attendre plusieurs tirages avant d'avoir un gagnant. Ces boules ont tendance a sortir toujours en dehors des valeurs...

J'espère qu'un jour nous aurons 49 candidats !!

Oui je vais publier tous les beaux codes rapidement !

didje007
Active Participant
Active Participant
on

Merci à Emmanuel,

La méthode de désignation du vainqueur était expliqué en détail dans le challenge 30 notamment. Mais je n'étais pas cetain que ce soit encore cette méthode qui soit utilisé, Voilà pourquoi je n'ai pas crier victoire dès hier!!!

ouadji
Trusted Enthusiast
Trusted Enthusiast
on

et bien moi  ... je n'avais jusqu'à présent rien compris au système de choix.

Je me disais ... chuuut, c'est certainement crypté ...

Je viens seulement de "comprendre" ... j'avais donc les boules [19...21]

ouf ... j'ai enfin compris ! 

bravo à Didje, clap, clap, calp ....

Contributors