[Challenge] Résoudre le problme d'SMBC du 2013-02-01

[prgasp77]

Bonjour à tous. Aujourd'hui sur le site Saturday Morning Breakfeast Cereal, on peut trouver le comic suivant :


Traduction approximative : « On appelle transformée de fourier (ndt : littéralement, plus de quatres) la conversion d'un nombre vers une base dans laquelle celui-ci contient le plus de quatres, faisant de ce nombre plein de quatres. Dans cette base, le nombre est dit fouriest (ndt : littéralement, le plus de quatres) ».

Je vous propose ici d'essayer de trouver un algorithme efficace pour calculer la base dans lequel le nombre donné n est fouriest. Préférez s'il vous plaît du pseudocode ou du code impératif (pas d'objet ni de fonctionnel).

À vos clavier !


Ce message est un doublon fait (par mes soins) sur www.developpez.net/forums. Voyons laquelle des deux communautés est la plus rapide (bien qu'elles se recouvrent mutuellement).
-----

[CM63]

Bonne soirée,

Exercice très intéressant! Mais qu'est-ce que tu appelles du code impératif? On a le droit de le faire en Python? Ou VB?

Bonne soirée.

[prgasp77]

Il faut que le code soit lisible par tous, en particulier par ceux qui ne connaissent pas ce langage (à l'exception du C qui est considéré comme connu par tous − tout de moins sa syntaxe). Pour répondre plus formellement à ta question, j'appelle ici langage impératif un langage dans lequel cet algo sera l'inverse même d'un algo spaghetti ; juste quelques appels à des fonctions bien définies, et sinon une exécution linéaire, avec possiblement des boucles. Pas de goto, pas d'objet, pas de pointeur de fonction, etc.


Bon, je me lance ; la première solution évidente est le brute-force. On peut chercher une base borne, dont on sait que toute base supérieure ne pourra pas être solution. Par exemple, soit n le nombre à transformer, je sais que pour toute base b supérieure à n, n exprimé en base b ne contiendra aucun 4.
On peut ensuite affiner le crible et trouver d'autres bases dans lesquelles n exprimé dans celles-ci ne contiendra aucun 4 (comme 4, 3 et 2 xD).

[obi76]

Bonjour,

très interessant comme défi. Mais évidement le bruteforce c'est la solution bateau et la moins performante, à creuser

[A voir en vidéo sur Futura]

[Tryss]

Déjà, on peut facilement calculer une borne supérieure du nombre maximum de 4 que peut posséder le nombre :



Ensuite c'est un peu plus compliqué, mais je ne serrai pas étonné si on avait une sorte de structure fractale qui apparaissait

En effet, le nombre de 4 dans une base b suit le pattern :



...



Ou n*C veut dire "répéter n fois la chaine C" et C+k veut dire "Ajouter k à chaque symbole de la chaine C"


Et le n-ième chiffre correspond au nombre de 4 de n+1 dans la base b

Ça correspond à quelque chose du type L-system

On génère toutes les chaines pour les bases, puis on prend le maximum.


D'ailleurs je me demande si on n'a pas là un moyen efficace de générer le nombre de 4 dans toutes les bases de façon rapide.

[prgasp77]

Ha ! Tu commences à construire quelque chose En revanche, je ne ocmprends pas très bien la phrase suivante :

le n-ième chiffre correspond au nombre de 4 de n+1 dans la base b

J'essaie de comprendre par l'exemple. . Dois-je en conclure que le nombre 2 a

• 0 chiffre '4' en base 2 (?)
• 0 chiffre '4' en base 3
• ...
• 1 chiffre '4' en base 6

ou qu'en base 1 le nombre 6 a 1 chiffre '4' ?

[Tryss]

Non, c'est pas dans ce sens là malheureusement

J'aurai du indicer le A par b pour que ce soit plus clair

Le nombre 0 a 0 4 en base b
Le nombre 1 a 0 4 en base b
...
Le nombre 4 à 1 4 en base b
etc.


Il faut donc générer une suite An pour chaque base b. Cette méthode n'a donc un possible intérêt que dans le cas ou on souhaiterai faire les calculs pour un grand nombre de valeurs.

Par contre, on voit apparaitre une structure assez intéressante:

Fouriest base - bis.pngFouriest base.png


Statistiquement il suffirait donc de regarder les premières bases, ainsi que certaines grandes bases