SlitherÎn Python
SlitherÎn Python
Conț inuturi
................................................................................................................................................................ 1
Capitolul 1............................................................................................................................................... 7
Cerinț e preliminare...................................................................................................................................... 7
1.1 Rezultatele învăț ării ș i pentru cine este această carter ......................................................................... 7
2.3 Sintaxă.........................................................................................................................................13
4.1 - Booleans..................................................................................................................................26
4.2 - ThedacăDeclaraț ie.....................................................................................................................28
4.3 - Thedacă-altfeldeclaraț iet .............................................................................................................30
4.4 - Theelifdeclaraț iet ..................................................................................................................32
4.5 - Înglobatdacădeclaraț ii.............................................................................................................33
2
6.2 - Funcț ii de string......................................................................................................................46
6.3 - Metode de ș iruri......................................................................................................................47
6.5 - Imutabilitate...........................................................................................................................51
6.6 - Tăierea ș irurilorg ...........................................................................................................................52
3
10.6 - Deschiderea ș i citirea fiș ierelor.....................................................................................................95
14.2 - Afirmatii...........................................................................................................................136
14.3 - încearcă ș i exceptă........................................................................................................................137
4
14.5 - Exerciț ii..............................................................................................................................142
Capitolul 15 - Mai multe despre tipurile de date..................................................................................................145
15.1 - Tupluri..................................................................................................................................145
16.2 - Memoizare......................................................................................................................156
16.3 - Partea Quicksort1 .................................................................................................................158
16.4 - Partea Quicksort2 .................................................................................................................160
16.5 - Exerciț ii..............................................................................................................................160
Capitolul 17 - Programare orientată pe obiect (OOP)....................................................................162
5
20.4 - Exerciț ii..............................................................................................................................192
Capitolul 21 - Structuri de Date de Bază................................................................................................195
21.1 - Stiva.............................................................................................................................195
21.2 - Coadae ..........................................................................................................................199
21.3 - Exemplus.............................................................................................................................201
21.4 - Exerciț ii..............................................................................................................................203
Capitolul 22 - Structuri de date mai avansate.............................................................................206
6
Capitolul 1
Cerinț e preliminare
Există doar două lucruri pe care trebuie să le faci înainte de a citi această carte: a avea
Python instalat pe computerul tău. Nu o să trec prin procesul de a face
Aș adar, am lăsat câteva linkuri mai jos despre cum să-l instalaț i pe orice sistem de operare.
veț i folosi. Vom folosi Python 3.7 pe parcursul acestei cărț i; cu toate acestea, s-ar putea
deja ai Python instalat dacă eș ti pe Mac sau Linux. De asemenea, voi dezvolta pe
Windows 10, dar asta nu ar trebui să facă o diferenț ă.
1.1 Rezultate ale învăț ării ș i pentru cine este această carte
Slither în Python este disponibil gratuit online ș i se adresează oricui doreș te să înveț e.
să programeze sau doreș te să înveț e câte ceva despre ș tiinț a calculatoarelor ș i are puț in
fără cunoș tinț e despre niciuna.
7
Nu este necesară experienț a anterioară în programare sau un fond în ș tiinț a calculatoarelor.
Spre deosebire de orice alte resurse Python pe care le-am găsit (nu că acestea nu ar exista), ele nu
explicaț ionează conceptele importante de informatică, cum ar fi memoria sau „cum funcț ionează calculatoarele
muncă” pe care cred că este esenț ială pentru a deveni un bun programator (având câteva
cunoș tinț ele de bază în informatică pot adesea să te ajute să ieș i din situaț ii ciudate
când programez). În această carte voi acoperi fundamentele Python
limbaj de programare ș i introduce aceste concepte importante din ș tiinț a calculatoarelor
ș i teorii.
Pe scurt, programarea sau codarea este despre a face computerele să facă ceea ce
Vrei, informatica este despre cum o fac computerele. Fiecare merge mână în mână,
te ajută să înveț i mai repede, îmbunătăț eș te înț elegerea ta generală a unei limbi ș i face
să fii un programator mai bun. Această carte îș i propune să facă exact asta prin Python.
O altă abilitate importantă pe care o au toț i marii programatori este rezolvarea problemelor. A fi capabil să
gândeș te-te la o problemă dintr-o perspectivă diferită, descompune-o într-o formă mai uș oară
o problemă mai gestionabilă sau reformularea problemei este extrem de importantă.
A gândi computaț ional este de asemenea important (probabil cel mai important. Cei mai mulț i oameni
eşuează pentru că nu învaţă să gândească computaţional). Ia în considerare să faci o ceaşcă de ceai.
Este ceva ce facem în fiecare zi fără a ne gândi prea mult. Cu toate acestea, asta nu va ...
funcț ionează bine pentru noi când vine vorba de scrierea programelor de calculator. Trebuie să împărț im
probleme împărț ite într-un set de paș i bine definiț i.
(Vă rog să nu-mi trimiteț i e-mailuri despre metoda mea de preparare a ceaiului!).
Sper că până la sfârș itul acestei cărț i veț i avea o înț elegere solidă a Python
limbaj de programare, o înț elegere fermă a informaticii importante
8
concepte, capacitatea de a utiliza tehnicile de rezolvare a problemelor în mod eficient ș i cele mai.
în mod important, gândeș te computaț ional.
[Link] .DATE
2. hello: Salut lume!
3. helloLen: echiv $-hello
4.
[Link] .TEXT
6. GLOBAL _start
7.
8._start:
9. mută eax,4
10. mută ebx,1
11. mută ecx, salut
12. mov edx,helloLen
13. int80h
14.
15. mută eax,1
16. mută ebx,0
17. int80h
Python are o comunitate imensă în spatele său. Dacă te blochezi într-o problemă sau nu poț i rezolva
sensul unui mesaj de eroare, pot garanta că vei găsi răspunsul tău în decurs de
minute.
9
Python are de asemenea un număr ridicol de mare de biblioteci open source, cadre ș i
module disponibile pentru a face orice doriț i să faceț i. Acest lucru face ca dezvoltarea dvs.
aplicaț iile ș i mai simple.
Pentru a încheia, dacă plănuieș ti să îț i construieș ti o carieră din asta, salariul mediu
pentru un dezvoltator Python în SUA este în jur de 92.000 de dolari.
În secț iunea anterioară am dat peste niș te cod urât în limbaj de asamblare. Acum este
timp să ne scriem primul program. O să traducem acel program în Python:
[Link]("Salut lume!")
Asta e tot! Chiar este atât de simplu. Creează un fiș ier nou în editorul tău de text, copiază textul de mai sus
scrieț i-l în ș i salvaț i-l ca [Link]. Toate programele Python se termină cu extensia .py.
Următorul pas, pentru a rula programul nostru, trebuie să deschidem o fereastră de terminal. Pe Windows, deschide
exploratorul de fiș iere ș i mergi la directorul (folderul) în care ai salvat fiș ierul. În partea de sus
în fereastra explorerului de fiș iere vei vedea ceva similar cu:
Fă clic pe aceasta ș i scrie „cmd” ș i apasă enter. Aceasta va deschide o fereastră de terminal în acea
director.
În cele din urmă, pentru a rula programul tău, în fereastra terminalului lângă _C:NAME>, tastează
urmat
python [Link]
Felicitări! Ai scris primul tău din multe programe Python. Acum vreau să te
să uit programul de mai sus. Îl am aici pur ș i simplu pentru a servi ca un impuls în motivaț ie.
În capitolul următor vom reveni la cele mai de bază noț iuni ș i te vom pune pe drumul cel bun.
pentru a stăpâni limba Python.
10
Capitolul 2 - Numere întregi, Operatori ș i
Sintaxă
2.1 Numere întregi
Înainte să începem, a înț elege materialul din acest capitol este important
totuș i, este foarte uș or! Nu este cu adevărat nimic dificil în acest capitol. Cu toate acestea, eu
voi spune, unele dintre exerciț iile de la final s-ar putea să te surprindă! aș a că fii atent
la conț inut.
Aș a cum am spus la sfârș itul capitolului precedent, uiț i acel program hello world.
În acest capitol vom începe cu cele mai elementare lucruri ș i asta înseamnă
folosind Python ca un calculator de intregi.
>>>
11
15//5
5*2+3
3+2*5
(3+2) *5
Acestea sunt cunoscute sub numele de expresii întregi. Ele sunt expresii care evaluează
la o valoare întreagă.
O valoare singulară pe cont propriu, cum ar fi prima expresie din lista de mai sus
expresiile se numesc literal întreg.
Un număr întreg este un număr întreg pozitiv sau negativ.
De asemenea, putem scrie numere negative în acelaș i mod în care am face-o în mod normal.
5 + -5evaluează la 0.
Pentru completitudine, semnul minus înaintea celui de-al doilea 5 în expresia de mai sus
se numeș te operatorul de negare unară. Acesta acț ionează asupra unei singure valori. Semnul + este un
operator binar deoarece operează asupra a două lucruri numite operanzi (5 ș i -5 în acest
caz).
• Literaluriîntregi
• Operatori întregi
oOperatori binari: +, -, * ș i //
oOperatori unari: - (negare)
• Operanzi: 5 + 3
• Expresii întregi
12
• Valori întregi
3+2*5
(3+2) *5
Ei oferă răspunsuri diferite. Aceasta este din cauza a ceva numit precedenț ă.
Precedenț a defineș te ordinea în care operatorii sunt evaluaț i ș i operatorii
sunt evaluate de la cea mai mare prioritate la cea mai mică.
1.(…)
2. *, /
3. +, -
2.3 Sintaxă
13
Acum să aruncăm o cheie în funcț ionare. În REPL-ul Python încearcă acestea
expressions:
4+3+
(1+1))
5+3 2
9+ -3
8+ +9
1* *6
14
sublinind unde au avut loc aceste erori. De fapt, Python este destul de bun la
indicând unde au avut loc cele mai multe erori în comparaț ie cu multe alte limbi
(cel puț in în opinia mea).
Notă laterală importantă
2**2
3**2
4%3
13%10
2.4 Exerciț ii
Întrebarea 1
• Este operatorul ** (putere) asociativ pe stânga sau pe dreapta? (Încearcă să îț i dai seama de asta)
în REPL)
Întrebarea 2
• Este operatorul % asociativ pe stânga sau pe dreapta? (Încearcă să îț i dai seama de asta în
REPL)
Întrebarea 3
Întrebare 4
Întrebarea 5
15
• Din următoarea listă de expresii întregi, care expresie(e) au
Sintaxă invalidă?
o((4 * 6 - (4 // 2))
o9 * -11 + 6
o6 - +4
1.x = 7
2.y = 5
3.
4.z = x - yValoarea 2 este acum, în esenț ă, stocată în variabila z
x, y, ș i zsunt variabile.
Pentru această secț iune, cea mai bună alegere ar fi să-ț i deschizi editorul de text ș i un
linie de comandă (fereastră terminal). Creează un fiș ier nou ș i numeș te-l cum vrei
vrei, dar asigură-te că îl salvezi cu extensia .py.
Copiaț i cele trei instrucț iuni de atribuire de mai sus în fiș ier ș i salvaț i-l. Apoi în
în promptul de comandă, rulează programul (python [Link]). Nimic
16
se pare că s-a întâmplat DAR voi ilustra mai jos ce s-a întâmplat în
fundal.
2) Memory: x
---------------------------------
# Aloca o zonă de memorie pentru x
---------------------------------
3) Memorie: x
---------------------------------
17
5) Memorie: x y
---------------------------------
6) Memorie: x y z
---------------------------------
| | | | 7 || | 5 || # Atribuie o zonă de memorie pentru z
---------------------------------
7) Memorie: x y z
---------------------------------
| | | | 7 || | 5 | 2 | Stochează valoarea 2 în această zonă
de memorie
---------------------------------
Ș i aș a mai departe, executând fiecare instrucț iune de asignare pe rând. Cu toate acestea, am putea
18
În acest caz, "reciclăm" (sau actualizăm) slotul de memorie, aș a cum se arată mai jos.
1) Memory: x y z
---------------------------------
| | | |*7*| | | 5 | 2 | Memoria a fost deja alocată pentru x,
reutilizaț i-l.
---------------------------------
2) Memory: x y z
---------------------------------
---------------------------------
Acum putem folosi acest lucru pentru a face lucruri utile, de exemplu, să calculăm
suprafaț a totală a Pământului (aproximativ).
1.radius_of_earth = 6371
[Link] = 3.14
3.surface_area = 4 * pi * (radius_of_earth ** 2)
NOTĂ IMPORTANTĂ:
19
3.2 - Tipuri de puncte flottante
We haven't seen these yet. This is a new type (like integer). They are
numite numere în punct flotant (numere zecimale pentru omul mediu). În
Python, acesta esteplutitortip.
tip(3.14)
<tip'float'>
Floaturile funcț ionează aproape la fel ca ș i integerii (ceea ce sunt sigur că te aș tepț i).
We can perform the same calculations with them. Float expressions also
evaluează la tipuri de float.
>>>2.0//1.0
2.0
>>>2.0*4.0
8.0
# etc....
Nu ș tiu despre tine, dar acel simbol de diviziune pare ciudat. De ce să nu pur ș i simplu
folosiț i un singur/ ?
Ei bine, poț i!// este pentru împărț irea la podea (cifrele după punctul decimal sunt eliminate).
Să ne uităm la cum/ ș i//work:
100//3
33
>>>100/3
33.333333333333336
Putem vedea aici că atunci când folosim întregi,// rotunjeste în jos la un număr întreg
(int) dar când folosim/ rezultatul este convertit într-unplutitorAcesta se numeș te tip
turnare.
În mod similar:
>>>100.0//3.0
33.0
20
>>>100.0/3.0
33.333333333333336
Acesta este ceva la care trebuie să fii atent când faci împărț iri. Dacă tu
foloseș te/ cu operanzi întregi ș i valoarea rezultată conț ine cifre după
loc zecimal, s-ar putea să întâlneș ti o eroare dacă următoarea parte a codului tău este
aș teptând un întreg.
De asemenea, avem toț i ceilalț i operatori standard cu care ne-am întâlnit (operatori float în
acest caz).
De asemenea, putem scrie numere cu zecimale negative în modul aș teptat:
-3.14
Până acum, programele noastre nu au fost chiar atât de interesante ș i nu sunt foarte
benefic. Nu putem interacț iona cu ei când sunt în miș care. Cele mai multe
aplicaț iile în zilele noastre permit utilizatorului să ofere input (fie că este vorba de introducerea
date sau făcând clic pe opț iuni în jurul ecranului). În această secț iune, ne vom uita la
cum poț i obț ine input de la utilizator în timp ce programul tău se execută.
Pentru a face asta, folosim o funcț ie, ș i anumeinput()Vom ajunge la funcț ii mai târziu în aceasta
carte, aș a că nu te îngrijora în legătură cu ele, doar ș tii că atunci când tastăminput(), al nostru
>>> x=intrare()
Bună
>>> x
Bună
Esential, input()prinde o linie din intrare (vom ajunge la asta mai târziu), converteș te
linie într-un ș ir ș i o returnează.
21
Putem vedea că din codul de mai sus ar putea părea că programul nostru are
îngheț at (nu a fost). Putem adăuga un prompt prietenos care să apară când întrebăm
utilizator pentru introducere. Să aruncăm o privire mai atentă la un program mai prietenos cu utilizatorul.
>>> nume
John
Metoda 2
x=int(input())
y=float(introduceț i())
>>> x=int(introduceț i)
Bună
Urmează urmă (cea mai recentă apelare cea mai recentă):
22
Primim oValueErrorVom analiza diferitele tipuri de erori puț in mai târziu.
De asemenea, vom analiza capacitatea de a gestiona aceste situaț ii (de aceea prefer
a doua metodă).
Aceasta, în opinia mea, este una dintre cele mai utile funcț ii pe care Python le are de oferit. Ca
progresăm prin această carte ș i lucrurile încep să devină puț in mai dificile, eu
sunt sigur că vei folosi asta destul de mult.
123456>>>print"Bună"
Bună
>>>print(3.14)
3.14
>>>printBună din nou
Bună din nou
Recapitulare:
• / sau
împărț irea ta obiș nuită
• Am învăț at cum să luăm input de la utilizator cuintrare()funcț ie
• Am învăț at cum să imprimăm informaț ii în fereastra terminalului cu
theprint()funcț ie.
23
Să ne uităm la un program care le pune pe toate acestea împreună! (Timp pentru editor de text)
3.5 - Exerciț ii
Notă importantă:
Soluț iile pentru unele dintre aceste exerciț ii necesită gândire creativă.
Nu te aș tepta să ajungi imediat la o soluț ie!
Întrebarea 1
Extinde programul de mai sus pentru a permite utilizatorului să introducă numărul de iepuri.
x=3
y=11
# Codul tău pentru a schimba aici
#y=3
24
Întrebarea 4
# EXAMPLE
# Secvenț ă:
# 0 1 2 3 4 5 6 7 ...
#SOLUȚ IE
x= x+1
Secvenț a 1:
0 2 4 6 8 10 12 ...
Secvenț a 2:
0-1-2-3-4-5-6 ...
Secvenț a 3:
6-6 6-6 6-6 .....
Secvenț a 4 (Dificil):
-6 -3 0 -6 -3 0 -6 -3 0 -6 -3 0...
25
Capitolul 4 - Flux de control
4.1 - Booleani
Notă importantă:
Dacă poț i să-ț i aminteș ti de exemplul preparării unei ceș ti de ceai, am avut o
pasul care a mers cam aș a:
ABoolean este un tip care are două valori: adevărat sau fals.
Acest lucru mă duce la un punct important. În Python, valori diferite ale diferitelor
tipurile pot fi adevărate sau false.
De exemplu, cu numere întregi,0este fals în timp ce orice alt întreg este adevărat. Cu
pluteș te,0.0este fals, în timp ce orice alt float este adevărat ș i, în final, cu stringuri,
empty string ('') este falsă, în timp ce orice altă ș ir de caractere este adevărată.
>>>Fals==0
Adevărat
>>>Fals==1
Fals
>>>Fals==0
Adevărat
>>>False==0.1
Fals
26
De asemenea, putem converti orice altă valoare într-un boolean folosindbool()funcț ia dacă
valoarea poate fi interpretată ca o valoare de adevăr.
Booleanii au, de asemenea, operatori. Aceș tia sunt diferiț i de operatorii pe care i-am văzut.
cu numere întregi ș i zecimale. Acestea sunt operatori Boolean.
Tabelul de adevăr OR
P Q P SAU Q
Adevărat Adevărat Adevărat
Adevărat Fals Adevărat
Fals Adevărat Adevărat
Fals Fals Fals
Ș I Tabelul adevărului
P Q PȘIQ
Adevărat Adevărat Adevărat
Adevărat Fals Fals
Fals Adevărat Fals
Fals Fals Fals
P NU P
Adevărat Fals
Fals Adevărat
Iată câteva exemple în Python
Adevărat sau Adevărat
Adevărat
AdevăratSauFals
Adevărat
FalssauFals
Fals
Adevărat ș iAdevărat
Adevărat
Adevărat ș i Fals
Fals
27
>>> notTrue
Fals
nuFals
Adevărat
Din nou, cunoaș terea acestor tabele de adevăr ca pe dosul mâinii tale este crucială.
Vei face faț ă acestor lucruri foarte des!
!= Nesemnal cu
< Mai puț in decât
>>>1==1
Adevărat
>>>1==2
Fals
>>>10!=4
Adevărat
>>>4!=4
Fals
>>>11>9
Adevărat
>>>13<23
Adevărat
>>>16<2
Fals
>>>13<13
Fals
>>>13<=13
True
Cred că ai înț eles ideea. Aș a că, să trecem la instrucț iunea if.
1.wants_drink = input("Do you want a drink with your meal? (yes or no): ")
2.ifwants_drink =="yes":
3. Aceasta va costa încă 1,50 £
Mul ț umesc! Poftă bună!
28
Dacă executăm codul de mai sus cu două tipuri diferite de intrare, putem obț ine două
rezultate diferite:
# UTILIZATORUL RĂSPUNDE DA
Vrei o băutură cu masa ta? (da sau nu): da
Aceasta va costa un supliment de 1,50 £
Mulț umesc! Poftă bună!
UTILIZATORUL RĂSPUNDE NU
Vrei o băutură cu masa ta? (da sau nu): nu
Mulț umesc! Poftă bună!
Codul de mai sus se citeș te destul de clar, aproape ca în engleză. Dacă utilizatorul spune
da pentru a dori o băutură, apoi imprimă că va costa mai mult.
dacă<CONDI Ț IE>:
Fă ceva dacă condiț ia evaluează la adevărat
Câteva lucruri importante de reț inut despre sintaxă. Este întotdeauna urmat de
condiț ia, apoi un două puncte (::). Pentru blocul de cod care urmează, acesta trebuie să fie
cu indentare!! Îmi place să folosesc taburi, totuș i poț i folosi spaț ii. În acest moment, mă duc
să-ț i spun să alegi un număr de spaț ii. Este obiș nuit să foloseș ti 4 spaț ii. Pentru taburi, 1
tab va fi suficient.
Programul de mai sus nu face nimic util, de fapt este complete gunoi dar este
arată sintaxa pentru instrucț iunile if destul de bine.
Orice lucru care este indentat după declaraț ia if este numit un bloc de cod.
Totul după instrucț iunile if, cum ar fimy_float = 4.3, va fi executat
indiferent denumărul_meufiind mai mic sau egal cu 10.
Probabil că vei face multe greș eli de sintaxă la început, noi toț i am făcut aș a.
nu lăsa să te descurajeze deloc, este complet normal. Chiar ș i cei mai
dezvoltatorii experimentaț i fac greș eli de sintaxă din când în când.
Deș i instrucț iunea if este utilă, ce ne facem dacă ne aflăm într-o situaț ie în care dorim
pentru a face un lucru dacă o condiț ie este îndeplinită, altfel, faceț i altceva? Următorul,
vom examina declaraț ia if-else.
29
4.3 - Declaraț ia if-else
În secț iunea anterioară, am învăț at cum să adăugăm un control de flux foarte basic.
programul nostru, totuș i, ne-am imaginat un scenariu în care am dorit să facem
altceva dacă condiț ia pentru declaraț ia if nu a trecut.
Este din nou destul de uș or de citit programul de mai sus. Când executăm programul de mai sus
programul ar putea avea două ieș iri diferite:
# SCENARIUL 1
Introduceț i-vă vârsta: 33
Puteț i intrare
La revedere
# SCENARIUL 2
Introdu vârsta ta: 14
Eș ti prea tânăr pentru a intra
La revedere
Sintaxa este din nou evidentă:
dacă<CONDI Ț IE>:
Fă ceva dacă condiț ia a fost adevărată
altfel:
Fă ceva diferit!
REAMINTEȘ TEȚI:
30
Adu-ț i aminte de capitolul despre numere întregi, unde aveam modulul (%) operator?
Pentru a-ț i reîntrema memoria, acest operator a returnat restul după împărț ire.
dacă numărul este par Ș I numărul este mai mic de 100 Ș I numărul este
mai mare de 50"
Putem chiar să-l simplificăm puț in. Îț i aminteș ti că ț i-am spus că valorile ar putea fi adevărate?
sau fals? Ei bine, să ne uităm din nou la programul nostru de numere pare.
1....
2.
[Link]ă (număr % 2) != 0:
4. Numărul tău a fost impar
5. altfel:
6. Numărul tău a fost par.
7.
8....
Reț ineț i că spunem dacă restul nu este egal cu zero în condiț ie.
31
4.4 - Declaraț ia If
Programele noastre devin acum un pic mai complexe ș i avem câteva
control decent, dar se comportă ca ș i cum ar exista doar două opț iuni. Ce dacă
au fost 3 sau mai multe opț iuni? Instrucț iunea if-else poate rezolva aceasta pentru noi!
dacă<condi ț ie1>:
Fă ceva
elif<condi ț ie2>:
Fă altceva
elif<condi ț ie3>:
Fă altceva
.
.
.
elif<condi ț ia N>:
Fă altceva
altfel:
Fă altceva
Putem avea atâtea declaraț ii elif câte ne plac.
32
4.5 - Instrucț iuni if imbricate
Acesta este un exemplu simplu, dar instrucț iunile conditionale îmbinate if...elif...else sunt folosite peste tot.
4.6 - Exerciț ii
Notă importantă:
Soluț iile pentru unele dintre aceste exerciț ii necesită să gândeș ti creativ.
Nu te aș tepta să ajungi imediat la o soluț ie!
Întrebarea 1
Scrie un program care ia trei intrări,a, bș icș i afiș ează dacă sau
nu acele numere formează un triunghi dreptunghic. Formula de care vei avea nevoie este
c=(√a2+b2)c=(a2+b2)
33
Întrebarea 2
Fizz buzz este un joc în care se aplică următoarele reguli:
Exemple:
1=1
2=2
3 = fizz
4=4
5 = buzz
6=6
.
.
15 = fizz-buzz
* Remember what I said about how if...elif..else statements are evaluated sequentially (first to last) until
prima condiț ie este îndeplinită
Întrebare 3
Scrie un program care primeș te ș ase numere,x1, y1, r1and x2, y2, r2(care sunt
coordonatele x ș i y ale centrului unui cerc ș i raza acestui cerc)
afişează dacă cele două cercuri se suprapun sau nu.
Vei avea nevoie de formula pentru distanț a între două puncte pentru a rezolva
acesta care este:
d(P,Q)=(√(x2−x1)2+(y2−y1)2))d(P,Q)=((x2−x1)2+(y2−y1)2))
Restul necesită o rezolvare a problemei! Poate că desenează scena pe hârtie ar putea
Ajutor?
34
Capitolul 5 - Buclă ș i Iteraț ii
Notă importantă:
Acest capitol poate fi cu mult mai provocator decât capitolele anterioare ș i acolo
este mult de înț eles aici.
# INSTRUCȚ IUNI IF
dacă<condi ț ie>:
Fă ceva
Ș i un alt lucru
BUCLE WHILE
while<condition>:
Fă ceva
Ș i un alt lucru
La fel ca în instrucț iunile if, <condiț ia> este o expresie Boolean. Corpul conț ine de asemenea
o secvenț ă de instrucț iuni. În mod similar, extensia corpului buclei este determinată de
indentarea declaraț iilor.
Modul în care funcț ionează, totuș i, este uș or diferit ș i operează în următorul mod:
35
8.
9.x = Adevărat #
10.în timp ce x ==Adevărat: # <- Evaluează expresia (evaluează la Adevărat)
11. print("Salut") #
12. x = False #
[Link]("x este acum fals") #
14.
15.-------------------------------------------------------------------------------
16.
17.x =Adevărat #
[Link] ==Adevărat: #
19. print("Salut") # <- Afi ș ează "Salut" în fereastra terminalului
20. x = False #
[Link]("x este acum fals") #
22.
23.-------------------------------------------------------------------------------
24.
25.x =Adevărat #
26.în timp ce x ==Adevărat: #
27. print("Salut") #
28. x = False # <- Atribuie False lui x (x con ț ine False)
[Link]("x este acum fals") #
30.
31.------------------------------------------------------------------------------
32.
33.x =Adevărat #
[Link]ă x ==Adevărat: #
35. print("Salut") #
36. x = False # <- Am ajuns la final, a ș a că re-evaluează condi ț ia
[Link]("x este acum fals") #
38.
39.
40.
41.x =Adevărat #
42.între timp x ==Adevărat: # <- Evaluează expresia (e ș uează, deci iese din buclă)
1.i = 0
2.în timp ce i < 5:
3. print(i)
4. i=i+1
5.
6.# IE Ș IREA
7.0
8.1
9.2
10.3
11.4
36
Acest lucru ar putea părea puț in confuz, dar permite-mi să explic ce se întâmplă. Variabila iis
numit un contor (sau o variabilă de bucle) ș i controlează de câte ori se repetă bucla
iterează.
Ce-ar fi dacă am avea condiț ia asi < 10000? Cele patru linii de cod ar rămâne totuș i
ț ineț i apăsat, iar programul va număra de la 0 la 9999.
Îț i aminteș ti că am spus că poț i considera memoria ca pe niste sertare? Ei bine, haideț i să luăm asta
example:
-------------------------------------
| | | | | Fiecare "cubi ț ă" este o *loca ț ie de memorie*
-------------------------------------
-------------------------------------
| | | | | Fiecare are o *adresă*
-------------------------------------
-------------------------------------
| 32 | 44 | 89 | 12 | # Să presupunem că acestea sunt umplute cu valori
-------------------------------------
-------------------------------------
| 32 | 44 | 89 | 12 | # Să spunem că adresa primului
location is 2
-------------------------------------
^
|
2
37
# ACEASTĂ FORMULĂ TREBUIE SĂ FIE GENERALĂ, AȘ A CĂ DACĂ AM DORI PRIMA LOCAȚ IE
ACEASTA AR FI: adresa_curentă + 0 (2 + 0 = 2 care este adresa primului
location)
De fapt, nu numărăm de la 0, începem indecș ii (la care vom ajunge mai târziu) cu 0. E...
este doar o practică bună să numărăm de la 0 în bucle ca aceasta, deoarece de obicei folosim o valoare precum
îi indexăm în liste (vom ajunge la acestea mai târziu) ș i recomand să te obiș nuieș ti cu ele acum.
Dacă asta te mai confuzează, va avea sens complet când ajungem la liste puț in mai târziu.
pe.
Este foarte rar să vezi contoare care încep de la ceva de genul 30 ș i unde contoarele fac.
începeț i cu un număr impar sau mare ca acestea, de obicei există un motiv foarte, foarte bun pentru
facând asta.
Să ne uităm la un alt exemplu. Vom scrie un program care permite utilizatorului să introducă 3
numere ș i le vom aduna ș i vom imprima rezultatul.
[Link] = 0
2.
3.i = 0
4.în timp ce i < 3:
5. total = total + int(input())
6. i += 1
[Link](total)
There are two patterns we usually follow when writingwhileloops. These are:
Fă-ceva-de-n-ori
2. Fă-atâta-timp-cât-nu-este-condi ț ie
Voi ajunge la al doilea model în câteva momente, dar pentru acum voi analiza primul model.
We have been using the first pattern in the previous examples which is as follows:
whilei<N:
Fă ceva
i+=1
În modelul de mai sus, cunoaș tem valoarea lui N înainte de a evalua condiț ia buclelor.
Poate că a venit de la input-ul utilizatorului sau poate fi rezultatul unor anterioare
calcul
38
Ca o convenț ie de denumire, este o practică bună să numeș ti contorul ca ș i cum ar fi ...
folosit ca un nume de variabilă undeva altundeva, atunci jork va face.
Iată un alt exemplu care poate părea că contrazice acest model la o gândire mai atentă
despre problemă, dar ce ar fi dacă am vrea să numărăm invers, aș a că în loc de 0, 1, 2,
am vrut 2, 1, 0 (Probabil te gândeș ti că ar trebui să facem doi = i - 1)?
Iată cum se face, dar utilizatorul introduce numărul de la care numărăm înapoi:
1.n = int(input())
2.
3.i = 0
4.în timp ce i < n:
5. print(n - i - 1)
6. i += 1
Să aruncăm o privire asupra celui de-al doilea model de bucle, modelul „Fă-în timp ce-nu-condiț ie”. Cu
nu ș tim de câte ori vom merge în jurul buclei înainte de a
încheie.
Presupunem că utilizatorul introduce numere de câte ori doreș te, nu ș tim cât de multe.
încă o dată, iar condiț ia noastră este că nu pot introduce un număr negativ:
[Link] = int(input())
2.
3.în timp ce numărul nu este mai mic decât 0:
4. printaț i(numărul)
5. number = int(input())
[Link]("A ț i introdus un număr negativ")
Pentru a rezuma:
39
Notă importantă:
În aceeaș i secț iune voi discuta despre două noi instrucț iuni. Instrucț iunea break ș i
declaraț ia continuă. Există o mică dezbatere cu privire la când ș i unde ar trebui să
folosiț i-le ș i care este cea mai bună practică în legătură cu utilizarea acestor declaraț ii, dar voi vorbi
despre asta un pic mai târziu în această secț iune.
Instrucț iunea break este folosită pentru a ieș i din buclă sărind peste restul codului buclei.
bloc fără a testa condiț ia pentru buclă.break întrerupe fluxul de
program prin întreruperea buclei ș i continuă să execute restul tău
program.
while<condi ț ia1>:
# Declaraț ii
dacă<condi ț ie2>:
pauză
# Mai multe declaraț ii
# Restul programului
Iată un exemplu de asta în acț iune:
[Link] = 10
2.
3.i = 0
4.cât timp i < număr:
5. ifi == 5:
6. pauză
7. print(i)
8. i += 1
[Link]("Ie ș irea din program")
10.
11.# IEȘ IRE
12.0
13.1
14.2
15.3
16.4
17. Ieș irea din program
Cred că este destul de auto-explicativ cum funcț ionează break, aș a că să aruncăm o privire la
declaraț ia continuă.
40
Declaraț ia continue este utilizată pentru a sări peste declaraț iile rămase din corpul
loop ș i începe următoarea iteraț ie a buclei. Spre deosebire de
instrucț iunea de întrerupere, continua nu termină bucla, ci pur ș i simplu sare înapoi la
începe.
[Link] = 5
2.
3.i = -1
4.în timp ce i < număr:
5. i += 1
6. ifi == 2:
7. continua
8. print(i)
[Link]("Ieşirea din program")
10.
11.# IEȘ IRE
12.0
13.1
14.3
15.4
[Link]şirea din program
Observaț i cum acest lucru a deranjat modelul nostru de buclă, deoarece a trebuit să punem i += 1.
prima declaraț ie ș i a trebuit să o iniț ializăm la -1.
Acum acesta este un caz trivial, dar are utilizările sale. Să ne uităm când ș i unde acestea
declaraț iile ar trebui să fie folosite. Deocamdată, totuș i, recomand evitarea lor ș i nu
foloseș te-le ca o cârjă pentru a ieș i dintr-un ciclu. În cea mai mare parte, în această carte, dacă găseș ti
tu însuț i folosind aceste afirmaț ii de obicei există ceva greș it cu bucla ta ș i
ar trebui să te gândeș ti la problemă puț in mai mult.
Când sunt utilizate la începutul unui bloc de cod al unui ciclu, ele acț ionează ca precondiț ii.
precondiț ia este o condiț ie impusă asupra cuiva (ciclul, funcț ia etc.) care trebuie să
se menț ine adevărat la începutul acelui „ceva” pentru a funcț iona corect.
Când sunt plasate la sfârș itul blocului de cod al buclei, acestea acț ionează ca postcondiț ii.
postcondiț ia este o condiț ie impusă asupra unui lucru care trebuie să fie adevărată după
execuț ia acelui „ceva” pentru a fi mulț umit că a fost executat corect.
Acum, acesta următorul ar putea fi puț in confuz, aș a că nu te încurca prea mult în el, eu sunt
Punându-l aici pentru completitudine.
41
Aceste afirmaț ii pot fi folosite ș i ca invarianti, în special, invarianti de buclă. Un
invariant este o afirmaț ie care este plasată într-un segment de cod care este repetat (buclă pentru
exemplu) ș i ar trebui să fie adevărat de fiecare dată despre buclă. Invarianț ii sunt adesea folosiț i în
bucle ș i recursie (despre care vom vorbi mai târziu).
Această parte poate fi confuză. Dacă un invariant este plasat la începutul unui ciclu while
carea condiț iei nu schimbă starea calculului (adică, nu are efecte secundare
efecte), atunci invariantul ar trebui să fie adevărat ș i la sfârș itul buclei. Când este folosit în
programarea orientată pe obiecte (la care vom ajunge mai târziu), invarianț ele pot face referire la
starea unui obiect.
Exemplul 1
Primul exemplu de problemă este să verificăm dacă un număr dat este un număr prim, presupunând
numărul dat este mai mare sau egal cu 2. Iată codul:
1.n = int(input())
2.
3.i = 2
[Link] < n ș i (n % i) != 0:
5. i += 1
[Link] < n:
7. Numărul tău nu este un număr prim
[Link]:
9. Numărul tău este un număr prim!
Încercă să înț elegi de ce am instrucț iuni if/else, lucrând la asta pe o foaie de hârtie
cu cifre mici.
Exemplul 2
Următorul exemplu va fi o extensie a programului Fizz-Buzz pe care l-ai
scris înainte. Totuș i, există o mică schimbare. Ultima dată ai scris un program care
afiș ează numărul, fizz, buzz sau fizz-buzz pentru un număr dat. În această rundă, voi merge la
scrie un program care afiș ează secvenț a până la un număr dat.
1.n = int(input())
2.
3.i = 1
[Link] < n:
5. dacă i % 3 == 0 ș i i % 5 == 0:
6. print("fizz-buzz")
7. elifi // 3 == 0:
42
8. print("fizz")
9. elifi // 5 == 0:
10. print("buzz")
11. altfel:
12. print(i)
13. i += 1
Observaț i ordinea în care sunt scrise instrucț iunile if/elif/else. Deoarece în Python instrucț iunile sunt
executate secvenț ial, trebuie să verificăm că numărul nu este divizibil atât cu 3 cât ș i cu
5 mai întâi.
Exemplu 3
În acest program exemplu, vom scrie un program care permite utilizatorului să
introduceț i continuu numere până când introduc numărul 0. Când introduc ei
numărul 0, vom imprima totalul tuturor celorlalte numere pe care le-au introdus.
[Link] = int(input())
2.
[Link] = 0
4.până când numărul nu este 0:
5. total += număr
6. number = int(input())
[Link](total)
Dacă acum te simț i puț in mai confortabil cu buclele while, atunci să aruncăm o privire la câteva
probleme de rezolvat pentru tine!
5.5 - Exerciț ii
Notă importantă:
Aceste exerciț ii sunt mai dificile, aș a că gândeș te-te cu atenț ie la soluț iile tale.
Întrebare 1
Scrie un program care afiș ează primele n numere din secvenț a Fibonacci.
Secvenț a Fibonacci este definită ca:
43
Adică, următorul număr din secvenț ă este suma celor două numere anterioare ș i
primele două numere din secvenț ă sunt 0 ș i 1. O parte din secvenț ă este afiș ată
mai jos:
Întrebare 2
Scrie un program care afiș ează o secvenț ă asemenea celei prezentate mai jos. Numărul de
stelele din partea cea mai lată ar trebui să fie egale cu numărul introdus de un utilizator:
# INPUT
7
# IEȘ IRE
*
**
***
****
*****
******
*******
******
*****
****
***
**
*
Întrebarea 3
Scrie un program Python care citeș te un singur întreg de la utilizator. Apoi citeș te un ...
număr necunoscut de întregi, fiecare dată tipărind dacă numărul a fost sau nu
mai mare sau mai mic decât precedentul. Poț i presupune că fiecare număr este diferit ș i
poț i opri când numărul introdus este 0. Iată un exemplu de input ș i output:
# INPUT
5
2
9
7
0
# OUTPUT
mai jos
mai înalt
mai jos
Ieşire...
44
Capitolul 6 - Ș iruri
6.1 - Introducere în ș iruri
În acest capitol, vom analiza mai bine ș irurile. Ne-am întâlnit cu ele
de mai multe ori în carte ș i ș tim că acestea reprezintă date textuale.
În Python, reprezentăm ș irurile de caractere ca o secvenț ă de caractere închise între " " sau '
. De exemplu:
Python oferă de asemenea un set mare de operaț iuni, metode ș i funcț ii pentru
lucrând cu ș iruri, unele dintre care ne vom întâlni mai târziu în acest capitol.
Lucrul cu ș iruri în Python este de asemenea destul de uș or în comparaț ie cu altele
limbi.
print() converteș te fiecare dintre argumentele sale în ș iruri de caractere, introduce un caracter de spaț iu în
ieș irea între fiecare dintre argumentele sale ș i apoi adaugă un caracter de linie nouă
ș i scrie rezultatul în ieș irea standard (în cazul nostru, fereastra terminalului).
IEȘ IRE
„Asta ș i aia”
În codul de mai sus, fiecare dintre ș iruri este un argument ș i poț i avea cât mai multe
atâtea argumente cât vrei (vom examina argumentele în detaliu mai târziu în
capitolul funcț iilor).
45
Special CharacterMeaning
\n Linie nouă
\r Întoarcere la linie
Tab
Ș i iată ce fac ei:
Salut Lume
Bună
Lume
Mere Portocale
Mere Portocale
The\t adaugă un tab, acesta\nse va muta pe un nou rând ș i\rva lua esenț ial
orice vine după acesta ș i suprascrie orice vine înaintea lui până la
lungimea oricărui lucru care vine după el. Nu te îngrijora prea mult, am doar
l-am întâlnit de câteva ori.
Probabil nu vom întâlni din nou caracterele tab sau carriage return.
pe parcursul acestei cărț i, dar vreau să te atenț ionez cu privire la caracterul de linie nouă. Doar
pentru că nu poț i vedea asta nu înseamnă că nu este acolo aș a că, dacă te confrunț i vreodată cu
ieș ire neaș teptată caracterul de linie nouă ar putea fi cauza! Dar vom de asemenea
uita-te la cum să te ocupi de asta un pic mai târziu.
Există, de asemenea, un ș ir special numit ș irul gol. Acesta este reprezentat ca "".
MethodWhat it does
len() returnează lungimea ș irului
str() Returnează reprezentarea sub formă de ș ir a unui obiect
chr() Converteș te un întreg într-un caracter
ord() Converte ș te un caracter într-un număr întreg
Să le vedem în acț iune:
>>>len("Bună")
5
>>>len("Salut\nLume") Numărul de caractere newline!
11
46
>>>str(5+5)
10
>>>chr(65)
'A'
>>>ord("B")
66
len() ș i str() funcț ionează aș a cum ne aș teptăm. Convertim un tip într-o ș ir de caractere folosind
funcț ia thestr()
La cel mai elementar nivel, calculatoarele stochează informaț ii sub formă de numere. Pentru a reprezenta
Cel mai simplu dintre aceste scheme se numeș te ASCII, de care s-ar putea să fi auzit.
reprezintă Codul Standard American pentru Schimbul de Informaț ii ș i acesta acoperă
caracterelor latine obiș nuite cu care probabil eș ti obiș nuit să lucrezi.
tipuri diferite.
[Link]ă(<argumente>)
Să analizăm câteva dintre cele mai frecvent utilizate metode de manipulare a ș irurilor:
Metodă Semnificaț ie
[Link]() returnează o copie a s cu primul caracter scris cu majusculă
[Link]() returnează o copie a s cu prima literă a fiecărui cuvânt capitalizată
[Link]() returnează o copie a s cu to ț i caracterii alfabetici scri ș i cu majuscule
returnează o copie a cărei toate caracterele alfabetice sunt convertite în
[Link]âț eș te()
litere mici
returnează True dacă sis nu este gol ș i toate caracterele sale sunt
[Link]()
alfanumeric (litere ș i cifre) ș i Fals în caz contrar.
returnează True dacă isis nu este gol ș i toate caracterele sale sunt alfabetice
[Link]()
ș i Fals în caz contrar
47
Metodă Semnificaț ie
returnează True dacă sis este non-vid ș i toate caracterele sale pot fi convertite
[Link]() la numere întregi ș i Fals în alte cazuri
returnează o copie a swith cu spaț iul alb pe partea stângă ș i
[Link]()
partea dreaptă eliminată
returnează o copie a lui cu spaț iul alb pe partea stângă
[Link]()
eliminat
returnează o copie a swith cu spaț iul alb pe partea dreaptă
[Link]()
eliminat.
Să ne uităm la acestea în acț iune:
Acesta este un ș ir
>>>[Link]()
Aceasta este o ș ir
Aceasta este o ș ir
>>>s.MAI_MARE()
ACEASTA ESTE UN STRING
76324
>>>s.este_cifra()
Adevărat
48
Aceasta este un ș ir
-------------------------------
BUNĂ Fiecare locaț ie de memorie conț ine un caracter
-------------------------------
-------------------------------
BUNĂ Fiecare locaț ie are, de asemenea, o adresă
-------------------------------
| | | | |
13 14 15 16 17 Acestea sunt adrese ipotetice
-------------------------------
BUNĂ Putem obț ine adresa lui 'E' ca 13 + 1
------------------------------- # La fel pentru 'H' ca 13 + 0
| | | | |
13 14 15 16 17
49
Putem indexa ș iruri într-un mod similar! Sintaxa pentru indexarea într-un ș ir este la fel
următoarele:
Bună
>>>s[0]
H
>>>s[1]
e
>>>s[2]
l
>>>s[3]
"l"
>>>s[4]
o
>>>s[5]
Urmează următoarea eroare (cea mai recentă apelare ultima):
Fiș ier "<stdin>", linia 1, în <modul>
IndexError: index de ș ir în afara limitelor
Observaț i că în ultima linie încercăm să indexăm un ș ir la poziț ia 5, dar primim
o eroare de index ș i ni se spune că indexul este în afara intervalului. Aceasta se datorează faptului că noi
Indecș ii de ș iruri pot fi, de asemenea, numere negative ș i vor specifica locaț ii relative
până la sfârș itul ș irului.
Bună
>>>s[-1]
o
>>>s[-2]
l
>>>s[-3]
l
>>>s[-4]
e
>>>s[-5]
H
123B U NĂ # String
0 1 2 3 4 # Indici pozitivi
-5-4-3-2-1 # Negative indices
Recapitulare pentru această secț iune:
50
6.5 - Imutabilitate
În Python, fiecare variabilă deț ine o instanț ă a unui obiect ș i există două
tipuri de obiecte, mutable ș i imutabile. Până acum, am avut doar
tipuri imutabile, adică întregi, float-uri, bool-uri ș i ș iruri. Un obiect fiind
imitabil înseamnă că valoarea sa nu poate fi schimbată odată creată.
10=3
True=False
SalutLume
Acest lucru nu ar avea niciun sens ș i e probabil destul de evident de ce. Totuș i,
acum că ș tim despre indexarea ș irurilor, a face ceva precum:
s="string"
s[0]="b"
Aceasta ar putea părea rezonabil. Cu toate acestea, nu este ș i există un motiv bun pentru asta.
Ce ar fi dacă am încerca ceva de genul:
s="string"
s[0]="bl"
Acum, asta ar putea părea razonabil, dar aminteș te-ț i cum sunt stocate ș irurile în
memorie. Când sunt create, au o lungime ș i încercarea de a schimba aceasta
o lungime precum cea de mai sus ar cauza probleme la un nivel inferior (nu că nu ar putea fi...
gata, pur ș i simplu nu merită în 99% din cazuri). Făcând ș irurile de caractere tipuri imutabile
creș te performanț a ș i securitatea, dar nu te îngrijora de asta pentru acum. Doar
ș tii că nu poț i schimba valoarea unui ș ir odată ce a fost creat.
Pentru a înț elege mai bine cum sunt stocate ș irurile în memorie ș i cum
sunt menț ionaț i, uitaț i-vă la codul de mai jos, apoi la diagrama care urmează.
a="Hello"
b=a
a="World"
51
Din prima parte a diagramului, am spus mai devremeunconț ine "Bună", totuș i
asta nu este cazul. Asta a fost pentru simplitate. Ce se întâmplă, de fapt, este că, Python
menț ine un spaț iu de nume de mapări între variabile ș i obiectele la care se referă.
Dupăa = "Hello" este executat, o mapare de laala valoareBunăeste adăugat
în spaț iul de nume.a acum punctează locaț ia din memorie care deț ine valoarea
„Bună”. Spunem căunconț ine o referire la valoareBunăstocat în
memorie.
Când liniab = aeste executat, ceea ce se întâmplă este,bacum indică la acelaș i lucru
locaț ie de memorie carea points to and when a = "World" este executat, un nou
instanț a de ș ir este creată ș i salvată într-o nouă locaț ie de memorie ș i
locaț ie careopunctele sunt actualizate.
Prin urmare, acest comportament este ceea ce face ca ș irurile să fie imutabile. Încercaț i să obț ineț i un
52
Ce ar fi dacă am dori să obț inem caracterele de la prima la a treia poziț ie a
ș irBunăde exempluHel.
Ei bine, putem! Folosim felierea pentru a face acest lucru. Felierea funcț ionează foarte asemănător cu indexarea.
în schimb, mai degrabă decât să specificăm doar indexul de început, oferim ș i indexul de sfârș it
vrem.
Bună
<<<<s[0:3]
Hel
>>>s[0:1]
'H'
Sintaxa este:ș ir[ <început> : <sfârș it> ]
Observaț i cum funcț ionează tăierea. Folosind primul exemplu, tăierea returnează un nou
ș ir cu totul dinsla indexul de început, până la, dar fără a include
indice de sfârș it.
Dacă am vrut totul după prima literă îns, putem omite indexul de sfârș it.
De asemenea, putem omite primul index ș i lăsa indexul final, ceea ce ne va oferi
totul de la indexul 0 până la indexul final specificat
>>>s="Hello"
>s[1:]
salut
>>>s[:3]
Hel
We can also omit both indexes, in which case we'll get the entire string
returned:
Bună
>>>s[:]
Bună
Reț ineț i că două puncte trebuie să rămână în orice caz.
>>>first=2
>>>last=4
Salut
>>>s[first:last]
'll
Indicii pot fi de asemenea numere negative ș i vor specifica locaț iile în raport cu
sfârș itul ș irului:
53
>>> s = "Hello"
>>> s[:-1]
Iad
>>> s[-4:]
Python oferă, de asemenea, secț ionare extinsă pentru ș iruri. Acest lucru adaugă un al treilea parametru
The+ operatorul se numeș te operator de concatenare ș i este folosit pentru a unea ș iruri de caractere
împreună.
>>>s1="Hello"
>>>s2="World"
>>>s1+s2
SalutLume
The* operatorul se numeș te operator de replicare ș i este utilizat pentru a replica un
ș ir.
Bună
>>>s*3
BunăBunăBună
Aceș ti operatori au, de asemenea, o prioritate asociată cu ei:
Aceasta este un ș ir
>>>s+' '*3
Aceasta este un ș ir '
>>> (s + ' ') * 3
Aceasta este un ș ir Aceasta este un ș ir Aceasta este un ș ir
54
Există ș i un alt operator special numitînoperator. Acest lucru va returna un
Boolean bazat pe faptul că un substring este conț inut într-un ș ir.
Aceasta este un ș ir
"Acesta"ins
Adevărat
„ Asta” e
Fals
Uneori vrem ca rezultatul nostru să arate bine ș i să aibă o lizibilitate mai bună. Să ne
uita-te la un exemplu cu lizibilitate proastă.
1.i = 0
2.în timp ce i < 12:
3. print(i, '* 15 = ', i * 15)
4. i += 1
5.
6.# IE Ș IRE
7.0 * 15 = 0
8.1 * 15 = 15
9.2 * 15 = 30
10.3 * 15 = 45
11.4 * 15 = 60
12.5 * 15 = 75
13.6 * 15 = 90
14.7 * 15 = 105
15.8 * 15 = 120
16.9 * 15 = 135
17.10 * 15 = 150
18.11 * 15 = 165
Putem observa că pe măsură ce numerele devin mai mari în ieș ire, spaț ierea
devine oprit ș i liniile încep să iasă în evidenț ă. Vom analiza cum să facem acest lucru să arate
frumos un pic mai târziu în această secț iune.
Pentru a obț ine o formatare mai bună a ieș irii, folosimformat()operator. Acesta
operatorpreparesa ș ir pentru imprimare.
55
elementele de date care vor fi inserate în fiecare loc de rezervă ș i formatate
conform comenzilor de format ale placeholder-ului.
Sintaxa generală pentru comanda aformat este{[: <aliniere> <lăț ime minimă>
<.precision> <type>]} unde parantezele pătrate indică parametrii opț ionali.
>>>pi=3.14159265359
>>>print('{:.3f}'.format(pi))
3.142
Să descompunem comanda de formatare aici ({:.3f}).
>>>pi=3.14159265359
>>>e=2.71828182845
Numărul pi este: {:.3f} ș i numărul e este {:.5f}
Numărul pi este: 3.142 ș i numărul e este 2.71828
Primul argument care trebuie formatat este asociat cu primul loc de înlocuire ș i
al doilea argument pentru al doilea marcaj ș i aș a mai departe.
1.e = 2.71828
2.
3.i = 0
4.în timp ce i < 6:
5. print('{:.{}f}'.format(e, i))
6. i += 1
7.
8.# IE Ș IRE
9.3
10.2.7
11.2.72
12.2.718
13.2.7183
14.2.71828
O altă opț iune pe care o avem pentru comanda format este lăț imea minimă.
Putem folosi această lăț ime minimă pentru a rezolva problema pe care am avut-o cu ieș irea
din tabla înmulț irii cu 15.
56
1.i = 0
2.în timp ce i < 12:
3. print('{:2d} * {:2d} = {:3d}'.format(i, 15, i*15))
4. i += 1
5.
6.# IE Ș IRE
7.0 * 15 = 0
8.1 * 15 = 15
9.2 * 15 = 30
10.3 * 15 = 45
11.4 * 15 = 60
12.5 * 15 = 75
13.6 * 15 = 90
14.7 * 15 = 105
15.8 * 15 = 120
16.9 * 15 = 135
17.10 * 15 = 150
18,11 * 15 = 165
Să ne uităm la exemplul cu stea, aceasta nu este în niciun caz o soluț ie bună, este pur ș i simplu
pentru a arăta utilizarea comenzii de formatare a aliniamentului:
1.i = 0
2.între timp i < 6:
3. print('{:^10s}'.format('* '*i))
4. i += 1
5.
6.i -= 2
7. în timp ce i > 0:
8. print('{:^10s}'.format('* '*i))
9. i -= 1
10.
11.# IEȘ IRE
12. *
13.* *
14.* * *
15.* * * *
16.* * * * *
17.* * * *
18.* * *
19.* *
20. *
După cum puteț i vedea în comanda de formatare, specificăm ș irul care trebuie centrat
cu o lăț ime minimă de 10 ș i tipul să fiescare este un ș ir.
57
6.9 - Exercitii
NOTĂ IMPORTANTĂ:
Nu pot să-ț i arăt tot ce există despre python. Cartea ar continua la nesfârș it.
O abilitate cu adevărat importantă pe care o au toț i programatorii buni este capacitatea de a ș ti ce
să caute atunci când se confruntă cu o problemă pe care nu o pot rezolva singuri. Pentru
de exemplu, s-ar putea să vreau să pot face ceva cu un ș ir, dar nu ș tiu
cum. Ș tiind unde să cauț i pentru a afla răspunsul este foarte important. Tu
s-ar fi putut să fi dat peste un site numit Stack Overflow până acum. Acesta este
va fi o resursă foarte bună pentru tine. Prin urmare, unele dintre întrebările în
aceste exerciț ii pot necesita să cauț i metode care să te ajute
ajungeț i la soluț ia dvs.
Există multe de învăț at din acest capitol. Ș irurile sunt importante ș i sunt folosite în tot timpul
timp. A deveni confortabil cu ele este la fel de important.
Întrebare 1
Scrieț i un program care ia ca input un singur număr întreg de la utilizator care va
specificaț i câte zecimale are numărulear trebui să fie formatat la.
Ia un număr de 2.7182818284590452353602874713527
EXEMPLU DE ÎNTRARE
4
# EXAMPLE OUTPUT
2.7183
Întrebarea 2
Scrie un program care va lua ca input, un ș ir de caractere ș i două numere întregi. Cele două
numerele întregi vor reprezenta indicii. Dacă ș irul poate fi tăiat folosind cei doi indici,
atunci tipăriț i ș irul feliat. Dacă oricare dintre cele două numere întregi este în afara ș irurilor
interval de index, apoi tipăriț i că ș irul nu poate fi tăiat la acele întregi.
# EXAMPLE INPUT
Aceasta este ș irul meu
2
9
# EXAMPLE OUTPUT
58
este asta m'
EXEMPLU DE INPUT
Aceasta este un ș ir
10
22
Întrebarea 3
Când te înscrii pentru conturi pe site-uri web sau aplicaț ii, s-ar putea să ț i se spună că
puterea parolei atunci când o introduceț i pentru prima dată. În acest exerciț iu, sunteț i
să scrieț i un program care ia ca intrare, un ș ir care va reprezenta un
parolă.
• cifre
• litere
mici
• LITERE MARI
• caractere speciale (consideraț i acestea ca fiind: $, #, @ ș i ^)
Punctajul unei parole ar trebui să fie evaluat în funcț ie de câte dintre categoriile de mai sus
sunt conț inute în parolă. Parola ar trebui să primească un scor de la 1 la
4.
Dacă parola este mai mare sau egală cu puterea 3 (conț ine caractere din)
3 dintre categoriile de mai sus) atunci ar trebui să imprimi puterea ș i că
parola este validă. În caz contrar, afiș aț i puterea ș i că parola nu este
valid.
# EXEMPLES DE ENTRÉES
978
hjj
jKl
nmM2
r@num978LL
LLLL
# EXAMPLE OUTPUTS
1
59
1
2
3
4
1
Întrebarea 4
Scrie un program care ia 3 numere cu virgulă mobilă ca input de la utilizator: a
raza de început, incrementul razei ș i o rază de sfârș it. Pe baza acestor trei
numere, programul tău ar trebui să afiș eze un tabel cu sfere corespunzătoare
suprafaț ă ș i volum.
A = 4πr2A = 4πr2
V=43πr3V=43πr3
EXEMPLU DE INTRARE
1
1
10
# EXEMPLU DE IEȘ IRE
Radii Arie Volum
---------- ---------- ------------
1.0 12.57 4.19
2.0 50.27 33.51
3.0 113,10 113.10
4.0 201.06 268.08
5.0 314,16 523,60
6.0 452,39 904.78
7.0 615.75 1436.76
8.0 804.25 2144.66
9.0 1017.88 3053,63
10.0 1256.64 4188.79
60
Capitolul 7 - Căutare liniară
7.1 - Ce este căutarea liniară?
În acest capitol vei codifica primul tău algoritm. Vom analiza
algoritmul de căutare liniară.
Căutarea liniară (sau căutarea secvenț ială) este o metodă de a găsi un element în
ceva. Acea ceva poate fi un ș ir, un fiș ier sau o listă. Elementul pe care îl suntem
caută orice ar putea fi (o literă, un număr, un cuvânt, etc).
eu=0
în timp ceeu< Nș i nuP:
eu+=1
Ce facem aici este să începem de la index 0 ("H") ș i să continuăm prin ș irul de caractere,
verificând fiecare index până când se găseș te 'W' ș i aceasta este căutarea liniară.
61
Acum avem o altă problemă. Există două condiț ii în bucla while.
Fie "W" este găsit ș i ieș im din buclă, fie căutăm întreaga ș ir de caractere ș i
"W" nu a fost găsit. Cum ș tim ce condiț ie a cauzat loop-ul să
termina?
Dacă condiț ia 1 (i < len(s)) esteAdevaratatunci "W" a fost găsit deoarece clar nu am
ajunge la sfârș itul ș irului SAU condiț ia 1 esteFalsîn care am ajuns
sfârș itul ș irului ș i "W" nu a fost găsit.
Asta este de obicei cum funcț ionează căutarea liniară; totuș i, putem avea mai mult
versiuni complicate la care vom ajunge în secț iunea următoare.
7.3 - Exemple
Notă importantă:
În această secț iune, voi trece prin câteva exemple suplimentare de căutare liniară.
folosind bucle while, unele dintre ele pot deveni un pic complicate, aș a că petreceț i ceva
timp trecând prin ele.
1.s = input()
2.
3.i = 0
[Link] i < len(s) ș i s[i] == " ":
5. i += 1
6.
7. dacă < len(s):
[Link](s[i:])
[Link]:
[Link]("Nu există caractere alfanumerice în acest ș ir")
62
Programul de mai sus va elimina toate caracterele de spaț iu alb de la început.
Acesta este un ș ir
# IESIRE
Acesta este greu de rezolvat ș i îmi amintesc că am primit această problemă când eu
învăț a să programeze. Pentru a rezolva această problemă, va trebui să utilizăm bucle while imbricate
în interiorul unul altuia.
1.s = input()
[Link] = ""
3.
4.i = 0
5.în timp ce i < len(s):
6. Găseș te un caracter non-spaț iu (începutul unui cuvânt)
7. în timp ce i < lungimea(s) ș i s[i] == " " :
8. i += 1
9.
10. j=i
11. dacă < len(s):
12. Găseș te sfârș itul acelui cuvânt
13. while j < len(s) and s[j] != " ":
14. j += 1
15.
16. Construieș te un ș ir din original fără spaț iile suplimentare.
17. output +=" "+ s[i:j]
18.
19. i=j+1
20.
21.
22.#Tipăriț i ș irul final
[Link](output[1:])
7.4 - Exerciț ii
Notă importantă:
Soluț iile pentru unele dintre aceste exerciț ii necesită gândire creativă.
Nu te aș tepta să ajungi la o soluț ie imediat!
63
Întrebarea 1
Write a program that takes a string from the user and prints the first number
întâmpinat împreună cu poziț ia sa.
# EXAMPLE OUTPUT
7 16
# EXAMPLE INPUT
Nu sunt cifre aici
#EXAMPLE OUTPUT
Niciun digit în ș ir
Întrebarea 2
Construind pe exerciț iul anterior, scrieț i un program care primeș te un ș ir ca
input de la utilizator ș i afiș ează primul număr întâlnit împreună cu
poziț ia de început a numărului.
1208 17
EXEMPLU DE ÎNTRARE
64
# EXAMPLE OUTPUT
Niciun număr în ș ir
Întrebarea 3
Write a program that takes a string as input from the user. The string will
consta din cifre ș i programul tău ar trebui să imprime prima repdigit. A
Numărul repdigit este un număr în care toate cifrele sunt aceleaș i. Exemple de
numerele repetate sunt 22, 77, 2222, 99999, 444444. De asemenea, poț i presupune că fiecare
numărul va avea cifre diferite, cu excepț ia cazului în care este un repdigit.
# EXAMPLE INPUT
34 74 86 34576 47093 3 349852 777 9082
777
# EXAMPLE INPUT
98 3462 245 87658
Niciun repdigit în ș ir
Întrebarea 4
Dacă deschizi un browser ș i mergi pe orice pagină web care are text pe ea ș i apesi
Ctrl+f, o casetă de căutare va apărea. Poț i să scrii orice cuvânt în această casetă de căutare ș i
toate apariț iile acelui cuvânt de pe pagină sunt evidenț iate. Acest lucru nu foloseș te
linear search; it uses something called regular expressions (don't worry about
ce sunt). La fel ca apariț iile cuvântului fiind evidenț iate, tu
de asemenea, li se spune de câte ori apare cuvântul.
Trebuie să scrii un program care mimează acest comportament. Programul tău ar trebui să
ia un ș ir ca input de la utilizator ș i apoi un al doilea ș ir ca input care este
cuvântul pe care utilizatorul doreș te să-l caute. Programul tău ar trebui să imprime cum
de multe ori cuvântul apare în ș ir.
65
căutare ș i căutând <- poț i considera aceasta ca 2 apariț ii
# EXEMPLU DE INPUT
În acest tip de căutare, se face o căutare secvenț ială peste toate elementele unul câte unul.
unu
căutare
# EXAMPLE INPUT
Nu va fi o întâmplare aici
python
66
Capitolul 8 - Liste
Notă importantă:
Doar un avertisment, este mult de acoperit în acest capitol ș i poate deveni destul de
tehnic în anumite locuri (în special secț iunea 8.4) aș a că acordaț i o atenț ie deosebită acestuia
secț iune, este foarte important!
Cel mai simplu tip de listă este lista goală ș i este reprezentată ca[]Gol
list isfalsey
>>>lista_gol=[]
>>>lista_vide==Fals
Adevărat
Într-o listă, elementele sunt separate prin virgule.
lista_mea=[1,2,3,654,7]
Această listă conț ine 5 elemente.
În Python, o listă este un tip de colecț ie, ceea ce înseamnă că poate conț ine mai multe obiecte.
(ș iruri, întregi, etc..) dar să fie tratate în continuare ca un singur obiect.
Listele sunt de asemenea un tip de secvenț ă, ceea ce înseamnă că fiecare obiect din colecț ie ocupă
o locaț ie numerotată specifică în interiorul său (ceea ce înseamnă că elementele sunt ordonate).
Listele sunt de asemenea iterabile, astfel încât putem itera prin elementele lor folosind indici.
67
Cu toate acestea, ele diferă în două moduri semnificative:
• O listă poate conț ine obiecte de tipuri diferite, în timp ce un ș ir poate doar
conț ine caractere
• O listă este un tip mutabil (Vom ajunge la asta mai târziu).
>>>my_list=[23,543,"hi"]
>>>len(my_list)
3
Avem de asemenea trei alte funcț ii destul de importante, acestea
suntsuma(), min()ș imax()ș i funcț ionează aș a cum te aș tepț i.
>>>my_list=[1,2,3,4,5,6]
>>>sum(lista_mea)
21
min()and max()de asemenea, lucrează cu ș iruri, deoarece ș irurile au un ordonare lexicografică
ordonare, 'a' fiind minimul ș i 'z' fiind maximum:
>>>my_list=[6,324,456,2,6574,-452]
>>>max(my_list)
6574
>>>min(lista_mea)
-452
>>>min("string")
'g'
>>>max("string")
't'
De asemenea, putem sorta o listă folosindordonat()funcț ie. Cesortat()funcț ia funcț ionează
prin conversia unei colecț ii într-o listă ș i returnarea listei sortate.
>>>student_grades=[88,23,56,75,34,23,84,63,52,77,96]
>>>sorted(student_grades)
[23,23,34,52,56,63,75,77,84,88,96]
În informatică, căutarea ș i sortarea sunt două probleme mari ș i sunt
subiecte importante.
Putem adăuga ș i elimina elemente de la sfârș itul unei liste. Adăugarea este a adăuga
and pop is remove. We can do this because lists aremutable.
>>>lista_mea=[1,5,8]
>>>my_list.append(99)
>>>lista_mea
[1,5,8,99]
68
>>>my_list.pop()
99
>>>lista_mea
[1,5,8]
>>>my_list.pop(2)
5
>>>lista_mea
[1,8]
Observaț i că atunci când eliminăm, ne este returnat numărul pe care l-am eliminat. Implicit,
dacă nu sunt trimise argumente laelimină()atunci ultimul element este eliminat. Putem
de asemenea, trimiteț i un index lapop()ș i va scoate elementul de la acel index
ș i returnaț i-l nouă.
Putem stoca valoarea care este returnată după apelareapop()într-o altă variabilă
>>>my_list=[1,5,9]
>>>x=my_list.pop()
>>>x
9
Dacă avem o listă de ș iruri sau caractere, le putem alătura folosind
thealătură-te()funcț ie:
>>>my_list=["O","r","a","n","g","e","s"]
"".join(my_list)
Portocale
Ș irul înainte de funcț ia de unire se numeș te ș ir de unire ș i este ceea ce va
fii între fiecare element al listei atunci când le alături. În acest caz
nu vrem nimic (ș irul gol).
Cu toate acestea, dacă am avea cuvinte, am putea dori să le unim împreună cu spaț ii:
>>>my_list=["Hello","World.","This","is","a","string."]
>>>' '.join(my_list)
Salut Lume. Aceasta este un ș ir.
Nota laterală:
69
8.3 - Indatarea listelor
>>>my_list=[3,5.64,"Hello",True]
>>>lista_mea[2]
Bună
>>>lista_mea[0]
3
I've talked about how we can have other lists as elements inside lists. In
Python ș i multe alte limbaje, listele în interiorul listelor sunt utile pentru a reprezenta
multe tipuri de date (matrici, imagini, foi de calcul ș i chiar mai mult)
spaț ii dimensionale). Acestea sunt de obicei denumite multidimensionale
arrays sau liste multidimensionale.
>>>my_list=[[1,2,3], [7,8,9]]
>>>lista_mea[0][1]
2
Acest lucru funcț ionează astfel, mai întâi selectăm lista încorporată dorită, apoi selectăm
elementul din acea listă. În exemplul de mai sus, vrem lista de la indexul 0
([1,2,3]) atunci selectăm elementul de la indexul 1 (2).
Un tip mutabil (sau o secvenț ă mutabilă) este unul care poate fi schimbat după ce a fost
creată. O listă este o secvenț ă mutabilă ș i, prin urmare, poate fi modificată pe loc.
70
>>>s[0]="b"
Urmărirea erorilor (apelul cel mai recent a fost efectuat):
Fiș ier "<stdin>", linia 1, în <modul>
TypeError: obiectul 'str' nu faceatribui ț i elementul notsupport
Primeș ti o eroare. Aruncă o privire înapoi la capitolul despre ș iruri (Capitolul 6) ș i
revizuieș te diagrama care există în acel capitol.
Bună
>>>t=s
tiss
Adevărat
>>>t==s
Adevărat
Aceste variabile,ssitse referă la acelaș i obiect (ș irul
"Bună". Ce ar fi dacă am încerca să actualizăm s?
Bună
>>>t=s
tiss
Adevărat
>>>s="World"
>>>t
Bună
Variabilasse referă acum la un alt obiect ș it încă referinț e
„Salut”. Deoarece ș irurile sunt imutabile, trebuie să creăm o nouă instanț ă. Nu putem
schimbă-l în loc.
>>>a=[1,3,7]
>>>b=a
71
poate
Adevărat
>>>[Link]ă(9)
>>>a
[1,3,7,9]
>>>b
[1,3,7,9]
>>>aisb
Adevărat
Comportamentul s-a schimbat aici ș i asta se datorează obiectului la care se face referire.
deaș ibismutable. Modificarea sa nu crează un nou obiect ș i
referinț a originală nu este suprascrisă pentru a indica un obiect nou. Noi nu
suprascrie referinț a din variabilăa, în schimb scriemprin aceasta pentru a modifica
obiectul mutabil la care face referire.
Cu toate acestea, există câteva trucuri mici adăugate în acest comportament. Luaț i în considerare
următorul cod:
>>>a=[1,3,7]
>>>b=a
>>>a=a+[9]
>>>a
[1,3,7,9]
>>>b
[1,3,7]
Ce se întâmplă aici? Asta contrazice ceea ce tocmai am discutat, nu-i aș a?
Ei bine, evident că nu, dezvoltatorii Python nu ar lăsa un bug atât de mare în
limbaj. Ce se întâmplă aici este că am executat următorul cod:a = a +
[9]. Aceasta nu scrie pentru a modifica lista la care se referă. În schimb, o nouă
lista este creată din concatenarea listeia ș i lista9.
Asta nu este tot, sunt ș i câteva trucuri ascunse. Există o subtilitate în plus. Consideră
următorul cod:
>>>a=[1,3,7]
>>>b=a
>>>a+=[9]
>>>a
[1,3,7,9]
>>>b
[1,3,7,9]
Se pare căx += ynu este întotdeauna prescurtare pentrux = x + yDeș i cu
tipuri imuabile fac acelaș i lucru, cu liste se comportă foarte
diferit. Se dovedeș te că+= operatorul aplicat pe liste, modifică
72
listă în loc. Asta înseamnă că scriem prin referinț ă înunș i
adăuga[9]la listă.
>>>a=[1,3]
>>>b=a
>>>a[1]=9
** ÎNAINTE DE A ACTUALIZA A **
** DUPĂ ACTUALIZAREA A **
uneste o referinț ă la un obiect de tip listă care conț ine referinț e la întregi.
breferinț ele la acelaș i obiect listă. Dar când "schimbăm"a, nu suntem clar
schimbându-l. Actualizăm o referinț ă în cadrul acestuia. În timp cebdoar puncte către
listăas-a schimbat ceea ce este în interiorul său, prin urmareb's reference nu este afectată.
73
colectorul menț ine memoria curată ș i o opreș te să devină inundată cu lucruri
like the unreferenced 3).
[1,2,3]
> b = [4, 5, 6]
>>>a+b
[1,2,3,4,5,6]
>>>a+=b
>>>a
[1,2,3,4,5,6]
De asemenea, avem ș i* operator, care face ceea ce se aș teaptă:
>>>a=[1,2,3]
>>>a*3
[1,2,3,1,2,3,1,2,3]
Avem ș i un nou operator. Acesta esteînoperator. Theînoperatorul este
un operator de testare a apartenenț ei ș i returneazăAdevăratdacă o secvenț ă are o specificare
valoarea se află într-un obiect
>>>a=[3,7,22]
>>>4ina
Fals
>>>3ina
Adevărat
Theînoperatorul poate fi aplicat oricărui tip iterabil (liste, ș iruri, etc).
Împărț irea listelor funcț ionează exact aș a cum o face cu ș irurile de caractere. Acest lucru are sens deoarece ambele
[1,2,3,"Salut",Adevărat]
>>>a[3:]
["Hello",True]
>>>a[-4:-2]
[2,3]
Slicing-ul extins funcț ionează exact la fel ca ș i cu ș irurile.
a=[1,2,3,"Bună",Adevărat]
>>>a[::-1]
[True,'Hello',3,2,1]
74
>>>a[::2]
[1,3,Adevărat]
Important:
>>>a=[1,2,3]
>>>b=a
Dacă am actualizata, apoibar fi afectată. Ce ar fi dacă am dori să facem o
copie deaș i păstrează-l înb? Putem folosi tăierea pentru a face asta, deoarece tăierea returnează un
obiect nou
>>>a=[1,2,3]
>b=a[:]
bisa
Fals
Putem vedea acum că ele nu se referă la acelaș i obiect, aș a că actualizarea unuia va
nu afecta cealaltă.
8.7 - Exerciț ii
Notă importantă: Am învăț at multe până în acest punct. Soluț iile dumneavoastră ar trebui să
combinând (acolo unde este necesar) tot ce am învăț at până acum. Dacă eș ti
dacă nu eș ti sigur de ceva, nu te teme să te întorci la capitolele anterioare. E
este complet normal să nu îț i aminteș ti totul atât de devreme. Cu cât mai mult
practica, cu atât mai mult din aceste lucruri se va lipi!
Întrebarea 1
Scrie un program care ia un ș ir ca intrare de la utilizator, urmat de un
number and output each word which has a length greater than or equal to the
număr.
EXEMPLU DE INPUT
elefant pisică câine ș oarece urs lup leu cal
5
75
cal
Puteț i folosi următorul cod la începutul programului dvs.
cuvintele_mele=input().split()
num=int(input())
Întrebarea 2
Scrieț i un program care acceptă un ș ir ca intrare de la utilizator, urmat de
o altă sfoară (sufixul) ș i ieș i fiecare cuvânt care se termină cu sufixul.
# EXAMPLE INPUT
mere portocale pere struguri lămâi pepeni
es
cuvinte=input().split()
suffix=input()
Întrebare 3
Scrieț i un program care construieș te o listă de întregi din input-ul utilizatorului. Ar trebui să vă opriț i
# EXAMPLES INPUT
3
5
6
7
0
# EXAMPLE OUTPUT
76
[3, 5, 6, 7]
Întrebarea 4
Folosind soluț ia ta la întrebarea 3, luând o listă construită din inputul utilizatorului,
întreabă utilizatorul pentru două bucăț i suplimentare de input. Întregi de data aceasta.
# EXAMPLE INPUT
6
3
9
0
*********************************
* LISTA AR TREBUI SĂ FIE ÎN PREZENT: [6, 3, 9] *
*********************************
1
2
Întrebarea 5
Scrie un program care construieș te o listă de întregi din inputul utilizatorului. Programul tău
ar trebui apoi să găsească cel mai mic dintre aceste numere întregi ș i să-l pună la primul index (0)
în listă. Inputul se termină când utilizatorul introduce 0.
# EXAMPLE INPUT
10
87
11
5
65
342
12
0
# LISTA AR TREBUI SĂ FIE ACUM: [10, 87, 11, 5, 65, 342, 12]
# EXAMPLE OUTPUT
[5, 87, 11, 10, 65, 342, 12]
Această problemă este puț in mai greu de rezolvat, gândeș te-te la soluț ia ta!
77
Întrebarea 6
** ACESTA ESTE O PROBLEMĂ DIFICILĂ **
# EXEMPLU DE INTRODUCERE
2
6
34
90
0 # SFÂRȘ ITUL PRIMULUI INPUT
5
34
34
77
98
0 # SFÂRȘ ITUL AL DOILEA INPUT
# EXAMPLE OUTPUT
[2, 5, 6, 34, 34, 34, 77, 90, 98]
Nu presupune că ambele liste vor avea aceeaș i lungime!
78
Capitolul 9 - Algoritmi de sortare de bază
9.1 - Ce este sortarea?
Am învăț at multe până acum ș i acum este timpul să punem în aplicare ceea ce am învăț at.
foloseș te. Acum vom analiza primele tale algoritmi importanț i.
Sortarea este procesul de aranjare sistematică a elementelor. În ș tiinț a calculatoarelor,
sortarea se referă la aranjarea articolelor (indiferent ce ar fi acestea) într-o ordine
secvenț ă.
Sortarea este de obicei folosită pentru a susț ine eficienț a căutării sau a căutării, pentru a permite
procesarea datelor într-o ordine definită posibilă ș i pentru a realiza fuziunea de
secvenț e eficiente.
Sortarea prin selecț ie este un algoritm de sortare de uz general. Pentru ca sortarea prin selecț ie
pentru a lucra trebuie să presupunem că există o anumită secvenț ă de elemente care sunt
comandabil (întregi, zecimale, etc.).
Sortarea prin selecț ie este un algoritm de sortare in-place, ceea ce înseamnă că nu construim un
listă nouă, mai degrabă, reorganizăm elementele acelei liste.
În sortarea prin selecț ie, împărț im lista în două părț i, subarray-ul sortat ș i
subarray nesortat ș i toate elementele din subarray sortat sunt mai mici decât
sau egal cu toate elementele din subarray-ul nesortat. De asemenea, începem cu
presupunerea că întreaga listă este nesortată.
79
Apoi, căutăm în întreaga listă poziț ia celui mai mic element. Noi
trebuie să căutăm întreaga listă pentru a ne asigura că am găsit cel mai mic
element. Dacă există multiple apariț ii ale celui mai mic element, luăm
poziț ia primului. Apoi, mutăm acel element în poziț ia corectă
a subarray-ului sortat. Repetăm paș ii de mai sus pe subarray-ul nesortat
Acest lucru este ilustrat mai jos
6 3 9 7 2 8
|||========================| GĂSEȘ TE POZIȚ IA CEA MAI MICĂ
PARTE NESORTATĂ ELEMENT ÎN LISTĂ Ș I SCHIMBAȚ I CU
6
--------------------------------------------------------------------------
--
--------------------------------------------------------------------------
--
--------------------------------------------------------------------------
--
80
PARTE SORTATĂ NEORDERAT # ELEMENT ÎN LISTĂ Ș I ÎNLOCUIȚ I CU
7
PARTE 7 ESTE CEL MAI MIC (FĂRĂ SCHIMBARE)
--------------------------------------------------------------------------
--
--------------------------------------------------------------------------
--
Este timpul să codificăm sortarea prin selecț ie! Să ne uităm la codul pentru aceasta mai jos:
1.i = 0
2.în timp ce i < len(a):
3. p=i
4. j=i+1
5. whilej < len(a):
6. ifa[j] < a[p]:
7. p=j
8. j += 1
9.
10. tmp = a[p]
11. a[p] = a[i]
12. a[i] = tmp
13.
14. i += 1
81
• Cele trei linii de mai susi += 1schimbă elementul cel mai mic în
poziț ie corectă.
• Procesul se repetă apoi.
O altă modalitate bună de a înț elege ce se întâmplă în mijlocul unui cod este să
lipiț i într-unprint()declaraț ie pentru a tipări ce valori deț in ce variabile la
acel timp curent. O altă modalitate bună este să setez puncte de întrerupere. Nu voi
îț i arăt cum să faci asta, deoarece este în general o caracteristică a editorului de text pe care îl foloseș ti
foloseș te aș a că caută cum să setezi puncte de întrerupere pentru editorul tău ș i cum să le foloseș ti!
Sortarea prin inserț ie este un alt algoritm de sortare de uz general, care se face în loc.
Pentru a contrasta modul în care funcț ionează sortarea prin inserț ie comparativ cu sortarea prin selecț ie:
• Sortare prin selecț ie: Selectaț i cel mai mic element din subarray-ul nesortat
ș i îl adaugă la subarray-ul sortat al listei.
• Sortare prin inserț ie: Ia următorul element din subarray-ul nesortat ș i inserează-l
în poziț ia sa corectă în subarray-ul sortat.
-----------------------------------------------------------------------
|
|
2 4 5 3 96
|=============||==========| VREM SĂ PLASĂM ACUM 3 ÎN EL
82
SORTAT NEORDONAT # POZIȚ IE CORECTĂ
-----------------------------------------------------------------------
3
2 4 5 _ 96
|=============||==========| Scoate 3 din listă
SORTED UNSORTED
-----------------------------------------------------------------------
3
2 4 5 _ 96
|=============||==========| Este 3 < 5? DA, AȘ A CĂ MUTĂ 5 ÎN SUS
SORTED UNSORTED
-----------------------------------------------------------------------
3
2 4 _ 5 96
|=============||==========| # ESTE 3 < 4? DA, AȘ A CĂ MUTĂ 4 ÎN SUS
SORTED UNSORTED
-----------------------------------------------------------------------
3
2 _ 4 5 96
|=============||==========| # ESTE 3 < 2? NU, PLASEAZĂ DUPĂ 2
SORTED UNSORTED
-----------------------------------------------------------------------
83
2 3 4 5 96
|=============||==========| # 3 SE AFLĂ ACUM ÎN POZIȚ IA CORECTĂ
SORTAT NEORDONAT
-----------------------------------------------------------------------
2 3 4 5 96
|==================||=====| TRECE LA URMĂTORUL ELEMENT
SORTED UNSORTED
Este timpul să codăm sortarea prin inserț ie! Să aruncăm o privire asupra codului pentru aceasta, voi da
explicaț ie ca comentarii:
Sortarea prin selecț ie ș i sortarea prin inserare sunt ceea ce numim algoritmi de sortare pătratică.
84
Aceasta înseamnă că ambele au o complexitate de timp O mare de:
O(n)2
Complexitatea temporală se referă la timpul necesar pentru ca algoritmul să se finalizeze.
Există în general trei categorii:
• Cel mai bun caz - De exemplu, cu sortarea prin inserț ie, să zicem că lista noastră este
already sorted and we try to sort it, then we are in a best case scenario
deoarece nu trebuie să mutăm niciun element ș i algoritmul
se termină repede.
• Cazul mediu: Acesta este modul în care algoritmul se comportă în termeni de timp pe
medie
• Cea mai proastă situaț ie: Aș a ar performa algoritmul în termeni
dacă lista noastră ar fi fost complet amestecată ș i dezordonată.
Big O se ocupă cu cazul cel mai rău ș i acesta este cazul cu care ne preocupăm de obicei
cu!
Există multă matematică în spatele acestui lucru ș i există un întreg subiect de informatică.
85
Complexitatea timpului
În acest diagramă, axa y reprezintă cât de mult a durat algoritmul pentru a termina
în secunde ș i axa x arată numărul de elemente din listă.
Linia albastră este pentru un algoritm O(n^2) iar cea portocalie este pentru un O(n)
algoritm (algoritm de timp liniar).
Cu toate acestea, este foarte clar că algoritmii O(n^2) devin foarte lent atunci când
dimensiunea intrării devine mare.
În lumea reală, o listă de dimensiune 1000 este mică ș i sortarea prin selecț ie sau sortarea prin inserț ie
nu ar funcț iona. Cu toate acestea, acest lucru nu înseamnă că nu au utilizările lor. De fapt,
în practică, sortarea prin selecț ie ș i sortarea prin inserț ie depăș esc algoritmii mai rapizi
pe liste mici ș i unele dintre algoritmii de sortare rapidi vor comuta de fapt la
aceș ti algoritmi O(n^2) când se apropie de sfârș itul procesului de sortare.
Se pare că întregul proces se finalizează mai repede când acest lucru este făcut (în unele cazuri).
Avem de asemenea ceva numit complexitatea spaț ială ș i aceasta se referă la modul în care
o mare memorie este ocupată de un algoritm. Ambele algoritmi au O(1)
complexitate spaț ială. Aceasta înseamnă că folosesc memorie constantă. Folosesc constant
memorie, deoarece sunt algoritmi de sortare in-place. Nu creează suplimentar
liste pentru a asista în procesul de sortare.
86
De obicei există un compromis între complexitatea temporală ș i complexitatea spaț ială. Aș a cum poț i
vezi aici, avem memorie constantă (Asta este bine) dar timp quadratic
complexitate (aceasta este rea). Am putea scrie un algoritm care este mai rapid, dar necesită
mai multă memorie. Depinde de problemă ș i de resursele de calcul pe care le avem.
a avea.
9.5 - Exerciț ii
Nu vor fi exerciț ii de programare în acest capitol, doar întrebări teoretice.
Sunt la fel de importante de înț eles ș i de făcut corect!
Întrebare 1
Care este complexitatea temporală a:
Întrebarea 2
Care este complexitatea spaț ială a:
Întrebare 3
Oferiț i două exemple de când am putea folosi sortarea prin selecț ie sau sortarea prin inserț ie în
lumea reală?
Întrebare 4
Dacă ne-am pomeni într-o situaț ie în care inputul era sortat, dar noi nu ș tiam
ș i încercăm să sortăm inputul, de ce am putea prefera sortarea prin inserț ie în locul celei prin selecț ie
sorta?
S-ar putea să trebuiască să mergi ș i să cauț i răspunsul la aceasta.
87
Procesarea inputului, fiș ierelor ș i textului
Procesarea fiș ierelor este procesul de creare, stocare ș i accesare a conț inutului unui fiș ier.
Până acum, am reuș it să stocăm datele temporar în programele noastre.
în obiecte precum liste. În lumea reală, aceasta nu ar fi de mare ajutor. Avem nevoie de
o modalitate de a putea salva date permanent. Pentru a face acest lucru, programele noastre
trebuie să stochezi date pe un hard disk. Acesta este un mediu de stocare persistent ș i datele din
această stocare va putea supravieț ui unei reporniri a sistemului sau unui crash al programului nostru. Dacă
rebootăm sistemul nostru, RAM-ul este ș ters ș i pierdem datele noastre. Am fost
stocarea datelor în RAM până acum.
88
modulul poate defini funcț ii, clase ș i variabile. Pentru a accesa un modul trebuie să
trebuie să-l importaț i în codul dvs. folosindimportacuvânt cheie.
importaț i sistem
# CODUL TĂU
Prin intermediul modulului sys putem accesa argumentele care sunt transmise către noi
script la linia de comandă. Multe scripturi Python necesită acces la acestea
argumente. Avem acces la ele prinargv([Link]).
argveste o prescurtare pentru vectorul de argumente. Aceasta este o listă care conț ine comanda-
argumentele liniei transmise scriptului. Primul element din această listă este scriptul
însuș i. Argumentele pentru script vin după numele scriptului. Să
uită-te cum funcț ionează asta. Creează un nou fiș ier Python ș i salvează-l ca [Link] ș i
introduceț i următorul cod:
importaț i sistemul
print([Link])
Să folosim acest lucru într-un mod mai constructiv. Creează un fiș ier nou
numit [Link] ș i lipiț i următorul cod:
[Link]
2.
[Link] = 0
4.
5.i = 1
6.în timp ce i < len([Link]):
7. total += int([Link][i])
8. i += 1
[Link](total)
89
În linia de comandă, tastează următoarele, apoi apasă Enter:
$ py [Link] 5 3 6
14
Putem trece numerele pe care dorim să le adunăm în script. Acest lucru ne economiseș te
a fi nevoit să cerem utilizatorului input de fiecare dată când dorim o nouă introducere. Amintiț i-vă
totuș i, argv este o listă de ș iruri de caractere ș i de aceea a trebuit să convertim argumentele la
numere întregi în codul de mai sus.
Important: Următoarele metode, spre deosebire deîntroduceț i() ș iprint(), nu voi adăuga niciodată
sau eliminaț i caracterele de linie. Va trebui să gestionăm caracterele de linie
noi înș ine.
Primul esteciteș te()metodă. Este cea mai de bază dintre cele [Link]ș te() va citi
întreaga conț inuturi a fiș ierului ș i întregul conț inut va fi atribuit unui
string singular.
12345importaț i sistemul
Important: Putem trece un fiș ier programului nostru folosind un operator de linie de comandă
numit operatorul de redirecț ionare a intrării. Când folosim acest operator, redirecț ionăm
input de la tastatură în fiș ierul text.
90
Sintaxa pentru această metodă [Link]()[Link] un fiș ier (obiect fiș ier)
aici).
Ar trebui să creezi un fiș ier text ș i să-l umpli cu câteva texte. Îț i recomand să
have about 10 lines of text. Each line can be a single word if you like.
Pentru a rula codul de mai sus, tastaț i următoarele în linia de comandă. Asiguraț i-vă că
fiș ierul de text ș i scriptul Python sunt în acelaș i director. Tastaț i următoarele,
apoi Apasă Enter.
Aceasta este ieș irea pe care o obț inem. A ta va arăta diferit în funcț ie de ceea ce
aveț i în fiș ierul dvs. Aș a cum puteț i vedea, am imprimat acel fiș ier pe care tocmai l-aț i creat.
[Link]
2.
[Link] = [Link]()
4.
[Link] ț i(conț inuturile)
După cum puteț i vedea, fiș ierul nostru text este acum stocat într-o listă, fiecare linie fiind un
element în listă. Observaț i cum caracterele de newline nu au fost eliminate.
Această metodă este bună, deoarece acum putem face unele manipulări pe fiecare linie de text
mai uș or.
91
În loc să folosim operatorul de redirecț ionare a intrării, putem citi pur ș i simplu liniile din
terminal.
Puteț i rula din nou scriptul de mai sus, de data aceasta omiț ând operatorul de redirecț ionare.
Important: Cu fiș ierele ajungem în cele din urmă la sfârș itul acestora. Acest lucru este indicat în
fiș ierul prin EOF (final de fiș ier). Nu trebuie să ne facem griji cum funcț ionează asta, deoarece
este gestionat la un nivel mai scăzut. Când nu redirectăm intrarea standard pentru a citi
dintr-un fiș ier, trebuie totuș i să indicăm EOF la linia de comandă. Pe
În Windows, acest lucru se face apăsând ctrl+z. Pe Linux, acest lucru este indicat prin apăsarea
ctrl+d. Când rulezi din nou scriptul de mai sus ș i omiti redirecț ionarea, vei fi
Îndemnat să introduci continuu linii de text. Când ai terminat, apasă
ctrl+z sau ctrl+d.
$ py [Link]
linie unul
linie doi
linie finală # APĂSAȚ I ENTER, Apoi CTRL+Z SAU CTRL+D PENTRU A INDICA EOF.
Putem citi încă multe linii de input folosind această metodă, va trebui doar să avem nevoie de o
ciclul. Să vedem cum se face asta.
[Link]
2.
[Link] = [Link]()
[Link]:
5. print([Link]()) # Elimină caracterul de linie nouă deoarece print() va adăuga unul.
6. linie = [Link]()
92
Sunt pe linia doi.
Vreau să arunc o altă privire laciteș te()metodă. Putem de fapt controla cum
mare parte din input este citit. Dacă redirecț ionăm inputul către un fiș ier, putem limita cât de mult
al fiș ierului pe care îl citim în orice moment dat. În mod similar, dacă nu redirecț ionăm, putem limita
cât de mult din inputul utilizatorului prin consolă citim. Facem asta prin transmiterea
un întreg ca argument al metodei. Acest întreg reprezintă câte
caractere pe care vrem să le citim.
[Link]
2.
[Link] = [Link](6)
4.
[Link]ă(con ț inuturile)
Rularea codului ș i redirecț ionarea intrării standard către un fiș ier text ar produce:
Aș a cum poț i vedea, am trecut integerul 6 funcț iei de citire, spunându-i să doară
citeș te 6 caractere.
Aminteș te-ț i: Spaț iul gol contează ca un caracter ș i la fel ș i newline-ul.
personaj!
93
Să vedem asta în acț iune în REPL-ul Python:
>>>importsys
>>> [Link]("Salut")
Bună5
>>>
De asemenea, putem redirecț iona fluxul standard de ieș ire către un fiș ier folosind ieș irea
operator de redirecț ionare>). Haideț i să vedem cum se face asta.
[Link]
2.
[Link]("Salut Lume! ")
Dacă verifici directorul în care este stocat scriptul tău, ar trebui să vezi acum un
fiș ier numit [Link].
Deschide-l ș i vizualizează conț inutul său, ar trebui să conț ină ceea ce tocmai am scris în
flux de ieș ire.
Când redirecț ionăm ieș irea standard către un fiș ier, un fiș ier va fi creat dacă nu există.
există deja.
Avem de asemenea ș iwritelines()metoda disponibilă pentru noi care nu este atât de
diferit deciteș te_linii() except că scrie în loc să citească.
[Link]
2.
3.my_lines = ["Line one\n","Line two"]
[Link].scrie_linii(my_lines)
94
Apoi, în linia de comandă, rulează:
Dacă deschizi [Link], vei găsi că acesta conț ine ș irurile din lista de mai sus pe
două linii separate.
încă o dată în această carte. E doar bine să ș tii despre toate fluxurile de date standard
avem acces la.
În această secț iune vom examina deschiderea ș i citirea din fiș iere care sunt
stocate în stocare permanentă. Deș i fluxurile de date standard din
secț iunea anterioară sunt fiș iere, acestea erau stocate în RAM ș i erau deja deschise.
Când citim un fiș ier, iniț ializăm un obiect fiș ier care acț ionează ca un link de la
program pentru fiș ierul stocat pe disc.
Există diverse moduri în care putem deschide un fiș ier, ne preocupă doar
cu patru dintre ei aici.
95
2.w- Acest mod deschide un fiș ier pentru scriere. Dacă fiș ierul nu există, îl creează.
un fiș ier nou cu numele specificat al fiș ierului. Dacă fiș ierul există ș i scriem
orice ceea ce a fost anterior în fiș ier este suprascris.
[Link]- Aceasta deschide un fiș ier în modul de adăugare. Dacă fiș ierul nu există, îl creează.
un fiș ier nou cu numele specificat. Dacă există, adăugăm la fiș ier
în loc să îl suprascrie.
4.'x'Aceasta deschide un fiș ier pentru creaț ie exclusivă, eș uând dacă acesta există deja
ș i aruncând unEroareFileExistă.
Odată ce fiș ierul este deschis, putem citi conț inutul său folosind metodele din secț iunea
3.4:citeste(), citeș te_linii() ș iciteș teLinie().
Să ne uităm la un exemplu de deschidere a unui fiș ier de pe disc ș i citirea conț inutului său
contents:
1.my_file = open('[Link]','r')
[Link] = my_file.readlines()
[Link](content)
Asiguraț i-vă că aveț i un fiș ier numit "[Link]" salvat în acelaș i director ca al dvs.
script ș i, în scopuri de demonstrare, asigură-te că are câteva linii de text în el.
$ py [Link]
["Aceasta este linia unu.\n","Eu sunt linia doi.\n","Ș i eu sunt linia trei"]
Acum poț i vedea că conț inutul fiș ierului tău a fost citit cu succes.
Este în formă de listă, deoarece am folositciteste_linii()metodă.
În secț iunea anterioară am examinat deschiderea fiș ierelor. Acum să vedem cum să
scrie-le ș i închide-le.
Aș a cum aț i putut ghici, scriem în fiș iere folosindscrie()metoda prin care ne-am întâlnit
în secț iunile anterioare. Pentru a scrie într-un fiș ier, acesta trebuie deschis în modul de scriere
mod.
1.my_file = open('[Link]','w')
2.my_file.write("Sunt scris într-un fi ș ier\n")
96
1$ py [Link]
Acum deschide fiș ierul numit [Link]. Nu-ț i face griji dacă nu a existat, unul va fi creat.
a fost creat. Ar trebui să vezi acum linia "Sunt scris într-un fiș ier" conț inută în
acefă dosar.
Când un fiș ier este deschis, sistemul de operare alocă memorie pentru a urmări acest lucru.
starea fiș ierului ș i sistemul de operare nu pot realoca acea memorie până când
fiș ierul este închis. Dacă nu închidem fiș ierele deschise, atunci consumăm memorie
în mod inutil.
Când programul tău există, fiș ierul este închis automat, dar poate că noi nu o facem.
vrem să ieș im imediat după ce terminăm de citit ș i scris într-un fiș ier.
Închidem fiș ierele folosindînchide()funcț ie. Acest lucru este demonstrat mai jos:
1.my_file = open("[Link]","w")
2.my_file.write("Bună\n")
3.my_file.close()
Fiș ierul a fost acum închis ș i memoria poate fi realocată pentru alte utilizări.
A fi nevoit să deschizi fiș iere ș i să-ț i aminteș ti să le închizi poate deveni o adevărată bătaie de cap.
97
Apoi facem tot ce trebuie să facem. În acest caz, scriem în fiș ier. Când noi
ieș ire dincublochează fiș ierul este închis. Deschiderea ș i închiderea fiș ierelor în acest mod este
de obicei, cum o fac majoritatea oamenilor.
O altă utilizare acaun enunț care ar putea clarifica lucrurile este, de exemplu, noi
importam modulul sys ș i nu ne plăcea cât de lung este numele „sys”
era (ș tiu că acesta este un exemplu prostesc, dar unele module au nume lungi), noi
pot să-l import ca atare:
[Link]ă sys ca s
[Link] = [Link]()
Acum, de fiecare dată când vrem să ne referim la modulul sys, îl numim după aliasul său,s.
Ceea ce vrem să facem este să procesăm acest fiș ier ș i să ieș im într-un nou fiș ier dacă fiecare
studentul a trecut sau a picat cursul.
Logan TRECE
98
Vrem să trecem numele fiș ierului de intrare ș i numele fiș ierului de ieș ire ca argumente la
scenariul ș i considerăm că o notă de promovare este sub 40.
2.
[Link] = [Link][1] Fiș ierul sursă de intrare
[Link] = [Link][2] Fiș ierul de ieș ire
5.
[Link] open(src,'r') ca fin, open(dst,'a') ca fout: Deschide în modul de adăugare
7.
8. student = [Link]().strip() # Îndepărtează caracterul de întrerupere a liniei
9. whilestudent:
10.
11. student_data = [Link]() # ['Liam', '84'] for example
12.
13. name = student_data[0]
14. nota = int(date_studenti[1])
15.
16. daca mark < 40:
17. grade ="FAIL"
18. altfel:
19. grade ="PASS"
20.
21. [Link]('{:s} {:s}\n'.format(nume, nota)) Scrie în fiș ierul de ieș ire
le
22.
23. student = [Link]().strip() # Get the next student
Observaț i cum putem deschide mai multe fiș iere în acelaș i timp!
Logan PAS
Prelucrarea fiș ierelor este o sarcină comună, aș a cum am spus, aș a că obiș nuieș te-te cu ea, vei
probabil voi face asta mult!
10.9 - Exerciț ii
Notă importantă: Aceste întrebări sunt mai dificile decât cele anterioare ș i devin
considerabil mai dificile pe măsură ce progresează, în special întrebarea 4. Nu fi
descurajat, totuș i. Persistă în ele. Dacă reuș eș ti să finalizezi aceste 4
99
întrebări, eș ti pe calea de a deveni un mare dezvoltator ș i problemă
rezolvitor!
Întrebare 1
Scrieț i un program care multiplică un număr arbitrar de argumente din linia de comandă.
$ py [Link] 5 99 32 ....
$ py [Link] 8 8 9 3 2
3456
Întrebare 2
Scrie un program care citeș te linii din intrare standard (fără redirecț ionare) ș i
le trimite la ieș irea standard (fără redirecț ionare).
Întrebarea 3
Scrie un program care citeș te un fiș ier text ș i afiș ează (folosindprint()este bine) cum
multe cuvinte sunt conț inute în acel fiș ier. Numele fiș ierului de text ar trebui să fie
primit ca un argument de linie de comandă pentru scriptul tău.
Programul tău nu ar trebui să considere liniile goale ca fiind cuvinte ș i nu trebuie să-ț i faci griji
1$ py num_words.py [Link]
Pentru a testa că soluț ia ta este corectă, foloseș teA doua adresă inaugurală a
Abraham Lincoln701
Întrebarea 4
Scrie un program care citeș te conț inutul unui fiș ier. Fiecare linie va conț ine un
cuvânt sau expresie. Programul tău ar trebui să genereze (folosindprint()este bine) fie că
nu cada linie este un palindrom sau nu, "Adevărat" sau "Fals". Numele fiș ierului text
ar trebui să fie trecut ca un argument din linia de comandă la scriptul tău.
100
Un palindrom este un cuvânt sau o expresie care este la fel citită invers ca ș i înainte.
De exemplu, „racecar” este un palindrom, în timp ce „AddE” nu este.
Programul tău nu ar trebui să fie sensibil la majuscule: "Racecar" ar trebui să fie totuș i
$ py [Link] [Link]
To test that your solution is correct, use the following as your input text:
maș ină de curse
AdaugăE
HmllpH
A fost o maș ină sau o pisică pe care am văzut-o
Hannah
T poate apărea în contexte în care limba este jucată cu
Capabil am fost eu înainte să văd Elba
Adevărat
Fals
Fals
Adevărat
Adevărat
Fals
Adevărat
Adevărat
Întrebarea 5
** ACEASTĂ ÎNTREBARE ESTE DIFICILĂ **
La fel ca întrebarea 3, scrie un program care citeș te un fiș ier text. De data aceasta, programul tău
ar trebui să afiș eze câte cuvinte unice sunt conț inute în fiș ier.
101
De data aceasta trebuie să îț i pese de punctuaț ie ș i soluț ia ta nu ar trebui să
fiț i sensibili la majuscule. De exemplu,încredereș iîncredereș iÎncrederear trebui să fie
considerat acelaș i cuvânt, prin urmare, ar trebui să existe o singură apariț ie a acelui cuvânt
fii înregistrat ca unic ș i dacă ai da pesteîncredereiarăș i, atunci
nu-l înregistra.
Programul tău ar trebui să fie rulat astfel:
$ py cuvinte_unice.py [Link]
Pentru a testa dacă soluț ia ta este corectă, foloseș teA doua adresă inaugurală a
Abraham Lincoln343
102
Acest lucru ar putea părea puț in confuz, dar permite-mi să explic ce se întâmplă. Variabila iis
numit un contor (sau o variabilă de bucle) ș i controlează de câte ori se repetă bucla
iterează.
Ce-ar fi dacă am avea condiț ia asi < 10000? Cele patru linii de cod ar rămâne totuș i
ț ineț i apăsat, iar programul va număra de la 0 la 9999.
Îț i aminteș ti că am spus că poț i considera memoria ca pe niste sertare? Ei bine, haideț i să luăm asta
example:
-------------------------------------
| | | | | Fiecare "cubi ț ă" este o *loca ț ie de memorie*
-------------------------------------
-------------------------------------
| | | | | Fiecare are o *adresă*
-------------------------------------
-------------------------------------
| 32 | 44 | 89 | 12 | # Să presupunem că acestea sunt umplute cu valori
-------------------------------------
-------------------------------------
| 32 | 44 | 89 | 12 | # Să spunem că adresa primului
location is 2
-------------------------------------
^
|
2
37
Variabila de buclă este o variabilă temporară ș i rolul său este de a stoca un anumit
element pentru durata iteraț iei date. Să trecem prin exemplul nostru
ș i vezi cum funcț ionează asta.
Ce-ar fi dacă ne-am afla într-o situaț ie în care nu aveam ceva peste ce să iterăm, dar
Am vrut să executăm un bloc de cod de un număr fix de ori?
Python oferă două funcț ii încorporate pentru a face acest lucru. Acestea sunt
theinterval()funcț ia ș ixrange()function.
[Link](5, 10):
2. print(i)
$ py [Link]
5
6
7
8
9
După cum poț i vedea, începem de la 5 ș i ajungem până la, dar fără a include 10. Dacă omitem
parametrul de start, atunci se va seta implicit la 0 ș i sunt sigur că poț i ghici asta
explică ce face parametrul step din cunoș tinț ele tale despre acesta în extensie
feliere.
104
Funcț ia range a construit o secvenț ă din5 către9 ș i iterăm peste
folosind bucla for.
Dicț ionarele sunt tipuri de colecț ii, dar nu secvenț e. Adică, elementele sale nu sunt
ordonate aș a cum sunt într-o listă sau într-un ș ir.
CHEI VALUES
____________ ____________________
| | | |
| "Tony" -|-------|-> "457-2344356" |
| | | |
| "Adam" -|-------|-> "359-5550983" |
| | | |
|----------| |------------------|
În acest exemplu, implementăm un catalog telefonic folosind un dicț ionar. Dacă căutăm
cheiaTony, suntem conduș i spre valoare"457-2344356".
Complexitatea Big O pentru operaț ia de căutare este O(1). Este constantă. Nu...
indiferent cât de mare este dicț ionarul, timpul necesar pentru a căuta o valoare este întotdeauna
la fel. Magie, nu-i aș a? Ia-o ca pe o magie, nu voi intra în detalii despre cum o face.
în această carte, deoarece este un pic prea avansată pentru începători, dar eș ti mai mult decât
bine ai venit să vezi cum se face.
105
De asemenea, nu ș tim ordinea în care sunt stocate perechile cheie-valoare într-un Python
dicț ionar, aș a că nu scrie programe care să se bazeze pe ordinea lui. Dacă ai un
un dicț ionar care este acelaș i de fiecare dată când rulezi programul, ordinea va fi
diferit de fiecare dată.
For the above phone book example, that would be done as follows:
phonebook = {"Tony":"457-2344356","Adam":"359-5550983"}Observaț i sintaxa pentru
dicț ionarele folosesc acolade în loc de paranteze pătrate.
Cu dicț ionarele, o cheie poate fi orice tip imutabil. Valorile pot fi de orice tip.
tip, inclusiv alte dicț ionare.
Dacă încercăm să accesăm un dicț ionar pe baza unei chei care nu există în cadrul
dictionar, primim o eroare. Această eroare este cunoscută ca oKeyErrorîn Python.
>>> phonebook["Bob"]
Urmărire (apelul cel mai recent a eș uat):
KeyError:'Bob'
Aminteș te-ț i, dicț ionarele nu sunt tipuri secvenț iate, aș a că nu putem accesa prin
poziț ie. Totuș i, putem folosi numere întregi ca chei, dar chiar ș i atunci, ele sunt doar
că; întregi.
>>> my_dict = {1"unu"3trei2:"two"}
106
>>> dictionarul_meu[3]
trei
>>> my_dict[0]
Urmărire a erorilor (cea mai recentă apelare a fost cea mai recentă):
Dacă avem o pereche cheie-valoare în care valoarea este o listă, putem indexa lista ca
urmează:
>>> my_dict = {"first": [2,4,8]}
>>> my_dict["first"][0]
2
De asemenea, putem adăuga noi intrări într-un dicț ionar existent. Când adăugăm un nou
Introducere, adăugăm o nouă mapare a unui pereche cheie-valoare în dicț ionar.
Sintaxa pentru a face aceasta este:
dictionary[<key>] = <value>
>>> my_dict = {}
>>> my_dict["one"]=1
>>> my_dict
{"one":1}
Aș a cum putem adăuga intrări în dicț ionar fără ca un nou dicț ionar să fie creat
de fiecare dată, dicț ionarele sunt tipuri mutabile.
Amintiț i-vă că cheile trebuie să fie de un tip mutabil, iar valorile pot fi de orice tip.
Putem elimina înscrierile din dicț ionar folosinddeldeclaraț ie. Aceasta este
făcut astfel:
>>> carnet de telefoane= {"Tony":"457-2344356","Adam":"359-5550983"}
>>>delphonebook["Tony"]
107
În exemplul de mai sus, spunem, ș tergeț i intrarea din dicț ionar
a cui este cheiaTony.
Putem obț ine lungimea unui dicț ionar la fel cum facem cu ș irurile de caractere ș i
liste:
>>> agendă= {"Tony":"457-2344356","Adam":"359-5550983"}
>>>len(phonebook)
[Link] = {"Tony":"457-2344356","Adam":"359-5550983"}
[Link]ă "Tony" în agenda telefonică:
3. printaț i(phonebook["Tony"])
[Link]:
5. cheia nu există
Motivul pentru care am introdus dicț ionare în acest capitol este pentru că noi
use pentrubucle pentru a parcurge fiecare dintre cheile unui dicț ionar.
[Link] = {"Bill":"457-2344356","Adam":"359-5550983"}
2.
[Link]:
4. {} numărul este {}.
Putem recupera o listă a cheilor sau valorilor unui dicț ionar folosind fie
thechei()metodă sauvalori()metodă respectivă.
>>> agendă telefonică= {"Bill":"457-2344356","Adam":"359-5550983"}
>>> [Link]()
dict_keys(['Bill','Adam'])
>>> [Link]()
dict_values(['457-2344356','359-5550983'])
108
Acestea nu sunt cu adevărat liste, deoarece nu le putem indexa, dar putem itera peste ele.
folosind unpentruciclare.
dict_items([('two',2unul1)])
Putem observa că tuplurile au forma(e1, e2, ....., en) unde e1....en sunt
elemente.
pentru(k, v)înmy_dict.items():
print("Cheie: {} ș i Valoare: {}".format(k, v))
Aminteș te-ț i, [Link]() returnează o 'listă' de tupluri, fiecare tuplu conț inând două
elemente, cheia ș i valoarea. Când spunempentru (k, v) în
my_dict.items()ăam spunem esenț ial pentru fiecare tuplă din lista tuplelor,
atribuiekla elementul din prima poziț ie din tuplu ș ivla elementul din
a doua poziț ie. Voi ilustra asta mai jos:
(k, v)
| |
V V
("one", 1)
109
Key: one and Value: 1
pentru(k, v)sortate([Link]()):
print("Cheie: {} ș i Valoare: {}".format(k, v))
Aș a cum puteț i vedea, dicț ionarul a fost sortat în funcț ie de chei. Deoarece
cheile sunt ș iruri de caractere, ele sunt sortate lexicografic.
De asemenea, putem sorta după valori, totuș i, nu avem cunoș tinț ele necesare pentru a face asta.
încă. Ne vom întoarce la asta în capitolul despre funcț ii.
110
11.7 - Exerciț ii
Întrebarea 1
Scrie un program care citeș te un fiș ier. Fiș ierul va conț ine un număr de articole.
stocat într-un magazin ș i numărul de fiecare articol disponibil. Programul tău
ar trebui să analizeze fiș ierul ș i să construiască un dicț ionar din acesta, apoi să scoată stocul
disponibil în ordine alfabetică ș i într-un format specific. Puteț i folosi
următoarele ca fiș ier text de intrare:
Portocale 12
Mere 10
Pere 22
Lapte 7
Sticle de apă 33
Batoane de ciocolată 11
Băuturi energizante 8
Apples : 10
Chocolate Bars : 11
Energy Drinks : 8
Milk : 7
Oranges : 12
Pears : 22
Water Bottles : 33
Întrebarea 2
Scrieț i un program care citeș te un fiș ier text. Fiș ierul este o listă de detalii de contact pentru
oameni. Cu fiecare contact, primeș ti numele, numărul de telefon ș i adresa de email
adresă. Dicț ionarul tău ar trebui să fie o mapare de la numele contactelor la emailuri
ș i numărul de telefon pentru acel contact. Programul tău ar trebui apoi să întrebe utilizatorul
intrare. Intrarea ar trebui să fie un nume unic. Dacă numele poate fi găsit în
contact list then output the name and contact details for that person,
altfel ieș ireNiciun contact cu acel nume.
111
Fiș ierul listei de contacte este:
Tony
Noe
Ion
Annie
Bert
Name: Tony
Email: tony@[Link]
Phone: 987-56543239
Name: Noah
Email: [Link]@[Link]
Phone: 324-43576413
Name: Bert
Email: [Link]@[Link]
Phone: 654-99275234
Aceste detalii ar trebui să fie tipărite câte una pe măsură ce utilizatorul introduce numele, nu
în vrac aș a cum am menț ionat mai sus.
Întrebarea 3
112
În capitolul precedent am încercat să numărăm câte cuvinte erau conț inute
într-un fragment de text. În această întrebare trebuie să faci acelaș i lucru, cu toate că
should output how many times each word occurred in the text.
Din nou, punctuaț ia contează. De data aceasta dorim să eliminăm orice punctuaț ie
înconjurând un cuvânt. Programul tău nu ar trebui să fie sensibil la majuscule
$ py dict_count.py [Link]
Pentru a verifica că soluț ia ta este corectă, foloseș teAl doilea discurs inaugural al
Abraham Lincolnaceasta este o
exemplu din afară):
.
.
.
58
oath : 1
de : 22
presidential : 1
office : 1
acolo : 2
este : 6
mai puț in : 2
occasion : 2
pentru : 9
an : 3
extins : 1
address : 2
decât: 4
.
.
113
.
You need not format the output. The length of your dictionary should be 701.
Întrebare 4
Scrie un program care ia două dicț ionare ș i iese intersecț ia lor.
intersecț ia a două dicț ionare ar trebui să fie un al treilea dicț ionar care conț ine cheia-
perechi de valori care sunt prezente în ambele dicț ionare. Poț i să durezi
codifica aceste două dicț ionare în. Nu este necesar să fie citite din nicio parte.
Pentru a testa dacă soluț ia ta este corectă, poț i rula programul tău cu cele două
următoarele dicț ionare:
d1= {"k1":True, "k2":True, "k3":True, "k4":True}
d2= {"k6":True, "k2":True, "k5":True, "k1":True, "k8":True, "k4":
Adevărat
114
Capitolul 12 - Funcț ii ș i Module
12.1 - Ce sunt funcț iile?
În Python, o funcț ie este un cod care primeș te un input, efectuează unele
computare ș i produce o ieș ire. În programare, o funcț ie este o
bloc reutilizabil de cod care îndeplineș te o sarcină specifică.
Putem apela o funcț ie de mai multe ori în timpul execuț iei unui program. Avem
am făcut asta de multe ori în întreaga această carte deja.
Unele dintre funcț iile comune cu care ne-am întâlnit suntlen()ș iprint(). Când noi
vrem să ș tim lungimea a ceva ce transmitem acelui ceva
cellen()funcț ie de exemplu.
Cel mai adesea, funcț iile încorporate Python nu sunt suficiente. Să luăm în considerare...
algoritm de căutare liniară, de exemplu. Este posibil să dorim să căutăm un ș ir de mai multe ori.
Definim funcț iile noastre folosinddefcuvânt cheie. Să aruncăm o privire asupra unei funcț ii
care afiș ează "Salut, lume!" pe ecran.
[Link]():
2. Salut, lume!
115
tipăriț iSalut, lume!pe ecran. Această funcț ie poate fi utilizată astfel în cadrul
codul nostru:
[Link]():
2. Salut, lume!
3.
[Link]ă()
Ultima linie de mai sus apelează funcț ia noastră. Acest lucru ar trebui să fie familiar deoarece ai apelat
Îț i voi explica cearg1, arg2, ..., argneste în secț iunea următoare, dar să luăm un
uită-te lareturnaredeclaraț ie.
[Link]():
2. Salut, lume!
[Link]():
2. Salut, lume!
3.
4.x = salut()
[Link](x)
6.
7.# ALTERNATIV
[Link](hello())
116
În secț iunea anterioară, am analizat sintaxa pentru o funcț ie. În aceasta, am avut
ceva de genul:
def myFunc(arg1, arg2, arg3):
#
[Link](x, y):
2. rezultatul = x + y
3. returnresult
4.
[Link]ă(add(5, 7))
Mai devreme am analizat o funcț ie care a imprimat hello world. Funcț iile care fac
procedurile care nu returnează valori sunt numite proceduri.
Funcț iile care returnează o valoare inspectează starea programului nostru. Ele returnează o
valoare bazată pe inspectia lor.
117
Aminteș te-ț i deîmpărț i()metodă? Am spus că dacă nu trecem niciun argument la aceasta
metoda, atunci va împărț i un ș ir pe baza spaț iului. Aceasta se numeș te
un argument implicit.
Un argument implicit este un parametru care presupune o valoare implicită dacă nu este specificată una.
În funcț ia de mai sus, trebuie să trecem un raadius ca argument atunci când o apelăm.
Cu toate acestea, nu trebuie să trecem o coordonată x sau y. Dacă nu trecem o coordonată x sau y.
coeficient, funcț ia noastră implicitează aceste valori la 0.
1.defmy_function(*argv):
2. pentru argument argv:
3. print(arg)
4.
5.my_function("prima","a doua","chiar a treia")
1.defmy_function(**kwargs):
2. fork, vinkwargs:
3. print("{} : {}".format(k, v))
4.
5.my_function(first="Hello", second="World")
Ieşirea ar fi astfel:
lume
first : Hello
118
După cum probabil îț i poț i da seama,kwargseste un dicț ionar. Indicam că este un cuvânt cheie
parametru de lungime variabilă de către**înainte de numele variabilei.
Atât parametrii normali, cât ș i cei cu lungime variabilă pe bază de cuvinte cheie trebuie plasaț i la sfârș it
a listei parametrilor atunci când definiț i parametrii funcț iilor dvs. Există bine
motivul pentru aceasta. Dacă am fi avutdef func(x, y, *argv, z)nu am ș ti
unde*argvs-a încheiat.
Nu toate variabilele sunt accesibile din toate părț ile programului tău. Partea unui
programul în care o variabilă este accesibilă se numeș te domeniul său. O variabilă care este
definit în corpul principal al unui fiș ier se numeș te variabilă globală. Va fi vizibilă
pe tot parcursul fiș ierului ș i orice fiș ier care importă acel fiș ier.
Variabilele globale pot avea consecinț e neintenț ionate din cauza „domeniului” lor
(ele pot fi accesate de oriunde). Există doar foarte speciale
circumstanț ele în care ar trebui să folosim variabile globale în software-ul pe care îl facem în
viaț a reală.
Variabilele care sunt definite în interiorul blocurilor de cod sunt locale acestui bloc.
Un bloc este o construcț ie care delimitează domeniul de aplicare al oricărei declaraț ii în interiorul său. În
Python, o variabilă definită într-o funcț ie este locală acelei funcț ii. Este
accesibil din momentul în care este definit până la sfârș itul acelei funcț ii.
Parametrii formali ai unei funcț ii acț ionează ca variabile locale. Cu toate acestea,
atribuț iile la un parametru nu pot afecta niciodată argumentul asociat decât dacă
sunt un tip modificabil, pe care l-ai văzut în secț iunea anterioară.
1.defadd_to_list(cuvânt, listă_de_cuvinte=[])
2. word_list.append(word)
3. lista_cuvintelor_returnate
4.
[Link]():
6. word ="apple"
7. tlist = adaugă_la_listă(cuvânt)
8. print(tlist)
119
9. word ="orange"
10. tlist = add_to_list(word, ['pear'])
11. printa(tlist)
12. word ="banana"
13. tlist = adaugă_la_listă(cuvânt)
14. print(tlist)
15.
[Link]()
$ py [Link]
măr
["pară","portocală"]
["măr","banana"]
Lista goală este iniț ializată o singură dată de Python. Este iniț ializată când
thedefpentru acea funcț ie este întâlnită pentru prima dată. Aceasta înseamnă că lista are memorie
ș i orice adăugat la acesta va rămâne acolo.
1.defadd_to_list(cuvânt, listă_de_cuvinte=None):
2. dacă lista_de_cuvinte este None:
3. word_list = []
4. word_list.append(word)
5. returnword_list
6.
[Link]():
8. word ="apple"
9. tlist = adaugă_la_listă(cuvânt)
10. print(tlist)
11. word ="orange"
12. tlist = adaugă_la_listă(cuvânt, ['pară'])
13. print(tlist)
120
14. word ="banana"
15. tlist = adaugă_la_listă(cuvânt)
16. print(tlist)
17.
[Link]()
măr
["pere","portocale"]
["banana"]
Nimiceste un tip special. Este un obiect care indică lipsa valorii ș i este
un tip imutabil. De fapt,Nimicse întoarce dintr-o funcț ie dacă nu există return
declaraț ie în acea funcț ie adică o procedură.
121
12.7 - Crearea propriilor noastre module
Putem crea module proprii pentru a organiza logic codul nostru. Să spunem că
vrem să creăm un modul care conț ine unele funcț ii matematice. Facem asta ca
urmează:
1.# [Link]
2.
[Link](x, y):
4. returnx + y
5.
[Link](x, y)
7. returnează x * y
8.
[Link]():
10. print(adaugă(x, y))
11. print(multiply(x, y))
12.
13.if__name__=="__main__":
[Link]()
Theadauga()ș iînmulț iț i() funcț iile sunt bune ș i am întâlnit altele similare
funcț iile înainte. Theprincipala()function we have also come across in a previous
secț iune dardacă __name__=="__main__":, nu am dat peste înainte.
Când executi un program direct din linia de comandă (aș a cum ai fost
executând), interpretul Python setează o variabilă specială pentru acel script. Aceasta
variabila este__name__Când un script este executat direct, acea variabilă este setată
la"__main__", altfel, dacă este importat, de exemplu, atunci este setat la
numele modulului,matematicăîn acest caz.
Modul în care Python gestionează__name__ variabila s-a schimbat în Python 3.7. Este
acum subPEP 567. La suprafaț ă, nimic nu s-a schimbat drastic.
122
12.8 - Exerciț ii
Când îndeplineș ti aceste exerciț ii, foloseș te următorul model atunci când scrii
scripts:
Întrebarea 1
Scrieț i un modul [Link] conț ine funcț ii care implementează
atât sortarea prin selecț ie cât ș i sortarea prin inserț ie adică modul tău ([Link]) ar trebui să conț ină
[Link]
2.
3.a = [5, 6, 3, 8, 7, 2]
[Link](sorting.selection_sort(a))
5.a = [5, 6, 3, 8, 7, 2]
[Link]ă(sorting.insertion_sort(a))
$ py [Link]
[2, 3, 5, 6, 7, 8]
[2, 3, 5, 6, 7, 8]
Întrebarea 2
Scrie un modul [Link] modul ar trebui să includă următoarele
functions:
• adauga()
• înmulț iț i()
123
• împărț iț i()
• scade()
Modulul tău ar trebui să fie importat ș i rulat după cum urmează într-un alt script
[Link]
$ py [Link]
22
5
-18
1
2
6
18
Întrebare 3
Scrie o funcț ie numitălength()care imitălen()funcț ie. Funcț ia ta
ar trebui să funcț ioneze pentru ș iruri, dicț ionare ș i [Link]()ar trebui să dureze doar 1
argumentaț i ș i returnaț i lungimea structurii de date transmise.
Funcț ia dumneavoastră ar trebui să fie testată cu următoarele:
1.a = [5, 3, 4, 1, 2, 3]
[Link]ă(lungimea(a))
3.
4.a = []
[Link](lungimea(a))
6.
124
7.d = {}
[Link]ă(len(d))
9.
10.d = {"one":True,"two":True}
[Link](length(d))
12.
13.s ="This is a string"
[Link](lungimea(s))
15.
16.s = ""
[Link](len(s))
$ py [Link]
6
0
0
2
16
Întrebarea 4
Scrie o funcț ie numităfib() care calculează ș i returnează n-lea Fibonacci
număr. Funcț ia ta ar trebui să ia 1 argument, numărul Fibonacci pe care îl
vrea să calculeze.
[Link](fib(3))
[Link](fib(0))
[Link](fib(1))
[Link](fib(10))
[Link](fib(13))
$ py [Link]
3
1
1
89
377
Aminteș te-ț i:
fib(n)=fib(n−1)+fib(n−2)
fib(0)=1
125
fib(1)=1
Întrebarea 5
Scrie o funcț ie numităciteș te_fiș ier() care ia un singur argument, un nume de fiș ier
(ca un ș ir), ș i returnează conț inutul fiș ierului sub formă de listă cu fiecare element
în listă fiind un singur rând din fiș ier.
[Link] = read_file("[Link]")
Întrebarea 6
Scrie o procedură de funcț ie numitărep_all()care ia 3 argumente, o listă de
întregi ș i 2 numere. Procedura ta ar trebui să înlocuiască toate apariț iile ale
primul număr cu al doilea.
1.a = [4, 2, 3, 3, 7, 8]
[Link]ă_tot(a, 3, 10)
[Link](a)
$ py [Link]
[4, 2, 10, 10, 7, 8]
126
Capitolul 13 - Căutare binară
13.1 - Joc de ghicit numere
Să presupunem că avem un tablou sortat de lungime 100,000. Să presupunem în continuare
cineva a ales un număr din acel tablou, la întâmplare ș i noi nu
ș tim ce este. Ni se oferă 20 de încercări pentru a ghici răspunsul. Acest lucru poate părea
imposibil ș i că avem doar noroc de partea noastră.
Putem folosi cunoș tinț ele pe care le avem până acum pentru a scrie o funcț ie care să facă o estimare asupra acestui lucru,
Să analizăm două modalităț i prin care am putea încerca acest lucru. Prima este căutarea liniară.
[Link]
2.
[Link] = [xforxinrange(0, 100000)]
[Link] = randint(0, len(arr))
5.
6.i = 0
7.în timp ce i < 20 ș i i != secret:
8. i += 1
9.
[Link] < 20:
11. print("Numărul secret este " + str(i))
12.încazcontrar:
În mod evident, aceasta este o idee teribilă deoarece numărul secret trebuie să fie între 0 ș i
20 which has a 20/100000 chance of happening.
O altă abordare pe care am putea să o adoptăm este să facem 10 ghiciri aleatorii.
127
[Link]
[Link] = [xforxinrange(0, 100000)]
[Link] = randint(0, len(arr))
4.
[Link] = randint(0, len(arr))
6.i = 1
7. în timp ce i < 20 ș i ghicirea != secret:
8. ghicire = randint(0, len(arr))
9. i += 1
10.
[Link] < 20:
12. Numărul secret este
13. altfel:
14. Noroc prost, nu ai ghicit numărul secret
O abordare mai bună? Poate, dar putem face mult mai bine. De fapt, putem ghici
număr în cadrul a 20 de încercări de fiecare dată fără eș ec. Folosim un algoritm nou
a fost denumit Căutare Binara pentru a face asta.
2 4 9 12 34 35 77
|_____________________| # Numărul pe care încercam să-l ghicim este aici
2 4 9 12 34 35 77
| low | high
|_____________________| Vom numi aceste două poziț ii joase ș i
înalt
2 4 9 12 34 35 77
| low înalt
2 4 9 12 34 35 77
scăzut înalt De asemenea, suntem capabili să calculăm indicele
pentru
128
|_____________________| numărul din mijlocul valorilor scăzute ș i ridicate
2 4 9 12 34 35 77
scăzut mijloc înalt De asemenea, suntem capabili să calculăm indicele
pentru
|_________|____________| numărul din mijlocul scăzut ș i înalt
#
Presupunem că numărul pe care îl căutăm este 4
#
2 4 9 12 34 35 77
scăzut mijloc înalt De asemenea, suntem capabili să calculăm indexul
pentru
|_________|____________| numărul din mijlocul valorilor mici ș i mari
2 4 9 12 34 35 77
scăzut mijloc ridicat Întrucât lista este sortată, putem verifica dacă
the
|_________|____________| # numărul din 'mijloc' este <= sau > 4
2 4 9 12 34 35 77
scăzut mijloc înalt În acest caz, 4 este < 12, deci nu avem nevoie
la
|_________|____________| nu te deranja să cauț i nimic deasupra mediei
index
2 4 9 12
| low | high Aș a că am tăiat acea porț iune din listă
|_________| ș i fă din mijloc noul înalt
2 4 9 12
scăzut | high Repetaț i procesul,
129
|_________| împărț ind continuu lista la jumătate până când
condiț ie
aceeaș i valoare scăzută < valoare mare eș uează adică valoare scăzută == valoare mare
Calculăm punctul de mijloc obț inând media dintre minim ș i maxim adică(scăzut +
înalt) // 2. Observaț i că facem o împărț ire întreagă aici, deci vom rotunji în jos dacă
există un loc zecimal.
Aproximativ, doar 10% dintre dezvoltatori sunt capabili să scrieț i corect căutarea binară.
Există o mică scurgere în mijlocul ei, aș a că trebuie să fim atenț i pentru ca turma noastră.
soluț ia funcț ionează corect în toate cazurile.
defbinar_căutare(arr, elem):
2. low = 0 Defineț i valoarea iniț ială scăzută.
3. high = len(arr) Definiț i valoarea iniț ială mare.
4.
5. în timp ce low < high: Condiț ia care trebuie să fie adevărată.
6. mid = (low + high) // 2 # Calculează indexul mediu.
7.
8. dacă ifarr[mid] < elem: Verificaț i dacă valoarea se află în prima sau a doua jumătate
.
9. low = mid + 1 # Actualizaț i valoarea mică dacă valoarea medie < element (în secunda
jumătate).
10. altfel:
11. înalte = mediu # Altfel, actualizaț i valoarea mare (elem în prima ha
lf).
12. returnlow Returnează poziț ia elementului
13. căutăm.
Este important camijlocș iînaltniciodată nu sunt egale. Acesta este un loc în care unele
dezvoltatorii fac greș eli atunci când codifică acest algoritm.
130
Trebuie să adăugăm1când actualizaț i valoarea scăzută deoarece dacălow == mid, vom încheia
într-o buclă infinită ș i aceasta este o veste proastă! Acesta este un alt loc unde
dezvoltatorii greș esc.
Având în vedere că căutarea binară are dezavantajele menț ionate mai sus, îț i recomand să o înveț i.
din memorie.
Acum putem lua acest algoritm de căutare binară ș i să-l modificăm uș or pentru a se potrivi nevoilor noastre.
joc. O să adăugăm o verificare astfel încât să nu facem mai mult de 20 de iteraț ii din
algoritmul de căutare binară adică împarte lista de mai mult de 20 de ori.
Versiunea noastră îmbunătăț ită a jocului va ghici (găsi) numărul secret în cadrul
20 încercări de fiecare dată.
This is important because we get guess the answer correctly, in the worst case,
în 20 de încercări, în timp ce abordările noastre anterioare, cel mai rău caz ar fi avut
au fost 100.000 de încercări!
Sortarea prin inserț ie ș i sortarea prin selecț ie aveau o complexitate de timp de:
131
O(n)2
O(log(n))
Mai specific:
O(log2n)
Este puț in mai complicat să se spună care este timpul de execuț ie al unui algoritm ca acesta. Aș a cum o
o regulă generală, dacă împărț im intrarea la jumătate la fiecare iteraț ie, atunci va
are un timp de execuț ie logaritmic (sau cel puț in, un component logaritmic în timpul său de execuț ie
complexitate).
Amintiț i-vă graficul Sortării prin Inserț ie ș i al unui algoritm O(n). Iată graficul
a complexităț ii de timp a unui algoritm cu căutare binară.
Poț i observa clar că, pe măsură ce intrarea devine mult mai mare, timpul necesar pentru...
algoritmul pentru completare începe să se stabilizeze ș i creș terea dimensiunii intrării începe
a avea un efect din ce în ce mai mic asupra performanț ei algoritmului.
132
Complexitatea spaț ială a căutării binare este de asemenea O(1), ceea ce înseamnă memorie constantă, deoarece noi
13.6 - Exerciț ii
Întrebarea 1
Răspunde la următoarele întrebări:
Întrebarea 2
Folosind ceea ce ai învăț at în acest capitol, scrie o funcț ie numităinsera()acela
utilizează un algoritm eficient (indiciu, indiciu...) ș i primeș te o listă ș i un element ca
introduce ș i returnează indexul la care acel element ar trebui să fie inserat în
listă.
De exemplu, apelarea funcț iei de inserare aș a cum este ar trebui să returneze următoarele:
Întrebarea 3
Din nou, folosind ceea ce ai învăț at, scrie o funcț ie numităcontine()asta durează
două argumente, o listă ș i un element ș i returnează dacă acel element
este inclus în acea listă.
De exemplu:
contains([1, 3, 5, 7], 3)
# RETURNĂRI
Adevărat
------------------------------
133
conț ine([1, 3, 5, 7], 2)
#RETURURI
Fals
134
Capitolul 14 - Tratarea erorilor
14.1 - Ridicarea Excepț iilor
În Python vei întâlni multe tipuri de erori ș i sunt sigur că te-ai confruntat cu
suficient până acum!
Am văzut erori de sintaxă care apar din cauza sintaxei incorecte, de exemplu, prea multe
paranteze de închidere. Vei întâlni ș i ceva numit erori de excepț ie.
Erorile de excepț ie apar ori de câte ori un cod Python sintactic corect generează o
eroare. Există multe tipuri de erori de excepț ie, pentru a numi câteva, vei primi
unImportErrorcând încerci să imporț i un modul care nu poate fi găsit, vei
obț ine unZeroDivisionErrorcând al doilea operand al împărț irii sau al modulului
operatorul este zero. Dacă întâlneș ti o eroare care nu se încadrează într-o specifică
categoria de excepț ie, Python va arunca oRuntimeError.
1.defdecrease_velocity(curr_vel, decrease):
2. returncurr_vel - decrease
3.
[Link]():
5. car_velocity = 20
6. inp = int(input())
7. whileinp:
8. car_velocity = decrease_velocity(car_velocity, inp)
9. dacă_viteza_masinii < 0:
10. ridicaExceptie("Maș ina nu poate avea o viteză negativă")
11. inp = int(input())
12.
[Link]ă__nume__=="__principal__":
[Link]()
5
6
7
5
Eroare de urmărire (ultima apelare cea mai recentă):
funcț ia principală()
Fiș ier "[Link]", linia 10, în main
Aș a cum poț i vedea, am ridicat o excepț ie cu propriul nostru mesaj de eroare personalizat.
Putem chiar să ridicăm tipuri specifice de excepț ii. UnEroaredevaloarepoate fi potrivit pentru
acest exemplu ș i pur ș i simplu înlocuimExcepț ie cuValueError.
De asemenea, putem ridica excepț ii atunci când ne aș teptăm ca erorile să apară aș a cum
în mod normal am face. Am ridica o excepț ie în acest caz pentru a oferi o mai bună
mesaj de eroare detaliat.
14.2 - Afirmatii
Dacă îț i aduci aminte de începutul acestei cărț i, am vorbit despre pre ș i
condiț ii post. O condiț ie prealabilă este o condiț ie care este întotdeauna adevărată înainte de
executarea unor coduri. Condiț iile prealabile pot fi utilizate în funcț ii pentru
aplicarea unui contract între o funcț ie ș i invocatorul său. Să presupunem că avem
o funcț ie care necesită o listă ca argument. Vrem să afirmăm că
argumentul trecut funcț iei este o listă ș i nu altceva, cum ar fi un ș ir.
[Link](arr):
2. assert(type(arr) == list)
3. # Faceț i sortarea
4.
[Link]():
6.
7. arr = [6, 3, 5, 1, 8]
136
8. sortator(arr)
9.
10. Am ajuns până aici
11.
12. arr ="Hello"
13. sortator(arr)
14.
[Link]ă__nume__=="__principal__":
[Link]()
principala()
Fiș ierul "[Link]", linia 13, în main
ordonator(arr)
Fiș ier "[Link]", linia 2, în sorter
assert(type(arr) == list)
După cum poț i vedea, afirmaț ia noastră a fostAdevăratcând am trecut lista, aș a că programul
a continuat ca de obicei. Când am trecut un ș ir de caractere funcț iei de sortare,
afirmaț ie returnatăFalsiar programul nostru s-a încheiat ș i a generat unEroare de aserț iune.
În această secț iune voi vorbi despre gestionarea excepț iilor pe care le putem întâlni.
întâmpinare în codul nostru. În Python, pentru a gestiona excepț iile, folosim
aîncercăș icu excepț iabloc. Capturăm erorile folosind aceste construcț ii.
[Link] = input()
2. cu deschiderea (filename) ca f:
137
3. lines = [Link]()
4.
[Link](liniile)
Urme de apel (cea mai recentă apelare a avut loc ultima dată):
cu open("[Link]") ca f:
Programul nostru s-a prăbuș it. Ce ar fi dacă am dori să gestionăm acest lucru în mod corespunzător ș i
Permiteț i utilizatorului să introducă din nou numele fiș ierului? Folosim unîncearcăș iexceptblochează la
fă asta.
3. încercă:
4. cu deschiderea(filename) ca f:
5. print([Link]())
6. filename = input("Enter a file name: ")
7. exceptFileNotFoundError:
8. Fiș ierul respectiv nu există în directorul curent
9. filename = input("Enter a file name: ")
$ py citeste_fisiere.py
['This is line one.\n', "I'm line two.\n", "And I'm line three"]
Introduceț i un nume de fiș ier: [Link]
BaseException
+-- SystemExit
+-- Interrupere Tastatură
138
+-- GeneratorExit
+-- Excepț ie
+-- StopIteration
+-- Opreș teAsyncIteraț ia
+-- EroareAritmetica
| +-- EroarePunctFloat
| +-- OverflowError
| +-- ZeroDivisionError
+-- AssertionError
+-- AttributeError
+-- Eroare de buffer
+-- EOFError
+-- ImportError
| +-- Eroare: Modul netăcut
+-- LookupError
| +-- Eroare de index
+-- KeyError
+-- Eroare de memorie
+-- NameError
+-- UnboundLocalError
+-- Eroare de tip OSError
| +-- BlockingIOError
| +-- EroareProcesCopil
| +-- ConnectionError
| | +-- BrokenPipeError
| | +-- ConnectionAbortedError
| | +-- ConnectionRefusedError
| | +-- ConnectionResetError
| +-- FileExistsError
| +-- Eroare: Fi ș ierul nu a fost găsit
139
| +-- EroareNuEsteDirector
| +-- EroareDePermisiune
| +-- EroareCautareProces
| +-- Eroare de Timeout
+-- RuntimeError
| +-- NotImplementedError
| +-- Eroare de recursie
+-- TypeError
+-- Eroare de valoare
| +-- UnicodeError
| +-- UnicodeDecodeError
| +-- UnicodeEncodeError
| +-- UnicodeTranslateError
+-- Atenț ie
+-- Avertizare de deprecatie
+-- AvertizareUtilizator
+-- AvertismentBytes
140
numele fiș ierului după ce se întâmplă. Putem avea mai multe clauze except după
thetrybloc.
3. încearcă:
4. cu open(filename) ca f:
5. print([Link]())
6. filename = input("Enter a file name: ")
7. exceptFileNotFoundError:
8. Fiș ierul respectiv nu există în directorul curent
9. filename = input("Enter a file name: ")
10. cu excepț ia:
11. A apărut o eroare neaș teptată
12. filename = input("Enter a file name: ")
[Link] = int(input())
2.încercare:
14.4 - în sfârș it
De obicei, dacă avem unîncearcăș iînafarădebloc, vom încerca să facem ceva specific
care poate fi predispus la erori. În exemplul din secț iunea anterioară, că
ceva specific deschidea un fiș ier. Nu ar trebui să cerem utilizatorului pentru
introduceț i din nou înîncearcăbloc. De asemenea, nu ar trebui să cerem utilizatorului să introducă
numele fiș ierului din nou după ce am gestionat excepț ia încuexcepț ia bloc.
În schimb, vrem o modalitate de a curăț a după aceea. În Python, facem acest lucru
cuînsfârș it declaraț ie.
Acest lucru este demonstrat mai jos:
3. încearcă:
4. cu open(filename) ca f:
5. print(f.citeste_liniile())
6. exceptFileNotFoundError:
7. Fiș ierul respectiv nu există în directorul curent
8. cu excepț ia:
9. A apărut o eroare neaș teptată
10. în sfârș it
141
11. filename = input("Enter a file name: ")
14.5 - Exerciț ii
Întrebare 1
Scrie un program care ia un număr dintr-un argument de linie de comandă ș i
afiș ează multiplii acelui număr până la 10. Utilizatorul ar trebui să poată de asemenea
pentru a specifica un flag de formatare ș i/sau un flag de scurtare la linia de comandă. Ca un
exemplu, aruncă o privire la câteva moduri diferite în care un utilizator ar putea să ruleze
program:
$ py times_tables.py 15
0 * 15 = 0
1 * 15 = 15
2 * 15 = 30
3 * 15 = 45
4 * 15 = 60
5 * 15 = 75
6 * 15 = 90
7 * 15 = 105
8 * 15 = 120
9 * 15 = 135
10 * 15 = 150
$ py times_tables.py -f 15
0 * 15 = 0
1 * 15 = 15
2 * 15 = 30
3 * 15 = 45
4 * 15 = 60
5 * 15 = 75
142
6 * 15 = 90
7 * 15 = 105
8 * 15 = 120
9 * 15 = 135
10 * 15 = 150
$ py times_tables.py -f -s 15
0
15
30
45
60
75
90
105
120
135
150
exemplu)
• Utilizatorul introduce aceeaș i steag de două sau mai multe ori.
• Utilizatorul introduce două sau mai multe numere
Întrebarea 2
Când ar trebui să folosim următoarele?
143
• a ridica
• în cele din urmă
• încearcăș iexcepț ie
• Ce este o precondiț ie?
• Ce este o postcondiț ie?
144
Capitolul 15 - Mai multe despre tipurile de date
15.1 - Tuple
O tuplă este în esenț ă o listă imutabilă. Tuplele, la fel ca ș irurile, nu pot fi modificate.
după creare. Cu toate acestea, un tuplu este diferit de un ș ir de caractere în sensul că, în timp ce ș irurile
consistă exclusiv din caractere, un tuplu poate conț ine obiecte de orice tip (ca o listă).
>>> prietena_mea=2, 4, 8, 16
>>> tupla_mea
(2, 4, 8, 16)
În general, încapsulăm un tuplu între paranteze, deoarece asta face lucrurile mai uș oare.
citiț i.
>>> tupla_mea= Bună
>>> tupla_mea
"Bună ziua"
>>> t= (4,)
>>>tip(t)
<clasa'tuplu'>
>>> v= (4)
>>>tip(v)
<clasă'int'>
(2, 4, 6, 8, 2, 4, 6, 8)
145
De asemenea, putem tăia ș i indexa în acelaș i mod în care o facem cu ș irurile de caractere:
>>> t= (5, 4, 3, 2, 1)
>>> t[3]
2
>>> t[::-1]
(1, 2, 3, 4, 5)
>>> t[1:3]
(4, 3)
...printează(c)
...
a
b
c
We can use the înoperator pentru a verifica dacă o valoare există într-un tuplu
>>> t= ("John","Liam","Tony")
>>>print"Tony"int
Adevărat
Ș i în cele din urmă, aș a cum era de aș teptat, primim o eroare dacă încercăm să schimbăm conț inutul unui tuplu:
>>> t= (1, 2, 3)
>>> t[0] =4
Urmează (cea mai recentă apelare ultimei):
>>> d= {"a":10,"b":11,"c":12}
pentru(k, v) î[Link]():
146
...print(k, v)
...
a10
b11
c12
15.2 - Seturi
Un set este o colecț ie de obiecte de tip arbitrar. Obiectele setului se numesc
membrii săi. Seturile sunt un tip neordonat (ca dicț ionarele). Ele sunt de asemenea
iterabile. O caracteristică importantă a mulț imilor este că acestea conț in doar o singură copie a unei
un obiect particular adică duplicatele nu sunt permise. Seturile sunt tipuri mutabile.
Seturile sunt folosite în general pentru testarea apartenenț ei ș i eliminarea duplicatelor. Ele
de obicei deț in o colecț ie de obiecte similare.
Pentru a profita din plin de seturi, va trebui să aveț i o bună înț elegere a setului
teorie. Nu voi acoperi teoria mulț imilor în această carte, aș a că poț i să te documentezi despre ea.
aici:Introducere în teoria mulț imilor. Cu toate acestea, este posibil să fii familiarizat cu setul de bază
teoria aș a cum ai acoperit-o la ș coală. Mulț imile sunt foarte importante ș i sunt unul dintre
tipuri de date care apar în interviuri.
De asemenea, putem crea un set folosind valori separate prin virgulă, închise între acolade.
braces:
x= {1, 2, 3, 4}
Reț ineț i că nu putem folosi{} pentru a crea un set gol, deoarece acest lucru ar crea un
dicț ionar gol.
147
Pentru a adăuga un nou membru la un set, folosimadauga()method:
>>> x= {2, 4, 6}
>>> [Link]ă(8)
>>> x
{8, 2, 4, 6}
>>> s=setabcdefghijk
>>> s
{'d','e','i','h','k','g','j','f','a','b','c'}
{9, 2, 4, 5, 6}
Aceasta este deosebit de utilă atunci când căutăm elemente unice în ceva.
>>> A= {2, 3, 4, 5, 6, 7}
>>> B= {4, 5, 6, 10, 34, 22, 1}
>>> [Link](B)
{4, 5, 6}
148
Putem obț ine uniunea a două mulț imi A ș i B folosinduniune()metodă. The
uniunea a două mulț imi este mulț imea elementelor din A ș i B:
>>> A= {1, 3, 3, 7}
>>> B= {2, 3, 6, 8}
>>> [Link](B)
{1, 2, 3, 6, 7, 8}
We can get the set difference between two sets A and B using
thediferenț ă() metoda. Diferenț a mulț imii A faț ă de B este mulț imea elementelor din A dar
nu în B. La fel, diferenț a de seturi B faț ă de A este setul de elemente din B, dar nu din A:
>>> A= {1, 2, 3, 4, 5, 6}
>>> B= {4, 5, 6, 7, 8, 9}
>>> [Link]ț ă(B)
{1, 2, 3}
>>> [Link]ț ă(A)
{8, 9, 7}
De asemenea, putem verifica dacă mulț imea B este o submulț ime a lui A utilizândissubset()metodă. Set A
A este un subsistem al setului B dacă fiecare membru al lui A este, de asemenea, un membru al lui B:
>>> A= {2, 4, 6}
>>> B= {1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> A.este_submultime(B)
Adevărat
>>> B.este_submulț ime(A)
Fals
>>> A= {2, 4, 6}
>>> B= {1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> B.este_supraconjunctie(A)
Adevărat
>>> A.este_superior(B)
Fals
149
15.3 - Liste ș i comprehensiuni de liste
Am văzut cum să creaț i liste ș i ar trebui să fii obiș nuit să o faci la acest
punct. Cu toate acestea, consideraț i următoarea sarcină:
Scrie un program care construieș te o listă ce conț ine toate numerele paire din a
a doua listă.
Sarcina de a construi o listă prin procesarea elementelor dintr-o altă listă este foarte
task comun în informatică. Până acum, a trebuit să folosim un anumit tip de buclă
pentru a itera peste toate elementele din a doua listă ș i a selecta numerele pare
Numerele. Python a oferit un scurtcircuit pentru asta numit comprehensiune de listă.
Ai văzut cum folosesc o compunere de liste într-un capitol anterior pentru a construi un
lista de 1.000 de întregi.
De exemplu, pentru a crea o listă care conț ine fiecare număr de la 0 la 1.000, noi
a putea folosi următoarea compunere a listei:
lst= [xpentruxinrange(0,1000)]
Lista de mai sus se citeș te: "Adaugă x la noua listă pentru fiecare x din listă"
elementelor de la 0 la 1000.
Pentru a rezolva sarcina, am menț ionat la începutul acestei secț iuni că am putea folosi
următoarea compunere a listei:
>>> lista_mea= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> evenimente= [xpentruxînlista_meadacă nux%2]
>>> pare
[2, 4, 6, 8, 10, 12, 14]
Amintiț i-vă, 0 este fals, prin urmare,dacă nu x % 2este adevărat dacă x % 2 este egal cu 0.
150
Putem folosi o expresie de listă pentru a construi o listă de valori pătrate din
o altă listă folosind următoarea compunere a listelor:
>>> vals= [1, 2, 3, 4, 5, 6]
>>> pătrate= [x**2forxînvals
>>> pătrate
[1, 4, 9, 16, 25, 36]
Lista de mai sus se citeș te astfel: "Adaugă pătratul lui x dacă x este par"
altfel doar x pentru fiecare x din vals
Compresiile de liste sunt atât de comune încât este uș or să te împiedici de ele ș i de multe ori le vei vedea.
sunt utilizate dacă cercetezi orice probleme online. În general, ele sunt o
constructor găsit doar în Python. Dacă treci la Java, de exemplu, în
în viitor, nu vei putea folosi comprimele de listă deoarece acestea nu există în
Java.
Comprehensiile nu se aplică doar listelor. Ele pot fi folosite ca scurtături pentru
creând o nouă colecț ie din alte colecț ii. Prin urmare, ne-am stabilit ș i
compresiuni de dicț ionar:
>>> setul meu= {xpentruxinrange(10)}
>>> setul_meu
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
>>> my_dict= {x:Truepentruxîn intervalul (5)}
>>> my_dict
{0Adevărat,1Adevărat,2Adevărat,3Adevărat,4:Adevărat}
15.4 - Exerciț ii
151
Descărcaț i următorul fiș ier (copiaț i această pagină într-un fiș ier text):Dicț ionar.
Întrebarea 1
În timpul unui studiu, mai mulț i ingineri software au fost întrebaț i care sunt cele mai bune 3
Programul dumneavoastră ar trebui să fie rulat astfel ș i să ofere următoarea ieș ire:
$ py [Link] [Link]
8
Întrebare 2
Scrie o compunere de listă care creează o listă conț inând toate numerele impare
între 0 ș i 10.000.
Întrebarea 3
Folosind dicț ionarul pe care l-ai descărcat anterior, scrie un program care construieș te o listă
care conț ine toate cuvintele care au 18 caractere sau mai mult. Tu
ar trebui să foloseș ti o comprehensiune de listă pentru a face asta!
Notă: Acest lucru poate dura ceva timp, deoarece fiș ierul de intrare este mare!
Întrebarea 4
152
Folosind dicț ionarul pe care l-ai descărcat anterior, scrie un program care construieș te o listă
conț inând toate cuvintele care conț in fiecare vocală (a, e, i, o ș i u). De exemplu,
the word "equation" should be in the list. You should make good use of a list
înț elegere pentru a face asta!
Întrebarea 5
Folosind dicț ionarul pe care l-ai descărcat anterior, scrie un program care construieș te o listă
conț inând toate cuvintele care conț in exact 4 a-uri ș i se termină în 'ian'. Pentru
exemplu, cuvântul "alabastrian" ar trebui să fie în listă. Ar trebui să faci bine
foloseș te o compunere a listelor pentru a face asta!
Întrebarea 6
Folosind dicț ionarul pe care l-ai descărcat anterior, scrie un program care construieș te o listă
conț inând toate cuvintele din dicț ionar a căror inversă apare de asemenea. Pentru
exemplu, cuvintele "lager" ș i "regal" ar trebui să fie în listă. Ar trebui să faci
utilizare bună a comprehensiunilor pentru a face asta!
va dura foarte mult timp să ruleze dacă nu implementaț i o soluț ie mai eficientă!
153
Capitolul 16 - Recursie ș i Quicksort
16.1 - Recursie
Înainte să continui, vreau să spun asta, scrierea unei soluț ii recursive este
DIFICIL când începem. Nu te aș tepta să funcț ioneze din prima. A scrie o
soluț ia recursivă implică o nouă modalitate de a gândi ș i poate fi de fapt
destul de descurajant pentru cei noi, dar rămâi cu el ș i te vei întreba cum ai ajuns
întotdeauna ai găsit-o atât de dificilă.
Deci, ce este, de fapt, recursia? O soluț ie recursivă este una în care soluț ia la
o problemă este exprimată ca o operaț iune asupra unei versiuni simplificate a aceleaș i
problemă.
Acum, probabil că asta nu a avut prea mult sens ș i este foarte complicat să
explică exact cum funcț ionează aș a că să luăm un exemplu simplu:
[Link](x):
2. returnreduce(x-1)
Pentru a rezolva această problemă, trebuie să adăugăm ceva numit cazul de bază.
Aceasta este pur ș i simplu o verificare pe care o adăugăm astfel încât funcț ia noastră să ș tie când să înceteze apelurile
în sine. Cazul de bază este de obicei cea mai simplă versiune a problemei originale
ș i unul la care ș tim întotdeauna răspunsul.
154
Să corectăm eroarea noastră adăugând un caz de bază. Pentru această funcț ie, vrem să se oprească.
când ajungem la 0.
[Link](x):
2. dacă x == 0:
3. return0
4. returnreduce(x-1)
reduce(5)
0
Groza, funcț ionează! Să aruncăm o altă privire asupra a ceea ce se întâmplă de data aceasta. Noi numim
reduce(5) care apelează reduce(4)... care apelează reduce(0). Ok, stop aici, avem
a lovit cazul nostru de bază. Acum, ceea ce va face funcț ia este să returneze 0 apelului anterior
de reduce(1) care returnează 0 la reduce(2).... care returnează 0 la reduce(5) care
îț i returnează răspunsul. Iată, prima ta soluț ie recursivă!
De exemplu, 4! = 4 * 3 * 2 * 1
Cazul nostru de bază pentru acest exemplu este N = 0, deoarece 0! este definit ca 1. Aș adar, să scriem nostra
funcț ie:
[Link](n):
2. dacă n == 0:
3. return1
4. returnează * factorial(n-1)
Bine, să vedem asta în acț iune. Vom apela funcț ia noastră ș i vom trece 4 pentru n:
factorial(4) apelează factorial(3) ..... care apelează factorial(0) care este cazul nostru de bază
aș adar, întoarcem 1 înapoi la apelul anterior al factorial(1) care ia 1-ul nostru ș i
înmulț eș te-l cu 1, ceea ce evaluează la 1, care este întors la factorial(2)
care ia 1-ul nostru ș i îl înmulț eș te cu 2, ceea ce evaluează la 2, care îl pasează.
înapoi la factorial(3) care înmulț eș te 3 cu 2 pentru a obț ine 6, care o transmite înapoi la
factorial(4) care multiplică 4 6 care evaluează la 24 care este returnat ca al nostru
răspuns.
Acestea sunt cazuri foarte simple ș i nu foarte utile, dar a putea identifica când
o soluț ie recursivă poate fi implementată ș i apoi implementând acea soluț ie
155
este o abilitate care te va face un programator mai bun. Pentru anumite probleme
recursia poate oferi o soluț ie intuitivă, simplă ș i elegantă.
16.2 - Memorare
Am scris soluț ia la problema Fibonacci de câteva ori
pe parcursul acestei cărț i. Când am redactat acele soluț ii, am folosit o abordare iterativă
abordare. Totuș i, putem adopta o abordare recursivă. Poate fi dificil să
recognize when a recursive solution is an option, but this is a great example of
când o soluț ie recursivă este o opț iune!
[Link](n):
2. dacă ifn <= 1:
3. return1
4. altceva:
5. returnfib(n-1) + fib(n-2)
Asta e mult mai simplu! În acest exemplu, vom lua fib(0) ca fiind 1 ș i fib(1) ca fiind 1.
de asemenea. Prin urmare, cazul nostru de bază este dacă n este 0 sau 1, returnăm 1. Cazul recursiv
provine direct din definiț ia secvenț ei Fibonacci, adică:
fib(n)=fib(n−1)+fib(n−2)
Cu toate acestea, este posibil să fi observat că, dacă introduceț i orice valoare mai mare decât
156
Putem observa că atunci când apelămfib(5) noi, în diverse momente în funcț iile noastre
execution, call fib(1)de 5 ori! ș ifib(2)De 3 ori! Acesta este inutil. De ce
trebuie să recalculăm valoarea pentrufib(1)iar ș i iar?
Putem reduce numărul de ori în care trebuie să calculăm diverse valori prin
folosind o tehnică numită memoizare. Memoizarea este
o tehnică de optimizare utilizată pentru a accelera programele noastre prin stocarea în cache
rezultatele apelurilor funcț iilor costisitoare. Un cache este, în esenț ă, o stocare temporară
zona ș i putem implementa un cache înfib()funcț ie pentru a stoca anterior
valori calculate ș i doar le extragem din cache când este nevoie în loc să
efectuarea apelurilor de funcț ie inutile.
Putem folosi un dicț ionar pentru a implementa un cache. Aceasta ne va oferi O(1) pentru
accesarea ș i va îmbunătăț i drastic performanț a funcț iei noastre.
[Link](n, cache=None):
2. Evita capcana argumentului mutabil implicit!
3. ifcache == None:
4. cache = {}
5. # Caz de bază
6. daca n <= 1:
7. return1
8. Dacă valoarea nu este în cache, atunci calculează-o ș i stocheaz-o în cache
9. elif nu este în cache:
10. cache[n] = fib(n-1, cache) + fib(n-2, cache)
11. Returnează valoarea
12. returncache[n]
157
Acum putem sunafib(900)ș i obț ineț i răspunsul imediat! Implicit, Python
limitează adâncimea recursivităț ii la 1000. Putem suprascrie acest lucru, dar de obicei nu este o
idee bună!
Putem vedea din arbore că sunt mai puț ine apeluri către funcț ie, chiar dacă
suntem o valoare mai mare. Aceasta este o creș tere semnificativă a performanț ei. Chiar ș i apelând
de lafib(5)ne-am salvat 6 apeluri de funcț ii!
Deoarece acesta este un algoritm de împărț ire ș i cucerire, dorim să luăm o listă de nesortate
numere întregi ș i împărț iț i problema în două probleme mai uș oare ș i apoi descompuneț i
fiecare dintre aceș tia în jos…. ș i aș a mai departe.
Pentru a realiza acest lucru, voi începe prin a explica operaț ia principală a quicksort-ului: partiț ionarea. Aceasta funcț ionează
158
[6, 3, 17, 11, 4, 23, 12, 30, 76, 44]
Deci, ce s-a întâmplat aici ș i cum funcț ionează? Trebuie să alegem câteva
numărul ca pivot. Funcț ia noastră de partiț ie primeș te 3 argumente, lista,
primul element din listă ș i pivotul. Ce încercăm să realizăm aici este
când partitionăm lista, tot ce este la stânga pivotului este mai mic decât
pivotul ș i tot ce este la dreapta este mai mare decât pivotul. Pentru prima
partiț ia văzută mai sus, 30 este pivotul nostru. Întotdeauna ne vom lua partiț ia să fie
ultimul element din listă. După partiț ionare, observăm că unele elemente s-au schimbat
poziț ie, dar tot ce este la stânga lui 30 este mai puț in decât acesta ș i tot ce este la
dreapta este mai mare decât ea.
Să ne uităm la cod:
[Link](A, p, r):
2. q=j=p
3. whilej < r:
4. dacă A[j] <= A[r]:
5. A[q], A[j] = A[j], A[q]
6. q += 1
7. j += 1
8. A[q], A[r] = A[r], A[q]
9. întoarce
Ceareturnqla final nu este necesar pentru partajul nostru, dar este esenț ial pentru
sortarea întregii liste. Codul de mai sus parcurge listaAș i
menț ine indiciip, q, j, r.
peste fixat ș i este primul element din listă.reste pivotul ș i este ultimul
element în listă. Elemente în intervalA[p:q-1]sunt cunoscuț i a fi mai puț in decât
sau egal cu pivotul ș i totul de laA[q-1:r-1]sunt mai mari decât
pivot. Singurele indici care se schimbă suntq ș ijLa fiecare pas noi
comparaA[j]cuA[r]Dacă este mai mare decât pivotul, se află în corect
poziț ie, aș a că incrementămjș i treceț i la următorul element. DacăA[j]este mai puț in
decâtA[r]noi schimbămA[q]cuA[j]După acest schimb, incrementămqastfel
extinderea gamei de elemente cunoscute ca fiind mai mici sau egale cu pivotul.
De asemenea, creș temj pentru a trece la următorul element care trebuie procesat.
159
16.4 - Quicksort partea 2
Acum ne îndreptăm spre partea de quicksort. Amintiț i-vă că este un algoritm recursiv, aș a că va
apelează continuu lapartiț ionaț i() până când nu mai rămâne nimic de împărț it ș i tot
elementele sunt în poziț iile lor corecte. După prima partiț ie, noi
apelpartiț ionare()din nou, de data aceasta o numim pe lista elementelor din stânga lui
pivotul ș i lista de elemente la dreapta pivotului.
Să ne uităm la cod:
[Link](A, p, r):
2. ifr <= p: # Dacă r <= p, atunci lista noastră este sortată
3. returnare
4. q = împărț ire(A, p, r) partiț ionează lista de intrare
5. quicksort(A, p, q-1) apelează din nou quicksort pe tot ce este la stânga pivotului
6. quicksort(A, q+1, r) apelează din nou quicksort pe tot ceea ce este la dreapta pivotului
7. returnA
Este atât de simplu. Tot ce facem aici este să verificăm dacă indexul pivotului este mai mic decât sau
egal cu indexul începutului listei noastre pe care dorim să o partitionăm. Dacă este aș a, returnăm
deoarece orice listă a fost trecută nu mai trebuie să fie partitionată mai departe.
Altfel, împărț im lista A ș i apelăm din nou quicksort pe cele două noi sub
liste.
Pe linia 3, ne întoarcem fără a specifica nimic de întors. Aceasta se datorează faptului că.
funcț ia quicksort este o procedură.
Quicksort funcț ionează cel mai bine pe liste mari care sunt complet amestecate. Are cu adevărat
performanț ă slabă pe liste care sunt aproape sortate. Sau în notaț ia Big-O, cea mai bună
cazul (amestecat) este O(n log(n)) ș i în cel mai rău caz, (aproape sau complet
lista ordonată) este O(n^2).
Din nou, te încurajez să încerci asta pe hârtie cu o listă simplă. Te va ajuta să clarifici
ce se întâmplă.
16.5 - Exerciț ii
Important: These exercises are quite difficult! Make use of problem-solving
tehnici pentru a te ajuta să ajungi la o soluț ie. Schiț ând ce se întâmplă pe
hârtie, este o modalitate bună de a te ajuta!
160
Unele dintre aceste întrebări sunt genul de întrebări pe care le poț i aș tepta dacă obț ii un
întrebare de recursie când intervievăm la companii precum Google, Facebook
sau Amazon.
Întrebare 1
Ce este:
• Recursie?
• Memoizarea?
Întrebarea 2
Scrie o funcț ie recursivă care adună toate numerele de la 1 la 100.
Întrebarea 3
Scrieț i o funcț ie recursivă care primeș te un întreg ca argument ș i returnează
dacă acel întreg este o putere a lui 2. Funcț ia ta ar trebui să returnezeAdevăratsauFals
Întrebarea 4
Scrie o funcț ie recursivă care ia un ș ir de caractere ca argument ș i returnează
dacă acea sirgă este un palindrom. Funcț ia ta ar trebui să returnezeAdevăratsauFals.
Întrebare 5
Scrie o funcț ie recursivă care ia o listă de întregi ca argument ș i
returnează maximul acelei liste.
Sugestie: Gândindu-ne recursiv, maximul este fie primul element al listei sau
maximul listei rămase!
161
Capitolul 17 - Programare Orientată pe Obiect
Programare (OOP)
17.1 - Clase ș i Obiecte
Până acum, am întâlnit multe dintre tipurile încorporate ale Pythonului, cum ar fi
ca booleans, întregi, dicț ionare s.a.m.d. Acestea sunt toate tipuri de clasă. Asta înseamnă
că orice instanț ă a unui ș ir, listă, număr float etc. este un obiect al clasei ș ir, listă sau
float. Cu alte cuvinte, fiecare obiect de tip string, de exempluBună, este un exemplu de
clasa de ș iruri. Un obiect este o implementare a unui tip
Cel mai adesea, tipurile încorporate ale Python nu sunt suficiente pentru a modela datele pe care le
vrem, aș a că ne-am construit propriile tipuri (sau clase) care modelează datele exact aș a cum
avem nevoie.
O modalitate bună de a gândi la asta este că o clasă este un formator de prăjituri ș i o instanț ă a
această clasă este cookie-ul pe care l-am tăiat.
162
17.2 - Definirea unui nou tip
Să zicem că am vrut să modelămTimpTipurile de date încorporate din Python nu vor
a fi suficient, a modela acest lucru cu uș urinț ă ș i logic. În schimb, am crea noi
propriuTimpclasă. Definim o nouă clasă folosindclasădeclaraț ie.
[Link]:
2. trece
Salvează codul de mai sus într-un fiș ier numit my_time.py ș i importă-l astfel:
>>>de laimporta_timpul_meu
>>> t= Time()
>>>tip(t)
<clasa'[Link]'>
>>>esteinstanț ă(t, Time)
Adevărat
>>>print(t)
<time.Timeobjectat0x000001A7C6902F60>
Putem vedea căt este de tipTimpș iteste o instanț ă deTimpș i putem să o vedem
este un obiect stocat la adresa de memorie0x000001A7C6902F60.
[Link]:
2.
3. defset_time(time_obj, ore, minute, secunde):
4. time_obj.hours = hours
5. time_obj.minute = minute
6. time_obj.seconds = seconds
7.
8. defdisplay(time_obj):
9. print("Ora este {}:{}:{}".format(time_obj.hours,
10. time_obj.minutes,
11. time_obj.seconds))
163
Aș a cum este arătat mai sus, accesăm atributele ore, minute ș i secunde folosind
operatorul de perioadă de exemplutime_obj.hours = hoursAsta
spune, pentru moment
obiectul care a fost trecut, setează atributul său ore la orele trecute ca un
argument.
>>>de latimpul_meuimportTimp
>>> t= Time()
>>> Time.set_time(t,11, 32, 45)
>>> [Link](t)
Ora este 11:32:45
>>> t2= Timp()
>>> Time.set_time(t2,22, 43, 17)
>>> [Link](t2)
Ora este 22:43:17
>>> [Link](t)
164
Este ora 11:32:45
By convention, this first parameter, which we’ve been calling obj_timp, este
denumitsinAcesta se referă la instanț a pe care metoda este aplicată.
face metodeleset_time()ș iafiseaza()metode de instanț ă.
Metodele de instanț ă sunt metode care acț ionează asupra unei instanț e particulare a unui obiect.
Primul său parametru este întotdeauna obiectul asupra căruia va opera. În mod implicit,
Toate metodele din clase sunt metode de instanț ă, cu excepț ia cazului în care le declarăm ca fiind metode de clasă.
[Link]:
2. defset_time(self, ore, minute, secunde):
3. [Link] = hours
4. [Link] = minutes
5. [Link] = secunde
6.
7. defdisplay(self):
8. "Ora este {}:{}:{}'.format([Link],
9. [Link],
10. [Link]))
>>> t= Timp()
>>> t.set_time(11, 32, 45)
>>> t2= Timp()
>>> t2.stabileste_timpul(22, 34, 18)
>>> [Link]()
Ora este 11:32:45
>>> [Link]()
165
Voi lăsa asta aș a pentru acest capitol. Există multe de asumat aici ș i
este cu adevărat lucruri importante! Restul cărț ii va fi concentrat exclusiv pe obiecte-
programare orientată pe obiect. Aș adar, asiguraț i-vă că înț elegeț i materialul din acest
rezervaț i ș i completaț i exerciț iile următoare.
17.4 - Exerciț ii
Întrebare 1
Scrie o clasă care modelează unLampăClasa lampă va avea două metode.
prima va inicializa lampa ș i este apelatăconectare(). Acest lucru va seta
theis_on atribut care este un boolean pentruFalsA doua metodă este
apelatcomută()Dacă lampa este stinsă, o va aprinde.este_activatcătreAdevărat) ș i dacă
lampa este aprinsă, o va stinge (setis_on pentruAdevărat).
Fals
Întrebarea 2
Scrie o clasă care modelează unCerculClasa cercului va avea patru metode.
mai întâi se va iniț ia cercul. Cinitialise()metoda ar trebui să ia trei
parametriix_coord, y_coord, ș irazaAceasta va seta x ș i y ale cercurilor
coordonate ș i raza sa. Următoarea metodă se numeș tecalc_aria(). Ar trebui să
calculati aria cercului (cautati formula). A treia metoda este
apelatcalc_perimetru()ș i ar trebui să calculeze circumferinț a cercului
(Caută formula). A patra metodă estese suprapune(). Ar trebui să dureze ca un
argument, un alt cerc ș i afiș aț i dacă cele două cercuri se suprapun sau nu.
166
Clasa ta poate fi importată ș i utilizată astfel:
>>>de lamy_circleimportCircle
Întrebarea 3
Scrieț i o clasă care să modeleze notele unui student pentru modulele particulare. Clasa
va avea patru metode. Prima ar trebui să iniț ializeze studentul. Studentul
ar trebui să aibă un nume ș i o vârstă. Notele ar trebui modelate ca un dicț ionar
in which the key is the name of the module and the value is the grade. This
ar trebui să fie iniț ial gol. A doua metodă se numeș teadaugă_modul()ș i
ar trebui să adăugaț i un modul la obiectul student. Al treilea este
apelatupdate_module_grade()ș i ar trebui să actualizeze nota pentru un anumit
modulul. Ultima metodă se numeș teafiș ează_note() ș i ar trebui să afiș eze
module studenț i ș i nota asociată fiecărui modul.
Clasa dumneavoastră poate fi importată ș i utilizată după cum urmează:
>>>de laimportăStudentulMeu
167
>>> [Link]ă_modul("Reț ele")
>>> [Link]ă_notă_modul(77)
>>> s1.arata_note()
Notele lui Noah sunt:
Python:87
Reț ele:77
168
Capitolul 18 - OOP: Metode Speciale ș i
Supraîncărcarea operatorilor
[Link]:
2. def__init__(self, x, y):
3. self.x = x
4. self.y = y
5.
6. defdisplay(self):
7. print("Coordonata X: {} Coordonata Y: {}".format(self.x, self.y))
După cum puteț i vedea, nostru__init__()metoda a fost apelată automat când noi
am creat o instanț ă a clasei punct.
169
TypeError:__init__() missing2required positional arguments:'x'and'y'
Cu toate acestea, putem seta valori implicite pentru aceș ti argumenti. Acest lucru ne va permite să
iniț ializează o instanț ă dePunctfără a trece argumentele:
[Link]:
2. def__init__(self, x=0, y=0):
3. self.x = x
4. self.y = y
5.
6. defdisplay(self):
7. print("Coordonata X: {} Coordonata Y: {}".format(self.x, self.y))
Putem suprascrie această metodă pentru a ne permite să formatăm ș i să imprimăm obiectele noastre aș a cum dorim.
a considera potrivit. Prin urmare, când apelămprint()pe un obiect al unei clase pe care am definit-o,
170
Facem acest lucru returnând un ș ir formatat. Să vedem cum am putea face asta.
pentruPunctclasă. Acum am putea înlocuiafiseaza()funcț ie ș i înlocuieș te-o
cu__str__(), astfel putem să tipărim doar instanț a noastră de punct.
[Link]:
2. def__init__(self, x=0, y=0):
3. self.x = x
4. self.y = y
5.
6. def__str__(self):
7. reîntoarce"Coordonata X: {} Coordonata Y: {}".format(self.x, self.y)
Valoarea de returnare a acestei metode speciale trebuie să fie un obiect de tip ș ir.
[Link]:
2. def __init__(self, x=0, y=0):
3. self.x = x
4. self.y = y
5.
6. def__str__(self):
7. Returnează "Coordonata X: {} Coordonata Y: {}".format(self.x, self.y)
8.
9. def__len__(self):
10. distance_from_center = ((self.x)**2 + (self.y)**2)**0.5
11. returndistance_from_center
171
Este regretabil că nu putem returna un număr în virgulă mobilă, prin urmare, dacă noi
dacă vrem o acurateț e reală, va trebui să implementăm o metodă diferită pe care o vom avea
a apela la instanț ă.
[Link]:
2. def __init__(self, x=0, y=0):
3. self.x = x
4. self.y = y
5.
6. def__str__(self):
7. Coordonata X: {} Coordonata Y: {}
8.
9. def__len__(self):
10. distance_from_center = ((self.x)**2 + (self.y)**2)**0.5
11. returnare(int(distanta_de_la_centru))
12.
13. def__eq__(self, other):
14. return((self.x, self.y) == (other.x, other.y))
Am putea adăuga, de asemenea, două puncte pentru a obț ine un nou punct. În acest caz, noi
ar suprasolicita__add()__ metodă. The__add__() metoda implementează
funcț ionalitatea + operator, nu+=operator. Prin urmare, trebuie să ne întoarcem
un nou obiect ca+ operatorul nu este pentru adunare în loc.
172
Să ne uităm la asta:
[Link]:
2. def__init__(self, x=0, y=0):
3. self.x = x
4. self.y = y
5.
6. def__str__(self):
7. return "Coordonata X: {} Coordonata Y: {}".format(self.x, self.y)
8.
9. def__len__(self):
10. distance_from_center = ((self.x)**2 + (self.y)**2)**0.5
11. returnează int (distanț a de la centru)
12.
13. def__eq__(self, altul):
14. return((self.x, self.y) == (other.x, other.y))
15.
16. def__adăuga__(self, other):
17. new_x = self.x + other.x
18. new_y = self.y + other.y
19. returnPoint(new_x, new_y)
Putem supraîncărca+=operator, care este pentru adăugare în loc. În acest fel, noi
nu trebuie să returnezi o referinț ă la un nou obiect punct ș i să o asignezi unei
variabilă nouăp3în schimb, actualizăm obiectul(ă)p1în acest caz) atributele de date.
173
Acest lucru se face prin suprasarcina__iadd()__ metodă.
[Link]:
2. def__init__(self, x=0, y=0):
3. self.x = x
4. self.y = y
5.
6. def__str__(self):
7. return"Coordonata X: {} Coordonata Y: {}".format(self.x, self.y)
8.
9. def__len__(self):
10. distance_from_center = ((self.x)**2 + (self.y)**2)**0.5
11. returnint(distanta_de_la_centru)
12.
13. def __eq__(self, other):
14. return((self.x, self.y) == (other.x, other.y))
15.
16. def__adăuga__(self, other):
17. new_x = self.x + other.x
18. new_y = self.y + other.y
19. returneazăPunct(nou_x, nou_y)
20.
21. def__iadd__(self, altul):
22. temp_point = self + other
23. self.x, self.y = temp_point.x, temp_point.y
24. returnează-te
Fii atent când supraîncarci operatorii in-place. În acest caz, folosim să creăm un
punct temporar ș i apoi actualizaț isineinstanț ă folosind atribuirea multiplă.
Îț i aminteș ti când am schimbat valoarea dintr-o variabilă cu alta ș i noi
a trebuit să creăm o variabilă temporară? Putem face asta mult mai repede făcândx, y = y,
x. În acest cazx, yș iy, xsunt tupluri!
18.5 - Exerciț ii
Întrebarea 1
Creează unContBancarclasa. Clasa contului bancar ar trebui să aibă următoarele
attributes: echilibrusiaccount_ownerClasa contului bancar ar trebui să
a aveadepozitș iretragemetode. De asemenea, ar trebui să fiț i capabil săimprimarebanca
cont, pentru a afiș a numele proprietarului contului ș i soldul. Când
implementează corect, ar trebui să poț i folosi clasa cont bancar ca
urmează:
>>>account=BankAccount("John Smith")
>>>print(contul)
Owner: John Smith
Balance: $0
>>>[Link](200)
>>>print(contul)
Owner: John Smith
Balance: $200
>>>[Link](50)
>>>print(account)
Owner: John Smith
Balance: $150
>>>[Link](200)# Not enough in the account to withdraw 200
>>>print(acest cont)
Owner: John Smith
175
Balance: $150
Întrebarea 2
Create a Linieclasă. Clasa linie ar trebui să aibă patru atribute: unx1ș i
oy1coordonate pentru un punct pe linie ș i unx2ș i uny2coordonate pentru
al doilea punct pe linie. Ar trebui să poț i face câteva lucruri cu un
instanț a unei linii. Ar trebui să poț i apela lalenmetodă pe o linie pentru a arăta
lungimea sa, adaugă două linii împreună, scade două linii, înmulț eș te o linie cu un
integertipăriț i linie ș i compară două linii pentru a vedea dacă sunt egale. În acest
egalitatea cazurilor înseamnă că ambele linii au aceeaș i lungime. Când este implementată
Corect, ar trebui să poț i utiliza clasa Line după cum urmează:
>>>lineOne=Line(2,2,4,4)
>>>lineTwo=Line(1,1,3,3)
>>>len(liniazăUnu)
2
>>>linieTrei=linieUnu+linieDouă
>>>len(liniaTrei)
4
>>>lineFour=lineOne-lineTwo
>>>len(liniaPatru)
1
lineFive=lineTwo*3
>>>len(liveFive)
6
>>>print(lineOne)
Line Details:
Point1: (2,2)
Point2: (4,4)
>>>print(liniaUnu==liniaDoi)
Adevărat
>>>print(lineOne==lineFive)
Fals
176
Capitolul 19 - OOP: Tipuri de Metode &
Modificatori de acces
Deja ne-am întâlnit cu metodele de instanț ă. Ele sunt tipul de metode pe care le avem
am lucrat în ceea ce priveș te programarea orientată pe obiect până în acest moment.
Metodele de instanț ă sunt cel mai comun tip de metode în clase. Ele sunt
se numesc metode de instanț ă deoarece acț ionează asupra instanț elor specifice ale unei clase. Ele pot
De exemplu, dacă avem oPersoanăclasă, atunci fiecare instanț ă a unei persoane poate
au un nume unic, vârstă etc. Metodele de instanț ă aueuca primul
parametru, ș i acest lucru ne permite să trecem prinautopentru a accesa atributele datelor
unic pentru acea instanț ă ș i, de asemenea, alte metode care pot reside în cadrul nostru
clasă.
Invocăm metodele de clasă printr-o instanț ă sau printr-o clasă. Spre deosebire de
metode de instanț ă al căror prim parametru estesinonim, cu metode de clasă, este primul
parameter is not an object, but the class itself. This first parameter is called cls.
Folosim un decorator pentru a marca o metodă ca fiind o metodă a clasei. Decoratorul
este@classmethod.
177
Să ne uităm la un exemplu întorcându-ne la nostruTimpclasă. Vrem o funcț ie
care poate converti secunde în format de 24 de ore cu ore, minute ș i secunde.
Această metodă ar trebui să fie legată de clasa deTimpmai degrabă decât un specific
instanț ă.
[Link]:
2. def __init__(self, ore=0, minute=0, secunde=0):
3. [Link] = hours
4. [Link] = minutes
5. [Link] = seconds
6.
7. def__str__(self):
8. Timpul este {:02}:{:02}:{:02}
9. [Link],
10. [Link])
11.
12.# ALTE METODE POT FI AICI...
13.
14. @classmethod
15. defseconds_to_time(cls, s):
16. minute, secunde = divmod(s, 60)
17. ore, minute = divmod(minute, 60)
18. extra, ore = divmod(ore, 24)
19. returneazăcls(ore, minute, secunde)
>>>de lamy_timeimportTime
178
>>> t= Time.seconds_to_time(11982)
>>>print(t)
Am menț ionat ș i variabilele de clasă mai devreme. La fel ca înainte, variabilele de clasă sunt
legat de o clasă mai degrabă decât de o instanț ă specifică. Putem folosi o metodă a clasei pentru a
[Link]:
2.
3. COUNT = 0
4.
5. def __init__(self, ore=0, minute=0, secunde=0):
6. [Link] = hours
7. [Link] = minutes
8. [Link] = seconds
9. [Link] += 1
10.
11. def__str__(self):
12. Timpul este {:02}:{:02}:{:02}
13. [Link],
14. [Link])
15.
16.# ALTE METODE POT FI AICI...
17.
18. @classmethod
19. defsecunde_la_timp(cls, s):
20. minute, secunde = divmod(s, 60)
21. ore, minute = divmod(minute, 60)
22. extra, ore = divmod(ore, 24)
23. returnează cls(ore, minute, secunde)
179
>>> t3= Timp12, 34, 54)
>>> [Link]
Poate fi complicat să îț i dai seama când să foloseș ti aceste lucruri. Ca o regulă generală,
o metodă poate fi invocată (ș i are sens să) în absenț a unei instanț e,
atunci se pare că, această metodă este un bun candidat pentru o metodă de clasă.
Metodele statice sunt metode care sunt legate de clasă într-un fel, dar
nu este nevoie să accesaț i date specifice clasei ș i nu este nevoie de o instanț ă pentru a fi
invocate. Le poț i apela pur ș i simplu când doreș ti.
În general, metodele statice nu ș tiu nimic despre starea clasei. Ele sunt
metode care acț ionează mai degrabă ca utilităț i.
[Link]:
2.
3. COUNT = 0
4.
5. def __init__(self, ore=0, minute=0, secunde=0):
6. [Link] = hours
7. [Link] = minutes
8. [Link] = seconds
9. [Link] += 1
10.
11. def__str__(self):
12. Timpul este {:02}:{:02}:{:02}.format([Link],
13. [Link]
14. [Link])
15.
16.# ALTE METODE POT FI AICI...
17.
18. @classmethod
19. defseconds_la_timp(cls, s):
20. minute, secunde = divmod(s, 60)
21. ore, minute = divmod(minute, 60)
180
22. extra, ore = divmod(ore, 24)
23. returneazăcls(ore, minute, secunde)
24.
25.
26. @staticmethod
27. def valida(hours, minutes, seconds):
28. 0 <= ore <= 23 ș i 0 <= minute <= 59 ș i 0 <= secunde <= 59
Această metodă statică este pur ș i simplu o utilitate care ne permite să verificăm că orele sunt
corect. Am putea folosi asta pentru a opri un utilizator să creeze un timp atât
ca35:88:14deoarece nu ar avea niciun sens logic.
de lamy_timeimportTime
>>> [Link](5, 23, 44)
Adevărat
>>> [Link](25, 34, 63)
Fals
>>> t= Timp22, 45, 23)
>>> [Link]([Link], [Link], [Link])
Adevărat
Poate fi, de asemenea, dificil să observi când să foloseș ti metodele statice, dar din nou, dacă găseș ti
acces la variabile care nu trebuie să fie accesate de fiecare (sau poate că da)
în care sunt publice).
181
Până acum am folosit atribute ș i metode publice. Clasele pot apela
metodele ș i accesul la variabilele din alte clase.
În Python, nu există o verificare strictă pentru modificatorii de acces, de fapt ei nu
există, dar programatorii Python au adoptat o convenț ie pentru a o depăș i.
Prin convenț ie, acestea sunt accesibile oricărei persoane (prin oricine mă refer la alț ii)
cursuri).
Pentru a "face" aceste variabile private, adăugăm o linie dublă de subliniere în faț a
numele variabilei. Ca un atribut sau metodă să fie privată, înseamnă că doar
clasa în care sunt conț inute poate să le apeleze ș i să le acceseze. Nimic din exterior.
În limbajul Java, dacă ai două clase ș i ai încercat să apelezi o metodă privată
dintr-o altă clasă ai primi o eroare.
Al treilea modifier de acces despre care voi vorbi este protejat. Acesta este la fel ca privat
cu toate că toate subclasele pot, de asemenea, să acceseze metodele ș i variabilele de membru. Voi
vorbeș te despre subclase în următorul capitol, aș a că nu-ț i face griji în legătură cu asta acum, dar
19.5 - Exerciț ii
Întrebarea 1
Scrie un program Python care conț ine o clasă denumităPersoanăO instanț ă de
oPersoanăar trebui să aibă atribute de nume ș i vârstă. Ar trebui să poț i să tipăreș ti un
instanț a clasei care, de exemplu, ar trebui să afiș ezeJohn are 28 de ani.
182
Clasa ta ar trebui să aibă o metodă numitădinAnulDeNaș tere() care are ca parametrii
ar trebui să ia o vârstă ș i un an de naș tere. De exemplu,deLaAnulNaș terii('John',
1990)ar trebui să returneze o instanț ă dePersoanăcare are 29 de ani (la momentul
scriind această carte, 2019).
>>>de lamy_personimportPerson
Întrebarea 2
Scrie unStudentclasă care iniț iază un student cu 3
attributes: nume, noteș istudent_numberNota ar trebui să fie un dicț ionar de
module la note. Numărul de student al primei instanț e a studentului ar trebui să fie
Numărul studentului al doilea student ar trebui să fie 19343553.
19343554 ș i aș a mai departe. Ar trebui să ai trei metode,adauga_modul()care
primeș te un parametru, un nume de modul, ș i iniț iază nota la 0.
a doua metodă ar trebui să fie,actualizează_modul()care ia două parametrii,
numele modulului ș i nota pentru modul. Metoda finală ar trebui să permită
utilizatorul să imprime un student.
Gândiț i-vă cu atenț ie la cum veț i implementa creș terea numărului de studenț i.
Executarea programului tău ar trebui să dea următoarea ieș ire:
>>>de lamy_studentimportStudent
183
Grades:
Python88
>>> adam= Student("Adam")
>>> adam.adauga_modul("Java")
>>> [Link]ă_modul("Java",60)
>>>print(adam)
Name: Adam
Numărul studentului:19343554
Grades:
Java:60
Întrebarea 3
ModificăStudentclasă pentru a include o metodă care va valida notele. O notă
ar trebui să fie între 0 ș i 100.
Python88
Proiect
Eș ti însărcinat cu crearea unei aplicaț ii de simulare a reț elei în care două
partidele există. Vom numi aceste partideExpeditorș iRecepț ionerAr trebui, de asemenea, să
există un proces care verifică continuu dacăExpeditorare vreo pachete de date
184
a trimite, dacă o face, atunci procesul ar trebui să le livereze laDestinatar.
TheExpeditorar trebui să creeze periodic pachete de date care să fie trimise (Acestea pot fi
ș iruri generate aleatoriu). TheReceiverar trebui să verifice periodic dacă are
a primit pachete de date, dacă da, atunci ar trebui să le imprime, apoi să le ș tergă
ei.
Indicaț ie: Ar trebui să reflectezi cu atenț ie asupra ce clase sunt necesare ș i ce
metodele pe care ar trebui să le conț ină. Ceva numit 'buffer' ar putea fi de ajutor aici
pentru procesul tău care mută pachete întreExpeditorș iReceiverCiteș te
despre buffere ș i ce sunt acestea. Gândeș te-te cu atenț ie la ce tipuri încorporate în Python
ar putea fi capabil să implementeze un buffer.
185
Capitolul 20 - Moș tenirea OOP
20.1 - Ce este moș tenirea?
În programare, ne întâlnim adesea cu obiecte care sunt destul de asemănătoare sau este posibil să
vezi că o clasă este un tip de altă clasă. De exemplu, o maș ină este un tip de
vehicul. În mod similar, o motocicletă este un tip de vehicul. Putem vedea o relaț ie
apare aici. Tipul de relaț ie este o relaț ie „este un”.
În programarea orientată pe obiect, numim aceasta moș tenire, iar moș tenirea ajută
modelul us este o relaț ie. Moș tenirea este unul dintre pilonii obiect-
programare orientată pe obiect ș i vom explora aceasta în acest capitol.
186
[Link]:
2. def__init__(self, lungime, lăț ime):
3. [Link] = lungime
4. [Link] = width
5.
6. defarea(self):
7. [Link] * [Link]
8.
9. defperimetru(self):
10. return2 * [Link] + 2 * auto.lăț ime
11.
[Link]ăPătrată:
13. def__init__(self, lungime):
14. [Link] = length
15.
16. defarea(self):
17. [Link] * [Link]
18.
19. defperimetrul(self):
20. return4 * [Link]
Acest lucru pare să fie puț in redundant, totuș i, deoarece atât un pătrat, cât ș i un dreptunghi au
4 laturi fiecare ș i ambele au o suprafaț ă ș i un perimetru. Dacă ne uităm mai multe
privind cu atenț ie această situaț ie, observăm că un pătrat este un caz special al unui dreptunghi
în care toate laturile au aceeaș i lungime.
Putem folosi moș tenirea pentru a reflecta această relaț ie ș i a reduce cantitatea de
cod pe care trebuie să-l scriem. În acest caz unSquare este un tip deDreptunghiastfel încât face
are sens ca un pătrat să moș tenească de la clasa dreptunghi.
Să ne uităm din nou la acest cod, dar de data aceasta am făcut modificări la pătrat.
o clasă pentru a reflecta această relaț ie. Există câteva lucruri noi care se întâmplă aici, dar
Îț i voi explica mai târziu.
[Link]ăDreptunghi:
2. def__init__(self, lungime, lăț ime):
3. [Link] = length
4. [Link] = width
5.
6. defarea(self):
7. [Link] * [Link]
8.
9. defperimetru(self):
187
10. întoarce2 * [Link] + 2 * [Link]
11.
[Link](Rectangle):
13. def__init__(self, lungime):
14. super().__init__(lungime, lungime)
4
>>>print([Link]())
10
>>>print([Link]())
8
188
calculează suprafaț a unui cub. De asemenea, va avea o nouă metodă
apelatvolumpentru a calcula volumul cubului. Putem face o utilizare bună
desuper()aici pentru a ne ajuta să reducem cantitatea de cod de care avem nevoie.
[Link]ăPătrat(Rectangh):
2. def__init__(self, lungime):
3. super().__init__(lungime, lungime)
4.
[Link](Pătrat):
6. defarea(self):
7. side_area = super().area()
8. return6 * aria_laterala
9.
10. defvolum(self):
11. side_area = super().area()
12. returnside_area * [Link]
După cum puteț i vedea, nu a fost necesar să anulăm__init__() metodă aș a cum este
moș tenit de laPătratÎnsă, am anulatsuprafaț ă()metodă din
clasa părinte (Cadran) peCubpentru a reflecta cum este aria unui cub
calculat. Am folosit de asemeneasuper()metodă pentru a ne ajuta cu acest lucru.
După cum puteț i vedea, folosind moș tenirea am redus semnificativ cantitatea de
cod comparat cu modul în care am fi implementat aceste trei clase
anterior.
189
Vreau doar să mă întorc la suprascrierea__init__() metodă pentru un secund. Să
presupune unPersoanăclasă ș i unAngajatclasă care derivă dinPersoană.
Everything about an employee is the same as a Persoanădar angajatul va
de asemenea, au un ID de angajat.
[Link]:
2. def__init__(self, nume, vârstă):
3. [Link] = name
4. [Link] = age
5.
6. defshow_nume(self):
7. print("Nume: " + [Link])
8.
9. defshow_age(self):
10. vârsta:
11.
[Link]ăAngajat(Persoană):
13. def__init__(self, nume, varsta, idAngajat):
14. super().__init__(nume, vârstă)
15. [Link] = employeeId
16.
17. defshow_id(self):
18. ID angajat:
>>> emp.afiseaza_nume()
Name: Simon
>>> emp.arata_varsta()
Age: 25
>>> emp.show_id()
Employee ID: 4532245
Motivul pentru care îț i arăt asta este că, deș i am arătat deja cum
pentru a suprascrie metode, oamenii se confundă atunci când suprascriu
the__init__()metodă pentru a include de asemenea atribute noi în clasa derivată.
190
20.3 - Moș tenire multiplă
Până acum, am analizat moș tenirea simplă. Adică, clasele copil care moș tenesc de la
o clasă de părinț i unică. Moș tenirea multiplă este atunci când o clasă poate moș teni de la
mai mult decât o clasă părinte.
Th;is allows programs to reduce redundancy, but it can also introduce a certain
nivel de complexitate, precum ș i ambiguitate. Dacă plănuieș ti să faci mai multe
moș tenirea în programele tale, ar trebui să fie făcută cu grijă. Gândeș te-te la
programul tău general ș i cum ar putea afecta acest lucru. De asemenea, ar putea afecta
claritatea programelor tale.
De exemplu:
[Link]:
2. defmetodă():
3. # codul tău aici
4.
[Link]:
6. defmethod():
7. # codul tău aici
8.
[Link](A, B):
10. trece
11.
12.>>> [Link]()
Nu voi intra prea adânc în moș tenirea multiplă, deoarece este destul de auto-
explicativ despre cum să îl foloseș ti, aș a că o să dau doar un exemplu de cum se face
poate fi folosit:
[Link]ăCPU:
2. def__init__(self, num_registers):
3. self.num_registers = registers
4. Alte metode
5.
[Link]ăRAM:
7. def__init__(self, sumă):
8. [Link] = amount
9. Alte metode
191
10.
[Link]ăCalculator:
12. def__init__(self, num_registers, amount):
13. CPU.__init__(număr_registre)
14. RAM.__init__(cantitate)
15.
16. # Alte metode
20.4 - Exerciț ii
Întrebare 1
Create two classes: Persoanăș iAngajat. Clasa persoană ar trebui să
a aveanumeș ivârstăatribute. Clasa angajatului ar trebui să aibă unul
adicionalemployeeId atribut. Angajatul ar trebui, de asemenea, să
a aveaclock_in ș iieș iremetode. Când sunt implementate corect, tu
ar trebui să fie capabil să folosească cele două clase astfel:
>>> angajat.învârte_afară()
Tom a ieș it din serviciu.
Întrebare 2
Creează oFormăclasă. Clasa de formă ar trebui să aibă două
attributes: num_sidesș iside_lengthAr trebui să aibă ș i o metodă
apelatafiseaza_tip()
192
AmbeleTriunghiș iPentagonclassele ar trebui să aibăsuprafaț ă()metode.
>>> [Link]()
3.9
>>> stilou= Penatgon4Aceasta se referă la lungimea laturii
>>> pent.afiseaza_tip()
Sunt un pentagon
>>> [Link]()
27.53
Întrebarea 3
Creează unCeasclasă. Ar trebui să aibă trei atribute:oră, minut, ș ial doilea. Acesta
ar trebui să aibă ș i o metodă numităarată_timp()care afiș ează timpul în format de 24 de ore
timp. De asemenea, ar trebui să aibă o metodă numităbip()care avansează timpul cu 1
al doilea.
Data01/01/2020 ș iorais00:00:00
Notă: Există câteva modalităț i de a completa această întrebare, totuș i vreau să te ...
foloseș te moș tenirea multiplă. Dacă o faci, atunci codul pentru CalendarClock ar trebui să fie
destul de scurt.
194
Capitolul 21 - Structuri de date de bază
Structura de bază a fiecărui software pe care îl vei scrie va consta în două principale
lucruri: date ș i algoritmi. Ș tim că algoritmii sunt utilizaț i pentru a manipula
datele din software-ul nostru (ș i această manipulare ar trebui să fie efectuată ca
eficient cât mai bine posibil). Din acest motiv, este important să ne structurăm datele astfel încât
că algoritmii noș tri pot manipula datele eficient.
Am întâlnit deja diverse structuri de date, liste ș i dicț ionare, ca să numim câteva
puț ini. De asemenea, ș tii că utilizarea listelor, de exemplu, ne face foarte uș or să
stochează ș i manipulează secvenț e de date (Crede-mă, fără această abstractizare,
devine un pic deranjant).
Am văzut de asemenea că structurile de date ne permit să modelăm sistemele pe care le observăm
în lumea reală. De exemplu, am putea proiecta ș i construi o clasă care să ne permită
pentru a modela o bibliotecă. Am putea folosi cu uș urinț ă acest lucru pentru a construi un sistem de gestionare a bibliotecilor
sistem.
În acest capitol vom examina două structuri de date fundamentale care sunt
folosit peste tot în informatică. De asemenea, vom analiza unele exemple de
cum să profiti de ele.
21.1 - Stiva
Stiva este una dintre cele mai fundamentale structuri de date în informatică. Fiecare
de fiecare dată când rulezi un program, acel program profită de un stivă. Mai întâi voi
explică cum funcț ionează, apoi îț i voi explica cum calculatorul tău profită de
ea.
O stivă este o structură de date liniară care urmează un anumit ordin în care
operaț iunile sunt efectuate. O stivă este o structură de date LIFO (Ultimul intrat, primul ieș it).
Adică, ultimul element introdus în stivă este primul element care va
părăseș te stiva. Te poț i gândi la o stivă ca la o stivă de farfurii de cină. Farfuriile sunt
înghesuite, una peste alta. Ultimul farfurie pusă deasupra stivei
va fi prima placa care va fi îndepărtată deoarece nu putem îndepărta placa la
fundul (sau teancul de farfurii s-ar răsturna ș i toate s-ar sparge).
O stivă (în mod obiș nuit) are 4 operaț ii principale: push (adaugă un element în vârf),
pop(remove un element de la vârf), top (arată elementul de la vârf) ș i
195
isEmpty (este stiva goală). De asemenea, putem adăuga o metodă de lungime ș i este de obicei
util!
1.#######
2.# Stiva
3.#######
4.
5.|------| <-- Sus
6.|------|
7.|------|
8.|------|
9.|------|
10.|------|
11.|------|
12.
13.
14.###########
15.# Dacă scoatem:
16.###########
17.
18.|------| <-- Pop
19.
20.|------| <--Vârful nou
21.|------|
22.|------|
23.|------|
24.|------|
25.|------|
26.
27.
28.###############
29.# Dacă împingem
30.# a new element:
31.###############
32.
33.|------| <--Adaugă nou
34.|------| element
35.|------| (nou vârf)
36.|------|
37.|------|
38.|------|
39.|------|
40.|------|
Stiva este o structură de date atât de fundamentală încât multe instrucț iuni ale computerului
seturile oferă instrucț iuni speciale pentru manipularea stivelor. De exemplu, Intel
Procesorul Pentium implementează setul de instrucț iuni x86. Acest lucru permite maș inii
limbaje pentru programatori pentru a programa calculatoarele la un nivel foarte scăzut (Assembly
limbă, de exemplu).
Un tip foarte special de stivă numit "Stiva de apeluri" sau "Stiva de program", de obicei
scurtat la "Stiva" este ceea ce unele dintre instrucț iunile din instrucț iunea x86
set manipulare.
196
Să considerăm ce se întâmplă cu următorul program la un nivel inferior (Pentru
oricine are o înț elegere solidă a calculatoarelor, acesta este un nivel puț in ridicat, dar un
exemplu bun).
.
.
.
print(4)
.
.
.
În snippet-ul de mai sus în Python, avem un set de instrucț iuni care se execută în
ordine (Aș a cum am văzut întotdeauna). La un moment dat, apelăm funcț ia de imprimare pentru
afiș aț i numărul 4 în fereastra noastră de terminal. Aici intervine stiva
în acț iune. Să ne uităm la modul în care programul nostru ar putea fi stocat în memorie (La un nivel înalt
nivel)
Memory Address Instrucț iune
----------------------------------
0x0000003 .......
.
.
.
0x0000004 ....... Câteva instrucț iuni înainte de tipărire.
(SUNT CONȘ TIENT CĂ ACEASTA NU ESTE CE SE ÎNTÂMPLĂ DE FAPT, DAR SĂ MERGEM CU ACEASTA)
DEOCAMDATĂ).
197
Când rulăm un program, acesta este încărcat în memorie ca cod maș ină (Codul
computerul ș tie cum să execute). Instrucț iunile sunt stocate secvenț ial. În aceasta
din perspectiva asta, putem privi funcț iile ca fiind "mini programe" în interiorul programului nostru principal.
Adică, codul pentru ele este stocat în altă parte în memorie. Când noi
apeleazăprint(4)de fapt spunem, sari la locul unde este codul pentru print
începe să execuț i instrucț iunile în mod secvenț ial până când funcț ia este finalizată, apoi
întoarceț i-vă la locaț ia originală ș i continuaț i să executaț i de unde aț i rămas.
Înainte să explic asta, CPU-ul are multe piese speciale de memorie în interiorul său,
numite registre (Acestea sunt ca bucăț i mici de RAM, de obicei de 32 de biț i sau 64 de biț i în
Una dintre aceste registre se numeș te registrul pointerului de instrucț iune, adesea
prescurtat la IP. Conț ine adresa de memorie a următoarei părț i de cod pentru
executa.
În acest caz, executăm instrucț iunea la0x0000004( apoi creș teț i IP-ul), în
următoarea instruire pe care o numimprint(4)care se află la locaț ia0x0000005 însă codul
pentru funcț ia de imprimare este stocată la0x0000001la0x0000003Aici este unde
stiva intră în joc. Ș tim că atunci când tipărim numărul dorit
continuăm de unde am rămas ș i executăm instrucț iunea la0x0000006. În acest caz
împingem adresa de retur (0x0000006) pe stivă, setează IP-ul
spre0x0000001ș i începe să execute codul pentru funcț ia de imprimare. Când suntem
terminat, scoatem adresa de returnare de pe stivă (0x0000006) ș i plasează acest lucru în
IP-ul. Acum programul nostru continuă să ruleze de unde am rămas.
Sunt sigur că îț i poț i imagina cum funcț ionează recursia acum la acest nivel (în esenț ă o
serie de împingeri, împingeri, împingeri ...... scoateri, scoateri, scoateri).
Lucrurile sunt mult mai complexe decât atât, dar nu este necesar pentru a
explicaț ia modului în care stivele sunt utilizate la cele mai fundamentale niveluri. Nu
nu te îngrijora prea mult dacă nu ai înț eles totul. Nu este necesar pentru asta
carte, dar arată doar cât de importantă este stiva.
Stivele au multe utilizări la nivel înalt, de exemplu, mecanismele de anulare în text
editori în care ț inem evidenț a tuturor modificărilor de text într-o stivă. Acestea pot fi folosite
În browsere pentru a implementa un mecanism de mers înapoi/înainte pentru a merge înapoi ș i înainte
Haideț i să privim codul pentru un stivă în Python. Vom implementa o stivă folosind un
listă
[Link]:
198
2. def__init__(self):
3. [Link] = []
4.
5. defpune(self, elem):
6. [Link](elem)
7.
8. defpop(self):
9. iflen([Link]) == 0:
10. returnNone
11. altfel:
12. [Link]()
13.
14. defisEmpty(self):
15. iflen([Link]) == 0:
16. returneazăAdevărat
17. returneazăFals
18.
19. deftop(self):
20. [Link][-1]
Aceasta este o versiune foarte simplă a unui stivă, dar acum putem folosi stiva noastră ca
urmează:
[Link] = Stack()
2.
[Link](1)
[Link](4)
[Link](2)
6.
[Link]([Link]())
8.
[Link]([Link]())
[Link]([Link]())
[Link]([Link]())
21.2 - Coada
Cozile sunt într-un anumit sens similare cu stivele. Ele sunt o structură de date liniare, cu excepț ia
mai degrabă decât ordinea de operare fiind Ultimul intrat, primul ieș it, ele sunt FIFO (Primul intrat)
Primul Ieș ire). Se comportă exact ca orice coadă la care te-ai gândi în viaț a reală. O
199
queue at a supermarket for example, you get in line at the back and wait until
Ajungi la faț ă pentru a pleca.
aparent este). Ce se întâmplă de fapt în această situaț ie este că fiecare program este
folosind rapid CPU-ul, apoi revenind în coadă. Acest lucru se întâmplă peste
ș i din nou. Un algoritm de programare a CPU se ocupă cu programul care primeș te
mergi mai departe pe CPU ș i este posibil să implementeze o variaț ie a unei cozi pentru a gestiona
[Link]:
2. def__init__(self):
3. self.q = []
4.
5. defenqueue(self, elem):
6. [Link](elem)
7.
8. defdequeue(self):
9. iflen(self.q) != 0:
10. [Link](0)
11.
12. defisEmpty(self):
13. dacă len(self.q) > 0:
14. returnFalse
15. returneazăAdevărat
Ș i iată. O clasă Queue foarte simplă. Observaț i cum scoatem elemente de la index
0. Amintiț i-vă căpop()metoda pentru liste acceptă un argument opț ional care este
indicele listei din care vrei să elimini un element. Dacă nu furnizăm
200
acest argument opț ional are ca valoare implicită -1 (sfârș itul listei, ceea ce este ceea ce
stacks fac). Aici eliminăm elementul de la începutul listei, dar adăugăm
elemente la sfârș it.
[Link] = Queue()
2.
[Link](1)
[Link](4)
[Link]ă.intră(2)
6.
[Link]([Link]())
8.
[Link]([Link]())
[Link]([Link]())
[Link]([Link]())
12.
[Link]([Link]())
Fals
1
4
2
Adevărat
21.3 - Exemple
Primul exemplu pe care o să-l analizez este pentru stive. Această întrebare este cunoscută că
au fost solicitate în timpul interviurilor de codare anterioare la Google!
De exemplu:
([{}])
Echilibrat
(()[])
Desechilibrat
{(){[]}}
201
Echilibrat
Input: [()(){]
Dezechilibrat
O abordare pe care o putem adopta pentru această problemă este să folosim o stivă. Fiecare dată când noi
Iată o posibilă soluț ie. Să presupunem că clasa noastră de stivă dinainte există:
[Link] = ["(","[","{"]
2.# Re ț ineț i că pairs este un dic ț ionar care mapează paranteza de închidere
3.# la paranteza de deschidere
[Link] = {")":"(","]":"[","}":"{"}
5.
[Link](input_string):
7. stivă = Stivă()
8. forbracketininput_string:
9. ifbracketinopening:
10. [Link](bracket)
11. [Link]():
12. returnFalse# Nu se poate popa nimic deoarece stiva este goală, deci este dezechilibrată
Putem folosi mai bine harta perechilor ș i să ne facem codul un pic mai ordonat, dar
nu va fi la fel de uș or de citit, aș a că am ales o abordare puț in mai lungă.
Acum putem rula codul nostru după cum urmează pentru a obț ine rezultatul dorit din
exemplu de intrare ș i ieș ire de mai sus:
Nu am un exemplu de utilizare a cozii, deoarece nu pot să-mi dau seama de nimic util.
fă cu ei cu cunoș tinț ele pe care le avem în acest moment. Nu te îngrijora
totuș i, va fi o întrebare bună despre cozi care va apărea în curând.
202
21.4 - Exerciț ii
Întrebare 1
Îț i sunt date două ș iruriSș iT. Ambele ș iruri conț in caractere alfanumerice
caractere sau un caracter '#'. Un '#' înseamnă ș tergere. Scopul tău este să foloseș ti
cunoaș terea stivelor pentru a proiecta o funcț ie care va decide dacă ambele ș iruri
sunt egale după ce operaț ia de ș tergere a fost aplicată. De exemplu:
S=, T="xw#z"
Output:True
Explicaț ie: Când operaț iunea de ș tergere cu backspaceesteaplicate, ambele ș iruri devin
xz
S="abcd##", T ="acbd##"
Output:False
Explicaț ie: S devine 'ab'ș iT devine 'ac' care suntnuacelaș i
S="z##y", T="#d#y"
Output:True
Ambele ș iruri devin 'y'
S="er##", T="u#u#"
Output: true
Întrebarea 2
Este posibil să creezi o coadă prin utilizarea a două stive. Implementează o
clasă de coadă similară cu cea de mai sus, cu excepț ia faptului că nu foloseș te o listă pentru a implementa coada
Întrebarea 3
Este de asemenea posibil să creezi un stivă prin utilizarea a două cozi. Implementează
o clasă de stivă asemănătoare cu cea pe care am văzut-o anterior, cu excepț ia faptului că în loc să folosească o listă pentru
203
Acesta ar putea fi puț in complicat, va trebui să te gândeș ti la asta.
Mini Proiect 1
Trebuie să proiectaț i un calculator RPN. RPN înseamnă Notaț ie Poloneză Inversă.
Un calculator RPN este cunoscut ș i sub numele de calculator postfix. Noi, ca oameni, facem
matematica astfel, de exemplu,4 + 7sau trebuie să folosim regulile BEMDAS:8 + ((10 *
3) / 2). În RPN, am reprezenta acestea ca:4 7+ș i ultima expresie pe care o
reprezentaț i ca8 10 3 2 / * +Ceea ce se întâmplă aici este operatorul (+ este în
poziț ia prefixului în loc de poziț ia infixului, aș a cum suntem obiș nuiț i). Aceasta ar putea părea o
puț in confuz, dar este de fapt destul de simplu ș i putem folosi o stivă pentru a rezolva
această problemă.
• Adăugare: (+)
• Scădere: (-)
• Înmulț ire*)
• Împărț ire la podea (//)
• Negaren)
• Puteree)
204
Calculatorul tău ar trebui să citească expresii RPN, câte una pe linie ș i
evaluează-le. Există un operator suplimentar de implementat. Acesta estepcare
reprezintă print. Dacă întâlneș tipapoi tipăriț i rezultatul. Puteț i presupunepva
întotdeauna apare la sfârș itul introducerii.
Exemplu:
473++p
14
4+7+3
58*np
-40
-(5 * 8)
361++2ep
Output: 100
(3 + 6 + 1)^2
Reflectaț i cu atenț ie la această problemă. Este chiar un proiect grozav pentru începători să găzduiască.
205
Capitolul 22 - Date mai avansate
Structuri
În capitolul anterior, am învăț at despre câteva date simple, dar fundamentale.
structuri cu implementări destul de simple. În acest capitol, ne vom
aruncă o privire la câteva structuri de date noi. Ele vor fi, de asemenea, puț in mai
avansate în implementarea lor.
Prima structură de date pe care o vom analiza în acest capitol este o listă înlănț uită.
O listă legată este o structură de date liniară în care fiecare element este un separat.
element. Obiectele listei legate nu sunt stocate în locaț ii contigue. În schimb,
Obiectele listei legate sunt legate între ele folosind pointeri.
Pe parcursul acestei cărț i, este posibil să fi făcut referire la listele Python ca la array-uri ș i invers.
diverse tipuri.
În multe alte limbaje de programare, un array este foarte asemănător cu o listă de dimensiune fixă
care stochează elemente de un tip specific. Acestea stochează elemente în mod contiguu în
memorie. Aceasta nu este neapărat cazul în Python.
Python este implementat într-o limbaj numit 'C'. Această limbaj este de nivel scăzut.
comparativ cu Python. În limbajul C, listele Python sunt implementate cu un
o structură de date oarecum similară cu o listă înlănț uită. Este mult mai complicat
decât o listă legată, dar multe dintre conceptele ș i tehnicile pe care le vom învăț a aici vor
aplicaț i la implementarea listelor C Python.
Există multe variaț ii ale listelor legate, dar în acest capitol, vom merge la
Uitaț i-vă la o variaț ie numită Listă Linkedă Simplă.
206
Există diverse elemente în acest sens, aș a că permite-mi să explic:
Listelor legate au diverse avantaje faț ă de array-uri (nu listele Python). Acestea
inclusiv dimensiunea dinamică (ele pot creș te ș i micș ora după cum este necesar, la fel ca Python)
liste, în timp ce array-urile nu pot face acest lucru) ș i uș urinț a inserț iei ș i ș tergerii.
Există, de asemenea, unele dezavantaje ale listelor legate în comparaț ie cu array-uri. Noi
nu le putem indexa, prin urmare dacă dorim să accesăm un element trebuie să iterăm
prin fiecare element, începând de la cap, în ordinea până găsim
elementul pe care îl căutăm.
Din diagrama de mai sus, putem descompune problema implementării unei liste legate
enumeră două lucruri:
1. O clasă de nod: Aceasta va con ț ine datele pe care nodul le va stoca ș i un pointer
la următorul nod.
2. Clasa Linked List: Aceasta va con ț ine nodul de început ș i metodele pe care le putem utiliza
executaț i pe lista legată.
[Link]:
2. def__init__(self, elem):
3. [Link] = elem
4. [Link] = None
Aceasta este clasa noastră de noduri pentru listă legată. Este foarte simplă ș i conț ine doar două
atributele. Primul este datele pe care nodul le va stoca ș i un atribut anexa.
atributul următor este setat laNiciunulîn mod implicit, deoarece nu va indica spre nimic iniț ial.
207
Acest concept de nod este foarte puternic atunci când vine vorba de structuri de date.
ne oferă multă flexibilitate atunci când dezvoltăm alte structuri de date, după cum vom vedea
mai târziu.
[Link]:
2. def__init__(self):
3. [Link] = None
Aici verificăm că capul listei înlănț uite nu este gol. Dacă este, atunci noi
atribuiț i un nouNodla lista înlănț uităcap. Altfel, creăm o nouă variabilă
apelatcurrAcest lucru ț ine evidenț a nodului pe care ne aflăm. Dacă nu am face asta, am...
ar ajunge să actualizeze lista legatăcapnod din greș eală. După ce creăm
această nouă variabilă, parcurgem elementele listei, mergând de la nod
a se nodi prinurmătorulpointer până găsim un nod al căruiurmătorulpointer-ul este
gol. Când găsim acel nod, îi actualizămurmătorulpointeur pentru a indica la un
nouNod.
208
Acest lucru poate dura puț in timp pentru a-l înț elege sau a-l învârti în minte, dar
cu atât mai mult lucrezi cu structuri de date de acest tip sau asemănătoare, cu atât mai mult are sens.
va face.
Să ne uităm la metoda noastră de ș tergere. Avem multe opț iuni atunci când ș tergem
elemente dintr-o listă legată la fel cum facem cu adăugarea lor. Am putea elimina
primul element, ultimul element sau prima apariț ie a unui element. Din moment ce
lista noastră legată poate conț ine multe apariț ii ale aceleaș i date, vom elimina
prima apariț ie a unui element.
După cum puteț i vedea, din acest diagramă dorim să ș tergem nodul care conț ine2.
Pentru a face acest lucru, găsim primul nod care esteurmătorulpointer indică către unNodcă
conț ine valoarea2Când găsim astaNodtocmai am actualizaturmătoarepunctator către
indică acelaș i nodNodvrem să ș tergem puncte de asemenea. Practic, noi
redirecț ioneazăurmătorulpunctul de acces pentru a sări peste elementul pe care dorim să-l ș tergem. Acesta este
destul de uș or de făcut.
Trebuie să acoperim câteva cazuri aici. Primul este că lista este goală în
care nu returnează nimic. A doua este că capul listei legate este
209
elementul pe care dorim să-l ș tergem. Dacă este, atunci facem capul listei
al doileaNodîn listă (care poate fiNiciunuldar e în regulă, înseamnă doar lista
doar a avut un singur articol). În cele din urmă, dacă nu este niciunul dintre aceste cazuri, parcurgem lista
utilizăm căutarea liniară până când găsim prima apariț ie a elementului, apoi noi
redirecț ionaț iurmătorulpointerul deNodcare indică cătreNodvrem să
ș terge, cătreNodethenextpunctul deNodvrem să ș tergem punctele de asemenea.
Acea ultimă parte ar putea părea confuză, dar facem ceea ce vezi în
diagram. Probabil că este cel mai bine în acest moment, dacă eș ti confuz de acest lucru, să desenezi asta
scenariul pe hârtie pentru a ajuta la clarificarea lucrurilor.
Există câteva alte metode utile pe care le putem adăuga aici, dar le vom lăsa
pentru mai târziu.
Chiar înainte să termin cu listele legate, vreau să vorbesc puț in mai mult despre
complexităț ile metodelor lor ș i de ce ai putea să le foloseș ti (sau nu).
Complexitatea timpului de rulare a metodei add este O(n) în acest caz, deoarece trebuie să
iteraț i peste fiecare intrare din listă pentru a găsi ultimul element. Timpul de execuț ie
complexitatea metodei de ș tergere este de asemenea O(n). Deș i nu întotdeauna
iteraț i peste fiecare element din listă, Big-O se ocupă de cel mai grav caz, care este
trecând prin întreaga listă. Există optimizări pe care le-am putea face totuș i
ș i vom ajunge la ele mai târziu.
Listele legate în Python de obicei nu au un caz de utilizare. Acest lucru se datorează faptului că Python
listelor sunt deja foarte bine optimizate ș i dinamice. Cu toate acestea, în limbile precum
ca C sau C++, Listele Înlănț uite sunt esenț iale (Unde tablourile dinamice, cum ar fi listele python,
s-ar putea să nu existe). De asemenea, apar în interviurile tehnice, aș a că este cel mai bine să ș tiț i
Ei. De fapt, dacă aș angaja un inginer, aș fi foarte sceptic în privinț a angajării unuia
cine nu ș tia să codeze o listă legată.
Înainte de a începe această secț iune, vreau să îț i fac o avertizare. Vom folosi
recursie destul de mult aici. Dacă recursia nu este punctul tău forte (ceea ce este...
probabil nu voi fi în acest punct), poate să revizuiască partea de recursie.
Cu toate acestea, această secț iune ar putea fi un loc bun pentru a te ajuta să înț elegi
recursie. Arborii binari de căutare (BST) m-au ajutat să înț eleg recursia (bine, la
cel puț in atunci când recursia a început să aibă sens pentru mine).
210
Un arbore de căutare binară (BST) este oarecum diferit de structurile de date pe care le
am întâlnit până acum. Nu este o structură de date liniare. Este un tip de date ordonate
structură care stochează elemente. BST-urile permit căutări rapide, adăugări ș i eliminări
de obiecte. BST-urile îș i păstrează obiectele în ordine sortată astfel încât operaț iile care pot fi
sunt rapide, spre deosebire de o listă înlănț uită al cărei adăugare ș i eliminare
operaț iile sunt O(n). Operaț iile de adăugare ș i eliminare pe un BST sunt O(log n).
Căutarea într-un BST este, de asemenea, O(log n). Acesta este cazul mediu pentru cele trei.
operaț iuni.
Aceasta este o situaț ie similară cu căutarea liniară versus căutarea binară pe care am analizat-o.
mai devreme.
O arbore binar este un tip de arbore în care fiecare Nod din arbore are cel mult două
noduri copil. Un arbore de căutare binar este un tip special de arbore binar în care
elementele sunt ordonate. Un diagramă ar putea să te ajute să vizualizezi acest lucru, aș a că iată una:
Există multe de înț eles aici, aș a că lăsaț i-mă să explic. Rădăcina acestui copac este nodul
care conț ine elementul10. Lucrul mare etichetatSub Arboreeste sub drept
arborele nodului rădăcină.
211
Capitolul 21 - Structuri de date de bază
Structura de bază a fiecărui software pe care îl vei scrie va consta în două principale
lucruri: date ș i algoritmi. Ș tim că algoritmii sunt utilizaț i pentru a manipula
datele din software-ul nostru (ș i această manipulare ar trebui să fie efectuată ca
eficient cât mai bine posibil). Din acest motiv, este important să ne structurăm datele astfel încât
că algoritmii noș tri pot manipula datele eficient.
Am întâlnit deja diverse structuri de date, liste ș i dicț ionare, ca să numim câteva
puț ini. De asemenea, ș tii că utilizarea listelor, de exemplu, ne face foarte uș or să
stochează ș i manipulează secvenț e de date (Crede-mă, fără această abstractizare,
devine un pic deranjant).
Am văzut de asemenea că structurile de date ne permit să modelăm sistemele pe care le observăm
în lumea reală. De exemplu, am putea proiecta ș i construi o clasă care să ne permită
pentru a modela o bibliotecă. Am putea folosi cu uș urinț ă acest lucru pentru a construi un sistem de gestionare a bibliotecilor
sistem.
În acest capitol vom examina două structuri de date fundamentale care sunt
folosit peste tot în informatică. De asemenea, vom analiza unele exemple de
cum să profiti de ele.
21.1 - Stiva
Stiva este una dintre cele mai fundamentale structuri de date în informatică. Fiecare
de fiecare dată când rulezi un program, acel program profită de un stivă. Mai întâi voi
explică cum funcț ionează, apoi îț i voi explica cum calculatorul tău profită de
ea.
O stivă este o structură de date liniară care urmează un anumit ordin în care
operaț iunile sunt efectuate. O stivă este o structură de date LIFO (Ultimul intrat, primul ieș it).
Adică, ultimul element introdus în stivă este primul element care va
părăseș te stiva. Te poț i gândi la o stivă ca la o stivă de farfurii de cină. Farfuriile sunt
înghesuite, una peste alta. Ultimul farfurie pusă deasupra stivei
va fi prima placa care va fi îndepărtată deoarece nu putem îndepărta placa la
fundul (sau teancul de farfurii s-ar răsturna ș i toate s-ar sparge).
O stivă (în mod obiș nuit) are 4 operaț ii principale: push (adaugă un element în vârf),
pop(remove un element de la vârf), top (arată elementul de la vârf) ș i
195
[Link]:
2. def__init__(self):
3. [Link] = None
4.
5. defcăutare(self, valoare):
6. returnself.recursive_search([Link], valoare)
7.
8. def cautare_recursiva(self, nod, valoare):
9. dacă nodul este None sau [Link] == valoare:
10. nod de returnare
11. dacă valoarea < [Link]:
12. returnself.recursive_search([Link]ânga, valoare)
13. altfel:
14. returnself.recursive_search([Link], valoare)
Acest lucru poate părea puț in ciudat, deoarece avem două funcț ii de căutare, dar există un motiv bun.
Dacă nu trecem de cazul nostru de bază, atunci verificăm dacă valoarea pe care o căutăm este
mai mic decât valoarea nodului la care ne aflăm în prezent; dacă da, atunci căutăm în stânga
subarborele acelui nod apelând lacercetare_recursivămetoda ș i trecerea
nodi curenț istângacopac. Altfel, valoarea pe care o căutăm este mai mare
decât valoarea nodului curent, caz în care numimcautare_recursivaș i
treceț i în nodurile curentedreptcopac.
Aminteș te-ț i că arborele stâng sau drept al unui nod este pur ș i simplu un pointer către un nod (putem privi
213
Pentru a clarifica, un nod frunzăstângaș iright «copacii» suntNiciunul.
Următorul pas va fi să examinăm inserarea unui element în arbore. Ceea ce facem aici
este practic acelaș i lucru pe care l-am făcut cu căutarea, cu excepț ia cazului în care noi
ajunge la un nod frunză pe calea noastră, vom seta pointerul său stâng sau drept pentru a indica către o
nod nou (în funcț ie de dacă valoarea este mai mică sau mai mare decât
valoarea de la nodul copil).
• Caz de bază: Dacă nodul în care ne aflăm esteNiciunulatunci inseraț i noul nod aici.
• Caz recursiv:
• Dacă valoarea pe care o introducem este mai mică decât valoarea nodului curent
apoi verificăm dacă arborele din stânga al nodului curent esteNiciunulDacă este, atunci inserează
acolo, altfel, apelează din nou insert ș i trece subarborele stâng.
• Dacă valoarea pe care o inserăm este mai mare decât valoarea nodului curent
apoi verificăm dacă subarborele drept al nodului curent esteNiciunulDacă este, atunci
inserează acolo, altfel, apelează din nou insert ș i trece subarborele drept.
214
Iată cum se face asta:
[Link]:
2. def__init__(self):
3. [Link] = None
4.
5. definsert(self, val):
6. dacă rootul este None:
7. [Link] = Nod(val)
8. altfel:
9. self.recursive_insert([Link], val)
10.
11. def inserare_recursiva(self, nod, val):
12. dacă val < [Link]:
13. dacă [Link]ânga este Niciunul:
Asta e. Sper că poț i vedea de ce recursia este utilă aici. Face codul nostru
citim mai bine ș i când ne planificăm asta în minț ile noastre, se potriveș te în mod natural în
algoritmul nostru.
Următorul, ne vom uita la ș tergerea unui element. Acest lucru este mult mai dificil.
În cazul inserț iei, întotdeauna inserăm într-unul dintre nodurile frunză, dar dacă ș tergem
ceva, apoi apar trei posibilităț i. Prima este cea mai simplă situaț ie:
1. Nodul pe care îl eliminăm nu are noduri fiică (adică un nod frunză). În acest
în acest caz, putem pur ș i simplu să eliminăm nodul.
2. Cazul următor este când eliminăm un nod care are doar un copil.
Din nou, acest lucru este suficient de simplu de gestionat. În acest caz, pur ș i simplu tăiem
nodul pe care îl eliminăm din arbore ș i conectăm copilul său la părintele său.
215
3. Cazul final este atunci când eliminăm un nod care are doi copii.
Acesta este cel mai complex caz ș i necesită o gândire inteligentă. Acolo
totuș i, există o proprietate utilă a BST-urilor pe care o putem folosi pentru a rezolva acest lucru
Ambele aceste copaci sunt diferite, dar ambele sunt valide. Ce am făcut aici
cum să transformi primul copac în al doilea?
Putem lua această idee ș i o putem aplica pentru eliminarea elementelor cu doi noduri copil.
Iată cum vom face asta:
216
• Înlocuiț i elementul nodului care trebuie eliminat cu minimul pe care îl avem.
doar găsit.
• Ai grijă! Subarborele drept conț ine acum un duplicat.
• Aplicaț i în mod recursiv eliminarea pe subarborele din dreapta
Când se aplică eliminarea în subarborele din dreapta pentru a elimina duplicatul, noi
poate fi sigur că nodul duplicat va cădea sub cazurile 1 sau 2. Nu va cădea
în cazul 3 (Nu ar fi fost minimul dacă am fi făcut-o).
Există două funcț ii de care avem nevoie aici. Una este metoda de eliminare ș i
altele vor găsi nodul minim. Aici avem o funcț ie liberă (vom avea
aminoperaț ie pe BST-ul nostru!).
Iată cum să îl codifici, voi comenta ș i codul deoarece este puț in complex:
[Link]:
2. def__init__(self):
3. [Link] = None
4.
5. defremove(self, value):
6. returnself.recursive_remove([Link], None, valoare)
7.
8. defrecursive_remove(self, node, parent, value):
9. # Funcț ie de ajutor
10. defmin_node(nod):
11. curr = nod
12. [Link] != Niciunul:
13. curr = [Link]ânga
14. returncurr
15.
16. # Caz de bază (elementul nu există în arbore)
17. ifnode == None:
18. nodde întoarce
19.
20. Dacă elementul de eliminat este mai mic decât nodul curent
21. atunci este în subarborele stâng. Trebuie să setăm curentul
22. subarborele stâng al nodului este egal cu rezultatul eliminării
23. dacă valoare < [Link]:
24. [Link] = self.recursive_remove([Link], node, value)
25.
26. Dacă elementul de eliminat este mai mare decât nodul curent
27. atunci este în subarborele din dreapta. Trebuie să setăm elementul curent
28. subarborele drept al nodului este egal cu rezultatul eliminării
29. elifvalue > [Link]:
30. [Link] = self.recursive_remove([Link], node, value)
31.
32. Dacă elementul de eliminat este egal cu valoarea lui
33. nodul curent, atunci acesta este nodul de eliminat
34. altfel:
35. print([Link], notparentisNone)
36. Nu este nodul rădăcină
37. dacă nu părinte este None:
38. Nodul nu are copii (CAZUL 2)
39. dacă node.num_children() == 0:
40. daca [Link] == nod:
41. pă[Link] = Niciunul
42. altfel:
217
43. pă[Link] = None
44. Nodul are doar un copil (CAZUL 2)
45. elifnode.num_children() == 1:
46. Obț ine nodul fiu
47. dacă [Link]ânga != Niciunul:
48. child = [Link]
49. altfel:
50. copil = [Link]
51.
52. Indicaț i nodul părinte către nodul copil al
53. nodo pe care îl eliminăm
54. dacă pă[Link]ânga == nod:
55. pă[Link]ânga = copil
56. altfel:
57. [Link] = copil
58.
59. Nodul are doi copii (CAZUL 3)
60. elifnode.num_children() == 2:
61. Obț ine nodul minim în subarborele drept al nodului de ș ters
62. smallest_node = min_node([Link])
63.
64. Copiaț i valoarea celor mai mici noduri în nodul care deț inea anterior
65. valoarea pe care voiam să o ș tergem
66. [Link] = smallest_node.elem
67. self.recursive_remove(node, părinte, valoare)
68. Nodul de ș ters este nodul rădăcină
69. altfel:
70. Numai 1 element în copac (rădăcina) - setează rădăcina la Niciunul
71. ifnode.num_children() == 0:
72. node = None
73. Rădăcina are un singur copil - fă-l pe acesta rădăcină
74. elifnode.num_children() == 1:
75. dacă [Link]ânga != None:
76. [Link] = [Link]
77. dacă [Link] != None:
78. [Link] = [Link]
79. elifnode.num_children() == 2:
80. smallest_node = min_node([Link])
81. [Link] = cel mai mic_node.elem
82. self.recursive_remove(node, None, valoare)
83. nodde întoarcere
Asta e greu. Asigură-te că înț elegi operaț iunea de ș tergere, chiar dacă aia
înseamnă să treci prin asta din nou ș i din nou. Foloseș te un pix ș i o foaie dacă ai nevoie!
Este o întrebare bună de pus de un angajator, deoarece arată cum cineva
abordează o problemă dificilă (subliniind diferite scenarii, descompunând
problemă jos, etc.).
Asta este tot ce vreau să discut despre Arborii de Căutare Binari pentru moment. Există câteva
mai multe metode pe care le putem adăuga, ș i voi lăsa asta în seama ta în exerciț ii!
22.3 - Exerciț ii
Important: Unele dintre aceste exerciț ii sunt destul de dificile! Folosiț i-o pentru a rezolva problemele.
solving techniques to help you arrive at a solution. Sketching out what's
ce se întâmplă pe hârtie este o modalitate bună de a te ajuta!
218
E vremea să ridicăm un pic nivelul de dificultate al întrebărilor. Există
niș te întrebări foarte dificile aici. Mult noroc!
Întrebare 1
Am vorbit mai devreme despre complexităț ile de timp de execuț ie ale metodelor listei legate.
am implementat. Am menț ionat că am putea îmbunătăț i complexităț ile lor.
Întrebarea 2
Schimbă implementarea luiadaugă()sauș terge() metodele pe Linked
Listă de clasă pentru a obț ine o listă înlănț uită care se comportă ca:
•O stivă
• O coadă
Întrebare 3
O altă metodă utilă pe care clasa noastră Linked List ar putea să o aibă este olungime()metodă.
Adică, returnează numărul de elemente din lista legată.
Implementaț ilungime()metodă.
Întrebarea 4
Dacă ai gândit cu atenț ie despre implementarea ta alungime()metodă
dacă ai lucrat la exerciț iul anterior, atunci s-ar putea să poț i să sări peste această întrebare.
Cu toate acestea, nu mă aș tept că ai făcut-o.
Putem face mai bine decât atât. Cum ai putea schimba Lista Lincată
clasa astfel încât complexitatea de rulare a talungime()metoda este O(1)?
219
Întrebarea 5
Înălț imea (adâncimea) unui copac este numărul de muchii de pe cel mai lung drum de la
nodul rădăcină la nodul frunză. (O muchie este practic săgeț ile din diagrama noastră
pe care l-am analizat anterior)
Înălț imea este determinată de numărul de muchii din cea mai lungă cale, ca ș i cum ar fi
următoarele
220
Puteț i de asemenea să vizualizaț i înălț imea unui copac astfel:
Ar trebui să scrii o metodă recursivă pentru a găsi înălț imea oricărei binare date.
arbore de căutare
Întrebarea 6
Această întrebare este foarte dificilă
Putem, totuș i, să facem o optimizare a arborilor noș tri de căutare binară astfel încât
căutarea ș i inserarea sunt întotdeauna O(log n), indiferent de ordinea în care introducem
elemente.
Acest tip de arbore binar de căutare auto-echilibrat are un nume special. Se numeș te
un arbore AVL.
221