Nombre aléatoire

bleub13 · mai 2012

Bonjour,

je débute en dévéloppement. Je viens de commencer une application qui est un quizz.

J'ai créé des tableaux où je stocke mes questions. Un nombre est géré aléatoirement qui va allé piocher dans les tableaux.

Cependant, j'aimerai que les valeurs déjà utilisé soit interdite pour éviter de retomber sur une même question. Je ne sais pas comment faire.

Merci pour votre aide

/smile.png' class='bbc_emoticon' alt=':)' />

Draken · mai 2012

Ajoute un indicateur binaire a chaque question, pour mémoriser si elle a déjà été utilisée.

TRUE => la question est utilisable

FALSE => la question n'est plus utilisable

Alak · mai 2012

la retirer du tableau à la volé (â€“ removeObjectAtIndex:).

AliGator · mai 2012

NSMutableArray* unaskedQuestions = ... // ton tableau de questions<br />
<br />
-(Question*)pickRandomQuestion<br />
{<br />
  int idx = arc4random() % [unaskedQuestions count];<br />
  Question* q = [unaskedQuestions objectAtIndex:idx];<br />
  [q retain]; // pour éviter qu&#39;il soit détruit quand tu le retire du tableau si personne d&#39;autre ne le retient<br />
  [unaskedQuestions removeObjectAtIndex:idx];<br />
  return [q autorelease];<br />
}

Draken · mai 2012

Autre possibilité, tu crée un tableau pour mémoriser les numéros des questions déjà utilisées.

AliGator · mai 2012

'Draken' a écrit:

Autre possibilité, tu crée un tableau pour mémoriser les numéros des questions déjà utilisées.

Solution moins pratique, car ça veut dire que tu continues de tirer un numéro au hasard entre 0 et N-1 (N = nombre total de questions), et à chaque fois tu vérifies si c'est pas un numéro déjà tiré... et si c'est pas le cas, tu recommences...

Si tu as 50 questions, au début ça va aller, mais quand tu en auras posé 48 et qu'il t'en reste donc plus que 2 à choisir, tu vas devoir relancer un sacré paquet de fois ton random pour espérer tomber sur une des deux qui restent... et je te parle pas de quand il n'en reste qu'une !

Donc non, ce n'est pas vraiment top comme solution.

Mieux vaut faire l'inverse et garder un tableau de celles qui restent à poser, et faire son random dans ce tableau.

bleub13 · mai 2012

'AliGator' a écrit:

NSMutableArray* unaskedQuestions = ... // ton tableau de questions<br />
<br />
-(Question*)pickRandomQuestion<br />
{<br />
  int idx = arc4random() % [unaskedQuestions count];<br />
  Question* q = [unaskedQuestions objectAtIndex:idx];<br />
  [q retain]; // pour éviter qu&#39;il soit détruit quand tu le retire du tableau si personne d&#39;autre ne le retient<br />
  [unaskedQuestions removeObjectAtIndex:idx];<br />
  return [q autorelease];<br />
}

Je comprends la logique du code mais je ne sais pas comment l'adapter pour moi.

(Question*q correspond à quoi ? J'ai du mal avec la syntaxe

)

Voici un aperçu de mon code... si vous pouviez m'éclairer...

-(IBAction) clicSurNext:(id) sender{<br />
	[monBoutonA setEnabled:YES];<br />
	[monBoutonB setEnabled:YES];<br />
	[monBoutonC setEnabled:YES];<br />
	[monBoutonD setEnabled:YES];<br />
	[VraiOuFaux setStringValue:@&quot;&quot;];<br />
	[monBoutonStop setEnabled:YES];<br />
	[monBoutonNext setEnabled:NO];<br />
  <br />
	compteur ++;<br />
	aleatoire = arc4random()%7;<br />
	[VraiOuFaux setIntValue:compteur];<br />
  <br />
	mesQuestions =[NSArray arrayWithObjects:@&quot;Trouvez le synonyme de éplucher:&quot;,<br />
				   @&quot;Comment s&#39;appellent les petits de la louve ?&quot;,<br />
				   @&quot;Qui n&#39;est pas de la société Apple ? &quot;,<br />
				   @&quot;Qui est notre nouveau président ?&quot;,<br />
				   @&quot;Que veut dire le mot cocoa ?&quot;,<br />
				   @&quot;Quel jour sera le 11 Juillet 2013 ?&quot;,<br />
				   @&quot;Où se déroule les prochain JO ?&quot;,<br />
				   @&quot;Comment appelle-t-on un auteur de fables ?&quot;,<br />
				   @&quot;Quel mot est mal orthographié ?&quot;,<br />
				   @&quot;Quel est le président de Russie?&quot;, nil];<br />
  <br />
	[Question setStringValue:[mesQuestions objectAtIndex:aleatoire]];

devulder · mai 2012

Pour tes questions, il faut que tu créer un classe avec

un champ NSString *nomQuestion;

un champ NSString *reponseA;

un champ NSString *reponseB;

un champ NSString *reponseC;

un champ NSString *reponseD;

un champ int nombreReponsePossible;

un champ int bonneReponse;

Sinon tu vas te compliquer la vie pour gérer les réponses !

Draken · mai 2012

'AliGator' a écrit:

Solution moins pratique, car ça veut dire que tu continues de tirer un numéro au hasard entre 0 et N-1 (N = nombre total de questions), et à chaque fois tu vérifies si c'est pas un numéro déjà tiré... et si c'est pas le cas, tu recommences...

Si tu as 50 questions, au début ça va aller, mais quand tu en auras posé 48 et qu'il t'en reste donc plus que 2 à choisir, tu vas devoir relancer un sacré paquet de fois ton random pour espérer tomber sur une des deux qui restent... et je te parle pas de quand il n'en reste qu'une !

Donc non, ce n'est pas vraiment top comme solution.

Mieux vaut faire l'inverse et garder un tableau de celles qui restent à poser, et faire son random dans ce tableau.

Oui, sauf si je n'utilise le random que pour les 45 premières questions. Il suffit ensuite de parcourir le tableau linéairement pour récupérer les 5 dernières questions. J'utilise cette technique depuis mon premier jeu de rôle sur Amstrad 6128.

Bleub13, tu devrais essayer de définir tes questions dans un fichier plist. C'est beaucoup plus souple d'emploi qu'une définition en "dur" dans le code source.

System · mai 2012

Heu ça me paraà®t un peu archaà¯que ton truc Draken... oO On bosse sur des machines bien plus puissantes et avec plus de mémoire maintenant hein

/biggrin.png' class='bbc_emoticon' alt=':D' />

Xodia · mai 2012

Encore mieux, faire un webservice pour que tu puisses récupérer un jeu de questions ? (S'il y a plusieurs quizz hein).

'AliGator' a écrit:

NSMutableArray* unaskedQuestions = ... // ton tableau de questions<br />
<br />
-(Question*)pickRandomQuestion<br />
{<br />
  int idx = arc4random() % [unaskedQuestions count];<br />
  Question* q = [unaskedQuestions objectAtIndex:idx];<br />
  [q retain]; // pour éviter qu&#39;il soit détruit quand tu le retire du tableau si personne d&#39;autre ne le retient<br />
  [unaskedQuestions removeObjectAtIndex:idx];<br />
  return [q autorelease];<br />
}

Ce code me semble correcte, mais pourquoi "casser" votre tableau de question ?

Tu mets une autre variable de type BOOL ou char (meme taille je crois) que set a 1 si la question est deja passer

et si c'est 0, cela veut dire que la question n'a pas encore été poser ?

Pis si dans ton arc4random (D'ou elle sort cette fonction ^^), il te sort une question deja poser, refait un random ou regarde celui d'avant et d'apres s'il a deja été poser ?

Ceci étant dis, arc4random peut être remplacer par :

<br />
srand(time(0));<br />
int randomValue = rand() % [tab count];<br />

C'est plus commun comme fonction ^^

'devulder' a écrit:

Pour tes questions, il faut que tu créer un classe avec

un champ NSString *nomQuestion;

un champ NSString *reponseA;

un champ NSString *reponseB;

un champ NSString *reponseC;

un champ NSString *reponseD;

un champ int nombreReponsePossible;

un champ int bonneReponse;

Sinon tu vas te compliquer la vie pour gérer les réponses !

<br />
{<br />
NSString *question;<br />
NSArray *responses;<br />
int			 nbResponseToAsk;<br />
BOOL          alreadyHaveBeenAsked;<br />
}<br />

Et pour les réponses un petite classe ayant:

<br />
{<br />
NSString *reponse;<br />
BOOL	 isTrue;<br />
}<br />

M'voyer ?

Draken · mai 2012

'ldesroziers' a écrit:

Heu ça me paraà®t un peu archaà¯que ton truc Draken... oO On bosse sur des machines bien plus puissantes et avec plus de mémoire maintenant hein /biggrin.png' class='bbc_emoticon' alt=':D' />

Ah tu veux dire que les problèmes de mémoire n'existent plus avec les machine actuelles ? Merci d'ensoleiller ma journée.

AliGator · mai 2012

'Xodia' a écrit:

Ce code me semble correcte, mais pourquoi "casser" votre tableau de question ?

Tu mets une autre variable de type BOOL ou char (meme taille je crois) que set a 1 si la question est deja passer

et si c'est 0, cela veut dire que la question n'a pas encore été poser ?

Pis si dans ton arc4random (D'ou elle sort cette fonction ^^), il te sort une question deja poser, refait un random ou regarde celui d'avant et d'apres s'il a deja été poser ?

Bah pour toutes les raisons que j'ai expliqué à Draken !

Tirer une question au hasard dans ton tableau de toutes tes questions, et si jamais la question est déjà posée retirer un nombre au hasard encore et encore jusqu'à enfin tomber sur une question pas encore posée, ça va être loin d'être optimisé et plutôt long (la probabilité de tomber sur une question déjà posée augmentant au fur et à mesure que tu as posé de plus en plus de questions bien sûr, donc le nombre de retirages nécessaire va aller en augmentant).

Quand tu auras déjà posé 49 questions sur tes 50 questions par exemple (si tu en as 50 en tout), il ne t'en restera qu'une seule, pourtant tu vas n'avoir qu'une seule chance sur 50 que ton random tombe dessus, donc tu vas pas tomber dessus tout de suite, et devoir refaire un sacré paquet de tirages avant d'avoir la chance de tomber dessus !

Alors que si tu ne fais ton tirage que sur les questions restantes et pas sur toutes les questions, tu n'as rien du tout à faire à côté, pas besoin de test ni de re-tirage puisque tu tombes forcément sur une question pas encore posée. Beaucoup plus rapide, et beaucoup plus optimal.

Bien sûr le tableau de alreadyAskedQuestions est une copie du tableau contenant toutes tes questions, tu fais la copie au début de ton jeu et tu l'écrèmes au fur et à mesure que tu poses tes questions... et si tu recommences le jeu tu n'as qu'à refaire une copie de ton tableau de question avec [font=courier new,courier,monospace]self.alreadyAskedQuestions = [[allQuestions mutableCopy] autorelease];[/font] et le tour est joué, tes questions sont réinitialisées en une simple ligne de code (alors qu'avec des flags tu serais obligé de tout repasser question par question pour le remettre à NO...)

Bref je ne vois aucun inconvénient à ma méthode, et en plus elle est en complexité algorithmique O(1) alors que l'algo consistant à réitérer jusqu'à trouver est O(n) et que le nombre de retirages nécessaires et de temps pour tomber sur une question non posée va augmenter linéairement... donc je ne vois mais alors pas du tout quel avantage la solution de "tirer dans toutes les questions et retirer jusqu'à trouver une non posée" est intéressante ou mieux que de ne tirer que dans les questions non encore posées ?! C'est quoi l'avantage de l'autre solution ?!

zoc · mai 2012

'AliGator' a écrit:

Bref je ne vois aucun inconvénient à ma méthode, et en plus elle est plus elle est en complexité algorithmique O(1) alors que l'algo consistant à réitérer jusqu'à trouver est O(n)

Ah la fameuse complexité des algorithmes, une notion que beaucoup de développeurs néglige...

Ce seul argument suffit à me faire choisir l'algorithme de Ali plutôt que celui de Xodia.

Xodia · mai 2012

J'ai pas dis non plus que c'était l'algo parfait ^^, c'est vrai que celui que je propose prend plus de temps avec un facteur le nombre d'éléments du tableau qui plus il croit, plus c'est lent.

Le seul avantage de la méthode que je propose est qu'elle est simple a coder pour un débutant.

Apres j'avoue que la tienne est pas trop compliquer non plus, le seul truc est de bien gérer la mémoire.

Faut aussi voir les test de perf pour voir lequel prend le plus de temps (en sachant qu'en arrière-plan pour modifier les tableaux il faut boucler dessus, le redimensionner etc... (Au niveau interne des classes)) A tester..

AliGator · mai 2012

Non pas tant que ça car les NSArray sont fortement optimisés tant pour les accès séquentiels que pour les accès direct.

La structure interne des NSArray est franchement super optimisée, Apple a fait un gros travail dessus (cf l'article de RidiculousFish que j'ai déjà cité plusieurs fois et qui explique tout ça avec le détail des perfs et tout), ce qui fait que pour modifier un NSMutableArray ça prend 3 fois rien de temps.

Ca n'a vraiment rien à voir avec des tableau C par exemple. Avec NSArray, pour modifier le tableau pas besoin de boucler dessus (principe de la liste chaà®née, ça enlève un élément en plein milieu sans pb), pas besoin de le redimentionner (de toute façon il est alloué par chunks), donc au final un removeObjectAtIndex prend un temps négligeable (par rapport à si tu devais faire la même chose avec un tableau C où ça sera une méga galère par contre)

Xodia · mai 2012

Ok, oui si c'est comme les listes chaà®nées j'avoue que c'est rapide. Je vais essayer de trouver ton article pour comprendre comment il fonctionne. Merci

/wink.png' class='bbc_emoticon' alt=';)' />

Draken · mai 2012

Si le fait de retirer un élément de la liste ne consomme quasiment rien en performance/mémoire, alors d'accord .. * ton grognon *

FKDEV · mai 2012

Sinon, pour conserver le tableau initial, ou si on travaille avec un tableau en C, on peut toujours trier le tableau en envoyant les éléments tirés à la fin du tableau.

A chaque tirage, on envoie l'élément tiré à la case M-1 du tableau où M est le nombre d'éléments restants à tirer et on effectue le prochain tirage sur les M-2 premiers éléments.

Xodia · mai 2012

'FKDEV' a écrit:

Sinon, pour conserver le tableau initial, ou si on travaille avec un tableau en C, on peut toujours trier le tableau en envoyant les éléments tirés à la fin du tableau.

A chaque tirage, on envoie l'élément tiré à la case M-1 du tableau où M est le nombre d'éléments restants à tirer et on effectue le prochain tirage sur les M-2 premiers éléments.

C'est un peu tirer les cheveux ton truc

/xd-laugh.gif' class='bbc_emoticon' alt='xd' />

Faut faire attention a faire trop "joujou" avec les pointeurs comme sa, c'est facilement plantable si tu le fais pas bien.

Mais si tu fais cela, il faut switcher les deux pointeurs (celui piocher et celui qu'on prend la place).

AliGator · mai 2012

Et en plus un tri, quel que soit l'algo de tri utilisé, sera bien plus consommateur qu'une simple suppression de l'élément d'un tableau mutable des questions non posées.

Larme · mai 2012

J'avais utilisé un méthode similaire en C pour un projet. Je m'étais confronté au même problème d'un tableau statique, du nombre d'itérations à avoir quand il ne restait pratiquement plus de choix...

J'avais créé donc une liste chaà®née.

J'randomisais mon "k" et après, je supprimais ce k-ième élément, réduisant par la même occasion le max du random.

En bref, la méthode utilisée par le Croco sans objet :°)

Baarde · mai 2012

Non AliGator, tu n'utilises pas un tri. À chaque fois que tu choisis une valeur, tu la permutes avec la dernière valeur non tirée et tu réduis l'intervalle dans lequel seront tirées les prochaines valeurs. Ainsi, les valeurs déjà tirées se retrouvent à la fin du tableau (ou au début, ça fonctionne aussi).

Exemple :

Tu as le tableau suivant de longueur 7 :

A | B | C | D | E | F | G |

Tu tires un nombre aléatoire entre 0 et 6 : 2 (c'est à dire C). Tu permutes C avec la valeur à l'index 6 et tu réduis N.

A | B | G | D | E | F || C |

La valeur C ne peut plus être tirée car N vaut maintenant 6. Tu tires un nouveau nombre aléatoire entre 0 et 5. Tu permutes la valeur avec la valeur à l'index 5 et tu réduis à nouveau N.

La méthode présente plusieurs avantages :

Le nombre d'opérations à effectuer est réduit. Pour une tableau de N éléments, tu effectueras uniquement N permutations, lesquels ne nécessitent aucun redimensionnement ou décalage de valeurs.
Tu n'as pas besoin de te soucier de la gestion de la mémoire. Tous les objets restent en permanence dans le tableau.
Tu peux utiliser un NSMutableArray si tu le souhaites avec la méthode exchangeObjectAtIndex:withObjectAtIndex:
Tu conserves l'historique des valeurs déjà tirées.
Le tableau n'a pas besoin d'être modifié à la fin. Il suffit de réinitialiser N à la taille du tableau. Tu peux même implémenter le undo/redo en incrémentant/décrémentant N.

System · mai 2012

Je suis d'accord avec la solution de Baarde, qui n'est pas mauvaise en soit. Mais d'un point de vue purement esthétique je trouve ça bizarre de gérer N

/tongue.png' class='bbc_emoticon' alt=':P' /> Je ne vois pas en quoi ça serait mal de gérer 2 NSMutableArray ('questions' et 'answeredQuestions'). Certes la consommation mémoire sera au final plus élevée que l'utilisation d'une primitive N mais franchement... Au final c'est juste une seconde array avec les mêmes instances qui étaient contenues dans 'questions'. Donc la consommation mémoire ne va pas bcp bougée, si ce n'est l'allocation d'une NSMutableArray.

Au final le code serait, à mon sens, plus lisible.. non?

Par contre si on parle de plusieurs milliers de questions je pense effectivement que le côté -removeObjectAtIndex: (dans 'questions') puis -addObject: (dans la 'answeredQuestions') risque de prendre plus de temps qu'un -exchangeObjectAtIndex:withObjectAtIndex:

Il y a un tableau de perfs quelque part concernant -exchangeObjectAtIndex:withObjectAtIndex: ?

Bref, toutes les solutions proposées sont viables, mais ça dépend des cas. je préfèrerai utiliser 2 arrays si je suis sûr d'avoir entre 0 et 200 objets par exemple.. (je dis ça arbitrairement). Dans le cas où l'intervalle 0-XX où XX pourrait être faramineux, je vais préférer le méthode de Baarde..

Baarde · mai 2012

Ce n'est pas ma solution, c'est celle de FKDEV. Je me suis juste contenté de la détailler.

/wink.png' class='bbc_emoticon' alt=';)' />

Effectivement, avoir un seul tableau qui contient tous les objets peut être source de confusion. Mais on peut très bien concevoir une classe ayant un niveau d'abstraction plus élevé et utilisant le tableau dans son implémentation.

En ce qui concerne les performances, je pense que le gain est assez négligeable (sur une machine actuelle).

FKDEV · mai 2012

Merci Baarde, je ne l'aurais pas mieux expliquée. Et, en plus, je n'avais pas vu tous ces avantages avec cette solution.

Mais par intuition ça me paraissait la meilleure solution car on n'a rien à copier, rien à supprimer et l'algo a un comportement constant tout au long du jeu (si on suppose que la méthode exchangeObjectAtIndex:withObjectAtIndex: aura toujours le même comportement).

C'est une version optimisée en mémoire de la version à deux tableaux en fait.

Je trouve plus élégant de jouer avec N que de faire des copies de tableaux mais c'est une question de goût...

Après c'est sans doute moins facile à lire, mais ce n'est pas grave si c'est bien encapsulé.

De toutes façons, c'est un cas où le plus important c'est d'encapsuler l'ago et de bien choisir les interfaces de l'objet qui gère les questions pour pouvoir changer la mécanique interne si nécessaire.

Cela ne sert à rien de se prendre la tête quand on n'a pas tous les éléments en main, autant se concentrer sur l'aspect modulaire et "refactorable" du code pour sortir une version au plus vite et la confronter à une utilisation réelle.

AliGator · mai 2012

Yep c'est aussi pour la lisibilité et facilité d'implémentation de l'algo (en gros juste les quelques lignes de code que j'avais mises dans mon premier message suffisent, et un appel à mutableCopy au démarrage, et c'est tout l'algo est implémenté et c'est fini) que le tableau où on enlève les questions posées me plaisait.

La solution de FKDEV est bien aussi hein, mais plus casse-tête à mettre en place, pour peu de gain finalement en terme de perfs.

La question de l'utilisation mémoire est vraiment un faux problème, j'espère que vous avez conscience comme l'a souligné Louka qu'on ne duplique pas les questions, et donc qu'on a pas 2x50 questions en mémoire si on a 50 questions à l'origine. On fait des retain sur les questions, donc on a toujours seulement 50 instances, retenues 2 fois (une fois par chaque tableau), et pas 100 instances en mémoire.

Au final la seule chose qu'on a en mémoire en plus du tableau de toutes les questions, c'est un objet qui fait genre 20 octets on va dire (l'instance du conteneur NSMutableArray, mais sans son contenu), le contenu de ce NSMutableArray étant des objets déjà en mémoire ailleurs de toute façon.

bleub13 · mai 2012

J'ai réussi à faire ce que je voulais, merci.

J'aimerais maintenant qu'il me sauvegarde les questions déjà posés quand je ferme l'application et la relance pour rejouer.

J'ai trouvé des tutos mais je ne comprend pas vraiment tout ...

AliGator · mai 2012

Du coup si tu as choisi la solution que je préconise depuis le début, avec un NSMutableArray de alreadyAskedQuestions, il suffit de stocker ce NSArray dans les NSUserDefaults (ça se fait en une ligne), et le récupérer au prochain lancement (se code en une ligne aussi).

Nombre aléatoire

Réponses