Suite de Syracuse

**Akhey** · 02/10/2009, 17h40

Bonjour,
Je suis sur Borland Pascal, et je galère avec mon petit machin, à savoir la suite de Syracus où je dois afficher seulement les suites où les itérations sont plus élevées que les suites précédentes...
On m'a dit de mettre une autre boucle après la première pour afficher seulement les compteurs plus élevés, mais j'ai pas dû tout capter...
Pourriez-vous m'aider svp ?
Merci

**darrylsite** · 02/10/2009, 19h38

Sans code, je ne vois pas du tout comment on peut te répondre. Le mieux c'est de montrer ce que tu as dejà fait, et exposer ensuite clairement ta pré-ocupation.

Je crois avoir dejà lu quelques posts sur la suite de syriacus dans ce forum. Une petite recherche pourra peut etre t'aidé.

**Akhey** · 03/10/2009, 18h28

Voilà ce que j'ai fait pour le moment. Ca affiche toutes les suites, alors que je souhaite afficher seulement celles qui ont des itérations plus élevées.
(merci d'avance ^^)

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
program suite_de_syracuse;
 
  uses
    WinText;
 
  var
    n, i, vMax : Integer;                         {-suite, terme initial de la suite, valeur max}
    cpt: Integer;                                 {-compteur de boucles}
    depass: boolean;                              {-quand il devient vrai on arrête la boucle}
                                                  {si elle ne finit pas par 1 : avant de dépasser les capacités de Integer}
begin
    Writeln('Suite de naturels de Syracuse');
    Writeln('Determination des suites les plus longues');
 
    n := 1;
    i := 0;
    vMax := (maxInt - 1) div 3;
    depass := False;
    repeat
       i := i + 1;
       n := i;
       cpt := 0;
       repeat
          Write(n: 8);
          if n mod 2 = 0 then
            begin
              n := n div 2;
            end
          else if n > (maxInt - 1) div 3 then
            begin
              depass := True
            end
          else
            begin
              n := n * 3 + 1;
            end;
          cpt := cpt + 1
       until (n = 1) or depass;
       Writeln(n: 8);
 
 
       if depass then
         Writeln('----------------- dépassement après');
         Writeln('----------------- ', cpt, ' itérations pour ', i)
    until depass;
end.

**darrylsite** · 05/10/2009, 16h48

Qu'appelles tu iterations plus elements? Sont elles qui ont le max d'iteration? ou fixes tu une limite pour savoir si une iteration est elevée ou pas?

Pour connaitre le nombre d'iteration d'une suite donnée, tu peux la mettre dans une fonction qui te donne le nombre de son iteration.

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
 
function iteration(i : byte) : integer;
 var n, cpt : integer;
      depass: boolean;
begin
       n := i;
       cpt := 0;
      depass:=false;
 
       repeat
          if n mod 2 = 0 then
            begin
              n := n div 2;
            end
          else if n > (maxInt - 1) div 3 then
            begin
              depass := True
            end
          else
            begin
              n := n * 3 + 1;
            end;
          cpt := cpt + 1
       until (n = 1) or depass;
 
    iteration:=cpt;
end;

il te suffit d'appeler cette fonction pour un i donnée pour savoir le nombre d'iteration que ça fait. Ensuite, si la valeur est elevé tu peux l'afficher.

**Dr.Who** · 07/10/2009, 15h23

on peut faire une toute petite amélioration qui multiplie les performances par 2 :

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
const
  MaxIntS1D3 = (MaxInt-1) div 3;
 
function iteration(const i : byte) : integer;
var n, cpt : integer;
    depass : boolean;
begin
  n      := i;
  cpt    := 0;
  depass := false;
 
  repeat
    if (n and $1) = 0 then // si n est pair
      n := n shr 1            // n divisé par 2
    else
    if n > MaxIntS1D3 then
      depass := True
    else
      n := n * 3 + 1;
 
    cpt := cpt + 1;
  until (n = 1) or depass;
 
  iteration := cpt;
end;

pourquoi AND $1 au lieu de MOD 2 :

MOD fait appel à une division en premier puis retourne le reste de cette division. il y a donc plusieurs instructions assembleur qui sont appelée et .. ça prend du temps :

if (n and $1) = 0 then n := n shr 1 else ...

desassemblage :
test al,$01;
jnz @jump if not zero :to: if n > MaxInt...;
shr eax,1;
jmp @jump :to: Cpt := Cpt + 1...;

2 instructions sur faux, 4 sur vrai

if (n mod 2) = 0 then n := n div 2 else ...

desassemblage :
mov eax,esi;
and eax,$80000001;
jns @jump if no sign :to: test eax, eax;;
dec eax;
or eax,-$02;
inc eax;
test eax,eax;
jnz @jump if not zero :to: if n > MaxInt...;
mov ecx,$00000002;
mov eax,esi;
cdq;
idiv ecx;
mov esi,eax;
jmp @jump :to: Cpt := Cpt + 1...;

8 instructions sur faux, 14 sur vrai

voila, 14 instructions contre 4 ... de -6 à -10 instructions par itérations...
sans compter le reste.

pourquoi $1 ?

c'est simple, toute les puissances de 2 sont paire (sauf 2^0 = 1)

donc le seul moyen de faire un 7, un 9, un 1215 est de mettre le bit 0 de l'entier à 1!

exemple :

0000 = 0 &1=0
0001 = 1 &1=1
0010 = 2 &1=0
0100 = 4 &1=0
1000 = 8 &1=0

donc

3 = 0011 (2+1) &1= 1
5 = 0101 (4+1) &1= 1
9 = 1001 (8+1) &1= 1
11 (0xB) = 1011 (8+2+1) &1= 1
13 (0xD) = 1101 (8+4+1) &1= 1
256891 (0x3EB7B) = 0xB = 1101 &1= 1

pourquoi shr 1 ?

le binaire est basé sur les puissances de 2, glisser les bits vers la droite (SHR) fait passer tout les bits à 1 aux puissances inférieures et comme ce sont des puissances de 2 ... cela reviens à diviser par 2 (pour shl 1) ou par une puissance de 2. inversement quand on glisse les bits vers la gauche (SHL) fait passer les bits à 1 aux puissances supérieures et donc cela reviens à multiplier par 2 (pour shl 1) ou par une puissance de 2.

souviens toi : 1 2 4 8 16 32 64 128 256
chaque nombre suivant est le double du précédent, ce sont les puissances de 2.
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16

si j'ai :
1000 (8) : 1000 shr 1 = 0100 = 4
1100 (8+4=12) : 1100 shr 1 = 0110 = 4+2 = 6
plus dur avec un nombre impaire :
1011 (8+2+1=11) : 1011 shr 1 = 0101 = 4+1 = 5 = 11 div 2 = round(11/2)

et on peut faire pareil pour toutes les puissances de 2
diviser par 4 :: shr 2
diviser par 8 :: shr 3
diviser par 16 :: shr 4
diviser par 32 :: shr 5
diviser par 1024 :: shr 10

etc.

et inversement pour les multiplications : on utilise SHL :
shl 1 = *2
shl 2 = *4
shl 3 = *8
shl 4 = *16
shl 10 = *1024

etc.