J'ai vu que certains aimaient bien les petits problèmes.
 
Alors voilà, je me lance donc en espérant que celui-là ne fera pas un bide complet.  
 
Le problème est simple : on a une séquence de 5 millions de chiffres aléatoires dans un tableau.
 
1er problème : (facile) trouver toutes les répétitions de n chiffres successifs dans le tableau. Les écrire dans un fichier txt, ainsi que leurs positions. On fera cette recherche pour toutes les séquences où : 7 <= n <= 15
 
2e problème : (moins facile) trouver la séquence de chiffres la plus longue qui est répétée au moins une fois.
 
Les meilleures solutions sont les plus rapides.
 
 
Ex. de sortie du premier programme :
 

 
 
NB : pour ceux que le challenge intéresse, il faut avoir tous la même séquence aléatoire. Je propose le générateur congruentiel suivant (Knuth) :
 
Graine : r = 17
itérations : r = (1664525 * r + 1013904223) modulo 2^32
 
Les 5 millions de chiffres de la séquences seront générés 5 par 5 en prenant les 5 premiers chiffres de r à chaque fois, donc seulement si r>9999.  
L'opération étant itérée un million de fois (partie non chronométrée).
 
Ouala, bonne cogitation !

Donc, aucune restriction...
 
Le résultat du concours t'interresse-t-il ? (le code)

 
Euh sur quoi ? Sur la mémoire ?
Disons que des solutions "raisonnables" devraient être envisagées, mais les algos intéressants sont tjrs acceptés.
 
Disons 100 Mo de RAM maxi.
 
edit : plutôt 128 Mo...

 
Bien sûr, si ça vous intéresse d'essayer. Un petit concours d'optimisation est tjrs amusant (m^me si c'est du C, mais là, je risque de m'en prendre plein la tête... ).

Y a pas que la mémoire... Le code également :
- code-morphing
- dynamic-code
- FPU ? MMX ? SSE ? SSE2 ? 3DNow ?
...

 
Non, pas d'asm, juste du C/C++ ou autre langage portable.  
 
Edit : Sauf si ça intéresse certains, mais je crains que sur un forum C++...

Faut bien définir les rêgles...
- C/C++ pur sans les fonctions externes (sauf pour l'affichage) ?

 
Ok : C/C++ pur, on a le droit aux librairies standard, c'est tout.

Ben ce problème n'a pas l'air de soulever l'enthousiasme...  

Et zou, histoire que ce problème ne tombe pas tout de suite aux oubliettes.  
 
Allez, à première vue, ça ressemble à du O(N^2), mais il y a clairement une solution simple en O(N*Log(N)), et même une en O(N) pour des petites séquences.

O(N) ? si tu tries que tu parcoures à la recherche de doublon, ça fait du N*Log(N) + N

Squattage newbie : un cours simple sur les calculs de complexité vous auriez ?

 
 
j'avais pas vu ça ... non mais ces quoi ces conneires ? tu te rends compte que c'est peut être la partie qui prends le plus de temps ? rien que cette fonction elle fait chier
 
à ce petit jeu là, t'as plus vite fait de distribuer le fichier avec la séquence

ouais donne la liste, parce que là je commence à péter un plomb j'i bite rien à ta fonction de génération de merde, apprends à t'exprimer

je relirais demain -->

moi je laisse tomber, je me suis assez pris la tête sur des bêtises tout ça parce que l'énoncé est pas clair
 
« seront générés 5 par 5 »
alors la franchement je vois pas. à jamais

Une petite question concernant la génération : tu peux préciser ou se trouve le LSB et le MSB pour 'r' et pour la 'séquence'. Histoire que tout le monde construise la séquence de la même facon.
 
Moi je trouve cette sequence :
 
10422197381276214297921856697316293946912835318827........

 
Si je repete l'opération 1.000.000 de fois, j'obtiens les 2/3 des chiffres demandés. En fait certains résultats de r sont fortement réduits par le modulo (moins de 5 chiffres significatifs).
 
Compte-t-on alors les zéro en position MSB ? Je pense que non mais c'est pas super clair...

 
Ma séquence est pas bonne ! Elle est ennuyante ta formule à coder en C++ !

ATTENTION !!! SOLUTION !!!
Ne lisez pas ce qu'il y a en-dessous si vous voulez chercher encore !
 

 
Oui, c'est ça ma solution en O(N log (N)) (le +O(N) n'a pas besoin d'être précisé, je crois). Mais en commençant à la coder, je me pose une question : le tri a besoin d'une fonction de comparaison, or je me demande si la comparaison des séquences ne va pas tout faire tomber par terre. J'ai bien l'impression que si.
Par ailleurs, ça bouffe quand même pas mal de mémoire : au moins n*N pour des séquences de taille n, plus un buffer en Log(N) supplémentaire pour le quicksort.
Mon autre solution (en fait celle d'un pote) est impraticable pour des séquences de plus de 8 ou 9 chiffres car elle prend 10^n en mémoire. Par contre, je doute qu'on puisse faire plus rapide : il suffit de faire un tableau de tous les nombres possibles avec n chiffres (donc 10^n chiffes), et d'y stocker les listes des index à chaque apparition. Super simple, super rapide mais super dispendieux en RAM.

 
Je sais. Le problème est de remplir le tableau avec des chiffres aléatoires.  
Et puis bon, si c'est ça qui t'empêche de dormir :
 

 
(ps : je sais, l'utilisation du sprintf n'est pas heureuse, mais c'est encore la fonction dont je me souviens le mieux. Enfin bon, on s'en fout, là n'est pas le plus important)

 
C'est pour cela que j'ai précisé "pour r > 9999" dans l'énoncé, donc pour les nombres à 5 chiffres minimum...
 
Mais je suis d'accord, cette partie de l'énoncé est la moins intéressante et la plus rebutante. Le plus simple est que tout le monde parte sur le code que je donne (j'espère qu'il n'y a pas de bug).
 
Pour info, il me donne (N=5000000): (!! FAUX !!)
40 premiers : 1013911964351982868416495267061476227489
40 derniers : 3125048398216972947012249492535033240745

 
Ben oui, c'est bien pour ça que je la proposais.    
 
C'est un bon exercice d'utilisation des conteneurs STL (c'est aussi un bon exercice pour les codeurs en C). Si je suis pas trop paresseux, je m'en ferai peut-être une version des algos en Ocaml aussi (à moins que ça intéresse Joelf ou nraynaud). Une petite comparaison des perfs pourrait être intéressante (je n'ai aucune idée de ce que ça peut donner).
 
Ce problème n'est pas complètement gratuit, il a je pense des connexions (lointaines) avec le problème de séquençage de l'ADN, ou avec l'indexation de grands textes.

sprintf(buf, "%u:5", r);  
 
skoi ça ?

char buf[5] = "\0";  
 
en plus t'es un malin toi
 
 
pas standard
#include <stdio.h>
 
 
 
  const int              N = 5000000;
  const unsigned long SEED = 17L;
   
  void alea(unsigned long &rand){
      static unsigned long r;
      rand = r = 1664525L * r + 1013904223L;
  }  
 
à mettre dans namespace, à inliner
 
 
 
vector<char> &v
 
la je comprends pas le prototype, on parle pas d'entier ?

Bon c'est n'importe quoi la
 
J'ai un code similaire et mon premier nombre est 1042201148. Alors je vois pas comment tu extrais 10139 de ce premier nombre. J'ai vérifié à la main mes premiers nombres ....
 
Pour info, voila mon code de génération :
 

 
Ce qui m'etonne, c'est qu'en C++ la valeur de ton masque ne passe pas. Donc, tu n'appliques pas vraiment la bonne formule (ce qui est mon cas aussi bien sur) donnée dans l'ennoncé ! Je me trompe ?
 
En fait, on calcule ca :
 

 
En C, on aurait accès au __int64 mais pas en C++, d'ou ma remarque precedente.

tu trouve pas ca un peu lourd de specifier a chaque fois std::, tu fais jamais de using... ? surtout que la tu utilise un seul namespace

Oui, je sais... ca rend le code un peu moins lisible, désolé.

 
Ah, je sens qu'on est sur les rails, là.  
Dans le reste de mon code, j'inline, mais tu as raison.
Pour le printf, si tu peux me rappeler la version strstream, je changerai volontiers ma petite fonction de génération pour la rendre plus C++.
 
edit : pas la peine, xterminhate me la donne...
 
En fait, mon problème s'applique plutôt à un tableau de caractères (mais il peut se généraliser à toute collection d'objets finie ordonnée). Le fait que je dise que ces caractères soient des chiffres, c'est que je l'ai imaginé comme ça. Donc pour ce problème, ce sont des chiffres. Tu peux utiliser un vector<int> si tu préfères, tant que tu obtiens les mêmes valeurs dans ton tableau.

 
Effectivement, tu as corrigé toi-même. J'ai vu le pb quand j'ai compilé. Le plus simple (ce que j'ai fait dans ma fonction), c'est de virer carrément la partie modulo.

cai juste qu'il me semble pas que cette syntax de format de printf soit standard.
 
char buf[5] = "\0"; t'as réalisé ce que tu as écris là ?

 
Quel est le pb ?
(bon cassos boulot)

 
char buf[5] ;
buf[4] = '\0' ;
 
?

 
ca sert a koi ?    
 

à rien ! j'espère de comprendre ce qu'il a voulu faire..

"" fais exactement ce qu'il faut.

Bon, revennons à nos moutons !... le concours
 
El much -> tu as vérifié ton code parce que pour le moment, on a vraiment pas la meme sequence de départ !

el muchacho : distribue un fichier avec la séquence, chaque élément séparé par un espace, le tout compréssé (et pas en zip/rar hein)

 
Ouais, la grosse honte...  
J'ai vu la bourde quand j'y ai pensé dans le bus.  
En fait, je pensais plutôt à une initialisation du genre :
 
char buf[5] = "";
 
De toute façon, ça n'a pas d'incidence ici.

 
Bon je revois mon code...