Histoires de grenouilles et crapauds
car...@server.invalid
dans le chapitre des mathématiques récréatives, je suis tombé sur un
problème que je ne sais pas par quel bout empoigner, alors si vous pouviez
me donner un lien vers un peu d'aide ce serait sympa.
On a n crapauds et n grenouilles sur une ligne avec un espace entre eux
par exemple pour n=2
CC_GG
Les crapauds peuvent se déplacer vers la droite d'une case si la case à leur
droite est vide ou sauter par dessus une grenouille si la case à droite de
la grenouille est vide (symétriquement pour les grenouilles).
La question qui est posée est : combien de déplacements sont nécessaires si
on a n bestioles de chaque type pour "renverser" la situation initiale.
Par exemple, pour 1 crapaud et 1 grenouille on aura:
C_G
_CG
GC_
G_C
ou
C_G
CG_
_GC
G_C
4 mouvements nécessaires...
Pour 2 crapauds et 2 grenouilles c'est déjà plus coton... mais il me semble
intuitivement qu'on devrait pouvoir définir une relation de récurence.
D'avance merci de votre aide
zwim
car...@server.invalid a �crit
>Bonjour
>
>dans le chapitre des math�matiques r�cr�atives, je suis tomb� sur un
>probl�me que je ne sais pas par quel bout empoigner, alors si vous pouviez
>me donner un lien vers un peu d'aide ce serait sympa.
>
>On a n crapauds et n grenouilles sur une ligne avec un espace entre eux
>
>par exemple pour n=2
>
>CC_GG
>
>droite est vide ou sauter par dessus une grenouille si la case � droite de
>la grenouille est vide (sym�triquement pour les grenouilles).
>
>La question qui est pos�e est : combien de d�placements sont n�cessaires si
>on a n bestioles de chaque type pour "renverser" la situation initiale.
>
>Par exemple, pour 1 crapaud et 1 grenouille on aura:
>
>C_G
>_CG
>GC_
>G_C
>
>ou
>
>C_G
>CG_
>_GC
>G_C
>
>
>Pour 2 crapauds et 2 grenouilles c'est d�j� plus coton... mais il me semble
>intuitivement qu'on devrait pouvoir d�finir une relation de r�curence.
>
>D'avance merci de votre aide
>
C'est un joli petit probl�me.
Je pense qu'on peut le crossposter sur frje.
J'ai commenc� par essayer l'�num�ration � la main, mais c'est
difficile de savoir si c'est optimal.
J'ai utilis� 0 et 1 comme symboles plut�t que C et G qui sont
visuellement trop proches.
n=0, f(n)=1
_
n=1, f(n)=4
0_1
_01
10_
1_0
n=2, f(n)=9
00_11
0_011
010_1
0101_
01_10
_1010
1_010
110_0
11_00
n=3, f(n)=20 ?
000_111
00_0111
0010_11
001_011
0_10011
01_0011
010_011
01010_1
0101_01
01_1001
_101001
1_01001
110_001
1100_01
110010_
11001_0
110_100
11_0100
1110_00
111_000
Et puis j'ai cherch� la suite 1,4,9,20 dans l'encyclop�die.
http://www.research.att.com/~njas/sequences/?q=1%2C4%2C9%2C20
Mais �a ne me donne pas d'id�e pr�cise pour le moment.
Il faudrait �num�rer f(4) pour voir si on trouve bien 35 alors A066186
serait un bon candidat.
f(3) n'est d�j� pas facile � �num�rer, il faut faire attention �
garder la chaine dynamique et ne pas trop accumuler de 0 et de 1 en
paquets sinon il faut faire des mouvements parasites pour pouvoir
faire � nouveau des sauts.
Par exemple cette s�quence fait passer un second 0 � droite, mais il
faut ensuite le ramener vers la gauche pour poursuivre.
001_011
0_10011
01_0011
010_011
Ici il n'y a pas moyen de faire mieux je crois, mais pour n=4 �a
devient coton...
--
zwim.
Rien n'est impossible que la mesure de la volont� humaine...
zwim
zwim a �crit
>car...@server.invalid a �crit
>>Bonjour
>>
>>dans le chapitre des math�matiques r�cr�atives, je suis tomb� sur un
>>probl�me que je ne sais pas par quel bout empoigner, alors si vous pouviez
>>me donner un lien vers un peu d'aide ce serait sympa.
>>
>>On a n crapauds et n grenouilles sur une ligne avec un espace entre eux
>>
>>par exemple pour n=2
>>
>>CC_GG
>>
>>Les crapauds peuvent se d�placer vers la droite d'une case si la case � leur
>>droite est vide ou sauter par dessus une grenouille si la case � droite de
>>la grenouille est vide (sym�triquement pour les grenouilles).
>>
>>La question qui est pos�e est : combien de d�placements sont n�cessaires si
>>on a n bestioles de chaque type pour "renverser" la situation initiale.
J'ai repris le probl�me par programmation, et il s'av�re que j'avais
faux pr�c�demment.
Voici le programme pour ceux que �a int�resse :
http://cjoint.com/?lhvgVUhJRu
En gros je code en base 3, C=0, G=1 et _=2
Donc CC_GG vaut 00211.
Et j'utilise un immense tableau pour stocker le graphe des voisins, un
voisin �tant une position pouvant �tre obtenue � partir d'une autre
position gr�ce aux 4 mouvements l�gaux :
_a vers a_
a_ vers _a
01_ vers _10
_01 vers 10_
L'algo s'arr�te quand les 1 et les 0 ont chang� de place.
Voici ce que donne l'execution pour n=2
$ ./grenouilles.exe 2
----- NIVEAU 0 -----
22 : 00_11 : 0 -1
----- NIVEAU 1 -----
16 : 001_1 : 1 22
58 : 0_011 : 1 22
----- NIVEAU 2 -----
14 : 0011_ : 2 16
34 : 010_1 : 2 58
64 : 0_101 : 2 16
166 : _0011 : 2 58
----- NIVEAU 3 -----
32 : 0101_ : 3 34
46 : 01_01 : 3 34
172 : _0101 : 3 64
----- NIVEAU 4 -----
38 : 0110_ : 4 46
48 : 01_10 : 4 32
100 : 10_01 : 4 172
190 : _1001 : 4 46
----- NIVEAU 5 -----
42 : 011_0 : 5 38
66 : 0_110 : 5 48
88 : 100_1 : 5 100
92 : 1010_ : 5 100
136 : 1_001 : 5 100
192 : _1010 : 5 48
----- NIVEAU 6 -----
86 : 1001_ : 6 88
96 : 101_0 : 6 92
138 : 1_010 : 6 192
174 : _0110 : 6 66
----- NIVEAU 7 -----
102 : 10_10 : 7 86
114 : 110_0 : 7 138
144 : 1_100 : 7 96
----- NIVEAU 8 -----
110 : 1100_ : 8 114
126 : 11_00 : 8 114
198 : _1100 : 8 144
Avec pour chaque impression, le nombre en base 3, sa repr�sentation
visuelle, le niveau et la position parente au niveau pr�c�dent.
Et voici donc le r�sultat cherch�, le plus court chemin de la potion
de d�part � la position d'arriv�e (ici pr�sent� en ordre r�trograde).
##################### n=0
_ : 0 -1
##################### n=1
1_0 : 3 11
10_ : 2 19
_01 : 1 7
0_1 : 0 -1
##################### n=2
11_00 : 8 114
110_0 : 7 138
1_010 : 6 192
_1010 : 5 48
01_10 : 4 32
0101_ : 3 34
010_1 : 2 58
0_011 : 1 22
00_11 : 0 -1
##################### n=3
111_000 : 15 1071
1110_00 : 14 1143
11_0100 : 13 1305
1_10100 : 12 873
101_100 : 11 825
10101_0 : 10 821
101010_ : 9 829
1010_01 : 8 901
10_0101 : 7 1549
_010101 : 6 577
0_10101 : 5 145
001_101 : 4 97
00101_1 : 3 103
0010_11 : 2 175
00_0111 : 1 67
000_111 : 0 -1
##################### n=4
1111_0000 : 24 9774
11110_000 : 23 9990
111_01000 : 22 10476
11_101000 : 21 9180
1101_1000 : 20 9036
110101_00 : 19 9024
1101010_0 : 18 9048
11010_010 : 17 9264
110_01010 : 16 11208
1_0101010 : 15 15582
_10101010 : 14 3918
01_101010 : 13 2622
0101_1010 : 12 2478
010101_10 : 11 2462
01010101_ : 10 2464
0101010_1 : 9 2488
01010_011 : 8 2704
010_01011 : 7 4648
0_0101011 : 6 1732
00_101011 : 5 436
0001_1011 : 4 292
000101_11 : 3 310
00010_111 : 2 526
000_01111 : 1 202
0000_1111 : 0 -1
##################### n=5
11111_00000 : 35 88371
111110_0000 : 34 89019
1111_010000 : 33 90477
111_1010000 : 32 86589
11101_10000 : 31 86157
1110101_000 : 30 86121
11101010_00 : 29 86193
111010_0100 : 28 86841
1110_010100 : 27 92673
11_01010100 : 26 105795
1_101010100 : 25 70803
101_1010100 : 24 66915
10101_10100 : 23 66483
1010101_100 : 22 66435
101010101_0 : 21 66431
1010101010_ : 20 66439
10101010_01 : 19 66511
101010_0101 : 18 67159
1010_010101 : 17 72991
10_01010101 : 16 125479
_0101010101 : 15 46747
0_101010101 : 14 11755
001_1010101 : 13 7867
00101_10101 : 12 7435
0010101_101 : 11 7387
001010101_1 : 10 7393
00101010_11 : 9 7465
001010_0111 : 8 8113
0010_010111 : 7 13945
00_01010111 : 6 5197
000_1010111 : 5 1309
00001_10111 : 4 877
0000101_111 : 3 931
000010_1111 : 2 1579
0000_011111 : 1 607
00000_11111 : 0 -1
##################### n=6
111111_000000 : 48 796554
1111110_00000 : 47 798498
11111_0100000 : 46 802872
1111_10100000 : 45 791208
111101_100000 : 44 789912
11110101_0000 : 43 789804
111101010_000 : 42 790020
1111010_01000 : 41 791964
11110_0101000 : 40 809460
111_010101000 : 39 848826
11_1010101000 : 38 743850
1101_10101000 : 37 732186
110101_101000 : 36 730890
11010101_1000 : 35 730746
1101010101_00 : 34 730734
11010101010_0 : 33 730758
110101010_010 : 32 730974
1101010_01010 : 31 732918
11010_0101010 : 30 750414
110_010101010 : 29 907878
1_01010101010 : 28 1262172
_101010101010 : 27 317388
01_1010101010 : 26 212412
0101_10101010 : 25 200748
010101_101010 : 24 199452
01010101_1010 : 23 199308
0101010101_10 : 22 199292
010101010101_ : 21 199294
01010101010_1 : 20 199318
010101010_011 : 19 199534
0101010_01011 : 18 201478
01010_0101011 : 17 218974
010_010101011 : 16 376438
0_01010101011 : 15 140242
00_1010101011 : 14 35266
0001_10101011 : 13 23602
000101_101011 : 12 22306
00010101_1011 : 11 22162
0001010101_11 : 10 22180
000101010_111 : 9 22396
0001010_01111 : 8 24340
00010_0101111 : 7 41836
000_010101111 : 6 15592
0000_10101111 : 5 3928
000001_101111 : 4 2632
00000101_1111 : 3 2794
0000010_11111 : 2 4738
00000_0111111 : 1 1822
000000_111111 : 0 -1
##################### n=7
1111111_0000000 : 63 7172631
11111110_000000 : 62 7178463
111111_01000000 : 61 7191585
11111_101000000 : 60 7156593
1111101_1000000 : 59 7152705
111110101_00000 : 58 7152381
1111101010_0000 : 57 7153029
11111010_010000 : 56 7158861
111110_01010000 : 55 7211349
1111_0101010000 : 54 7329447
111_10101010000 : 53 7014519
11101_101010000 : 52 6979527
1110101_1010000 : 51 6975639
111010101_10000 : 50 6975207
11101010101_000 : 49 6975171
111010101010_00 : 48 6975243
1110101010_0100 : 47 6975891
11101010_010100 : 46 6981723
111010_01010100 : 45 7034211
1110_0101010100 : 44 7506603
11_010101010100 : 43 8569485
1_1010101010100 : 42 5735133
101_10101010100 : 41 5420205
10101_101010100 : 40 5385213
1010101_1010100 : 39 5381325
101010101_10100 : 38 5380893
10101010101_100 : 37 5380845
1010101010101_0 : 36 5380841
10101010101010_ : 35 5380849
101010101010_01 : 34 5380921
1010101010_0101 : 33 5381569
10101010_010101 : 32 5387401
101010_01010101 : 31 5439889
1010_0101010101 : 30 5912281
10_010101010101 : 29 10163809
_01010101010101 : 28 3786517
0_1010101010101 : 27 952165
001_10101010101 : 26 637237
00101_101010101 : 25 602245
0010101_1010101 : 24 598357
001010101_10101 : 23 597925
00101010101_101 : 22 597877
0010101010101_1 : 21 597883
001010101010_11 : 20 597955
0010101010_0111 : 19 598603
00101010_010111 : 18 604435
001010_01010111 : 17 656923
0010_0101010111 : 16 1129315
00_010101010111 : 15 420727
000_10101010111 : 14 105799
00001_101010111 : 13 70807
0000101_1010111 : 12 66919
000010101_10111 : 11 66487
00001010101_111 : 10 66541
0000101010_1111 : 9 67189
00001010_011111 : 8 73021
000010_01011111 : 7 125509
0000_0101011111 : 6 46777
00000_101011111 : 5 11785
0000001_1011111 : 4 7897
000000101_11111 : 3 8383
00000010_111111 : 2 14215
000000_01111111 : 1 5467
0000000_1111111 : 0 -1
Au del� de n=7, �a devient probl�matique au niveau conso m�moire :p
Oh le joli serpentin de _ !
La suite magique est donc : 0,3,8,15,24,35,48,63,...
Cette fois la recherche est positive sur l'encyclop�die
http://www.research.att.com/~njas/sequences/A005563
f(n) = n(n+2)
Reste plus qu'� le d�montrer pour les courageux, ce que je ne suis pas
ce soir...
Alain SEILLIEZ
>leur
>droite est vide ou sauter par dessus une grenouille
>si la case � droite de la grenouille est vide (sym�triquement pour les
>grenouilles).
j'ai l'impression que vous ne tenez pas compte de cette condition
"si la case � droite de la grenouille est vide '
ce qui donnerait
00_11
0_011
010_1
10_01
1010
101_0
1100
110_0
11_00
AMHA (mais je dois me planter!)
Alain
Philippe 92
> zwim a ï¿œcrit
>> car...@server.invalid a ï¿œcrit
>>>
>>> combien de dï¿œplacements sont nï¿œcessaires si on a n bestioles de
>>> chaque type pour "renverser" la situation initiale.
>
>
> Et j'utilise un immense tableau pour stocker le graphe des voisins
> Au delￜ de n=7, ￜa devient problￜmatique au niveau conso mￜmoire :p
Bonjour,
Pourquoi tant de mï¿œmoire ???
Une chaine de caractï¿œres reprï¿œsentant la liste des moutons,
pardon des crapeaux/grenouilles, ou pions blanc/noirs.
4 indices dans cette chaine : celui du 1er et du dernier
de chaque troupeau (pour raccourcir les boucles et donner une
condition simple pour l'arrï¿œt et certains tests)
Point final.
C'est comme pour la tour de Hanoi :
On peut obtenir directement les mouvements avec une simple boucle,
avec la paritￜ des numￜros des disques.
Ici la stratￜgie correcte est ￜ la portￜe d'un enfant.
Il n'y a donc pas besoin de la faire *chercher* par le programme :
On dï¿œplace les crapeaux tant qu'on peut.
On dï¿œplace les grenouilles tant qu'on peut.
on recommence jusqu'ￜ ce soit fini.
Les crapeaux se dï¿œplacent de la faï¿œon suivante (vers la droite) :
- s'il n'y a plus de grenouilles devant lui, et une case vide,
il avance
- s'il y a une case vide et une grenouille juste devant, il avance
- s'il a une grenouille et une case vide juste devant, il saute
Sinon il ne bouge pas.
Les grenouilles opï¿œrent de mï¿œme dans l'autre sens.
Quant au nombre de dï¿œplacements total :
>
> La suite magique est donc : 0,3,8,15,24,35,48,63,...
>
> Cette fois la recherche est positive sur l'encyclopï¿œdie [OEIS]
> http://www.research.att.com/~njas/sequences/A005563
>
> f(n) = n(n+2)
>
OEIS cite :
ￜ Probably the first to publish the number of moves for n of each
animal was Edouard Lucas in 1883. ￜ
Effectivement j'ai trouvￜ ￜa chez Lucas.
Sans preuve rigoureuse, il remarque que le nombre de positions
diffï¿œrentes obtenues est (n + 1)^2, y compris la position de dï¿œpart,
et donc qu'il y a (n + 1)^2 - 1 = n(n + 2) mouvements.
En fait il y a 2n avances et n^2 sauts
Il signale donc finallement :
ￜ En ajoutant le nombre des pas au double du nombre des sauts
on trouve 2n(n + 1). C'est ce que l'on doit obtenir si l'on
remarque que, pour occuper la case assignï¿œe, chaque pion doit
avancer de n + 1 cases, et par suite les 2n pions doivent exï¿œcuter
2n(n + 1) dￜplacements d'une case. ￜ
Il fournit enfin une gￜnￜralisation ￜ deux dimensions.
Amicalement.
--
Philippe C., mail : chephip avec free.fr comme domaine
site : http://mathafou.free.fr/ (divertissements mathï¿œmatiques)
zwim
Philippe 92 a �crit
>zwim a �crit :
>> zwim a �crit
>>> car...@server.invalid a �crit
>>>> eux. par exemple pour n=2 CC_GG
>>>>
>>>> chaque type pour "renverser" la situation initiale.
>>
>>
>> Et j'utilise un immense tableau pour stocker le graphe des voisins
>> ...
>
>Bonjour,
>
>Pourquoi tant de m�moire ???
C'est vrai �a, pourquoi autant.
Pour un probl�me de taille n, le codage en base 3 repr�sente au
maximum 3^(2n+1) positions posssibles.
Mon algo part d'une position donn�e et � l'�tape i+1 construit tous
les voisins des positions de l'�tape i.
J'ai donc allou� un tableau de taille 3^(2n+1) pour stocker cela, mais
dans la pratique seule une petite fraction de cet espace est
n�cessaire ( ce qui refl�te le fait que le probl�me initial n'est pas
si compliqu� ).
Test avec n=7
51450 / 14348907 : 0.003586 %
Je peux donc modifier l'algo pour remplacer le tableau par une file
d'attente moins gourmande.
>Une chaine de caract�res repr�sentant la liste des moutons,
>pardon des crapeaux/grenouilles, ou pions blanc/noirs.
>4 indices dans cette chaine : celui du 1er et du dernier
>de chaque troupeau (pour raccourcir les boucles et donner une
>condition simple pour l'arr�t et certains tests)
>Point final.
>
>C'est comme pour la tour de Hanoi :
>On peut obtenir directement les mouvements avec une simple boucle,
>avec la parit� des num�ros des disques.
>
>Ici la strat�gie correcte est � la port�e d'un enfant.
>Il n'y a donc pas besoin de la faire *chercher* par le programme :
>
>On d�place les crapeaux tant qu'on peut.
>On d�place les grenouilles tant qu'on peut.
>on recommence jusqu'� ce soit fini.
Certes mais il ne s'agit que d'une heuristique.
Le probl�me initial demande de trouver la strat�gie qui donne le
nombre minimal de mouvements, non une solution acceptable.
Or dans ce genre de probl�mes j'ai appris � me m�fier de l'intuition.
On se dit ceci DOIT �tre la meilleure solution et en fait l'analyse
exhaustive d�montre le contraire.
Cf. le probl�me du d�coupage du gateau de JM, jusque n=13, la
strat�gie est triviale, mais la nature du probl�me change compl�tement
� partir de n=15.
Philippe 92
> Philippe 92 a ï¿œcrit
>>> zwim a ï¿œcrit
>>>> car...@server.invalid a ï¿œcrit
>>>>> entre eux. par exemple pour n=2 CC_GG
>>>>> chaque type pour "renverser" la situation initiale.
>>>
>>> Et j'utilise un immense tableau pour stocker le graphe des voisins
>>> ...
>>
>
>
> Pour un problï¿œme de taille n, le codage en base 3 reprï¿œsente au
> maximum 3^(2n+1) positions posssibles.
Bonsoir,
Euh... on sait qu'il y a exactement n '0', n '1' et un '2' sur
les 2n+1 'cases'
Donc il n'y a que (2n+1)*C(2n,n) positions thï¿œoriquement possibles
Par exemple n = 7 : 3^15 = 14348907, 15*C(14,7) = 51480
>
> Mon algo part d'une position donnￜe et ￜ l'ￜtape i+1 construit tous
> les voisins des positions de l'ï¿œtape i.
>
> J'ai donc allouￜ un tableau de taille 3^(2n+1) pour stocker cela, mais
> dans la pratique seule une petite fraction de cet espace est
> nï¿œcessaire ( ce qui reflï¿œte le fait que le problï¿œme initial n'est pas
> si compliquￜ ).
>
Certes. (le problￜme initial n'est pas si compliquￜ)
De plus, d'une position donnï¿œe on ne peut atteindre qu'un nombre trï¿œs
faible d'autres positions : avance d'un crapaud ou d'une grenouille,
saut d'un crapaud ou d'une grenouille, donc au pire 4 positions.
Enfin certains de ces mouvements conduisent ￜ un blocage ￜvident (dont
on ne peut sortir qu'en revenant en arriï¿œre), ou simplement n'existent
pas (ne peuvent ï¿œtre atteintes).
Le graphe des positions sera donc "trï¿œs creux"
Et enfin il n'est pas nï¿œcessaire de stocker *toutes* les positions
oￜ que ce soit pour en parcourir le graphe.
Il suffit de dï¿œfinir soigneusement les rï¿œgles de parcours de ce
graphe, et de stocker autant de positions que la profondeur de
parcours courant.
Comme on atteindra la solution en n(n + 2) mouvements au maximum,
cela fait ce nombre de positions ￜ mￜmoriser uniquement, et autant
d'index pour le backtrack du parcours.
> Je peux donc modifier l'algo pour remplacer le tableau par une file
> d'attente moins gourmande.
en quelque sorte !
Soit avec n = 7 : 63 positions et 63 index
On est trï¿œs loin des 51480 positions possibles, et encore plus des
14 millions "sans prï¿œcautions".
>> Ici la stratￜgie correcte est ￜ la portￜe d'un enfant.
>> Il n'y a donc pas besoin de la faire *chercher* par le programme :
>
> Certes mais il ne s'agit que d'une heuristique.
> Le problï¿œme initial demande de trouver la stratï¿œgie qui donne le
> nombre minimal de mouvements, non une solution acceptable.
Y a-t-il d'ailleurs une stratï¿œgie donnant la solution en d'avantage
de mouvements ?? La stratï¿œgie "acceptable" est en fait la seule !
(sans aller retour superflus, crapauds ou grenouilles allant ou
sautant ￜ reculons le mouvement qu'ils viennent d'effectuer !)
> Or dans ce genre de problￜmes j'ai appris ￜ me mￜfier de l'intuition.
> On se dit ceci DOIT ï¿œtre la meilleure solution et en fait l'analyse
> exhaustive dï¿œmontre le contraire.
>
> Cf. le problï¿œme du dï¿œcoupage du gateau de JM, jusque n=13, la
> stratï¿œgie est triviale, mais la nature du problï¿œme change
> complￜtement ￜ partir de n=15.
Tout ￜ fait d'accord la dessus.
Mais ici cela ne se produit pas car les positions de blocage limitent
trￜs fortement les possibilitￜs ￜ essayer, et la recherche peut se
faire "intuitivement ￜ la main".
zwim
Philippe 92 a �crit
>zwim a �crit :
>> Philippe 92 a �crit
>>> zwim a �crit :
>>>> zwim a �crit
>>>>> car...@server.invalid a �crit
>>>>>> entre eux. par exemple pour n=2 CC_GG
>>>>>> chaque type pour "renverser" la situation initiale.
>>>>
>>>> Et j'utilise un immense tableau pour stocker le graphe des voisins
>>>> ...
>>>
>>
>> C'est vrai �a, pourquoi autant.
>>
>> maximum 3^(2n+1) positions posssibles.
>
>Bonsoir,
>
>Euh... on sait qu'il y a exactement n '0', n '1' et un '2' sur
>les 2n+1 'cases'
>Par exemple n = 7 : 3^15 = 14348907, 15*C(14,7) = 51480
Je suis d'accord mais le probl�me est la repr�sentation des donn�es.
3^15 se repr�sente facilement par un entier long.
En revanche passer d'une position th�orique � un entier entre 0 et
51480 est plus d�licat.
Au plus simple on peut faire un nombre cod� sur 2^14 et un autre
entier entre 1 et 15 pour dire o� se trouve la s�paration.
Soit 15 * 2^14 = 245760, ce qui fait d�j� bien plus que 51480...
>Le graphe des positions sera donc "tr�s creux"
Pas tant que �a en fait.
L'execution du programme passe en revue 51450 positions avant
d'aboutir � l'inversion.
Il n'y a donc que 30 positions inexplor�es, le graphe est plut�t plein
>Y a-t-il d'ailleurs une strat�gie donnant la solution en d'avantage
>de mouvements ?? La strat�gie "acceptable" est en fait la seule !
>(sans aller retour superflus, crapauds ou grenouilles allant ou
>sautant � reculons le mouvement qu'ils viennent d'effectuer !)
Oui, cf mon premier post, ou en essayant de la faire � la main pour
n=3 je me suis tromp� et ai donn� une solution sous-optimale.
Philippe 92
> Philippe 92 a ï¿œcrit
>> zwim a ï¿œcrit :
>>> Philippe 92 a ï¿œcrit
>>>> zwim a ï¿œcrit :
>>>>> zwim a ï¿œcrit
>>>>>> car...@server.invalid a ï¿œcrit
>>>>>>> entre eux. par exemple pour n=2 CC_GG
>>>>>>> chaque type pour "renverser" la situation initiale.
>>>>>
>>>>> Et j'utilise un immense tableau pour stocker le graphe des voisins
>>>>> ...
>>>>
>>>> Pourquoi tant de mï¿œmoire ???
>>
>> les 2n+1 'cases'
>> Par exemple n = 7 : 3^15 = 14348907, 15*C(14,7) = 51480
>
> 3^15 se reprï¿œsente facilement par un entier long.
>
> En revanche passer d'une position thￜorique ￜ un entier entre 0 et
> 51480 est plus dï¿œlicat.
Bonjour,
Il n'y a pas que des variables entiï¿œres, une variable peut ï¿œtre
un tableau, une liste, une chaï¿œne de caractï¿œres etc...
Un ï¿œtat se reprï¿œsente alors de faï¿œon triviale par une chaï¿œne de
15 caractï¿œres facilement manipulable.
On gagne ainsi en nombre de valeurs ce que l'on perd en taille
d'une valeur individuelle.
(et en plus on imprime directement la chaï¿œne en clair ;-)
De toute faï¿œon, la mï¿œmorisation de *toutes* les valeurs est inutile
comme dￜja signalￜ. (utilisation d'une pile par exemple)
>
>> Le graphe des positions sera donc "trï¿œs creux"
>
> Pas tant que ï¿œa en fait.
> L'execution du programme passe en revue 51450 positions avant
> d'aboutir ￜ l'inversion.
> Il n'y a donc que 30 positions inexplorï¿œes, le graphe est plutï¿œt plein
Je parlais du graphe, non pas de la liste des sommets.
>> Y a-t-il d'ailleurs une stratï¿œgie donnant la solution en d'avantage
>> de mouvements ?? La stratï¿œgie "acceptable" est en fait la seule !
>> (sans aller retour superflus, crapauds ou grenouilles allant ou
>> sautant ￜ reculons le mouvement qu'ils viennent d'effectuer !)
>
> Oui, cf mon premier post, ou en essayant de la faire ￜ la main pour
> n=3 je me suis trompￜ et ai donnￜ une solution sous-optimale.
Ton "1er post" ayant disparu (supersede = effacement du serveur)
il a fallu aller le chercher sur Google, qui garde tout.
Effectivement, mais avec des reculs obligatoires.
Le nombre minimum total des cases ￜ franchir est 2n(n + 1) :
Globalement, chacun des 2n animaux doit avancer, entre ses pas
et ses sauts, de n + 1 cases en tout.
Chaque grenouille doit "franchir" chaque crapaud, et sans qu'on
puisse pour l'instant prï¿œciser lequel des deux saute, cela fait au
moins S >= n^2 sauts en tout.
Si P est le nombre total de pas effectuￜ par l'ensemble des animaux,
le nombre de mouvements est S + P, et le nombre de cases franchies
est 2S + P >= 2n(n + 1)
Il y aura ï¿œgalitï¿œs si il n'y a aucun recul des animaux et si
les seuls sauts sont par dessus un animal de race opposï¿œe.
on a alors S + P = 2n(n + 1) - n^2 = n(n + 2) Et S = 2n.
Un tel dï¿œplacement est rï¿œalisable par l'algorithme que j'ai
proposￜ.
Il est ainsi forcï¿œment le meilleur sans recul des animaux
et sans sauts "homologues".
Reste ￜ prouver que cette stratￜgie est optimale.
C'est ￜ dire que l'on ne peut pas trouver mieux avec des
mouvements ￜ reculons ou des grenouilles sautant par dessus des
grenouilles.
un S + P infￜrieur ￜ la valeur n(n + 2) implique
- un S infï¿œrieur, c'est impossible S est au moins n^2.
- ou un P infï¿œrieur, c'est imposible avec le mï¿œme S
- Il reste donc comme seule posibilitￜ d'augmenter S et de diminuer
P d'avantage.
Augmenter S impose des sauts ￜ reculons (S augmente de 2a)
ou des sauts "homologues" grenouille sur grenouille, ou crapaud
sur crapaud.
Il semble douteux que cela amï¿œne une amï¿œlioration !
L'algorithme de recherche exaustive par parcours du graphe
(implicite hein, pas totalement stockￜ en mￜmoire ;-) ne peut,
en l'absence de preuve formelle, que prouver cela pour un nombre
fini de valeurs de n. Il restera toujours un doute.
Pour en dï¿œduire une preuve absolue, on pourrait prouver formellement
que le problï¿œme avec n bestioles peut se dï¿œduire du problï¿œme avec
n-1 ou n-k ou tous les i < n, au moins pour n > seuil.
Le parcours des graphes avec n < seuil dￜmontre alors la propriￜtￜ.
Mais je n'ai pas d'idï¿œe pour une telle preuve formelle.