On m'a demandé cette question: question similaire sur google. Une question similaire a été posée lors d'un entretien facebook.
Déterminer le gagnant du jeu de numéro de 2/9
Deux joueurs jouent le jeu suivant: Ils choisissent un nombre aléatoire N (moins de 2 milliards), à partir de 1, à partir de 1, à tour de rôle multipliant le numéro du tour précédent avec 2 ou 9 (leur choix). Quiconque atteint nième victoire.
Le candidat doit écrire une fonction qui compte n décide qui gagne (premier ou second joueur?)
Un choix aléatoire fondamental de 2/9 pour un travail de multiplication ou ils voudraient que nous ajoutions de l'intelligence à faire des mouvements. Pour EX: Commencez par la multiplication avec 2 et multipliez avec 9 uniquement lorsque vous voyez que l'autre personne ne sera pas en mesure d'atteindre n plus rapide que vous?
Quel est le meilleur moyen d'aborder ce type de questions?
9 Réponses :
La réponse (je ne suis pas sûr à 100%):
r = N mod 18 if r belongs to (1,9] player 1 wins if r belongs to (9,18) or is =1 then player 2 wins.
Probablement pas si vous ne pouvez pas l'expliquer :). Si vous n'avez pas de preuve complète, l'intuition derrière cela aiderait également.
J'ai une preuve à moitié formée, alors n'aurait pas posté de réponse aléatoire. La preuve est simple, mais la marge de cette page est trop étroite pour la contenir.
Je ne pense pas que cela soit correct. P1 perd toujours pour N = 37, mais votre théorie dit qu'il gagne. Ex. Supposons que le premier mouvement de P1 soit multiplié par 9. Puis P2 se multipliera par 9, pour un total de 81 gains P2. Supposons que le premier mouvement de P1 soit multiplié par 2. P2 multipliera ensuite par 2, pour un total de 4. Quel que soit le prochain déplacement de P1, P2 multiplie ensuite par 9, dépassant 37 et gagnant.
Oups, j'ai raté que P1 perd quand n% 18 == 1, votre théorie prédit correctement la perte de P1 pour n = 37. Mais P1 perd également pour n = 38 à 72, dont certains sont en désaccord avec votre théorie.
car ils doivent atteindre exactement Recherche C'est parce que, à chaque étape, un joueur se rapproche de n , ceci n'est possible que si n est du formulaire 2 ^ a * 9 ^ b , avec l'un des a, b autorisé à être 0 aussi.
A et B ci-dessus: Si A + B = Même , le second joueur gagnera, sinon la première victoire.
A ou b par un, et donc à a + b par un. Donc, le problème se réduit à: donné k , si à chaque étape, un lecteur doit soustraire 1 de k , quel joueur atteindra 0 d'abord?
Était exactement n spécifié? J'ai lu ceci comme atteignant n , donc n ou ci-dessus.
@ A.WebB - Je comprends "Atteindre n " pour signifier exactement n . Il n'a pas dit au moins n .
Pourrait être. Si tel est le cas, les joueurs ont mieux de chanceux alors lors du choix de n ou ils sont pour une conclusion ennuyeuse à leur jeu.
Le problème dit que N est pris de manière aléatoire et inférieure à 2 milliards, non pas qu'il s'agisse d'un multiple aléatoire de 18 ans. La façon dont je lis le problème est que quiconque obtient un numéro n ou plus dans ses victimes.
@CYRGO - Oui, il ne faut pas être un multiple de 18, j'ai corrigé cela. Comme indiqué cependant, le jeu peut se terminer dans un tirage / sans solution si n n'est pas du formulaire 2 ^ a * 9 ^ b . Pour n = 11 , personne ne gagne, car personne ne peut atteindre 11. Il est indiqué à atteindre n , pas atteindre ou dépasser n .
Pour 11: 1st: 2 ou 9 (peu importe), le 2e joueur choisit 9 et gagne. x = 1 -> x = 2 (ou x = 9) -> x = 18 (ou x = 81) à la fois de plus de 11 (11 a été atteint et dépassé). Donc le joueur 2 gagne.
@IVLAD Une chose que je ne comprends pas est par exemple 1458 = 2 * 9 * 9 * 9, comme si vous avez dit a + b = même puis le joueur2 gagnera, mais si le joueur1 multiplie 2, joueur2 Multiplie 9, Player1 multiplie 2 à nouveau au lieu de 9, alors personne ne peut gagner. Devrions-nous dire si a + b = même puis player2 pourrait gagner? Ai-je oublié quelque chose?
Si vous essayez simplement de rencontrer ou de respecter ou de dépasser considérer Si Alors, envisagons maintenant n , cela peut être résolu en déterminant les stratégies qui gagneront toujours dans divers cas. Je présenterai 5 cas (ou 2 cas, dont la seconde possède 4 sous-cas) qui couvrent tous les n et donnent la stratégie gagnante pour chacun.
t = ceil (journal (n) / journal (18)) , c'est laisser t être la plus petite puissance telle que 18 ^ t < / code> rencontre ou dépasse n .
18 ^ (T-1) * 9 T < / Code> Des tours, le deuxième joueur gagne. Le premier joueur ne peut pas gagner à la ronde antérieure car la multiplication par 9 n'est pas suffisante pour dépasser n (ni multiplier par 2).
18 ^ (t-1) * 9> = n et choisissez le plus petit k tel que 18 ^ (T-1 ) * 2 ^ k> n . Il existe quatre possibilités k = 1, 2, 3 ou 4 .
(k = 1) premier joueur gagne. Le premier joueur peut commencer par une 2, puis jouer comme le deuxième joueur a fait ci-dessus, en jouant le numéro opposé de l'autre joueur à chaque tour ultérieur jusqu'à ce que la prochaine ronde. Le second joueur sera toujours confronté à une puissance de 18 fois la version initiale 2. à 18 ^ (T-2) * 2, le joueur deux peut au plus atteindre 18 ^ (t-1) en multipliant par 9, qui ne suffit pas à gagner et peut au moins retourner 18 ^ (t-2) * 4 quel joueur on peut multiplier par 9 pour gagner avec 18 ^ (t- 1) * 2 .
(k = 3) premier joueur gagne également. Ce joueur de temps commence avec un 9 et joue comme avant. Le deuxième joueur sera toujours confronté à une puissance de 18 fois la version initiale 9. à 18 ^ (T-2) * 9, le joueur deux peut au plus atteindre 18 ^ (t-2) * 9 * 9 <18 ^ (T-2) * 18 * 8 = 18 ^ (t-1) * 2 ^ 3 , ne suffit pas à gagner et peut au moins retourner 18 ^ (t-1) en multipliant par 2 Quel joueur sera multiplié par 9 et gagnez.
(k = 2 ou 4) second joueur gagne. Ici, le second joueur doit jouer le nombre opposé comme avant, jusqu'à la fin de la fin, de sorte que chaque joueur rond commence par une puissance de 18. À 18 ^ (T-2) , le joueur on peut à la plupart d'accès 18 ^ (t-2) * 9 <18 ^ (t-1) , donc pas assez pour gagner. S'il retourne 18 ^ (T-2) * 9, joueur deux victoires avec 18 ^ (T-2) * 9 * 9> 18 ^ (T-2) * 18 * 4 = 18 ^ (T-1 ) * 2 ^ 2 Si le joueur on retourne à la place 18 ^ (t-2) * 2 , joueur deux retours 18 ^ (t-2) * 4 . Le joueur on peut alors faire au plus 18 ^ (t-2) * 4 * 9 = 18 ^ (T-1) * 2 , ce qui n'est toujours pas suffisant. Et maintenant, le joueur on peut au moins retourner 18 ^ (T-2) * 8 , qui suffit pour le joueur deux pour atteindre le but depuis 18 ^ (t-2) * 8 * 9 = 18 ^ (T-1) * 4 .
Bien expliqué. S'il vous plaît, commencez quel type de personne peut réussir ce test. Un brillant ou celui familier avec ce genre de puzzle qui vient de rencontrer un problème similaire auparavant.
@Jarekczek: Il n'est pas possible de dire avec certitude sans savoir ce que l'intervieweur recherche. C'est une erreur courante de supposer qu'une réponse correcte à la question "passe" de cette partie de l'entretien, et une réponse incorrecte "échoue" de cette partie de l'entretien, et de rejeter cela comme une question de connaissances générale limites, car elle est difficile- ish à résoudre sans expérience antérieure. Plus probablement, la question est destinée à ce que l'intervieweur puisse regarder le processus que vous suivez essayer pour le résoudre. Si vous trouvez facile, merci de connaître un peu de théorie du jeu, ils poseront une autre question.
J'ai maintenant un avis différent sur ce sujet. Bien que votre solution soit élégante, parfaitement expliquée et contient également une stratégie pour les joueurs, il est trop compliqué à proposer lors d'une interview. Je crois que l'intervieweur n'est pas plus de 30 minutes. Si vous démissionnez de savoir qui gagne, vous pouvez inventer un algorithme récursif plus simple comme la réponse de SRBH.KMR . J'ai encore des problèmes de compréhension de sa solution, peut-être que je montrerai une autre alternative plus simple.
@Jarekczek Il est probablement tout à fait possible de proposer cette solution en 30 minutes, mais je ne l'ai pas fait. La solution récursive / dp de SRBH.KMR serait bon de proposer une interview car elle démontre la résolution générale des problèmes technique. La prochaine étape consisterait à faire ce que Peter de Rivaz a fait et rechercher des hypothèses et des modèles de simplification du résultat. À votre guise, si vous êtes curieux et un peu têtu, vous pouvez établir la stratégie explicite pour le puzzle particulier.
Oui, vous êtes censé penser à une pièce optimale des deux joueurs et décider qui va gagner.
ici, une simple pensée récursive pourrait vous conduire à une solution. P>
Si un joueur est avec nombre Par conséquent, nous pourrions écrire une approche récursive comme suit: n code> et n * 9> = n code> puis le joueur actuel gagnera le jeu.
D'autre, il passera sur 2 * n code> ou 9 * n code> au 2ème joueur.
Maintenant, le 1er joueur ne perdra que le jeu uniquement si les deux options fournies par lui ( 2 * N code> et 9 * n code>) au 2ème joueur conduisent à un numéro gagnant pour 2e joueur, sinon il aura une chance de choisir un numéro gagnant à nouveau. P>
Étant donné que tous les numéros de jeu vont être de forme: 2 ^ i * 9 ^ j code> Nous pourrions écrire: p> F(i, j) = true; if (2^i * 9^j * 9) >= N
!(F(i+1, j) && F(i, j+1)); otherwise
Travaillerait, mais ce serait O (2 ^ journal n) = O (n) , qui est assez grand pour n jusqu'à deux milliards. Pour l'interprétation ou dépasse n , je pense que nous avons besoin de mathématiques plus intelligentes.
Je pense que l'approche ci-dessus fonctionnera pour exactement Atteindre n , nous n'avons qu'à saisir un N valide et modifier la condition de base en si (2 ^ i * 9 ^ j * 9) == n . Pour la complexité, je pense qu'une mise en œuvre commémorée sera beaucoup plus rapide qu'à une naïve, car nous résoudrions de nombreux sous-problèmes courants. [Actuellement, j'ai écrit un programme commémoré rapide pour cela et cela fonctionne extrêmement bien pour N = 2 milliards et au-delà, également]. Savez-vous comment évaluer la nouvelle complexité avec la mémoisation en place, en général?
De plus, si nous voulons mettre en œuvre une solution DP pour cela, je pense qu'il y aura log_base2 (n) * log_base9 (n) entrées à remplir dans la table. Par conséquent, la complexité est assez gérable pour N = 2 milliards. Corrigez-moi si j'ai tort, s'il-vous plait.
+1: Je soupçonne que c'est la solution attendue. Il n'y aura que 300 entrées dans la table DP à remplir, de sorte qu'il est très rapide. (Si vous utilisez C, veillez à ce que la comparaison ne déborde pas si vous utilisez des entiers 32 bits. N Convient à 32bits, mais 2 ^ i * 9 ^ j * 9 peut déborder).
Le jeu optimal sera normalement de jouer le contraire du mouvement de l'adversaire, à l'exception du début et de la fin.
En comparant avec une solution récursive, il s'avère que la réponse peut être calculée en fonction du chiffre le plus important. Dans une représentation de base 18 du nombre-1 comme suit:
+1 très gentil! J'ai défini le jeu des stratégies gagnantes explicitement dans ma réponse.
@Peter de Rivaz Pourriez-vous expliquer le code un peu? Je ne comprends pas pourquoi nous devons faire n- = 1 et n == 1 ou 4 <= n <= 8
La meilleure approche de ce type de questions.
Tout d'abord, vous devez avoir la compréhension de base alors vous commencez à Familiarisez-vous avec le jeu fort>. Vous pratiquez un niveau bas. Vous remarquez rapidement que pour 2-9, le démarreur gagne, tandis que pendant 10-18, il doit perdre. Donc, votre fonction est prête pour un cas de alors vous commencez penser à une stratégie générale de gagnante forte>. Connaître la stratégie vous donnerait l'algorithme. Après 5 minutes (plus tôt le mieux), vous comprenez que vous n'entrez pas à temps pour trouver la stratégie gagnante, car il n'est pas évident dans ce cas. Vous décidez donc de donner à l'ordinateur des principes de base et de le laisser résoudre le casse-tête pour vous. Vous savez que vous utiliserez la récursion. P> Vous essayez de trouver la règle de la récursion. Vous voudrez peut-être commencer à partir de la fin ou depuis le début. Je vais décrire l'approche de la fin. P> Le but du jeu est de pousser votre adversaire à la zone, où il doit vous donner la victoire forte>. Et ne pas être poussé à cette zone vous-même. De N / 9 à N, il y a une zone pour gagner. Si on est poussé pour jouer entre N / 9/2 et N / 9, il doit perdre. (Parce que les deux mouvements poussent son adversaire à la zone gagnante.) Vous écrivez donc votre fonction: p> Si vous avez atteint ce point, vous avez passé. Il ne reste plus de détails, comme si vous souhaitez utiliser Float ou Int, d'arrondir ou de descendre en utilisant Int. Mais en général, vous avez montré la bonne façon de penser et vous êtes prêt à faire face à l'intervieweur :) p> L'approche alternative n . P> gagne (n) code> et REACHES_SLIMLY_ABOVE (N) code>. Ce dernier serait appelé de manière récursive et les valeurs renvoyées ci-dessous 18 devraient être différentes, ressemblent à celles de la solution de Peter de Rivaz . Cependant, la solution ci-dessous et l'approche générale devraient être ok. Em> p> wins(a,n) {
if (9*a >= n)
// I win easily
return 1;
else
// if one of my moves pushes the opponent to the zone
// where he's not able to win, then I win!
return !wins(2*a, n) || !wins(9*a, n);
}
Dans l'approche de bas en haut, ne devrait-il pas le premier si (9 * a> = n || 2 * a> = n) retourne 1?
La deuxième condition n'est pas nécessaire. Si 9 * A> = N, alors il n'est pas vérifié du tout. Si 9 * A 9 * A> = n || 2 * A> = n . Il peut être expliqué en mots tels que si je peux gagner avec le déménagement "9", je n'ai pas besoin d'utiliser le "2" Move .
Les jeux déterministes à deux joueurs, tels que ceux-ci sont étudiés par la théorie du jeu combinatoire . Cette théorie de jeu frivole n'a aucune relation avec la théorie des jeux plus utile de Neumann et Nash populaire en économie. Le travail séminal est un livre charmant appelé Gagner des voies de Conway, Berlekamp & Guy.
pense . Pour tout jeu, soit:
Votre jeu est un cas particulier, un jeu impartial , où l'état du jeu a l'air identique aux deux joueurs. Le meilleur exemple est un jeu de matchstick simple appelé NIM. Il arrive que tous les jeux impartiaux équivalent à NIM (c'est le théorème de Sprague Grundy), de sorte que tous les jeux impartiaux peuvent être complètement résolus.
Résolvons votre jeu. Les états possibles du jeu sont les entiers positifs. Nous allons classer chaque État comme étant remporté pour le deuxième joueur (nous étiqueterons ces jeux zéro '0' jeux) ou gagnant pour le premier joueur (nous étiqueterons ces jeux Star '*' Jeux).
Les entiers supérieurs ou égaux à N sont tous des jeux zéro, car à ce stade, le jeu est terminé. Quiconque bouge qu'il est déjà perdu.
états où le joueur dont il est tourné peut passer aux positions zéro ci-dessus sont les jeux étoiles. Ainsi, les entiers n, états où le joueur dont il est tourné, il n'a aucun choix que de passer à la position d'étoile sont à nouveau des positions zéro. Donc, les entiers n, et ainsi de suite. En utilisant les arguments similaires, nous finançons éventuellement tous les entiers à un.
pour n = 1000 disent,
Généralisation Nous atteintes à la conclusion de Peter https://stackoverflow.com/a/13367642/284795
n / 9 <= n n / 9/2 <= n
post intéressant et réponses. Je serais tenté de proposer une fonction de force brute théorique qui énumère tous les chemins combinatoires utilisant 2/9 facteurs à N <= 2x10 ^ 12 (ou aussi près que possible). Je dis "théoriquement" parce que je suppose que ce genre de puissance de calcul est au-delà de FB?
Il existe de grandes réponses si n peut être divisé par 2 et 9 et une bonne approche de la théorie du jeu. Voici une approche de programmation dynamique simple en JavaScript pour fournir la réponse à toute réponse possible N.
function getWhoWins(n) {
if(getWhichPlayerWins(0, 1, n) === 0) {
console.log("First player wins for " + n);
} else {
console.log("Second player wins for " + n);
}
}
// Returns 0 if first, 1 if 2nd player would win
function getWhichPlayerWins(currentPlayer, currentNumber, targetNumber) {
if(currentNumber * 9 >= targetNumber) {
return currentPlayer;
}
var nextPlayer = (currentPlayer + 1) % 2;
if(getWhichPlayerWins(nextPlayer, currentNumber *2, targetNumber) === currentPlayer || getWhichPlayerWins(nextPlayer, currentNumber *9, targetNumber) === currentPlayer) {
return currentPlayer;
}
return nextPlayer;
}
K..so Dans ce cas, nous devons apprendre de l'état actuel et faire une décision de prédiction des résultats. Je suis sûr que l'intervieweur sera heureux de savoir qu'une fois que la conception non intelligente se fait bien à temps.
Donc, pour un design non intelligent, choisissez-nous 2/9 au hasard?
L'intervieweur voudrait que vous ajoutez de l'intelligence. Quand ils demandent "qui gagne?", Ils signifient "quel joueur peut gagner le jeu, en supposant une pièce optimale?"
Cela compte-t-il toujours comme une victoire si un joueur dépasse n? Sinon, beaucoup de NS ne peuvent jamais être atteints. ex. Il n'y a aucun moyen d'arriver à 3, à partir de 1, et seulement de multiplier par 2 ou 9.
Ils partagent le même numéro, non?