Bonjour,
le probleme est peu-etre déja connu de vous. On en trouve des énoncés simplifiés sur le net(concours de logiques). D'une manière générale c'est le suivant:
Pour n entier positif fixé et z=1+2+3+...+n=(n*(n+1))/2;
Comment placer les entiers de 1 à z dans une pyramide à n lignes tq un tel schemat:
Voici quelques exemples pour bien se fixer les idées(pour n=2,3,4,5):
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3 a b c impose c=|a-b|;
Ils sont trouvables à la main (si n grandi ça devient de plus en plus difficile)
Pour n=2:
Pour n=3:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 3 1 2 3 2 1
Pour n=4:
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 4 6 1 2 5 3 5 6 2 1 4 3 6 1 4 5 3 2 6 2 5 4 3 1
Pour n=5:
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 8 1 10 6 7 9 4 2 5 3 8 10 1 6 2 9 5 7 4 3 9 3 10 8 6 7 2 1 5 4 9 10 3 8 1 7 5 6 2 4
En fait ce sont tous les cas possibles à la symétrie axiale près, pour n=2,3,4,5, d'après un programme en C de ma fabrication (Dont je suis d'autant plus fier qu'il m'a fallut environ une semaine pour l'optimiser et qu'il mette moins de 1 heure pour n=9...)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 13 3 15 14 6 10 12 1 8 2 11 7 9 4 5
Pour n>5 je n'en trouve plus (je n'ai pas essayé pour n>10(trop long)).
Les questions que je me pose(et à vous par la même occasion) sont:
Y a-t-il d'autres pyramide pour n>5?
Les contraintes sur une telle pyramide sont-elles si complexes qu'il est impossible de répondre à cette question?
voici mon program en c que j'aimerai bien améliorer:
Code C : 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153 #include <stdlib.h> #include <stdio.h> int M[31][31],n,z,t,C[31],y; int i,j,l; FILE *a; int evol(int r) { for(i=1;i<r;i++) for(j=i;j<r;j++) if(M[1][r]==M[i][j]) return 0; for(l=2;l<=r;l++) { M[l][r]=abs(M[l-1][r-1]-M[l-1][r]); if(M[l][r]>y) { for(i=1;i<l-1;i++) if(M[i][r]==M[l][r]) return 0; for(i=1;i<r-1;i++) for(j=i;j<r;j++) if(M[l][r]==M[i][j]) return 0; } else { for(i=l-1;i>0;i--) if(M[i][r]==M[l][r]) return 0; for(i=r-1;i>0;i--) for(j=i;j<r;j++) if(M[l][r]==M[i][j]) return 0; } } return 1; } int ecrirepyramide(void) { for(i=1;i<=n;i++) { fprintf(a,"\n"); for(l=1;l<=i;l++) fprintf(a," "); for(j=i;j<=n;j++) fprintf(a,"%3d ",M[i][j]); } fprintf(a,"\n"); return 0; } int main(void) { int u,v,s,k; a=fopen("pyramide.txt","w"); do { printf("\n"); printf("taper n (n=0,1ou2 pour arreter):"); scanf("%d",&n); if((n>2)&&(n<31)) { z=(n*(n+1))/2; y=(z/2); printf("Compter jusqu a %d:\n1",z); fprintf(a,"\n\n\nPour n=%d:",n); for(u=2;u<=z;u++) { for(v=1;v<=z;v++) { M[1][1]=u; M[1][2]=v; M[2][2]=abs(u-v); if((u==v)||(M[2][2]==M[1][1])||(M[2][2]==M[1][2])); else { s=3; C[3]=1; while(C[s]<=z) { M[1][s]=C[s]; if(evol(s)==1) { s++; if(s>n) { if(M[1][n]>M[1][1]) ecrirepyramide() ; s--; if(C[s]==z) { j=0; for(i=s-1;(j==0)&&(i>2);i--) if(M[1][i]!=z) j=i; if(j>0) { s=j; C[s]++; } else C[s]++; } else C[s]++; } else C[s]=1; } else { if((s==3)&&(C[s]==z)) C[s]++; if(C[s]<z) C[s]++; else if(C[s]==z) { j=0; for(i=s-1;(j==0)&&(i>2);i--) if(M[1][i]!=z) j=i; if(j>0) { s=j; C[s]++; } else C[s]++; } } } } } printf(" %d",u); } } } while((n>2)&&(n<31)); fclose(a); return 0; }
Partager