Discussion :

[ch_hanen]

salut,
svp qq peut m'aider à trouver une solution pour cet exercice je suis bloquée :

Pour battre les trente deux cartes d’un jeu de belote, on divise le paquet en deux parties égales et on fait entrelacer les cartes de la première moitié entre celles de la deuxième moitié. La première carte de la première moitié sera placée en dessous de la première carte de la seconde moitié et ainsi de suite. Pour bien battre ces cartes, on répète cette opération un nombre fini de coups. Non suppose que les cartes sont numérotées de 1 à 32 (ou pour un cas général de 1 à 2n). Ces entiers sont mis dans cet ordre dans un tableau T.
1) Donner l’état final de T composé de 8 éléments après 4 coups
2) Ecrire un algorithme du module permettant de battre ces 2n cartes en K coups. Ces cartes sont supposées les 2n premières entiers non nuls disposés dans un tableau T.
3) Ecrire un programme qui remplit un tableau T de 2n éléments par les 2n premier entiers non nuls, les fait battre comme précédent décrit, en coups (K entier positif donné ≥) puis affiche de l’état final de T.

[ol9245]

salut,
svp qq peut m'aider à trouver une solution pour cet exercice je suis bloquée :

Pour battre les trente deux cartes d’un jeu de belote, on divise le paquet en deux parties égales et on fait entrelacer les cartes de la première moitié entre celles de la deuxième moitié. La première carte de la première moitié sera placée en dessous de la première carte de la seconde moitié et ainsi de suite. Pour bien battre ces cartes, on répète cette opération un nombre fini de coups. Non suppose que les cartes sont numérotées de 1 à 32 (ou pour un cas général de 1 à 2n). Ces entiers sont mis dans cet ordre dans un tableau T.
1) Donner l’état final de T composé de 8 éléments après 4 coups
2) Ecrire un algorithme du module permettant de battre ces 2n cartes en K coups. Ces cartes sont supposées les 2n premières entiers non nuls disposés dans un tableau T.
3) Ecrire un programme qui remplit un tableau T de 2n éléments par les 2n premier entiers non nuls, les fait battre comme précédent décrit, en coups (K entier positif donné ≥) puis affiche de l’état final de T.

je comprend que ca te fasse cxxxr cet exo, et que t'as envie qu'on le fasse pour toi. alors un petit conseil qui n'a l'air de rien : dans ce cas là, précise le langage que tu préfère comme ça si tu tombes sur un mec de bonne humeur et qui s'ennuie, eh ben, tu touches le gros lot direct : ton exo est fait gratos.

Bon, je plaisante évidemment.

qu'est-ce que tu as essayé et qui marche pas ?
tu as fait la routine qui fait un seul mélange ?
elle doit te retourner 1 (16+1) 2 (16+2) ... i (16+i) .... 16 32

[ch_hanen]

je comprend que ca te fasse cxxxr cet exo, et que t'as envie qu'on le fasse pour toi. alors un petit conseil qui n'a l'air de rien : dans ce cas là, précise le langage que tu préfère comme ça si tu tombes sur un mec de bonne humeur et qui s'ennuie, eh ben, tu touches le gros lot direct : ton exo est fait gratos.

Bon, je plaisante évidemment.

qu'est-ce que tu as essayé et qui marche pas ?
tu as fait la routine qui fait un seul mélange ?
elle doit te retourner 1 (16+1) 2 (16+2) ... i (16+i) .... 16 32

pour n'importe quel exercice on cherche la solution en algo puis en le traduit au langage voulu,l'essentiel ce qui me concerne j'ai pas compris le principe de l'entrelacement.

[pseudocode]

j'ai pas compris le principe de l'entrelacement.

La première carte de la première moitié sera placée en dessous de la première carte de la seconde moitié et ainsi de suite.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
         -------- (16+1=17)
(1)  --------
         -------- (16+2=18)
(2)  --------
         -------- (16+3=19)
(3)  --------
     .........
     .........
         -------- (16+15=31)
(15) --------
         -------- (16+16=32)
(16) --------

[Zavonen]

Que dire après cette splendide illustration (en couleurs).
Pseudocode, tu as une image pour illustrer toute situation ?
Je sui desoeuvré il il ne fait pas beau, alors je vais apporter une petite contribution en proposant une routine d'entrelacement, et une autre de battage en C, par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>
 
int jeu1[32] ; // avant entrelacement
int jeu2[32] ; // après entrelacement
 
// initialiser jeu1
void init()
{
    int i;
    for (i=0;i<32;i++)
        jeu1[i]=i;
}
 
 
void entrelacer ()
{
    int i,j;
    // le travail d'entrelacement proprement dit
    for (i=0;i<32;i++)
    {
        if (!(i%2))
            jeu2[i]=jeu1[i/2];
        else
            jeu2[i]=jeu1[15+i/2];
    }
    // recopier jeu2 sur jeu1
    for (i=0;i<32;i++)
        jeu1[i]=jeu2[i];
}
 
// battre en entrelaçant n fois
void battre ( int n)
{
    int i;
    for (i=1;i<=n;i++)
        entrelacer();
}
 
// pour visualiser
void voirjeu()
{
    int i;
    for (i=0;i<32;i++)
        printf("%d-",jeu1[i]);
    printf("\n");
}
 
// Programme principal
int main()
{
    init();
    battre(10);
    voirjeu();
    return 0;
}

[pseudocode]

Pseudocode, tu as une image pour illustrer toute situation ?

et oui, toujours !

[henderson]

Salut !

On y gagne probablement en travaillant avec un seul tableau et en utilisant la pile.

On donne :

N nombre (pair) de cartes
T un tableau de dimension N
K nombre de coups
h = N/2 pour séparer les deux tas

On utilise une boucle pour empiler le coup sur la pile

pour n de 0 à h-1
push T[h + n]
push T[n]

On utilise une boucle pour dépiler le coup dans le tableau

pour n de N-1 à 0
pop T[n]

Reste à mettre en pratique le push et le pop (en assembleur ça devrait se développer en un peu plus d'une dizaine de lignes)
Je peux montrer un exemple dans le contexte BCB (en fait, C et une part d'asm)

Il y a sans doute quelque chose à trouver ici, au niveau maths.
En effet, quelque soit le nombre de cartes, on constate un cycle (qui dépend de N) pour lequel le tri redonne l'état initial au bout de P coups.

A plus !

[Zavonen]

Reste à mettre en pratique le push et le pop (en assembleur ça devrait se développer en un peu plus d'une dizaine de lignes)
Je peux montrer un exemple dans le contexte BCB (en fait, C et une part d'asm)

Oui c'est sympa comme ça aussi, voilà le truc en C (a minima, aucun contrôle sur push et pop). Seul truc, il faut dépiler à l'envers pour retrouver le jeu entrelacé dans le bon sens, ce serait donc mieux d'utiliser une file.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <stdlib.h>
typedef struct
{ int  stack[33];
  int index;
} Pile;
 
Pile P;
int jeu1[32] ; // avant entrelacement
 
 
void push (int n, Pile * pS)
{pS->stack[pS->index++]=n;}
 
int pop (Pile *pS)
{ return pS->stack[--(pS->index)];}
 
// initialiser jeu1 et la pile
void init()
{
    int i;
    for (i=0;i<32;i++)
        jeu1[i]=i;
     P.index=0;
}
 
// empiler les deux demi-paquets
void empile_tout ()
{int i;
 for (i=0;i<16;i++)
 {push(jeu1[i],&P);
  push(jeu1[i+16],&P);
 }
}
 
void depile_tout ()
{int i;
 for(i=0;i<32;i++)
  jeu1[31-i]=pop(&P);
}
 
void entrelacer ()
{ empile_tout();
  depile_tout();
}
 
// pour visualiser
void voirjeu()
{
    int i;
    for (i=0;i<32;i++)
        printf("%d-",jeu1[i]);
    printf("\n");
}
 
// Programme principal
int main()
{
    int i;
    init();
    voirjeu();
    for(i=0;i<30;i++) entrelacer();
    voirjeu();
    return 0;
}

Cela dit, il n'y a pas d'économie de mémoire dans la mesure où la pile joue le rôle d'un second tableau.

Il y a sans doute quelque chose à trouver ici, au niveau maths.
En effet, quelque soit le nombre de cartes, on constate un cycle (qui dépend de N) pour lequel le tri redonne l'état initial au bout de P coups.

Quelle que soit la manipe, le nombre d'états possibles étant fini fact(32) on aura de toutes façons un cycle.
Pour avoir ici la périodicité il faut décomposer la permutation d'entrelacage en cycle, et prendre le ppcm des ordres des cycles.
Or il s'avère que :
0-16-1-17-2-18-3-19-4-20-5-21-6-22-7-23-8-24-9-25-10-26-11-27-12-28-13-29-14-30-
15-31
EST un cycle d'ordre 30 je l'ai vérifié avec un programme de mon cru
Donc elle est d'ordre 30. (Non! erreur voir plus loin)
Conclusion: Ce mode de battage ne permet que 30 donnes différentes.
Exécutez le pgm donné en exemple pour le voir.
En résumé: rien ne vaut une permutation aléatoire pour battre des cartes. Cependant on peut améliorer le système en 'coupant' auparavant, le nombre des possibilités est alors multiplié par 51 selon la position de la coupe (en admettant la coupe vide), ce qui reste encore très modeste comparé à fact(32).
Pour finir on peut écrire une version qui n'utilise ni tableau de recopie, ni pile, mais qui fait un entrelaçage en place. (pas très dur mais ch…)

[ol9245]

la 32 reste en 32 indéfiniment
la 31 monte d'un cran à caque tour
au pout de 15 tours, elle vient en 16
et la carte 16 vient se mettre derrière la 32.
donc en 15+1=16 tours, les deux dernières cartes reviennent à la même place.

ça m'étonnerais pas que le jeu entier ne soit reconstitué à ce moment là.

[Zavonen]

Je viens de vérifier après le message de ol9245:
J'ai fait une erreur toute bête dans mon programme d'affichage de la décomposition en cycles:
La bonne décomposition est 4 cycles d'ordre 5, qui sont les suivants:
[0, 16, 1, 3, 2, 5, 6, 7, 4, 9, 10, 11, 12, 13, 14, 15, 8, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
[0, 1, 2, 17, 4, 5, 3, 7, 8, 9, 10, 11, 6, 13, 14, 15, 16, 24, 18, 19, 20, 21, 22, 23, 12, 25, 26, 27, 28, 29, 30, 31]
[0, 1, 2, 3, 4, 18, 6, 7, 8, 20, 5, 11, 12, 13, 14, 15, 16, 17, 9, 19, 10, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
[0, 1, 2, 3, 4, 5, 6, 19, 8, 9, 10, 11, 12, 13, 7, 15, 16, 17, 18, 25, 20, 21, 22, 23, 24, 28, 26, 27, 14, 29, 30, 31]
La permutation est donc d'ordre 5 (vérifié par le programme suivant);

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
// Programme principal
int main()
{   int i,j;
    init();
    voirjeu();
    for(j=1;j<=5;j++)
    {for(i=0;i<j;i++) entrelacer();
    voirjeu();}
    return 0;
}

[henderson]

Salut !

Si on reprend l'ennoncé avec 8 cartes, on constate qu'il existe un cycle tel, qu'au bout de 6 coups, le système retrouve son état initial.
On en tire au moins une chose, c'est que pour 8 cartes, effectuer 7 coups revient à ne faire qu'un coup.
Malheureusement ce cycle dépend du nombre de cartes mis en lice nombre qui pourrait bien s'avérer "quelconque" lors d'une démonstration de l'algo.
La question aurait été de savoir si on peut déduire ce cycle à partir du nombre de cartes (une formule).
C'est pour une éventuelle optimisation de l'algo (c'est peut-être hors sujet ici, selon le contexte).

A moins d'erreurs, donc à vérifier, voici les cycles (nombre de coups pour retrouver l'état initial) de 2 à 34 cartes :
2,4,3,6,10,12,4,8,18,6,11,20,18,28,5,10,12 ... et pour 78 cartes, le cycle est 39

Le cycle pour 8 cartes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
1  - 5 1 6 2 7 3 8 4 
2  - 7 5 3 1 8 6 4 2 
3  - 8 7 6 5 4 3 2 1 
4  - 4 8 3 7 2 6 1 5 
5  - 2 4 6 8 1 3 5 7 
6  - 1 2 3 4 5 6 7 8 << état 0 
7  - 5 1 6 2 7 3 8 4 << état 1

Le cycle pour 32 cartes

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
1  - 17 1 18 2 19 3 20 ...
2  - 25 17 9 1 26 18 10 ...
3  - 29 25 21 17 13 9 5 ...
4  - 31 29 27 25 23 21 19 ...
5  - 32 31 30 29 28 27 26 ...
6  - 16 32 15 31 14 30 13 ...
7  - 8 16 24 32 7 15 23 ...
8  - 4 8 12 16 20 24 28 ...
9  - 2 4 6 8 10 12 14 ...
10 - 1 2 3 4 5 6 7 8 9 ... << état 0
11 - 17 1 18 2 19 3 20 ... << état 1

En attendant le soleil...

A plus !

[Zavonen]

Je ne trouve pas comme vous:
Pour 8 cartes je trouve que la permutation:
[0, 4, 1, 5, 2, 6, 3, 7]
est décomposable en les deux cycles d'ordre 3
[0, 4, 1, 3, 2, 5, 6, 7]
3
[0, 1, 2, 5, 4, 6, 3, 7]
3 Donc la périodicité est 3;
vérification:
0-4-1-5-2-6-3-7-
0-2-4-6-1-3-5-7-
0-1-2-3-4-5-6-7-

Pour 16 cartes:
[0, 8, 1, 3, 2, 5, 6, 7, 4, 9, 10, 11, 12, 13, 14, 15]
4
[0, 1, 2, 9, 4, 5, 3, 7, 8, 12, 10, 11, 6, 13, 14, 15]
4
[0, 1, 2, 3, 4, 10, 6, 7, 8, 9, 5, 11, 12, 13, 14, 15]
2
[0, 1, 2, 3, 4, 5, 6, 11, 8, 9, 10, 13, 12, 14, 7, 15]
4
3 cycles d'ordre 4 et un cycle d'ordre 2
donc périodicité 4
Vérification
0-8-1-9-2-10-3-11-4-12-5-13-6-14-7-15-
0-4-8-12-1-5-9-13-2-6-10-14-3-7-11-15-
0-2-4-6-8-10-12-14-1-3-5-7-9-11-13-15-
0-1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-

Compte tenu du résultat précédent on s'oriente vers une formule:
pour 2^n cartes – cycle d'ordre n
que je ne sais pas encore démontrer.
Pour les nombres pairs qcq on va voir .

Le soleil arrive ...

[pseudocode]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
Jeu complet, avant coupe
------------------------
 
31 ----
30 ----
29 ----
  ...
01 ----
00 ----
 
Soit une carte C a la position PosInit (entre 0...31)
 
 
Coupe
-----
Pile A     Pile B
 
15 ----    ---- 15 (ex 31)
14 ----    ---- 14 (ex 30)
13 ----    ---- 13 (ex 29)
  ...      ...
01 ----    ---- 01 (ex 17)
00 ----    ---- 00 (ex 16)
 
Position de la carte C:
 
si PosInit<16  alors position: PosPile = PosInit
si PosInit>=16 alors position: PosPile = PosInit-16
 
 
Apres Melange
-------------
 
31 ---- PileB.15
30 ---- PileA.15
29 ---- PileB.14
  ...
01 ---- PileB.0
00 ---- PileA.0
 
Position de la carte C:
 
si PosInit<16  alors position: PosFinal = 2*PosPile = 2*PosInit
si PosInit>=16 alors position: PosFinal = 1+2*PosPile = 1+2*(PosInit-16) = 2*PosInit + 1 - 32

Avec un nombre de carte N (divisible par 2)

Soit C une carte en position PosInit, après un melange la carte C sera en position PosFinal definie par:

si PosInit<N/2 alors PosFinal = 2*PosInit

si PosInit>=N/2 alors PosFinal = 2*PosInit +1 - N

Pour les matheux:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
N = Cste divisible par 2
 
{ U0 = cste (entre 0 et N-1)
{
{ Un<N/2,  Un+1 = 2*Un
{ Un>=N/2, Un+1 = 2*Un + 1 - N

[diogene]

- En numérotant la position des cartes par 0, 1 ,...N-1,
- En supposant que le nombre N de cartes est une puissance de 2 = 2^n,
- En supposant que le mélange est fait en sorte que le résultat du mélange commence par 0,(sur un exemple de 16 cartes :0 8 1 9 2 10 3 11 - 4 12 5 13 6 14 7 15)

On écrit en binaire la position de la carte : bn-1 ... b1, b0. Après un mélange, la carte en position bn-1 ... b1, b0 était avant ce mélange en b0 bn-1 ... b1.
Après p mélanges, la carte en position bn-1 ... b1, était initialement en position bp-1, bp-2,...bo,bn-1,...bp
Il s'agit donc d'effectuer une rotation de p bits de la position actuelle pour obtenir la position d'origine de la carte
Après n mélanges , on retombe sur la disposition d'origine.

Sur un exemple de 16 cartes :
0 1 2 3 4 5 6 7 - 8 9 10 11 12 13 14 15
après un premier mélange :
0 8 1 9 2 10 3 11 - 4 12 5 13 6 14 7 15
après un second mélange
0 4 8 12 1 5 9 13 - 2 6 10 14 3 7 11 15
après un troisième mélange
0 2 4 6 8 10 12 14 - 1 3 5 7 9 11 13 15
Par exemple,en position 12=1100,
après un mélange on a la carte initialement en position 0110 = 6
après deux mélanges on a la carte initialement en position 0011 = 3
après trois mélanges on a la carte initialement en position 1001 = 9
après quatre mélanges on a la carte initialement en position 1100 = 12

- En supposant que le mélange soit en ordre inverse (sur un exemple de 16 cartes : 8 0 9 1 10 2 11 3 - 12 4 13 5 14 6 15 7). Après un mélange, la carte en position bn-1 ... b1, b0 était avant ce mélange en /b0 bn-1 ... b1. (/b0 étant le complément de b0)
Après p mélanges, la carte en position bn-1 ... b1, était initialement en position /bp-1, /bp-2,.../bo,bn-1,...bp
Après 2n mélanges, on retrouve la position d'origine.

- Si N n'est pas une puissance de deux, mais simplement pair, je ne sais pas. Bien sur, il y a un cycle, mais de combien ? On n'est même pas sur que la configuration de départ appartienne au cycle.

[Zavonen]

Soit C une carte en position PosInit, après un melange la carte C sera en position PosFinal definie par:

si PosInit<N/2 alors PosFinal = 2*PosInit

si PosInit>=N/2 alors PosFinal = 2*PosInit +1 - N

la transfo est donc x->2x mod(N-1)
donc après k itérations x->(2^k)x mod(N-1)
Donc l'ordre du cycle correspond au plus petit entier k tel que 2^k=1 mod[N-1]
Examinons d'abord le cas où N-1 est premier dans ce cas on sait que
on a toujours x^(N-2) = 1 mod[N-1], le k cherché est donc forcément un diviseur de N-2 .
Cela donne un début de démonstration du résultat que j'ai énoncé pour N=8, 16 et 32 dans un précédent post:
pour N=8, les candidats possibles sont les diviseurs de 6 c' est à dire 2 3 et 6
2 étant éliminé il ne reste que 3 et 6 de fait c'est 3
pour N=32, les candidats possibles sont les diviseurs de 30: 2 3 5 6 10 15 30
Il se trouve que c'est 5
pour N=16 on ne peut utiliser cela car 15 n'est pas premier de fait c'est 4

[Zavonen]

Diogene nous écrit :

Après p mélanges, la carte en position bn-1 ... b1, était initialement en position bp-1, bp-2,...bo,bn-1,...bp
Il s'agit donc d'effectuer une rotation de p bits de la position actuelle pour obtenir la position d'origine de la carte
Après n mélanges , on retombe sur la disposition d'origine.

Il me semble qu'il a parfaitement raison et que cela correspond exactement à ma précédente remarque basée sur le post de Pseudocode:

la transfo est donc x->2x mod(N-1)

puisque la multiplication par deux décale tous les bits d'un cran vers la gauche et que le modulo récupère en queue le bit de poids fort quand il y a débordement
Par contre sa remarque a valeur de démonstration, puisqu'il s'agit que tout le monde retombe en place par rotation.
J'admet donc le résultat pour acquis dans le cas des puissances de deux.
Je vais faire un tableau pour les n pairs et voir si on peut intuiter qqch.

[Zavonen]

Voici le tableau annonçé qui confirme les premiers résultats pour les puissances de 2 et les nombres de la forme p+1 avec p premier.
La seule chose qu'on peut voir c'est que la périodicité reste inférieure à N, c'est presqu'une évidence car si le plus petit entier k tel que
2^k=1 était plus grand que N cela voudrait dire qu'on a plus de N éléments dans l'anneau Z/(N-1)Z.
Cela dit on remarque que dans le cas où N-1 est premier la périodicité est bien un diviseur de N-2, mais que ce peut être n'importe lequel, la loi n'est donc pas simple.

[diogene]

La longueur du cycle est p tel que 2^P-1 est divisible par N-1
Exemples :
N = 18
255 = 17*15 ; 2^8 = 256 ;longueur du cycle 8
N = 24
2047 = 23*89 ;2^11 = 2048 ;longueur du cycle 11
N = 26
1048575 = 25*41943 ; 2^20 = 1048576 longueur du cycle 20
N = 32
31 = 31*1 ; 2^5 = 32 ; longueur du cycle 5

Demonstration pour plus tard

[EDIT]
Si la carte est initialement en position k0, elle se trouve en position k après q brassages tel que k = (2^q k0)mod(N-1)
[\EDIT]

[pseudocode]

Et les vaillants forumeurs dérivèrent du P.O. pendant des jours et des jours...

[henderson]

Salut !

@Zavonen : je crois qu'on ne permute pas de la même manière :

[0, 4, 1, 5, 2, 6, 3, 7]

J'obtiens :

[4, 0, 5, 1, 6, 2, 7, 3]

0 passe sous 4 et donc n'est jamais première (sauf sur le retour à l'état initial du cycle)

A moins que l'ordre que j'utilise ne soit pas le bon (pourtant il me semble correspondre à l'énoncé... comme l'a montré pseudocode)!

A plus !