Divizarea în notație binară

Aceasta încheie descrierea cele mai simple operații aritmetice, trebuie să știți în scopul de a utiliza aritmetica binară, iar acum vom încerca să răspundem la întrebarea „De ce aritmetică binară.“ Desigur, cele de mai sus a arătat că numărul de înregistrare în sistemul binar simplifică foarte mult operații aritmetice, dar în același timp, recordul devine semnificativ mai mare, ceea ce reduce valoarea simplificării rezultată, deci trebuie să caute astfel de probleme, din care soluția este mult mai simplă în cifre binare.







Sarcina 1: Obținerea tuturor eșantioanelor

Foarte des există probleme în care trebuie să puteți construi toate combinațiile posibile dintr-un anumit set de obiecte. De exemplu, o astfel de sarcină:

Având în vedere o grămadă mare de pietre, puneți pietrele în două grămezi, astfel încât masa acestor două grămezi să fie cât mai aproape posibil.

Această problemă poate fi formulată după cum urmează:

Găsiți un eșantion de pietre dintr-o grămadă mare, încât masa totală să fie cât mai mică posibil de la jumătate din masa unui heap mare.

Sarcini de acest fel sunt destul de multe. Și toate acestea sunt reduse, după cum sa spus deja, capacității de a obține toate combinațiile posibile (mai departe le vom numi eșantioane) dintr-un anumit set de elemente. Și acum vom lua în considerare o metodă generală de obținere a tuturor probelor posibile utilizând operația de adăugare a numerelor binare. Să începem cu un exemplu. Să fie un set de trei obiecte. Construim toate probele posibile. Elementele vor fi notate cu numere ordinale. Adică, există următoarele elemente: 1, 2, 3.

Mostre: (0, 0, 1); (0, 1, 0); (0, 1, 1); (1, 0, 0); (1, 0, 1); (1, 1, 0); (1, 1, 1);

Dacă există una în poziția cu numărul următor, atunci aceasta înseamnă că elementul cu numărul egal cu această poziție este prezent în eșantion și dacă este zero, atunci elementul nu este prezent. De exemplu, eșantionarea (0, 1, 0); constă dintr-un element cu numărul 2 și o probă (1, 1, 0); este format din două elemente cu numerele 1 și 2.

Din acest exemplu este clar că eșantionul poate fi reprezentat ca număr binar. În plus, nu este greu de observat că sunt scrise mai presus de toate numerele binare de unu, doi și trei cifre. Îi rescriim după cum urmează:

001; 010; 011; 100; 101; 110; 111

Vom considera prima cifră ca fiind cea mai joasă ca prima, aruncați zerourile nesemnificative (adică, zerouri în cele mai înalte cifre până la prima unitate) și obțineți următoarea serie:

1; 10; 11; 100; 101; 110; 111

Am obținut o serie de numere binare consecutive, fiecare dintre care este obținută de la cea precedentă prin adăugarea unei singure. Puteți verifica afară. Folosind această regularitate observată, putem construi următorul algoritm pentru obținerea eșantioanelor.

Datele inițiale ale algoritmului

Având în vedere un set de elemente N - piese. Vom numi setul de elemente inițiale. Numărăm toate elementele setului original de la 1 la N. Noi compunem un număr binar de zerouri N nesemnificative. 0000 ... 0N Acest număr binar zero va denota un eșantion zero cu care va începe procesul de eșantionare. Cifrele unui număr sunt contorizate de la dreapta la stânga, adică cea mai veche cifră din stânga este cea mai veche.







Suntem de acord să desemnem acest număr binar cu majuscule BINARY

Dacă numărul BINARY este alcătuit în întregime din unități

Apoi oprim algoritmul

§ Adăugați la numărul BINARY o unitate conform regulilor aritmetice binare.

§ Din numărul BINARY primit, facem următorul eșantion, așa cum a fost descris mai sus.

Sarcina 2: Căutați numere primare mari

Pentru început, ne amintim că un număr prime este un număr natural care este divizibil doar de 1 și de el însuși. Exemple de prime: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31.

Căutarea numerelor prime prime este o sarcină matematică foarte importantă. Primele numere mari sunt necesare pentru criptarea fiabilă a mesajelor prin intermediul unor algoritmi de criptare. Și nu sunt necesare doar numere mari, ci numere foarte mari. Cu cât este mai mare numărul, cu atât este mai fidel codul construit pe acest număr.

Notă. Un cifru de încredere este un cifru, care necesită un decalaj foarte lung.

De ce? Un număr prime joacă rolul unei chei atunci când este criptat și decriptat. În plus, știm că numerele primare apar în seria numerică naturală nu prea des. Există o mulțime dintre ele în primele mii, apoi numărul lor începe să scadă rapid. Prin urmare, dacă luăm ca cheia nu este numărul foarte mare, criptanaliștii folosind computerul nu foarte repede va fi capabil să-l atingă (de cotitură peste ca cheia tot una simplă după alta), pentru o perioadă limitată de timp.

Un cod suficient de fiabil poate fi obținut dacă luați unul simplu, de exemplu 150 de caractere. Cu toate acestea, găsirea unei astfel de simple nu este atât de simplă. Să presupunem că un număr A (foarte mare) trebuie verificat pentru simplitate. Este același lucru cu căutarea divizoarelor sale. Dacă găsim divizori în intervalul de la 2 la rădăcina pătrată a lui A, atunci nu este simplu. Să estimăm numărul de numere pentru a verifica capacitatea de a diviza numărul A.

Să presupunem că numărul A are 150 de caractere. Rădăcina pătrată a acestuia va conține cel puțin 75 de caractere. Pentru a sorta numărul de divizori posibili, avem nevoie de un calculator foarte puternic și de un timp uriaș, ceea ce înseamnă că sarcina este aproape imposibil de rezolvat.

Cum să facem acest lucru

În primul rând, putem învăța de la mai rapid pentru a inspecta pentru divizibilitate un număr la altul, iar în al doilea rând numărul A poate încerca alese astfel încât să fie ușor, cu un grad ridicat de probabilitate. Se pare că acest lucru este posibil. Matematicianul Mersen a descoperit că numerele de tipul următor

Sunt simple cu un grad ridicat de probabilitate.

Pentru a înțelege fraza de mai sus, vom calcula câte numere prime sunt în primele mii și câte numere Mercen în aceleași mii sunt simple. Deci, numerele Mersen din primele mii sunt următoarele:

2 1 - 1 = 1; 2 2 -1 = 3; 2 3 - 1 = 7; 2 4 - 1 = 15; 2 5 - 1 = 31; 2 6 -1 = 63;

2 7 - 1 = 127; 2 8 -1 = 255; 2 9 - 1 = 511;

Caracterele aldine sunt marcate cu numere prime. Doar 9 numere Mercen sunt 5 simple. În procente, aceasta este de 5/9 * 100 = 55,6%. În același timp, există doar 169 de numere simple la 1000 de numere naturale. În procente, aceasta este de 169/1000 * 100 = 16,9%. Adică, în primele mii în raportul procentual, numerele simple dintre numerele Mersen apar aproape de 4 ori mai des decât între numerele pur naturale

Și acum luați un număr specific de Mersen, de exemplu 2 4 - 1. Vom scrie-o sub forma unui număr binar.

2 4 - 1 = 10000 - 1 = 1111

Luăm următorul număr Mercen 2 5 -1 și îl scriem cu un număr binar. Obținem următoarele:

2 5 -1 = 100 000 - 1 = 11111

Este deja clar că toate numerele Mersen reprezintă o secvență de unități, iar acest fapt oferă doar o mare victorie. În primul rând, în sistemul binar este foarte ușor să obțineți următorul număr Mersen. Pentru aceasta este suficient să adăugați unul la următorul număr. În al doilea rând, este mult mai ușor să căutați divizoare în sistemul binar decât în ​​zecimal.







Trimiteți-le prietenilor: