Programare_în_algoritmi_(1).pdf

S. M. Okulov PROGRAMARE ÎN ALGORITMI Ediția a VI-a (electronic) Moscow Knowledge Laboratory 2017

Pagina 2

UDC 519.85(023) Seria BBK 22.18 O-52 fondată în 2008 Okulov S. M. O-52 Programare în algoritmi [Resursa electronică] / S. M. Okulov.- ed. a VI-a. (el.).-Electron. date text (1 fișier pdf: 386 p.).-M. : Laboratorul de cunoștințe, 2017. - (Dezvoltarea intelectului școlarilor - Sistem). cerințe: Adobe Reader XI; ecran 10". ISBN 978-5-00101-449-2 Arta programării este prezentată sub forma unui curs de pregătire care dezvăluie secretele celor mai populari algoritmi. Probleme precum algoritmii combinatori, enumerarea, algoritmii grafici, geometria computaţională. Algoritmii sunt prezentate problemele olimpiadei selectate cu instrucțiuni pentru soluție. Recomandările practice pentru programele de testare sunt un plus necesar pentru școlari, studenți și specialiști care studiază serios programarea. Programarea în algoritmi / S. M. Okulov - Ed. a IV-a - M.: Laboratorul Cunoașterii, 383 p. - (Dezvoltarea intelectului școlarilor - ISBN 978-5-9963-0848 Articolele 1299 și 1301 din Codul civil al Federației Ruse, la eliminarea restricțiilor stabilite prin mijloace tehnice de protecție a dreptului de autor, deținătorul dreptului de autor are dreptul de a cere despăgubiri de la contravenient pentru daune sau plata unei despăgubiri ISBN 978-5-00101- 449-2 ○ Laboratorul de cunoștințe, 2015 c

Pagina 3

Cuprins Prefaţă. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1. Aritmetica numerelor întregi cu mai multe cifre. . . . . . 8 1.1. Operații aritmetice de bază. . . . . . . . . . . . . . 8 1.2. Sarcini. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2. Algoritmi combinatori. . . . . . . . . . . . . . . . . . . . . . . . 27 2.1. Probleme de combinatorică clasică. . . . . . . . . . . . . . 27 2.2. Generarea de obiecte combinatorii. . . . . . . . . . . . . . 34 2.2.1. Rearanjamente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.2. Plasări. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2.3. Combinații. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.2.4. Împărțirea unui număr în termeni. . . . . . . . . . . . . . 58 2.2.5. Secvențe de zerouri și unuri de lungime N fără două unii consecutive. . . . . . . . . . . 64 2.2.6. Subseturi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 2.2.7. Secvențe de paranteze. . . . . . . . . . . . . 71 2.3. Sarcini. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3. Enumerarea şi metodele de reducere a acesteia. . . . . . . . . . . . . . . . 87 3.1. Forța brută cu backtracking (schemă generală). . . . . . . . . . . . . . . . 87 3.2. Exemple de probleme pentru analiza schemei generale de enumerare 89 3.3. Programare dinamică. . . . . . . . . . . . . . . . .106 3.4. Exemple de probleme pentru analiza ideii metodei de programare dinamică. . . . . . . . . . . . . . . . . . . . . . . . .108 3.5. Metoda ramurilor și legate. . . . . . . . . . . . . . . . . . . . . . . . . . . .116 3.6. Metoda „sită”. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121 3.7. Sarcini. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .126 4. Algoritmi pe grafice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .158 4.1. Reprezentarea unui grafic în memoria computerului. . . . . . . .158 4.2. Căutați în grafic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .159 4.2.1. Căutare în profunzime. . . . . . . . . . . . . . . . . . . . . . . . . . .159 4.2.2. Lățimea prima căutare. . . . . . . . . . . . . . . . . . . . . . . . . . .161

Pagina 4

4 Cuprins 4.3. Copaci. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .162 4.3.1. Concepte de bază. Strângerea copacilor. .162 4.3.2. Generarea tuturor cadrelor unui grafic. . . . . . . . . . .163 4.3.3. Cadru de greutate minimă. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .165 4.3.4. Cadru cu greutate minimă. Metoda R. Prima168 4.4. Conectivitate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .170 4.4.1. Accesibilitate. . . . . . . . . . . . . . . . . . . . . . . . . . . . .170 4.4.2. Definiţia connectivity. . . . . . . . . . . . . . . . . . . . .172 4.4.3. Biconectivitate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .173 4.5. Cicluri. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .176 4.5.1. Cicluri Euler. . . . . . . . . . . . . . . . . . . . . . . . . . .176 4.5.2. Cicluri hamiltoniene. . . . . . . . . . . . . . . . . . . . . .177 4.5.3. Set fundamental de cicluri. . . . . . .179 4.6. Cele mai scurte căi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .180 4.6.1. Enunțarea problemei. Ieșire cale. . . . . . . . . . . .180 4.6.2. algoritmul lui Dijkstra. . . . . . . . . . . . . . . . . . . . . . .182 4.6.3. Căi într-un grafic fără contur. . . . . . . . . . . . . . . . .183 4.6.4. Cele mai scurte căi între toate perechile de vârfuri. algoritmul lui Floyd. . . . . . . . . . . . . . . . .186 4.7. Seturi independente și dominante. . . . . . . .188 4.7.1. Seturi independente. . . . . . . . . . . . . . . . . . .188 4.7.2. Metodă de generare a tuturor mulțimilor independente maxime ale unui grafic. . . . . . . . . . . . . . . . . . .189 4.7.3. Seturi dominante. . . . . . . . . . . . . . . .194 4.7.4. Problema de acoperire minima. . . . . . . . . . . .195 4.7.5. Metodă de rezolvare a celei mai mici probleme de partiție. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .196 4.8. Planse de colorat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .202 4.8.1. Colorarea corectă. . . . . . . . . . . . . . . . . . . . .202 4.8.2. Găsirea colorării minime a vârfurilor graficului. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .203 4.8.3. Folosind cea mai mică problemă de acoperire la colorarea vârfurilor graficului. . . . . . .207 4.9. Fluxuri în rețele, potriviri. . . . . . . . . . . . . . . . . . . .208 4.9.1. Enunțarea problemei. . . . . . . . . . . . . . . . . . . . . . . . .208 4.9.2. Metodă de construire a debitului maxim într-o rețea. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .210 4.9.3. Potrivirea maximă într-un grafic bipartit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .215

Pagina 5

Cuprins 5 4.10. Metode de rezolvare aproximativă a problemei vânzătorului ambulant. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .219 4.10.1. Metoda de optimizare locală. . . . . . . . . . . .219 4.10.2. algoritmul lui Euler. . . . . . . . . . . . . . . . . . . . . . . . .222 4.10.3. Algoritmul lui Christofides. . . . . . . . . . . . . . . . . .225 4.11. Sarcini. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .227 5. Algoritmi pentru geometrie computaţională. . . . . . . . . .249 5.1. Proceduri de bază. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .249 5.2. Linie dreaptă și segment drept. . . . . . . . . . . . . . . . . .255 5.3. Triunghi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .262 5.4. Poligon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .266 5.5. Carcasă convexă. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .272 5.6. Probleme legate de dreptunghiuri. . . . . . . . . . . . . . . . . . . . . . . .284 5.7. Sarcini. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .293 6. Probleme ale olimpiadelor selectate în programare. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .300 7. Note privind programele de testare. . . . . . . . . . . . . . . .358 7.1. Despre programare. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .359 7.2. Recomandări practice. . . . . . . . . . . . . . . . . . . . . .360 7.3. Testarea unui program pentru rezolvarea unei probleme (folosind un exemplu). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .370 Index bibliografic. . . . . . . . . . . . . . . . . . . . . . . .382

Aritmetica numerelor cu mai multe cifre

Finalizat:
elev în anul 3
Facultatea de Matematică
33 de grupuri

Introducere…………………………………………………………………………………….3

Reprezentarea unui număr în orice sistem numeric……………………………………..4
Operații pe numere lungi..…………………………………………………… .5
Adunarea numerelor din mai multe cifre…………………………………………….6
Scăderea numerelor din mai multe cifre…………………………………………...7
Înmulțirea numerelor din mai multe cifre ………………………………………………………8
Înmulțirea rapidă………………………………………………………………………….11
Comparația între înmulțirea „rapidă” și „școală”……………………………22
Acuratețea calculelor și îmbunătățirea acesteia…………………………………………………23

Concluzie……………………………………………………………………………….24

Literatură……………………………………………………………………….26

Anexa…..………………………………………………………………………… ………………………….27

Introducere
Pentru multe aplicații, tipurile de bază furnizate de procesor sunt destul de suficiente. Cu toate acestea, există multe probleme ale căror date inițiale sunt prea mari. Un număr de 1000 de cifre nu se va încadra în niciun registru. Prin urmare, reprezentarea computerizată a unor astfel de numere și operațiunile pe acestea trebuie implementate independent.
În același timp, timpul de execuție a unui algoritm extern care utilizează astfel de numere depinde foarte mult de eficiența implementării lor. De exemplu, dacă estimarea timpului este determinată de înmulțiri O(n2), atunci folosind un algoritm de două ori mai rapid pentru această operație dă
accelerare de 4 ori. Prin urmare, probabil că vom fi cel mai serios interesați nu doar de algoritmi corecti, dar eventual mai eficienți care, dacă este necesar, pot fi implementați la un nivel decent.

Reprezentarea unui număr în orice sistem numeric
De obicei, un întreg nenegativ N de lungime n este reprezentat ca N = a0 + a1*BASE + a2*BASE2 + ... + an-1 BASEn-1,
unde BASE este baza sistemului numeric, toți coeficienții sunt 0. ai< BASE.
De exemplu, numărul din această interpretare va arăta ca
1234510 = 5 + 4*10 + 3*102 + 2*103 + 1*104 (BAZA=10).
Numărul lung este stocat într-o matrice, unde elementul i corespunde coeficientului de BAZĂ al numărului.
Ca exemplu, luați în considerare tabloul pentru: : (5, 4, 3, 2, 1).
După cum puteți vedea, numerele sunt stocate în ordine inversă. Acesta este un fel de „pregătire pentru viitor”: adevărul este că implementările algoritmilor au un aspect mai natural.
Această reprezentare a lui N este un caz special al polinomului de gradul al n-lea P(x) = a0 + a1*x + a2*x2 + ... + an-1 xn-1, care este, de asemenea, convenabil de stocat ca o matrice de coeficienți . Prin urmare, majoritatea operațiilor de bază pe numere, cu simplificarea corespunzătoare a algoritmilor, funcționează pentru polinoame arbitrare (adunare, înmulțire etc.).
Semnul numărului, precum și locul punctului zecimal, pot fi stocate într-o variabilă separată și luate în considerare la efectuarea operațiilor. În continuare, vom opera numai cu numere întregi nenegative.
Radix BASE depinde de obicei de dimensiunea maximă a tipului de date subiacent de pe computer și este aleasă pe baza următoarelor considerații:
1. Baza trebuie să se potrivească cu unul dintre tipurile de date de bază
2. BASE ar trebui să fie cât mai mare posibil pentru a reduce dimensiunea reprezentării numerelor lungi și a crește viteza operațiunilor pe acestea, dar suficient de mică pentru ca toate operațiunile pe coeficienți să utilizeze tipul de date de bază.
3. Pentru comoditate, puteți selecta BASE ca putere de 10 (ieșire de informații, depanare).
Operații pe „numere lungi”
Să luăm în considerare o problemă destul de populară în programare pentru lucrul cu numere „lungi”. În realitate, nu se întâlnesc foarte des numere „astronomice” sau „microscopice”. Cu toate acestea, exercițiile discutate în această publicație pot servi drept o bună pregătire în domeniul programării și să-și ocupe locul cuvenit în orele cu studiu aprofundat al informaticii sau în cluburile de programare. Algoritmii prezentați mai jos sunt scriși în Turbo Pascal, versiunea 7.0 și C++. Dacă se dorește sau este necesar, acestea pot fi adaptate cu ușurință oricărui alt mediu software. Gama de reprezentare a numerelor întregi (Integer, Word, LongInt) este limitată, ceea ce a fost deja menționat de mai multe ori (cu toate acestea, această remarcă este relevantă și pentru valorile reale). Prin urmare, atunci când rezolvați probleme, trebuie să acționați întotdeauna cu prudență, ca și cum pentru a preveni o eroare de depășire a intervalului sau depășire. De exemplu, calculând factorialul ( n! = 1 * 2 * 3 * … * n), în intervalul de reprezentare a valorilor de tip Integer, doar 7 pot fi obținute corect! = 5040, iar în intervalul reprezentării tip LongInt - 12! = 479001600. Pentru valori mari, desigur, puteți utiliza tipuri de date reale, dar acest lucru nu mai garantează un rezultat precis. Prin urmare, pentru a obține valori precise atunci când se operează cu numere cu mai multe cifre, este util să se dezvolte alte modalități de reprezentare a unor astfel de numere, algoritmi pentru efectuarea de operații aritmetice și alte operații, proceduri de introducere și ieșire a rezultatelor etc.
Sunt numite numere care nu au suficiente cifre binare pentru a fi reprezentate în tipurile de date standard de computer "lung". Se numește implementarea operațiilor aritmetice pe astfel de numere „lungi”. "aritmetica lunga". Cel mai natural mod de a reprezenta un număr cu mai multe cifre este de a scrie fiecare dintre cifrele sale ca un element separat al unei matrice liniare (sau o listă, unde memoria pentru cifra va fi alocată după cum este necesar, în timp ce într-o matrice trebuie să -setează numărul maxim de elemente în el). Lăsați (pentru comoditatea acțiunilor ulterioare) cifrele unui număr „lung” atunci când scrieți într-o matrice să fie numerotate de la unu, începând de la cifra celor, adică o cifră din locul celor este un element de matrice cu numărul unu, o cifră din locul zecilor este un element de matrice cu numărul doi etc. Să definim un tip de date pentru lucrul cu numere „lungi” nenegative:
Dar dacă implementăm operații aritmetice pe acest număr, atunci dimensiunea matricei trebuie să fie suficientă pentru a găzdui rezultatul, de exemplu, al înmulțirii. Înmulțirea este cea mai complexă dintre toate operațiile aritmetice și rezultatul său final ocupă cel mai mare loc în memoria computerului. Cele mai simple operații pe numere cu mai multe cifre sunt adunarea și scăderea.
Adăugarea numerelor cu mai multe cifre (lungi).
Aproape toată lumea poate adăuga numere lungi folosind o bucată de hârtie și un creion. Ceea ce vom face acum este să transferăm înțelegerea noastră existentă într-un limbaj pe care un computer îl poate înțelege.
Schema de adunare este foarte simplă: adunăm numerele de la stânga la dreapta (numerele sunt stocate în ordine inversă). Dacă se detectează o depășire (adică, în timpul adunării, se obține o cifră mai mare decât maximul posibil într-un anumit sistem de numere), atunci are loc un „transfer” la următoarea cifră.
Să găsim suma numerelor A și B. Vom adăuga elemente de matrice cu aceleași numere și vom stoca rezultatele ca elemente ale matricei C (algoritmul de lucru cu astfel de matrice seamănă cu adăugarea coloanelor). Dacă la un anumit pas obținem C[i], atunci în locul lui C[i] lăsăm restul împărțirii C[i] la 10 (numărul de unități ale unei cifre date) și adăugăm 1 la elementul C ( transferați 1 la următoarea cifră).
Dacă numărul A este format din N cifre, iar numărul B este format din M cifre, atunci numărul C are fie max(N,M) cifre, fie max(N,M)+1 cifre. Să notăm cu K valoarea max(N,M)+1.
Înainte de a efectua adăugarea, ar trebui să adăugați zerouri nesemnificative la numărul cu mai puține cifre, astfel încât numărul de cifre să fie egal. Acest lucru poate fi realizat prin resetarea matricelor A și B la zero înainte de a introduce numere.
Algoritmul pentru adăugarea a două numere din mai multe cifre este prezentat în Anexa 1.
După executarea acestui algoritm, primele K elemente ale matricei C vor stoca suma numerelor A și B, C este cifra de ordin inferior. Ultima verificare vă permite să eliminați un zero nesemnificativ din cifra cea mai semnificativă a numărului C.
Scăderea numerelor din mai multe cifre
Scăderea se efectuează în mod similar, singura diferență fiind că „împrumutul” este reportat. Lucrăm cu numere pozitive, deci dacă subtraend este mare ca mărime, apare rezultatul.
Dacă lungimile sunt aceleași, dar una este mai mare decât cealaltă - acest lucru va duce la un împrumut neutilizat la sfârșitul procesului, iar rezultatul va fi adăugarea la BASEB.Size.
Pentru certitudine, vom presupune că A>B. Dacă nu, atunci trebuie să schimbați numerele și să faceți rezultatul negativ.
Dacă numărul A este format din N cifre, atunci numărul B nu poate avea mai mult de N cifre. Diferența nu va conține mai mult de N cifre.
Să aflăm diferența dintre numerele A și B. Vom scădea elementele tabloului B din elementele tabloului A cu numerele corespunzătoare. Vom stoca rezultatele obținute în tabloul C. Dacă la un pas obținem C[i]<0, то к элементу C[i] прибавляем 10, а от элемента C отнимаем 1(забираем 1 из следующего разряда).
Algoritmul pentru scăderea a două numere cu mai multe cifre este prezentat în Anexa 2.
Înmulțirea numerelor din mai multe cifre
Cel mai natural mod de a reprezenta un număr cu mai multe cifre este de a scrie fiecare dintre cifrele sale ca un element separat al unei matrice liniare (sau o listă, unde memoria pentru cifra va fi alocată după cum este necesar, în timp ce într-o matrice trebuie să -setează numărul maxim de elemente din el). Lăsați (pentru comoditatea acțiunilor ulterioare) cifrele unui număr „lung” atunci când scrieți într-o matrice să fie numerotate de la unu, începând de la cifra celor, adică o cifră din cifra unităților este un element de matrice cu numărul unu, o cifră din cifra zecilor este un element de matrice cu numărul doi etc. Să definim un tip de date pentru lucrul cu numere „lungi” nenegative:
Const MNax = 2000;
Tip Cifră = 0..9;
DlChislo = Matrice de cifre;
Pentru a rezolva această problemă, trebuie să puteți efectua următoarele acțiuni:
1) introducerea unui număr „lung”;
2) înmulțirea efectivă a două numere „lungi”;
3) ieșirea unui număr „lung”;
4) determinarea numărului de cifre dintr-un număr.
Implementăm fiecare dintre subsarcini ca o subrutină separată. Să începem cu introducerea. Este recomandabil să introduceți un număr mare ca șir și apoi să îl convertiți într-o matrice de numere. Procedura ia în considerare metoda de mai sus de plasare a unui număr „lung” într-o matrice, adică Din punctul de vedere al utilizatorului, numărul este scris în ordine inversă.
(Procedura de conversie a unui număr lung, scris ca șir, într-o matrice de cifre; variabila OK ia valoarea True dacă intrarea numărului nu conține caractere străine, altele decât cifre zecimale, în caz contrar - fals)
Procedură Translate(S: String; Var A: DlChislo; Var OK: Boolean);
Var I: Cuvânt;
ÎNCEPE
Zero(A); I:= Lungime(S); OK:= Adevărat;
În timp ce (I >= 1) Și OK Do
ÎNCEPE
Dacă S[I] în ["0".."9"]
Apoi A:= Ord(S[I]) - 48
Altfel OK:= Fals; I:= I - 1
Sfârşit
Sfârşit;
Procedura apelează subrutina Zero(A), al cărei scop este de a scrie un zero la fiecare cifră a unui număr lung. Iată textul acestei proceduri:
(Procedura pentru resetarea unui număr lung)
Procedura Zero(Var A: DlChislo);
Var I: Integer;
ÎNCEPE
Pentru I:= 1 To NMax Do A[I] := 0;
Sfârşit;
Astfel, un număr lung este scris într-o matrice, unde în față apar zerouri nesemnificative (ca elemente cu numere mari). Atunci când se efectuează acțiuni și se afișează un răspuns, acestea nu sunt luate în considerare.
Acum vom dezvolta o funcție pentru determinarea numărului de cifre semnificative dintr-un număr, deoarece va fi necesară la implementarea subrutinei de înmulțire.
(Funcție pentru determinarea numărului de cifre dintr-un număr lung)
Funcția Lina(C: DlChislo) : Integer;
Var I: Integer;
ÎNCEPE
I:= NMax;
În timp ce (I > 1) Și (C[I] = 0) Do I:= I - 1;
Lungime: = I
Sfârşit;
La elaborarea sa, s-a folosit următorul considerent: dacă un număr nu este egal cu zero, atunci numărul de cifre din notația sa este egal cu numărul primei cifre, diferit de zero, dacă numărul este privit din cea mai semnificativă până la cifra cea mai puțin semnificativă. Dacă numărul lung este egal cu zero, atunci se dovedește că numărul de cifre din notația sa este egal cu unul, ceea ce a fost necesar.
Și, în sfârșit, procedura principală, de dragul căreia au fost făcute toate lucrările anterioare. La compilarea algoritmului, se folosește ideea de înmulțire pe „coloană”, deși în versiunea noastră adunarea se efectuează nu la sfârșitul înmulțirii, ci pe măsură ce aceasta progresează, de exemplu. După ce am înmulțit următoarele cifre, adăugăm imediat cifra rezultată la cifra dorită și formăm un report către următoarea cifră.
(Procedura de înmulțire a numerelor lungi. A, B - factori, C - produs)
Procedură de multiplicare(A, B: DlChislo; Var C: DlChislo);
Var I, J: Integer; P: Cifră; VspRez: 0..99;
ÎNCEPE
Zero(C);
Pentru I:= 1 To Lina(A) Do (Buclă prin numărul de cifre din primul număr)
ÎNCEPE
P:= 0; (Inițial, transportul este zero)
Pentru J:= 1 To Lina(B) Do (Buclă prin numărul de cifre din al doilea număr)
ÎNCEPE
VspRez:= A[I] * B[J] + P + C;
C:= VspRez Mod 10; (Următoarea valoare a cifrei din cifra I + J - 1)
P:= VspRez Div 10 (Transportați la următoarea cifră)
Sfârşit;
C:= P (ultima purtare poate fi diferită de zero, o vom scrie în cifra încă liberă)
Sfârşit
Sfârşit;
Întregul program este prezentat în Anexa 3.

FAST_MULTIPLICATION
Ne-am propus să scriem nu numai cum are loc înmulțirea pe numere lungi, ci și să stabilim cum să o facem mai rapidă.
Să creăm un algoritm de multiplicare:
1. Găsiți cel mai mic număr Len – puterea a doi: Len. Mărimea A + Mărimea B. Pentru numerele luate în considerare Len=8.
2. Pad A și B cu zerouri înainte de Len. În exemplul nostru, A=(3,4,0,0,0,0,0,0), B=(5,4,3,2,1,0,0,0).
3. Calculați FFT a vectorilor reali pe ambele tablouri de cifre.
4. Înmulțiți scalar vectorii transformați, obținând un vector de mărimea Len.
5. Aplicați transformata Fourier inversă, al cărei rezultat va fi convoluția.
6. Convertiți convoluția într-o matrice de numere întregi, faceți transferuri.
Cifrele numerelor mari sunt stocate în format întreg. Prin urmare, pentru FFT ele trebuie copiate în tablouri temporare în virgulă mobilă. Dacă vă așteptați să primiți rezultate de lungime maximă N, atunci trebuie să alocați memorie pentru acestea de cel puțin dimensiunea
MaxLen=2k, unde MaxLen este puterea minimă a doi, mai mare decât N. De exemplu, dacă rezultatul maxim constă din 1000 de cifre bazate pe BASE, atunci cantitatea minimă de memorie este MaxLen=1024, deoarece aceasta este lungimea FFT care va fi calculat.
real *LongNum1=NULL, *LongNum2=NULL;
// Inițializarea poate fi făcută o singură dată pe parcursul întregului program.
void FastMulInit(ulong Len) (
ulong MaxLen;
if ((Len & -Len) == Len) // Len = puterea a doi
MaxLen = Len;
else ( // altfel calculează MaxLen - cea mai mică putere de 2,
MaxLen = 2; // astfel încât 2MaxLen . Len
face MaxLen*=2; în timp ce (MaxLen< Len);
}
LongNum1 = real nou;
LongNum2 = real nou;
}
// Deinițializare
void FastMulDeInit() (
șterge LongNum1;
șterge LongNum2;
}
Funcția RealFFT(), discutată în secțiunea corespunzătoare, efectuează transformarea „la loc”, returnând vectorii rezultați în formă comprimată.
În consecință, funcția de produs punct trebuie să țină cont de acest format.
// Înmulțirea scalară a vectorilor complecși în formă comprimată: LongNum1 = LongNum1*LongNum2
void RealFFTScalar(real *LongNum1, const real *LongNum2, ulong Len) (
Complex *CF1= (Complex*)LongNum1;
const Complex *CF2=(Complex*)LongNum2;
// primele două elemente sunt grupate într-un singur numere reale complexe

LongNum1 = LongNum1 * LongNum2 ;
pentru (ulong x = 1; x< Len/2; x++) // остальные – комплексные, как им и
CF1[x] = CF1[x]*CF2[x]; // ar trebui să fie după DFT
}
Să aruncăm o privire mai detaliată asupra ultimului pas.
Toate calculele au loc în format virgulă mobilă, folosind numere iraționale, astfel încât rezultatul nu va fi un set de numere întregi, ci mai degrabă o aproximare a acestuia. Pentru a obține răspunsul, fiecare coordonată de convoluție trebuie rotunjită la cel mai apropiat număr întreg.
a a a a….. a
b b b b ….. b
Problema constă în faptul că, dacă acuratețea calculelor nu este suficient de mare, atunci poate apărea rotunjirea la un număr greșit. Ca rezultat, algoritmul se va finaliza cu succes, dar răspunsul va fi incorect.
Unele dintre problemele legate de acuratețe au fost rezolvate în discuția despre FFT. Cu toate acestea, chiar și cu o trigonometrie absolut precisă, erorile de calcul se vor acumula, deoarece operațiile aritmetice nu pot fi efectuate cu acuratețe absolută. Prin urmare, dimensiunea tipului de date utilizat trebuie să fie suficient de mare, astfel încât eroarea la orice semn să fie mai mică de 0,5.
De exemplu, când se utilizează un tip de date de dimensiunea 1, fracția 1/3 este reprezentată ca 0,3. Când adunăm trei fracții obținem
1/3 + 1/3 + 1/3 = (format virgulă mobilă) 0,3 + 0,3 + 0,3 = 0,9
Dacă dimensiunea este de două cifre, atunci 1/3 = 0,33,
1/3 + 1/3 + 1/3 = 0,33 + 0,33 + 0,33 = 0,99. Precizia calculelor a crescut foarte mult.
În general, există două moduri de a crește precizia. Una dintre ele este legată de creșterea lungimii tipului folosit: De la float la double, apoi la long double, apoi la double double2...
Cealaltă abordare este mai flexibilă. Pentru un tip fix, sugerează reducerea lungimii bazei BASE. Acest lucru va face numărul mai lung și va ocupa mai multă memorie, dar acest lucru va crește precizia.
Limitările înmulțirii FFT
O evaluare interesantă a erorilor a fost făcută de Colin Percival.
Să presupunem că doriți să înmulțiți vectori cu 2n coordonate folosind FFT pentru vectori cu coordonate reale. Apoi din rezultatele sale rezultă că eroarea înmulțirii x cu y este estimată de sus prin expresia
a greșit< 2n BASE2 (.*3n + . 5 (3n+4) + .(3n+3)) (2)
Unde. - precizie de adunare/multiplicare, . - acuratețea calculelor trigonometrice,
Prin urmare, pentru dat., . Nu este greu să găsești BAZĂ minimă posibilă.
De exemplu, dacă tipul folosit este dublu (53 biți), .=2-53. Erorile de trigonometrie sunt limitate la .=./ 2 .
Să estimăm limita superioară a erorilor (2) printr-un număr Calculând aproximativ constantele, obținem 2n BASE2 2-53 (11,83 n + 11,07).< .
Pentru numerele cu lungimea 220, aceasta duce la inegalitatea BASE< 4100. Такова оценка худшего случая, обоснованная математически.
În practică, totuși, BASE=10000 este o alegere bună. Înmulțirea FFT cu această bază poate funcționa chiar și pentru multe numere mari. Cu toate acestea, nu vor exista garanții matematice ale rezultatului corect.
Când rotunjiți, ar trebui să vă uitați la diferența dintre valoarea rotunjită și rezultatul rotunjirii. Dacă este mai mică de 0,2, atunci înmulțirea dă cel mai probabil rezultatul corect dacă este mai mare, se recomandă reducerea BASE sau folosirea unui alt tip de bază pentru a stoca coeficienții;
După finalizarea pasului 5, nu există un produs finit, ci doar o convoluție - rezultatul fără transferuri. După cum s-a menționat deja când luăm în considerare piramida de multiplicare, valorile coeficienților de convoluție pot fi mult mai mari decât baza, ajungând la 2N*BASE2. Dacă ne amintim, în plus, că transformarea Fourier inversă împarte rezultatele funcției RealFFT() la N, atunci dimensiunea maximă a cifrei devine 2N2*BASE2, așa că trebuie avut grijă să nu se depășească. În special, BASE nu trebuie declarat mai lung de 4 cifre zecimale.
Ultimele două tipuri nu sunt acceptate de toate procesoarele

Ca un rezumat al celor de mai sus, observăm că există doar trei probleme:
1. Precizia trigonometriei
2. Precizie la calcularea FFT
3. Debordare tip bază.
Prima problemă este rezolvată când discutăm despre FFT. Al doilea și al treilea se rezolvă prin scăderea BASE, sau prin creșterea tipului de bază. În același timp, eficiența algoritmului scade, deoarece o bază mai mică înseamnă un număr mai mare de cifre, iar un tip de bază mai mare nu este întotdeauna disponibil.
Următoarea funcție transformă o Convoluție de lungime Len într-un număr mare C, făcând runde și purtând înainte. La sfârșitul execuției, variabila MaxError va conține eroarea maximă de rotunjire.
RealFFT() nu normalizează rezultatul, așa că trebuie făcut aici.
MaxError reală;
void CarryNormalize(real *Convolution, ulong Len, BigInt &C) (
inv real = 1,0 / (Len/2); // factor de normalizare
// DFT a fost efectuat pe un vector „complex”.
// de 2 ori mai scurt
real RawPyramid, Pyramid, PyramidError, Carry = 0;
scurt *c = C.Coef;
ulong x;
// În C vom plasa doar acea parte a rezultatului care se potrivește acolo
// DFT are lungime egală cu 2k, dar vector coeficient
// ar putea fi inițializat la mai puține elemente, nu la o putere de 2.
dacă (Len > C.SizeMax) Len=C.SizeMax;
MaxError = 0;
pentru (x = 0; x< Len; x++) {
RawPyramid = Convoluție[x] * inv + Carry;
// Adăugați 0,5 pentru a rotunji la cel mai apropiat număr întreg
Pyramid = podea(RawPyramid + 0,5);
PyramidError = fabs(RawPyramid - Pyramid);
dacă (PyramidError > MaxError)
MaxError = PyramidError;
Carry = podea(Piramida / BAZĂ); // calculează transporturile
c[x] = (scurt)(Pyramid - Carry * BASE);
}
// Totul este gata, nu mai rămâne decât să setați mărimea C, conform primei
// coeficient diferit de zero.
do ( x--; ) în timp ce (c[x]==0);
C.Mărimea = x+1;
}
Acum puteți implementa întregul algoritm.
// Calculați C = A*B, apelați FastMul(A, B, A) funcționează
void FastMul(const BigInt &A,const BigInt &B, BigInt &C) (
ulong x;
const scurt *a=A.Coef, *b=B.Coef;
dacă (!LongNum1 || !LongNum2) eroare ("FastMul nu a fost inițializat.");
// Pasul 1
ulong Len = 2;
în timp ce (Len< A.Size + B.Size) Len *=2;
dacă (Len< 8) Len = 8; // FFT работает

// Pasul 2. Rescrieți numărul într-o matrice temporară și completați-l cu zerouri de început
// Numerele sunt în ordine inversă, deci zerourile de început vor fi la sfârșit
pentru (x = 0; x< A.Size; x++) LongNum1[x] = a[x];
etc.............

Operațiile aritmetice asupra numerelor binare se efectuează după cum urmează:

Adăugarea a două numere binare multi-biți se realizează bit cu bit, ținând cont de unitățile de depășire din biții anteriori:

Scăderea numerelor binare pe mai mulți biți, similar cu adunarea, începe de la cifrele cele mai puțin semnificative. Dacă luați unul în ordinea mare, se formează două în ordinea inferioară:

Înmulțirea este o adunare repetată a sumelor intermediare și a deplasărilor:

Procesul de împărțire constă în operații de scădere care se repetă:

Subiectul 1.4 Codarea datelor într-un computer Codarea datelor cu cod binar

Pentru a automatiza lucrul cu date aparținând diferitelor tipuri, este foarte important să unificați forma lor de prezentare - pentru aceasta, tehnica este de obicei utilizată codificare, adică exprimarea datelor de un tip în termeni de date de alt tip. Omul natural limbi– nu sunt altceva decât sisteme de codificare a conceptelor pentru exprimarea gândurilor prin vorbire. Strâns adiacent limbilor ABC-uri(sisteme de codificare a componentelor limbajului folosind simboluri grafice). Istoria cunoaște încercări interesante, deși nereușite, de a crea limbi și alfabete „universale”. Aparent, eșecul încercărilor de implementare a acestora se datorează faptului că entitățile naționale și sociale înțeleg în mod firesc că schimbarea sistemului de codificare a datelor publice va duce cu siguranță la o schimbare a metodelor sociale (adică a normelor legale și morale), iar acest lucru pot fi asociate cu tulburări sociale .

Aceeași problemă a unui instrument de codificare universal este implementată cu destul de mult succes în anumite ramuri ale tehnologiei, științei și culturii. Exemplele includ un sistem de înregistrare a expresiilor matematice, un alfabet telegrafic, un alfabet al pavilionului naval, un sistem Braille pentru nevăzători și multe altele (Figura 1.2).

Figura 1.2 – Exemple de diferite sisteme de codare

Tehnologia informatică are și propriul său sistem - se numește codificare binarăși se bazează pe reprezentarea datelor ca o secvență de doar două caractere: 0 și 1. Aceste caractere sunt numite cifre binare,în limba engleză - binar cifră sau, pe scurt, pic(pic).

Un bit poate exprima două concepte: 0 sau 1 (Da sau nu, negru saualb, adevărat sau minciună etc.). Dacă numărul de biți crește la doi, atunci pot fi exprimate patru concepte diferite:

Trei biți pot codifica opt valori diferite:

000 001 010 011 100 101 110 111

Prin creșterea numărului de biți din sistemul de codificare binar cu unul, dublem numărul de valori care pot fi exprimate în acest sistem, adică formula generală arată astfel:

N=2 m ,

Unde N– numărul de valori codificate independente;

T– adâncimea de biți a codării binare adoptată în acest sistem.

Forme de reprezentare a numerelor

Calculatoarele folosesc două forme principale de reprezentare a numerelor: naturale cu virgulă zecimală fixăși semilogaritmică virgulă flotantă.

La reprezentarea numerelor cu un punct fix, poziția virgulei este fixată într-un anumit loc față de cifrele numărului și rămâne neschimbată pentru toate numerele care sunt reprezentate într-o grilă de cifre dată. De obicei, o virgulă este fixată înaintea primei cifre (cea mai semnificativă) și numai numerele care sunt mai mici de 1 în valoare absolută pot fi reprezentate în grila de biți Pentru a codifica semnul unui număr binar, cel mai semnificativ („semn”). cifra („0” – „+”, „1” este folosit) – „–”).

Dezavantaje Reprezentările în punct fix ale numerelor sunt:

necesitatea calculului prealabil și introducerii factorilor de scară pentru a elimina posibilitatea de depășire a rețelei de biți (adică atunci când numărul modulo depășește unu), precum și pierderea cifrelor de ordin inferior (adică atunci când numărul modulo este mai mic decât unul dintre cifra cea mai puțin semnificativă);

dependența preciziei relative de valoarea numerelor primite.

Precizia relativă maximă este atinsă prin efectuarea de operații pe cele mai mari numere posibile. Avantaj

este simplitatea și viteza mare a operațiunilor.

Utilizarea unei reprezentări în virgulă fixă ​​a numerelor face posibilă simplificarea circuitelor mașinii și creșterea performanței acesteia, dar prezintă anumite dificultăți de programare. Prin urmare, reprezentarea în virgulă fixă ​​a numerelor este utilizată ca principală numai în microcontrolere.

În calculatoarele mainframe, principala este reprezentarea numerelor în virgulă mobilă. Reprezentarea unui număr cu virgulă mobilă în cazul general are forma: = m· O n ,

q O Unde

– baza SS; În calculatoarele mainframe, principala este reprezentarea numerelor în virgulă mobilă. Reprezentarea unui număr cu virgulă mobilă în cazul general are forma:;

m n – un număr întreg numit ordinea numărului În calculatoarele mainframe, principala este reprezentarea numerelor în virgulă mobilă. Reprezentarea unui număr cu virgulă mobilă în cazul general are forma:(|m| < 1).

– mantisa numărului În calculatoarele mainframe, principala este reprezentarea numerelor în virgulă mobilă. Reprezentarea unui număr cu virgulă mobilă în cazul general are forma:=m Din moment ce computerul folosește SS binar, atunci n·2

, cu ordinul și mantisa reprezentate în formă binară. Dacă cifra cea mai semnificativă dintr-un număr este diferită de zero, se ia în considerare numărul; dacă cifra de început este zero, numărul nu este normalizat. Normalizarea numerelor în timpul procesului de calcul se realizează automat în computer. În acest caz, mantisa numărului este deplasată la stânga până când cea mai apropiată unitate apare în cea mai semnificativă cifră a rețelei cu o scădere corespunzătoare în ordinea numărului. În cazul depășirii grilei de biți, de exemplu, atunci când se adaugă numere normalizate de aceeași ordine, normalizarea este efectuată la dreapta cu un bit:

3,1415926 = 0,31415926·10 1;

0,00125 = 0,125·10 -2.

Dezavantaj reprezentarea numerelor în virgulă mobilă este aceea că pentru a efectua operații asupra numerelor în virgulă mobilă este necesar să se efectueze operații separat cu mantise de numere și separat cu ordine, ceea ce complică și încetinește executarea operațiilor. Avantaj– pentru un computer cu virgulă mobilă, intervalul de numere reprezentate este mai mare decât pentru un computer cu virgulă fixă.

Pentru a codifica numerele întregi de la 0 la 255, este suficient să aveți 8 biți de cod binar (8 biți). Șaisprezece biți vă permit să codificați numere întregi de la 0 la 65535, iar 24 de biți vă permit să codificați mai mult de 16,5 milioane de valori diferite.

Codificarea pe 80 de biți este folosită pentru a codifica numerele reale

Pentru a simplifica circuitele, scăderea într-un computer este înlocuită cu adăugarea de coduri numerice special construite. Aplicați direct,spateŞi adiţional coduri numerice (pe cont propriu).

Lucrări de laborator nr. 3 Aritmetica numerelor întregi cu mai multe cifre Este cunoscut faptul că variabilele de tip întreg într-un limbaj de programare nu pot lua valori arbitrar de mari. Mai mult, pentru a reprezenta un întreg, se folosește memoria limitată, ceea ce înseamnă că numărul de valori de tip întreg este finit, ceea ce contrazice conceptele noastre matematice. De exemplu, în limbajul de programare Pascal, doi (tip Integer) sau patru octeți (tip Longint) sunt de obicei alocați pentru stocarea numerelor întregi, adică 16 sau 32 de biți. În primul caz, puteți reprezenta 216 = 65536 numere diferite, în al doilea - 232 = 4294967296. Uneori trebuie să procesați numere care nu se află în acest interval. De exemplu, să presupunem că trebuie să calculați 2100 = 1267650600228229401496703205376. Vom numi astfel de numere „lungi”, iar mijloacele de lucru cu ele vor fi „aritmetica lungă”. Să luăm în considerare o modalitate de a stoca un număr „lung” în memoria computerului. Să luăm o matrice de numere întregi „scurte” obișnuite și să o considerăm o reprezentare pozițională a unui număr „lung” într-un sistem numeric cu o bază B. Apoi, fiecare element al acestei matrice va lua valori de la 0 la B - 1 și N astfel de elemente ne vor permite să reprezentăm numere nenegative de la 0 la BN-1. Pentru a simplifica, vom stoca o cifră zecimală în fiecare element al tabloului (adică vom lua B egal cu 10). În limbajul de programare Pascal, numărul de elemente ale unui tablou este specificat atunci când este descris, așa că trebuie să învățați cum să estimați numărul de cifre dintr-un număr „lung”. Este adesea posibil să se folosească formula pentru numărul de cifre din numărul N: K = . De exemplu, numărul de cifre din numărul 2100 este K = = = 31 Uneori este posibil să se estimeze numărul de cifre dintr-un număr comparându-l cu un număr mai mare. De exemplu, 3200 = 9100< 10100 Таким образом, в числе 3200 не более 100 десятичных цифр. Далее будем предполагать, что количество цифр N задано в программе как константа. Определим специальный тип для представления "длинных" целых Type item = longint; Long = array of item; Тип item будут иметь элементы, составляющие "длинное" число. Собственно "длинные" числа будут иметь тип Long. Выделить место для записи "длинного" числа - это еще не все. Надо договориться, как мы будем записывать "длинное" число в массив: с начала или с конца массива, с начала или с конца числа. Чтобы было понятнее, что имеется в виду, все варианты показаны на рисунке для случая N = 6 , размещаемое число - 1234 , пустые ячейки обозначены *: 1. 1234*** 2. ***1234 3. 4321*** 4. ***4321 Чтобы не хранить реальную длину числа, будем хранить в пустых ячейках незначащие нули и обрабатывать их наравне с заполненными. В этом случае выберем второй вариант заполнения массива: будем хранить цифры в обычном порядке в конце массива. Напишем основные операции с ѕдлиннымиї числами. 1. Преобразование строки в "длинное" число. Идея процедуры: исходя из длины строки рассчитываем позицию цифр в массиве. Сначала заполняем "длинное" число нулями, затем проходим по строке и помещаем каждую цифру в массив на рассчитанное место. procedure StringToLong(s:String; var x:Long); Var l,i,k:integer; begin l:=length(s); for i:=1 to N do x[i]:=0; for i:=1 to l do Val(s[i],x,k); end; Эту процедуру можно использовать при вводе "длинных" чисел и при преобразовании обычного числа в "длинное". 2. Вывод "длинного" числа. "Длинное" число выводится по одной цифре с начала массива. Обязательно нужно пропустить ведущие нули. Реализуйте процедуру вывода самостоятельно. 3. Сложение "длинных" чисел. Для сложения используется алгоритм сложения "столбиком". Процесс начинается от конца числа. Выделим специальную переменную с для хранения переноса. Сначала с равна нулю. На каждом шаге вычисляется сумма соответствующих цифр двух чисел и переноса. Последняя цифра результата помещается в выходной массив z, остальные - переносятся в следующий разряд. procedure AddLong(x,y:Long; var z:Long); Var i,c:integer; begin c:=0; for i:=N downto 1 do begin z[i]:=(x[i]+y[i]+c) mod 10; c:=(x[i]+y[i]+c) div 10; end; end; 4. Сравнение "длинных" чисел. Перебираем цифры с начала массива, пока не найдем две различные цифры. Больше то число, которому принадлежит большая из этих цифр. Реализуйте процедуру самостоятельно. 5. Умножение "длинного" целого на обычное целое. Эта процедура очень похожа на сложение: точно так же моделируется вычисление столбиком, точно так же на каждом шаге определяется перенос в следующий разряд. Реализуйте процедуру самостоятельно. 6. Умножение "длинного" целого на степень 10. Эта операция заключается в дописывании к числу нескольких нулей. При этом все значащие цифры сдвигаются влево. 7. Умножение "длинных" целых. Реализуйте алгоритм умножения "столбиком" с использованием процедур сложения, умножения на обычное целое число и умножения на степень 10. 8. Вычитание "длинных" целых. Также похоже на сложение. На каждом шаге из цифры одного числа вычитается цифра другого и перенос. Если результат отрицательный, то к нему прибавляется 10 и перенос становится равным 1, иначе перенос обнуляется. Не стоит пытаться моделировать школьную процедуру заема единицы из старшей цифры, поскольку при наличии нулей алгоритм сильно усложняется. 9. Деление "длинных" чисел c остатком. Сводится к вычитанию. Сначала обнулим остаток, далее будем добавлять к остатку по одной цифре делимого, взяв их слева. Каждый раз выполняем цикл: пока остаток не меньше делителя, вычитаем делитель из остатка и увеличиваем очередную цифру частного. Задание к лабораторной работе: Задание 1. Написать функции сложения длинных чисел; умножения длинного числа на целое обычное; умножения длинного числа на степень десятки; умножения двух "длинных" натуральных чисел. Задание 2. Написать процедуру деления с остатком "длинного" числа на "длинное", используя сравнение и вычитание длинных чисел. Задание 3.Решить задачу по вариантам, используя "длинную" арифметику: 1) По вводимому с клавиатуры числу n (0 <= n <= 1000), необходимо вычислить значение 2n. 2) Даны два натуральных числа, не превышающие 1000. Вывести точное значение A/B без лишних точек, нулей и пробелов. В случае присутствия бесконечной записи числа следует вывести период в скобках. Например, 10/7=1.(428571), 1/3=0.(3), 100/25=4. 3) Даны три натуральных числа, каждое из которых не превышает 10100. Определить и вывести максимальное из этих трех чисел. () 4) По заданному натуральному числу А (A <= 103000) требуется найти наибольшее число В такое, что B2 <= A. (другими словами извлечь квадратный корень из числа A). 5) Вычислить факториал целого числа N (N < 1000). Факториал обозначают как N! и вычисляют по формуле: N! = 1 * 2 * 3 * ... * (N-1) * N, причем 0! = 1. 6) В двух строках записаны два неотрицательных целых числа A и B, не превышающие 101000. Выведите значение A-B, учитывая знак. 7) Для натуральных чисел A и B (1 <= A <= 9, 1 <= B <= 104) требуется вычислить значение AB. 8) Факториалом натурального числа K называется произведение K!=1×2×3×...×K. Требуется написать программу, которая по заданному числу N (N ≤ 200) вычислит сумму 1!+2!+...+N!. Алгоритмы и анализ сложностиИТ(б)II курс, 3 семестр