[CamL] Enigme : Programmation sur les nombres en base 2 :)

[logarithmer]

Bonjour ! Voici une énigme pour les amateurs des nombres binaires =)
Programmer en oCamL les 2 fonctions suivantes :
- La fonction
nombreDeUn donnée n : entier positif ou nul resultat : entier
qui calcule le nombre de 1 dans l'écriture binaire de n.
- Une fonction rendant la liste des entiers inférieurs à un certain nombre qui sont des 2-palindromes (on pourra définir des fonctions auxiliaires mais le style de programmation sera impérativement fonctionnel).
Un nombre est 2-palindrome si son écriture en base 2 est la même qu'elle soit écrite de gauche à droite ou de droite à gauche. Plus précisément, si n=0, n est un 2-palindrome sinon n=somme pour i vaiant de 0 à k des ai.2^i, avec a0,a1,...,ak dans {0,1} et ak=1, et n est un 2-palindrome si ai=ak-i, pour tout entier i dans {0,...,k}. (Bien entendu, tous les i sont en indice, même le k-i à la fin).

Bonne chance à tous les informaticiens

[Asymetric]

Dis moi on aurait pas le même DM

[pikachuyann]

Faites-le ensemble !

Pour le "nombreDeUn" y'a pas une contrainte supplémentaire ? J'ai un algorithme naïf très "bourrin", dirais-je, en tête, m'enfin normalement vous y avez pensé aussi...
Pour l'autre faudrait que je me renseigne un poil plus sur les fonctions auxiliaires, mais j'ai de nouveau en tête un algorithme extrêmement bourrin (pour a allant de 1 à n, je fais la décomposition en base 2, je regarde s'il est palindromique ou pas, s'il l'est je le rajoute à ma liste, sinon non.) qui doit être, si mon idée de fonction auxiliaire est bonne, parfaitement codable.

Enfin, la question est-elle :
- d'obtenir le résultat de n'importe quelle façon
- ou d'obtenir le résultat de la façon la plus propre et rapide ?

[V@J]

Que veut dire "le style de programmation sera impérativement fonctionnel" ?
Parce que, si on a le droit à des fonctions récursives (j'espère que oui, sinon c'est dommage d'utiliser oCaml), il y a des moyens très simples de programmer tes 2 fonctions...

[Dodor]

En prépa, fonctionnel => non impératif, ie pas de références, pas de tableau, pas de boucles... donc nécessairement du récursif.
c'est vrai que la formulation "impérativement fonctionnel" peut laisser perplexe, mais il faut faire la part du français et du langage "info".

La première question se résout avec une fonction toute bête en log_2 (n).
La deuxième peut être vue de façon naïve avec une solution en $ n \times log_2 (n) $ ou une autre qui ne traite que des palindromes, en $ \sqrt{n} \times log_2(n) $, sauf si je me suis trompé dans mes calculs... La 1e met un temps suffisamment long pour que je perde patience quand $ n = 2^{30} - 1 $ (valeur maximale des entiers de OCaml sous mon environnement), la 2e met une fraction de seconde.

[fakbill]

Oui et ça pose un petit problème cette conception de l'info
OK ok c'est LA façon d'apprendre ce qu'est l'info théorique.
Le problème vient du fait que souvent les gens ne feront plus trop d'info une fois en école d'ingé.
Certains ont découvert l'info en fonctionnel et ne savent faire que ça.
Par ex, on retrouve des gens qui codent n! en récursif en C++ ou pire...normal vu qu'on ne leur a jamais montrer autre chose (ce n'est pas les qlqs heures de cours de C de 1A qui peuvent luter contre les heures d'info de prépa...surtout si on découvre l'info en prépa...on reste marqué).

[logarithmer]

Le but est effectivement de répondre le plus simplement possible et ce n'est pas un DM x) Ce sont des sujets d'un certain concours...
Si vous avez des idées, n'hésitez pas à les poster !

[Dodor]

Tu veux qu'on te fasse les sujets d'e3a 2004 (nombreDeUn), 2005 (2-palindromes) et 2008 (longueurMaxPlateau) ? (après recherche rapide)

[logarithmer]

Voilà Ravi de voir que tu as pu exploiter les capacités de notre ami Google

[Dadin]

Allez si vous voulez une question d'algo un peu plus difficile (mais très classique, et très utile) : on se donne $ f : \mathbb{N} \rightarrow \mathbb{N} $ et on considère la suite $ u_{n+1} = f(u_n) $ et $ u_0 \in \mathbb{N} $.
Si on suppose que cette suite est récurrente c'est à dire qu'il existe $ k $ et $ N $ tel que $ \forall n \geq N,\,\, f(u_n) = f(u_{n+k}) $.

Comment trouver la période du cycle, le plus rapidement possible ?