Vous avez découvert un nouveau jeu très amusant. Celui-ci se joue sur un plateau de N cases alignées numérotées de 1 à N sur lesquelles on peut poser des jetons.
À tout moment, chaque case contient au plus un jeton.
Une case contenant un jeton est dite remplie, une case n'en contenant aucun est dite vide.
Au début de la partie, toutes les cases sont remplies.
Les règles du jeu sont les suivantes :
À tout moment on peut vider ou remplir la case 1.
Si la case 1 est remplie, alors on peut remplir ou vider la case 2. (Règle valable pour N >= 2)
Pour tout 3 <= K <= N, on peut remplir ou vider la case K lorsque les K - 2 premières cases sont vides et que la case K - 1 est remplie. (Règle valable pour N >= 3)
Le but du jeu est de vider toutes les cases. Vous avez décidé d'écrire un programme permettant de résoudre le jeu en un minimum de coups.
Limites de temps et de mémoire (C++)
Temps : 0,5 s sur une machine à 1 GHz.
Mémoire : 4 000 ko.
Contraintes
1 <= N <= 18, où N est le nombre de cases du plateau.
Entrée
L'entrée est composée d'un unique entier : N, le nombre de cases du plateau.
Sortie
Votre programme doit afficher P lignes, avec P le nombre minimal de coups nécessaire pour finir le jeu.
Chacune des P lignes doit contenir un entier Pi compris entre 1 et N, décrivant le ie coup de votre séquence, par l'indice de la case remplie ou vidée à ce coup.
Exemple
entrée :
4
sortie :
2
1
4
1
2
1
3
1
2
1
Commentaires
Il s'agit ici de résoudre le jeu pour N = 4. Il faut au minimum 10 coups pour résoudre le jeu.
- Edité par Nonoze 7 novembre 2021 à 20:34:38
Avant de commencer un problème, prends TOUJOURS un papier et un crayon !
la première étape est de trouver un algo qui va te permettre de résoudre le problème. Il n'y a pas 36 manières de faire : essaye avec de petites instances et tu verras bien où ça te mène
Par exemple pour N=1 c'est simple : tu vides la case 1 est c'est bon …
N=2 : tu vides la case 2 pour tomber sur le cas N=1 …
N=3 : tu vides la case 1, tu vides la case 3, tu remplis 1 , tu vides 2 et tu vides 1 …
On peut supposer qu'une case remplie vaut 1 et une case vide vaut 0. Je pense que ça se fait de façon récursive. bien que je me sois déjà gouré là-dessus ...
edit:
Pour N > 2, je pense qu'on peut déduire la façon optimale pour N+1 si on la connait pour N.
- Edité par PierrotLeFou 8 novembre 2021 à 15:41:13
Le Tout est souvent plus grand que la somme de ses parties.
Il faut trouver la séquence de mouvement (vider ou remplier une des K cases) pour qu'à la fin il n'y ait que des cases vides, en respectant les contraintes à chaque étape.
Je recherche un CDI/CDD/mission freelance comme Architecte Logiciel/ Expert Technique sur technologies Microsoft.
Jai essayé pendant hyper longtemps, et finalement, j'ai réussis.
Merci pour toutes ces indications
- Edité par Nonoze 9 novembre 2021 à 20:38:48
Avant de commencer un problème, prends TOUJOURS un papier et un crayon !
Baguenaudier
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Avant de commencer un problème, prends TOUJOURS un papier et un crayon !
Avant de commencer un problème, prends TOUJOURS un papier et un crayon !
Le Tout est souvent plus grand que la somme de ses parties.
Avant de commencer un problème, prends TOUJOURS un papier et un crayon !
Avant de commencer un problème, prends TOUJOURS un papier et un crayon !
Avant de commencer un problème, prends TOUJOURS un papier et un crayon !