# intsort.py:
sorteren van een rij getallen
” ”” methode : s o r t e r e n door i n v o e g e n k l e i n s t e e le m e nt z o e ke n i n de r e s t e r e n d e d e e l r i j
Voorbeelden
en t o e v o e g e n aan de g e d e e l t e l i j k g e s o r t e e r d e d e e l r i j ” ”” import numpy
Sorteren
def l e e s r i j ( x ,m) :
Schrijf een programma dat een rij gehele getallen sorteert
print ’ Geef een a a n t a l g e h e l e g e t a l l e n ’ fo r i in ra ng e (m) :
• een eerste functie leest de rij gehele getallen; • een tweede functie sorteert deze getallenrij van klein naar groot;
i n v o e r = r a w i n p u t ( s t r ( i )+ ’ : ’ )
• een derde functie drukt de gesorteerde rij af.
x [ i ] = int ( invoer ) def d r u k r i j ( r ,m) : fo r i in ra ng e (m) : print r [ i ] ,
print
Voorbeeld: n = 5
def z o e k i n d e x k l e i n s t e ( a , n , va na f ) : i n d e x k l = va na f
0
1
2
3
4
8
4
6
5
2
4 ↑
6
2 ↑ 8
2
4
6
8
2
4
5
8
2
4
5
6
i=0 i=1 i=2 i=3
fo r i in ra ng e ( va na f +1 ,n ) : i f a [ i ] < a [ indexkl ] : indexkl = i
5
return i n d e x k l
5 ↑ 6 ↑ 8
def s o r t e e r r i j ( r , n ) : fo r i in ra ng e ( n−1) : indexkleinste = zoekindexkleinste (r , n , i ) i f r [ i n d e x k l e i n s t e ] != r [ i ] : hulp = r [ i ] r [ i ] = r [ indexkleinste ] r [ i n d e x k l e i n s t e ] = hulp
Voorbeeld: n = 10
def main ( ) : i n v o e r = r a w i n p u t ( ’ Geef a a n t a l : ’ ) x = 74
m = int ( invoer ) a = numpy . z e r o s ( [m] , i n t )
0
1
2
3
4
5
6
7
8
9
17 ↑l
23
37
42
59 ↑m
61
68
74
85
96 ↑r
l e e s r i j ( a ,m)
↑l
b = l i s t (a)
↑l
↑m ↑m
s o r t e e r r i j ( a ,m)
↑r
↑r ↑l ↑r
d r u k r i j ( a ,m) b. sort () x = 40
d r u k r i j ( b ,m)
0
1
2
3
4
5
6
7
8
9
17 ↑l
23
37
42
59 ↑m
61
68
74
85
96 ↑r
↑l ↑m
↑r
↑l
#startoproep
↑m
main ( )
↑r ↑l ↑r
docstring: een triple-quoted string, ev. over meerdere lijnen ("""...""") uitgebreidere commentaar: niet elke lijn moet met commentaarsymbool (#) beginnen
# binzoek.py:
binair zoeken in een gesorteerde rij getallen
import numpy
Binair zoeken Schrijf een programma dat
AANTAL = 50 def l e e s r i j ( a ) :
• met een eerste functie een aantal gehele getallen inleest (maximum 20), die gesorteerd van klein naar groot ingegeven worden; eindigen met EOF ;
print ’ Geef een a a n t a l g e h e l e g e t a l l e n ’
• met een tweede functie een bijkomend geheel getal inleest;
while i < AANTAL :
• met een derde functie bepaalt of het laatst ingelezen getal in de rij voorkomt of niet (dit moet zo effici¨ent mogelijk gebeuren); • in het hoofdprogramma afdrukt of het getal aanwezig was of niet, en, zo ja op welke plaats in de rij.
i = 0 try : i n v o e r = r a w i n p u t ( s t r ( i )+ ’ : ’ ) a [ i ] = int ( invoer ) i f i > 0 and a [ i ] < a [ i −1] : print ’ v o r i g e twee g e t a l l e n n i e t i n g e s o r t e e r d e v o l g o r d
Afhankelijk van het beturingssysteem is EOF: CTRL C of CTRL D
else : i += 1 except EOFError :
print break return i
else : print z o e k g e t a l , ’ i s n i e t a a nw e z ig ( ’ , index , ’ ) ’
def d r u k r i j ( r ,m) :
i f inde x == 0 :
fo r i in ra ng e (m) :
print z o e k g e t a l , ’ i s k l e i n e r dan e e r s t e g e t a l ’
print r [ i ] ,
e l i f inde x == n :
print
print z o e k g e t a l , ’ i s g r o t e r dan l a a t s t e g e t a l ’ else : print z o e k g e t a l , ’ kan t o e g e v o e g d worden op p l a a t s ’ , inde x
def b i n z o e k ( r , n , x ) : links = 0
# startoproep
r e c h t s = n−1 i f x < r [ l i n k s ] : return 0
main ( )
i f x > r [ r e c h t s ] : return n while l i n k s != r e c h t s
:
midden = ( l i n k s + r e c h t s ) / 2 i f r [ midden ] < x : l i n k s = midden + 1 else : r e c h t s = midden return l i n k s def main ( ) : a = numpy . z e r o s ( [AANTAL] , i n t ) n = l e e s r i j (a) drukrij (a ,n) i n v o e r = r a w i n p u t ( ’ Geef he t t e z o e ke n g e t a l : ’ ) zoekgetal = int ( invoer ) inde x = b i n z o e k ( a , n , z o e k g e t a l ) i f inde x < n and a [ inde x ] == z o e k g e t a l : print z o e k g e t a l , ’ i s a a nw e z ig op p l a a t s ’ , index , ’ ( va na f 0 ) ’
Een adressenbestand Schrijf een programma dat een aantal bewerkingen kan uitvoeren op adresgegevens. De invoer is een tekstbestand met per lijn een naam, voornaam, straat+nr, postcode, gemeente en telefoonnummer. De bewerkingen zijn: het inlezen van het bestand in een dictionary (sleutel is de tuple gevormd uit naam en voornaam), het maken van een gesorteerde lijst, het zoeken van een element op basis van naam en voornaam, het toevoegen van een element, het verwijderen van een element, het maken van een op postcode gesorteerde lijst en het bewaren van de gegevens op een tekstbestand. Een voorbeeld van een gegeven tekstbestand: Drieskens;Marc;Vendelstraat 15;3012;Wilsele;016/563227 Leupe;Dirk;Bergstraat 56;2500;Lier;03/4577001 Ooms;Willy;Voort 27;2310;Rijkevorsel;03/3124519
druk ( n )
#adres .py: beheer van adressen def i n l e z e n ( ) :
return
naw = d i c t ( ) try :
def z o e ke n ( naw ) : f i n = open ( ’ a d r e s . t x t ’ , ’ r ’ )
naam = r a w i n p u t ( ’Naam : ’ )
except :
vnaam = r a w i n p u t ( ’ Voornaam : ’ )
print ’ be st a nd kan n i e t geopend worden ’
druk ( ( naam , vnaam ) )
exit (1)
return
while True : r l i j n = fin . readline ()
def p o s t l i j s t ( naw ) :
i f r l i j n == ’ ’ :
namen = naw . ke ys ( )
break ;
spwt = naw . v a l u e s ( )
li j n = r l i j n . strip ()
# einde lijn teken verwijderen
velden = l i j n . s p l i t ( ’ ; ’ ) velden [ 3 ] = i nt ( velden [ 3 ] )
elem = [ ] fo r q in spwt :
# postcode omzetten naar int
naw [ ( v e l d e n [ 0 ] , v e l d e n [ 1 ] ) ] = v e l d e n [ 2 : ]
elem . append ( q [ 1 ] )
# postcode
comb = z i p ( elem , namen )
fin . close ()
comb . s o r t ( )
print ’ a a n t a l a d r e s s e n ’ ,
l e n ( naw )
fo r p , n in comb :
return naw
druk ( n ) return
def druk ( n ) : i f n in naw :
def t o e v o e g e n ( naw ) :
geg = naw [ n ] print ’%−18s : %−18s %4d %−18s %s ’ %
naam = r a w i n p u t ( ’Naam : ’ ) \
( n [ 0 ] + ’ ’+ n [ 1 ] , geg [ 0 ] , geg [ 1 ] , geg [ 2 ] , geg [ 3 ] ) else : print ’ geen g e g e v e n s o ve r ’ , n
vnaam = r a w i n p u t ( ’ Voornaam : ’ ) st r a a t = raw input ( ’ Straat : ’ ) p o s t c o = r a w i n p u t ( ’ P o st c o de : ’ ) postcode = int ( postco ) gemeente = r a w i n p u t ( ’ Gemeente : ’ )
def l i j s t ( naw ) :
t e l e f o o n = raw input ( ’ Telefoonnr : ’ )
namen = naw . ke ys ( )
naw [ ( naam , vnaam ) ] = ( s t r a a t , po st c o de , gemeente , t e l e f o o n )
namen . s o r t ( )
return
fo r n in namen :
def v e r w i j d e r e n ( naw ) :
print ’ ( 4 ) : e le m e nt t o e v o e g e n ’
naam = r a w i n p u t ( ’Naam : ’ )
print ’ ( 5 ) : e le m e nt v e r w i j d e r e n ’
vnaam = r a w i n p u t ( ’ Voornaam : ’ )
print ’ ( 6 ) : g e g e v e n s bewaren ’
i f ( naam , vnaam ) in naw :
print ’ ( 7 ) : op p o s t c o d e g e s o r t e e r d e l i j s t ’
del naw [ ( naam , vnaam ) ]
ke uz e = r a w i n p u t ( ’ Keuze : ’ )
else :
k = i n t ( ke uz e )
print ( naam , vnaam ) , ’ n i e t a a nw e z ig i n d i c t i o n a r y ’
i f k == 1 : naw = i n l e z e n ( ) e l i f k == 2 : l i j s t ( naw )
return
e l i f k == 3 : z o e ke n ( naw ) def bewaren ( naw ) :
e l i f k == 4 : t o e v o e g e n ( naw ) e l i f k == 5 : v e r w i j d e r e n ( naw )
try : f u i t = open ( ’ na dre s . t x t ’ , ’w ’ )
e l i f k == 6 : bewaren ( naw ) e l i f k == 7 : p o s t l i j s t ( naw )
except : print ’ be st a nd kan n i e t gemaakt worden ’
e l s e : break print ’ Dank u wel ’
return fo r n in naw :
# startoproep
geg = naw [ n ] r = l i s t ( n ) + l i s t ( geg ) r [3] = str ( r [3] )
# postcode omzetten naar string
print r s = ’; ’ l i j n = s . j o i n ( r ) + ’ \n ’ f u i t . write ( l i j n ) fuit . close ()
main ( )
def main ( ) : print ’ Beheer van een a d r e s s e n b e s t a n d
’
while True : print ’ ( 0 ) : st o ppe n ’ print ’ ( 1 ) : i n l e z e n van he t be st a nd ’ print ’ ( 2 ) : g e s o r t e e r d e l i j s t ’ print ’ ( 3 ) : e le m e nt z o e ke n ’
