Numere naturale k-binare
Definitie Numarul natural aIN se numeste k-binare, k³1, k
N , daca
in sistemul de numeratie cu baza 2, numarul a se scrie cu k cifre de 1,
indiferent de pozitia lor in numar, restul cifrelor fiind zero.
Enunt: Se considera numarul natural pIN si fie n =2p-1, pentru fiecare kI sa se proiecteze un algoritm care sa genereze toate numerele naturale a£n si care sunt k-binare.
Caz particular. Sa se exemplifice enuntul pentru p=6.
Descrierea algoritmurilor
Numarul natural pIN fiind precizat; presupunand p³1, se determina urmatoarele submultimi de numere naturale:
B1 contine primele p puteri naturale ale lui 2
Deci : B1 are elementele B1 :
Elementele lui B1 au proprietatea ca xI B1, x este un numar 1 - binar
Elementele lui B1 sunt unicele numere naturale mai mici decat n =2p-1 (care sunt1binar )
B2 contine elemente obtinute
astfel: fiecare element x din B1 se aduna cu orice element yIB1
, y>x. Se vor
obtine astfel C2p elemente 
B2 :
Elementele lui B2 au proprietatea ca xI B2, x este un numar 2 - binar
Elementele lui B2 sunt unicele numere naturale mai mici decat n =2p-1 (care sunt
2-binare ) .
Continuand rationamentul pentru k
p
elementele submultimii Bk vor fi generate astfel:
xIBk-1
anterior generata x se aduna cu toate elementele y>x , yI B1!
Elementele submultimii Bk
in numar de Ckp au
proprietatea ca xIBk , x
este k- binar.
Familia de submultimi are urmatoarele proprietati:
Bi 
Bj
= Æ, i¹j
= =B
Bi , 1 i p , x este
i-binar
Submultimea B1 se numeste
submultime de generatori naturali pentru elementele multimii B, deoarece ( )xIBx se scrie
in mod unic ca o combinatie liniara de elemente din B1 .
Caz particular p=6
p=6 n=26-1=64-1=63
n=63
B1= =, 
= C16=6
este1-binar
B2=
B2: 3 5 9 17 33
6 10 18 34
12 20 36
24 40
48
= C26=15
este 2-binar
Exemplu:
18| 2
0 | 9 | 2
1 | 4 | 2
0 | 2 | 2
0 |1 B10=10010 ; 18 este 2-binar
B3=
B3: 7 11 19 35
13 21 37
14 22 38
25 41
26 42
28 44
49
50
51
56
= C36=20
este 3-binar
Exemplu:
22 | 2
0 | 11 | 2
1 | 5 | 2
1 | 2 | 2
0 | 1 22= 10110 ; 22 este 3 - binar
B4=
B4: 15 23 39
43
45
46
51
53
54
57
58
60
= C46= C26=15 este 4-binar
Exemplu:
1 23 = 10111 23 este 4-binar
1
0
B5=
B5 : 31 47
55
59
61
62 C56 = C16=6 este 5-binar
Exemplu:
55(10)=110111 ; 55 este 5-binar
B6=
B6=63
C66 =1 este 6 - binar 63(10)=111111 ; 63 este 6-binar
Aceasta aplicatie este utilizata la proiectarea circuitelor integrate si la numerotarea circuitelor pe clase de impulsuri.
|
