Modérateur : Politburo
), du moins pour moi, jamais fait ça.
Code : Tout sélectionner
« { }
0 7 FOR A
0 9 FOR B
0 15 FOR C
{ 2 3 5}
A B C 3 ->LIST ^
EVAL * * +
NEXT
NEXT
NEXT
SORT
»
Code : Tout sélectionner
«
11 5 LN 3 LN 2 LN -> N X Y Z
« { }
0 N X / FOR A
0 N Y / FOR B
0 N Z / FOR C
A X * B Y * C Z * + +
IF DUP N <
THEN EXP +
ELSE DROP
END
NEXT
NEXT
NEXT
0 RND SORT
»
»
Je ne vois pas pourquoi il y aurait des trous !Une manière d'optimiser cela est de choisir les limites des 3 boucles de manière cohérente, ce qui est le cas dans l'exemple de charognard (12, 8 et 5) :
2^12->4096
3^8->6561
5^5->3125
On a des valeur max comparables mais on voit déjà qu'il y aura des trous dans la liste quand on va dépasser le nombre 3125.
Tu as raison, ton programme se limite aux nombres inférieurs ou égaux à 6912 et avec cela tu obtiens bien une liste de 159 nombres qui sont bien les 159 premiers nombres de Hamming.charognard a écrit :Je ne vois pas pourquoi il y aurait des trous !Une manière d'optimiser cela est de choisir les limites des 3 boucles de manière cohérente, ce qui est le cas dans l'exemple de charognard (12, 8 et 5) :
2^12->4096
3^8->6561
5^5->3125
On a des valeur max comparables mais on voit déjà qu'il y aura des trous dans la liste quand on va dépasser le nombre 3125.
3125*2 = 6250
4096*2 = 8192
Si tu as un exemple concret ?
Car pour moi ma couverture (12,8,5) suffit largement pour du 144*48=6912
Je ne crois pas que ce soit possible autrement qu'en testant les nombres un à un de manière croissante.caloubugs a écrit :Ce qui est dommage, c'est de passer par la construction d'une liste de nombres qu'on trie ensuite.
L'idéal, serait justement un algo qui construise progressivement les nombres dans l'ordre tout de suite sans être obligé de les stocker.
Et donc, de calculer les 100 premiers exactement pour avoir le 100e.
Code : Tout sélectionner
10 CLS
20 FOR A=0 TO 5
25 D=5^A
30 FOR B=0 TO 8
35 E=D*3^B
40 FOR C=0 TO 12
50 F=E*2^C-1
60 IF D<6912 THEN PSET (D MOD 144, D/144) ELSE C=13
70 NEXT C
80 NEXT B
90 NEXT A
100 DIM S(160)
140 I=1
150 FOR Y=0 TO 47
160 FOR X=0 TO 143
170 IF POINT (X,Y) LET S(I)=X+1+Y*144,I=I+1
180 NEXT X
190 NEXT YCe que je te disais c'est qu'un algo de ce type là est beaucoup plus compliqué que de tester si les nombres suivants sont des nombre de hamming pas.caloubugs a écrit :En fait, l'algorithme que je pensais est de construire les hamming les uns après les autres.
donc si j'ai déterminé H(n) et que j'applique l'algo, je trouve H(n+1).
.....
Je suis d'accord que je calcule plein de nombres de Hamming qui seront recalculés ensuite mais cette méthode permet d'obtenir le premier nombre de Hamming supérieur à n'importe quel seuil.
Bon, j'espère que je ne me suis pas planté...
Code : Tout sélectionner
10 N=100:DIM H(N):H(1)=1:FOR I=1 TO N-1
20 D=H(I):PRINT D;:J=1:A=INT(D/5)
30 IF H(J)<=A THEN J=J+1:GOTO 30
40 B=5*H(J):A=INT(D/3)
50 IF H(J)<=A THEN J=J+1:GOTO 50
60 C=3*H(J):A=INT(D/2):IF C<B THEN B=C
70 IF H(J)<=A THEN J=J+1:GOTO 70
80 A=2*H(J):IF A<B THEN B=A
90 H(I+1)=B:NEXT I:PRINT H(I)Code : Tout sélectionner
10 N=100:DIM H(N):H(1)=1:U=1:V=1:W=1:FOR I=1 TO N-1
20 D=H(I):PRINT D;:A=INT(D/5)
30 IF H(U)<=A THEN U=U+1:GOTO 30
40 B=5*H(U):A=INT(D/3)
50 IF H(V)<=A THEN V=V+1:GOTO 50
60 C=3*H(V):A=INT(D/2):IF C<B THEN B=C
70 IF H(W)<=A THEN W=W+1:GOTO 70
80 A=2*H(W):IF A<B THEN B=A
90 H(I+1)=B:NEXT I:PRINT H(I)Code : Tout sélectionner
1 2 3 4 5 6 8 9 10 12
Code : Tout sélectionner
1 2 3 4 5 6 8 9 10 12
/|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\
/ | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \
2 3 5 4 6 10 6 9 15 8 12 20 10 15 25 12 18 30 16 24 40 18 27 45 20 30 50 24 36 60
Code : Tout sélectionner
1
┌──────────────────────────┼──────────────────────────┐
2 3 5
┌────────┼────────┐ ┌────────┼────────┐ ┌────────┼────────┐
4 6 10 6 9 15 10 15 25
┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐ ┌──┼──┐
8 12 20 12 18 30 20 30 50 12 18 30 18 27 45 30 45 75 20 30 50 30 45 75 50 75 125
Code : Tout sélectionner
1 =1
┌──────────────────────────┼──────────────────────────┐
2 │ │ =2
┌────────┼────────┐ 3 │ =3
4 │ │ ┌────────┼────────┐ │ =4
│ │ │ │ │ │ 5 =5
┌──┼──┐ 6 │ 6 │ │ ┌────────┼────────┐ =6
8 │ : ┌──┼──┐ │ ┌──┼──┐ │ │ │ │ │ =8
° │ : │ : : │ │ : : 9 │ │ │ │ =9
│ : │ : : 10 │ : : ┌──┼──┐ │ 10 │ │ =10
12 : 12 : : ┌──┼──┐ 12 : : : : : │ ┌──┼──┐ │ │ =12
° : ° : : : : : ° : : : : : 15 : : : 15 │ =15
: : : : : : : : : : : ┌──┼──┐ : : : ┌──┼──┐ │
: : : : : : : : : : : : : : : : : : : : │
° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° °
20 18 30 20 30 50 18 30 18 27 45 30 45 75 20 30 50 30 45 75 25
Code : Tout sélectionner
1 =1
┌──────────────────────────┼──────────────────────────┐
2 │ │ =2
┌────────┼────────┐ 3 │ =3
4 │ │ ┌────────┼────────┐ │ =4
│ │ │ │ │ │ 5 =5
┌──┼──┐ 6 │ ° │ │ ┌────────┼────────┐ =6
8 │ : ┌──┼──┐ │ │ │ │ │ │ =8
+ │ : │ : : │ 9 │ │ │ │ =9
│ : │ : : 10 ┌──┼──┐ │ ° │ │ =10
12 : ° : : ┌──┼──┐ : : : │ │ │ =12
+ : : : : : : : : : 15 ° │ =15
: : : : : : : : : ┌──┼──┐ │
: : : : : : : : : : : : │
° ° ° ° ° ° : : : : : : :
+ + 20 18 30 20 30 50 18 27 45 30 45 75 25
Code : Tout sélectionner
{ 1 }
^abc
/ | \
/ | \
2 3 5Code : Tout sélectionner
{ 1 2 }
^bc ^a
/ | |
3 5 4Code : Tout sélectionner
{ 1 2 3}
^c ^a ^b
| | |
5 4 9Code : Tout sélectionner
{ 1 2 3 4}
^c ^ab
| / \
5 6 9Code : Tout sélectionner
{ 1 2 3 4 5}
^c ^ab
| / \
10 6 9Code : Tout sélectionner
{ 1 2 3 4 5 6}
^c ^b ^a
| | |
10 9 8Code : Tout sélectionner
{ 1 2 3 4 5 6 8}
^c ^b ^a
| | |
10 9 10Code : Tout sélectionner
{ 1 2 3 4 5 6 8 9}
^c ^b ^a
| | |
10 12 10Code : Tout sélectionner
{ 1 2 3 4 5 6 8 9 10}
^c ^b ^a
| | |
15 12 12Code : Tout sélectionner
{ 1 2 3 4 5 6 8 9 10 12}
^c ^b ^a
| | |
15 15 16Code : Tout sélectionner
LIST
10 m%=511: DIM H(m%): N=1: A=2:B=3:C=5: INPUT r% : T0=TIMER
20 DO
30 : h%=n% AND m%: n%=n%+1: H(h%)=N: IF r%<92 THEN PRINT N,
40 : IF A=N THEN a%=(a%+1)AND m%: A=2*H(a%)
50 : IF B=N THEN b%=(b%+1)AND m%: B=3*H(b%)
60 : IF C=N THEN c%=(c%+1)AND m%: C=5*H(c%)
70 : N=MIN(A,B,C)
80 LOOP WHILE n%<r%
90 PRINT N:PRINT "H(";n%;"=";H(h%);tab(30);INT((TIMER-T0)/6)/10;"s"
ready.
run
? 10
1 2 3 4 5 6 8 9
10 12 15
h 10 = 12 .4s
ready.
run
? 50
1 2 3 4 5 6 8 9
10 12 15 16 18 20 24 25
27 30 32 36 40 45 48 50
54 60 64 72 75 80 81 90
96 100 108 120 125 128 135 144
150 160 162 180 192 200 216 225
240 243 250
h 50 = 243 2.3s
ready.
RUN
? 100
h 100 = 1536 3.8s
ready.
RUN
? 200
h 200 = 16200 7.9s
ready.
_ Code : Tout sélectionner
H [ p q r ] H [ p q r ] H [ p q r ]
--- ---------- --- ---------- --- ----------
1 0 0 0 15 0 1 1 40 3 0 1
2 1 0 0 16 4 0 0 45 0 2 1
3 0 1 0 18 1 2 0 48 4 1 0
4 2 0 0 20 2 0 1 50 1 0 2
5 0 0 1 24 3 1 0 54 1 3 0
6 1 1 0 25 0 0 2 60 2 1 1
8 3 0 0 27 0 3 0 64 6 0 0
9 0 2 0 30 1 1 1 72 3 2 0
10 1 0 1 32 5 1 0 75 0 1 2
12 2 1 0 36 2 2 0 80 4 0 1
