Path: ...!news.mixmin.net!proxad.net!feeder1-2.proxad.net!usenet-fr.net!.POSTED!not-for-mail From: Olivier Miakinen Newsgroups: fr.rec.jeux.enigmes Subject: [Solution] F-Nim Date: Mon, 19 Dec 2022 17:46:32 +0100 Organization: There's no cabale Lines: 151 Message-ID: References: NNTP-Posting-Host: 200.89.28.93.rev.sfr.net Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Trace: cabale.usenet-fr.net 1671468392 4995 93.28.89.200 (19 Dec 2022 16:46:32 GMT) X-Complaints-To: abuse@usenet-fr.net NNTP-Posting-Date: Mon, 19 Dec 2022 16:46:32 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Firefox/52.0 SeaMonkey/2.49.4 In-Reply-To: Bytes: 6716 Bonjour, Le 30/11/2022 10:59, Jacques Mathon répondait à Jac. : > Le 30/11/2022 à 00:48, Jac a écrit : >> Jacques Mathon a présenté l'énoncé suivant : >> >>> Et le problème d'origine, tu l'avais résolu ? >>> Je me souviens que tu avais joué avec Olivier. >> >> Oui, j'avais écrit un p'tit module mais je m'étais trompé en recopiant >> les résultats ! > > Je m'en souviens. > Si tu as vraiment résolu le problème sauras-tu résoudre le codage > d'Olivier que je reprends ci-dessous ? > >> Voici donc où nous en sommes de la fonction choix. Chaque @ représente une >> lettre et chaque # représente un caractère qui n'est pas une lettre. >> ============================================================================= >> def choix(have, maxi): >> while True: >> if have <= maxi: >> return have >> @# @ # ## # >> @@@@@ @ # @@@@# >> @# @ # @# @#@ >> @@@@ ## @ >> ============================================================================= Puisque les deux Jac[.|ques Mathon] qui sont les seuls à répondre avaient déjà tous les deux résolu le problème alors même que je ne m'en souvenais pas, voici la solution. Je la donne avant d'oublier que j'ai posé cette énigme pour la deuxième fois, puis de la poser un jour une troisième fois comme si c'était la première. ;-) Ce jeu que j'ai appelé F-Nim est connu sous le nom de Fibonacci Nim, mais comme l'a finement suggéré Jacques Mathon il mériterait de s'appeler Nim de Zeckendorf. En effet sa stratégie repose sur la représentation des nombres sous forme de somme de nombres de Fibonacci non consécutifs, celle-ci étant unique d'après le théorème du mathématicien belge Édouard Zeckendorf. En prime, voici donc le programme complet en Python 3 permettant de jouer au jeu contre l'ordinateur. Ce programme offre la possibilité de demander à ce que l'ordi ne joue pas systématiquement le meilleur coup, car sinon il est imbattable aussitôt qu'il se trouve dans une position favorable. Remarquer la fonction choix qui, en moins de 10 lignes, fait des calculs selon la représentation de Zeckendorf. Lorsque c'est possible, à partir d'un nombre A il retourne un nombre B qui est plus petit que le plus petit nombre de Fibonacci dans la représentation de Zeckendorf de A − B. #!/usr/bin/python3 import random def choix(have, maxi): while True: if have <= maxi: return have u, v = 1, 2 while v < have: u, v = v, u+v have -= u def saisie(message, mini, maxi = 0): if maxi <= 0: invite = f'{message} (au moins {mini}) ? ' erreur = f'Vous devez choisir un nombre au moins égal à {mini}.' else: invite = f'{message} (entre {mini} et {maxi}) ? ' erreur = f'Vous devez choisir un nombre entre {mini} et {maxi}.' result = int(input(invite)) while result < mini or result > maxi > 0: print(erreur) result = int(input(invite)) return result def premier_a_jouer(): invite = "Qui commence ?" print("Choisissez qui va commencer.") print("1 = Vous jouez en premier.") print("2 = Vous jouez en deuxième.") print("3 = C'est le hasard qui décide.") result = saisie("Qui commence", 1, 3) if result == 3: result = random.randint(1, 2); if result == 1: print("Et donc vous commencez.") else: print("Et donc je commence.") return result def joueur_humain(have, maxi): print() s = "s" if (have > 1) else "" print(f"C'est à vous de jouer. Il reste {have} objet{s}.") retire = saisie("Combien en retirez-vous", 1, maxi) return retire TRACE_RANDOM = True def joueur_ordi(have, maxi, percent): print() s = "s" if (have > 1) else "" print(f"C'est à moi de jouer. Il reste {have} objet{s}.") if have <= maxi: if TRACE_RANDOM: print("Mon choix est évident.") return have if random.uniform(0, 100) <= percent: if TRACE_RANDOM: print("Je joue au mieux.") retire = choix(have, maxi) if 3*retire < have: return retire else: if TRACE_RANDOM: print("Je joue au hasard.") if 3*maxi >= have: maxi = int((have-1)/3); if maxi <= 1: return 1 return random.randint(1, maxi) def main(): print("Bienvenue à F-Nim !") have = saisie("Combien d'objets au départ", 2) percent = saisie("Pourcentage de fiabilité du programme", 0, 100) qui = premier_a_jouer() maxi = have - 1 while have > 0: if qui == 1: retire = joueur_humain(have, maxi) qui = 2 else: retire = joueur_ordi(have, maxi, percent) s = "s" if (retire > 1) else "" print(f"Je retire {retire} objet{s}.") qui = 1 have = have - retire maxi = min(have, 2 * retire) if qui == 1: print("J'ai gagné !") else: print("Vous avez gagné !") main() -- Olivier Miakinen