Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

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



  1. #1
    prgasp77

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


    ------

    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).

    -----
    --Yankel Scialom

  2. Publicité
  3. 📣 Nouveau projet éditorial de Futura
    🔥🧠 Le Mag Futura est lancé, découvrez notre 1er magazine papier

    Une belle revue de plus de 200 pages et 4 dossiers scientifiques pour tout comprendre à la science qui fera le futur. Nous avons besoin de vous 🙏 pour nous aider à le lancer...

    👉 Je découvre le projet

    Quatre questions à explorer en 2022 :
    → Quels mystères nous cache encore la Lune 🌙 ?
    → Pourra-t-on bientôt tout guérir grâce aux gènes 👩‍⚕️?
    → Comment nourrir le monde sans le détruire 🌍 ?
    → L’intelligence artificielle peut-elle devenir vraiment intelligente 🤖 ?
  4. #2
    CM63

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

    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.
    Déjà de base.

  5. #3
    prgasp77

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

    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).
    --Yankel Scialom

  6. #4
    obi76
    Modérateur*

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

    Bonjour,

    très interessant comme défi. Mais évidement le bruteforce c'est la solution bateau et la moins performante, à creuser
    \o\ \o\ Dunning-Kruger encore vainqueur ! /o/ /o/

  7. A voir en vidéo sur Futura
  8. #5
    Tryss

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

    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.
    Dernière modification par Tryss ; 02/02/2013 à 21h30.

  9. #6
    prgasp77

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

    Ha ! Tu commences à construire quelque chose En revanche, je ne ocmprends pas très bien la phrase suivante :
    Citation Envoyé par Tryss Voir le message
    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' ?
    --Yankel Scialom

  10. Publicité
  11. #7
    Tryss

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

    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

Discussions similaires

  1. [Blanc] problme ARISTON LSE 620A
    Par le routier dans le forum Dépannage
    Réponses: 5
    Dernier message: 21/03/2010, 18h03
  2. [Blanc] problme lave vaisselle Arthur Martin ASF2643
    Par michel pavon dans le forum Dépannage
    Réponses: 0
    Dernier message: 02/09/2007, 14h23
  3. problme de calcul de n
    Par flo1012 dans le forum Chimie
    Réponses: 3
    Dernier message: 17/09/2006, 17h07
  4. Problme avc lessiveuse Bauknecht WAL10988
    Par le_samaritain dans le forum Dépannage
    Réponses: 0
    Dernier message: 13/07/2006, 21h17
  5. problme de COM sur USB
    Par grmg dans le forum Logiciel - Software - Open Source
    Réponses: 4
    Dernier message: 20/06/2006, 02h41