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.

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

Le Sat, 07 Nov 2009 11:26:24 +0100
[email]caribou@server.inva[/email]lid 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.
>
>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
>

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.
[url]http://www.research.att.com/~njas/sequences/?q=1%2C4%2C9%2C20[/url]

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...

Le Sat, 07 Nov 2009 18:34:48 +0100
zwim a écrit
>Le Sat, 07 Nov 2009 11:26:24 +0100
>caribou@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 :
[url]http://cjoint.com/?lhvgVUhJRu[/url]

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
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
[url]http://www.research.att.com/~njas/sequences/A005563[/url]

f(n) = n(n+2)

Reste plus qu'à le démontrer pour les courageux, ce que je ne suis pas
ce soir...


--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

>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).

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

zwim a écrit :
> zwim a écrit
>> [email]caribou@server.inva[/email]lid a écrit
>>> On a n crapauds et n grenouilles sur une ligne avec un espace entre
>>> eux. par exemple pour n=2 CC_GG
>>>
>>> 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 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

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]
> [url]http://www.research.att.com/~njas/sequences/A005563[/url]
>
> 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 : [url]http://mathafou.free.fr/[/url] (divertissements mathématiques)

Le Sun, 08 Nov 2009 20:04:54 +0100
Philippe 92 a écrit
>zwim a écrit :
>> zwim a écrit
>>> [email]caribou@server.inva[/email]lid a écrit
>>>> On a n crapauds et n grenouilles sur une ligne avec un espace entre
>>>> eux. par exemple pour n=2 CC_GG
>>>>
>>>> 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 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
>
>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.



--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

zwim a écrit :
> Philippe 92 a écrit
>> zwim a écrit :
>>> zwim a écrit
>>>> [email]caribou@server.inva[/email]lid a écrit
>>>>> On a n crapauds et n grenouilles sur une ligne avec un espace
>>>>> entre eux. par exemple pour n=2 CC_GG
>>>>> 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 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
>>
>> 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.

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".

Amicalement.

--
Philippe C., mail : chephip avec free.fr comme domaine
site : [url]http://mathafou.free.fr/[/url] (divertissements mathématiques)

Le Tue, 10 Nov 2009 01:39:06 +0100
Philippe 92 a écrit
>zwim a écrit :
>> Philippe 92 a écrit
>>> zwim a écrit :
>>>> zwim a écrit
>>>>> [email]caribou@server.inva[/email]lid a écrit
>>>>>> On a n crapauds et n grenouilles sur une ligne avec un espace
>>>>>> entre eux. par exemple pour n=2 CC_GG
>>>>>> 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 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
>>>
>>> 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.
>
>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

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.

--
zwim.
Rien n'est impossible que la mesure de la volonté humaine...

zwim a écrit :
> Philippe 92 a écrit
>> zwim a écrit :
>>> Philippe 92 a écrit
>>>> zwim a écrit :
>>>>> zwim a écrit
>>>>>> [email]caribou@server.inva[/email]lid a écrit
>>>>>>> On a n crapauds et n grenouilles sur une ligne avec un espace
>>>>>>> entre eux. par exemple pour n=2 CC_GG
>>>>>>> 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 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
>>>>
>>>> Pourquoi tant de mémoire ???
>>
>> 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
>
> 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.

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.

Amicalement.

--
Philippe C., mail : chephip avec free.fr comme domaine
site : [url]http://mathafou.free.fr/[/url] (divertissements mathématiques)