[Index Jeux] Enigmes, suites logiques et autres casse-têtes !

[Ixy]

Oui mais la question est plutôt d'ordre mathématique

Hmm, 62 pour 2 billes
27 pour 3 billes
20 pour 4 billes

"Partie supérieure"("hauteur"^(1/"nombre billes")-1_|) * "nombre billes" dans le cas général ?

Il faut que tu expliques ta formule, en tout cas c'est pas mal du tout

45 avec deux billes.
Aucune idée pour 3.

Bravo C'est exactement ça !
Tu peux peut-être expliquer comment tu fais ça donnera des idées pour 3 billes (oui c'est un peu plus dur). A mon avis c'est pas très loin de l'idée de phi

[phi]

On va prendre l'exemple avoir 3 billes.

On détermine d'abord la valeur de la centaine de l'étage limite.
On lance une bille aux étages 101, 201, 301, 401, 501, 601, 701, 801, 901.

Ainsi si la bille casse à l'étage 101, ça veut dire que l'étage limite est avant. De 1 à 100.
Si elle ne casse pas mais qu'elle casse à l'étage 201, l'étage limite est entre 101 et 200.
...
Si elle ne casse pas à 901, ça veut dire que l'étage limite est entre 901 et 1000.

Supposons qu'on soit dans la situation entre 101 et 200.

On jette une bille aux étages 111, 121, 131, 141, 151, 161, 171, 181, 191.

Rebellotte, on arrive à déterminer un intervalle de dix étages en fonction de la casse.
Par exemple, entre 111 et 120.

On réitère pour trouver le chiffre des unités.

On a donc fait trois fois neuf lancers.

[Ixy]

Oui Phi c'est une très bonne stratégie

On peut faire un peu mieux car si on casse la bille dès le premier lancer, c'est-à-dire à 101, on a en quelque sorte gagné 8 lancers par rapport à si on avait cassé la bille à 901.


C'est ce que fait Manichéenne pour deux billes. Pour homogénéiser le nombre d'essais, je jette une bille à l'étage d, puis l'étage 2d-1, puis à l'étage 3d-2, etc.

Au final ça nous donne le résultat optimal pour deux billes càd 45 essais max.


Si vous faites une synthèse des 2 stratégies vous arriverez à la solution optimale pour 3 billes.

[phi]

Certes, mais bon, pour quelques poussières

[Ixy]

On peut faire quasiment 30% meilleur Je donnerai le résultat optimal plus tard sauf si une personne veut s'y essayer avant

[phi]

Attends un peu, je vais faire une simulation.

Pas envie de réfléchir

[phi]

19 ?
(fichu limite de 8 caractères)

[Ixy]

Exact ! Je suis curieux de savoir comment tu t'y es pris pour la simulation

[phi]

J'ai appliqué directement ce que tu as dis.

Un code en bon vieux C.

Code : Tout sélectionner

#include <stdlib.h>
#include <stdio.h>


int hauteur_max(int nb_essais, int nb_billes)
{
	if (nb_billes == 0)
		return 0;
	if (nb_billes == 1)
		return nb_essais+1;
	if (nb_essais == 0)
		return 1;
	int j;
	int resultat = 0;
	for (j = 1; j <= nb_essais; j++)
		resultat += hauteur_max(nb_essais-j, nb_billes-1);
	resultat+=1;
	return resultat;
}

int main()
{
	int nb_essais = 1;
	while (hauteur_max(nb_essais,3) < 1000) 
	{
		nb_essais++;
	}
	printf("%d\n", nb_essais);
	return 0;
}

À mon avis, ça ne doit pas être compliqué de faire un algo en programmation dynamique au cas où il y a beaucoup de billes et beaucoup d'étages.

Mais donne ta solution, mon approche est peu élégante.

[Ixy]

Sinon voici le raisonnement à faire :

Soit d le nombre d'essais minimal (pire cas)

Imaginons que ma première et deuxième billes se cassent dès le premier coup.
Il me reste d - 2 essais.
Donc je peux tester seulement les (d - 2) premiers étages. Avec le test de la deuxième bille ça fait d - 1 étages

Si la première bille casse mais pas la deuxième, je peux faire les (d - 2) étages suivants, puis les d - 3, etc. selon la fois où la deuxième bille casse.

Donc si la première bille casse, j'ai (d-1)(d)/2 étages que je peux tester au total en considérant tous les cas. (formule de Gauss, jusque ici c'est le raisonnement de Manichéenne)

Si la première bille se casse la deuxième fois, c'est la même chose mais j'ai le droit à un coup de moins. On remplace seulement d - 1 par d - 2.

Et ainsi de suite

La formule est donc de trouver le d minimal tel que

(d-1)(d)/2 + (d-2)(d-1)/2 + ... + 1*2/2 > 1 000 (pour couvrir tous les cas, en particulier si la bille casse au dernier étage)

Bon c'est une formule un peu moche, on peut vérifier que le d plus petit qui marche est 19, mais ceux qui ont fait un peu de mathématiques savent qu'on peut aussi minorer l'expression à gauche par une intégrale

(d)(d-1)/2 + (d-2)(d-1)/2 + ... + 1*2/2 > intégrale de 0 à d de x(x-1)/2 = 1/6 d^3 - 1/4 d^2

Pour d = 19 cette expression est égale à 1053, c'est bon !

EDIT : Joli Je n'avais pas penser à la récursivité

[freeshost]

Bon, je n'ai pas trop le temps de réfléchir sur le forum en ce moment. Je dois partir dans trente minutes. Je continue de parcourir le forum. Je reviendrai ce soir (vers 21h00).

Intéressant. On pourrait même alors calculer le nombre de marches parcourues (mettons 20 marches par entre-deux-étages) sachant qu'il n'y a pas d'ascenseur. C'est sport !

[dpld]

je réitère ma question : quelle est la nature de la bille (caoutchouc, métal, verre...) la densité des différents matériaux implique une probabilité qui lors d'une chute à un même étage aura un résultat différent ? Non ?

[Ixy]

Freeshost, c'est une autre question celle de faire le moins de marches possibles Tu peux t'y atteler si tu le souhaites

je réitère ma question : quelle est la nature de la bille (caoutchouc, métal, verre...) la densité des différents matériaux implique une probabilité qui lors d'une chute à un même étage aura un résultat différent ? Non ?

La question n'est qu'un prétexte, il s'agit d'un problème mathématique/de logique

[dpld]

Certainement mais ce sont des choses (mathématiques et logiques) que je n'ai pas eu l'occasion d'étudier, ayant très peu fréquenté l'école. Cependant, lorsque cette question est posée, ce qui me vient à l'esprit est : la composition de la bille (bois, verre, métal, caoutchouc...) et une autre question (que je n'avais pas envisagée au départ) est la matière du sol à l'arrivée.... Maintenant, effectivement, je n'avais pas envisagé qu'il était possible de la faire passer par ailleurs que par la fenêtre

Freeshost, c'est une autre question celle de faire le moins de marches possibles Tu peux t'y atteler si tu le souhaites

je réitère ma question : quelle est la nature de la bille (caoutchouc, métal, verre...) la densité des différents matériaux implique une probabilité qui lors d'une chute à un même étage aura un résultat différent ? Non ?

La question n'est qu'un prétexte, il s'agit d'un problème mathématique/de logique

[dpld]

Bon voilà il n'y a plus personne à cet étage.... Pauvre bille