i i “1423-Juvan-Lokalne” — 2010/8/23 — 8:16 — page 1 — #1 i i i i i i List za mlade matematike, fizike, astronome in računalnikarje ISSN 0351-6652 Letnik 27 (1999/2000) Številka 6 Strani 340–341 Martin Juvan: LOKALNE VOLITVE Ključne besede: računalništvo, programiranje, volilni imeniki, ureja- nje, programski jezik C. Elektronska verzija: http://www.presek.si/27/1423-Juvan.pdf c© 2000 Društvo matematikov, fizikov in astronomov Slovenije c© 2010 DMFA – založništvo Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali posameznih delov brez poprejšnjega dovoljenja založnika ni dovo- ljeno. Računalništvo - Na loge I LOKALNE VOLITVE Nedavno so se v Kašlju odločili, da kraj evno skupnost razdelijo na dva dela : Sp odnji Kašelj in Zgornji Kašelj . Seved a je treba po razdelitvi opravit i nove lokalne volitve. Žal pa sta volilna imen ika za oba Kašlja nekoliko neurejena. In tako so se v odboru za pripravo volitev spomnili Vas , kašeijskega programerskega vseznalca . Po iskati morate napake v volilnih imenikih. Vsaka oseba ima enolično določeno št irimestno identifikacijsko števil- ko. Vhodni podatki so t ri (neur ejena) za poredja števil. Vsako se konča z vredn ostj o - 1. P rvo zaporedje predstavlja seznam volivcev, torej gre za seznam ident ifikacijskih šte vilk t ist ih oseb, ki lah ko volijo. P azit i morate, da se v tem seznamu nobeno število ne pojavi večkrat; če se pojavi, izpišit e opozorilo (za vsakega volivca samo enkrat): Volivec xxxx j e prijavljen večkrat . Drugo in tretje zaporedje predstavljat a nova volilna imenika za Spodnji oziroma Zgornji Kašelj . Tu je treba preverit i več stvari. Najprej je t reba ugotovit i, ali imaj o osebe iz te h dveh imenikov sp loh volilno pravico, ali se torej nahajajo v pr vem seznamu. Če najdete osebo brez volilne pravice, izpišit e obvestilo (za vsako osebo v vsakem imeni ku sa mo enkrat): Oseba xxxx i z Spodnj ega Kaš l j a ni ma vol i l ne pravice. oziroma Oseba xxxx iz Zgornj ega Ka š l j a n i ma vo l i l ne pravice. Če se taka oseba nah aj a v obeh imenikih , izpišit e obe obvestili. Za osebe, ki imajo volilno pr avico, je t reba preveriti , da niso hk rati prijavljene v obe h Kašljih . Če so, morate izpisat i: Volivec xxxx je pri j av l jen v Spodn j em in Zgornjem Kašlju . Za volivce, ki so le v enem od obeh imenikov, je treba prever iti , da so vanj vpisani le enkrat. Obvestilo o odkriti napaki je pod obno kot pri seznamu oseb z volilno pravico: Volivec xxxx je v Spodnjem Ka š l j u prijavljen večkrat . Če gre za volivca iz Zgornjega Kašlja , v izpisu besedico Spodnj em za- menjam o z Zgor njem. Nazadnje je treba še pr everiti , da je vsak volivec Volivec mxx ni vpisan v noben volilni b e n i k . Volivec 1234 f e prij awl j an vet!kat. Oseba 4321 iz Spodnjega K3U1 ja nima valilae pravice. Oseba 7777 l z Zgornjega Ka#lja nima volilns pravice. Oneba 4321 iz Zgomjega KaHlja nima volillne pravfce. Volivec 3784 je v p i s a ~ v Spodnjem in Zgornjem KaBlja. Yolivec 8862 j e v Spodnjem Kaslju prf javljen veUs;rat. Volivec 1234 j e v Zgornjm Kaglju prijavljen veEkrat. Volivec 0999 ni vpisan v noben volilni imenfIt Računalništvo - Rešitve nalog I .LOKALN E VOLITVE - Rešitev s str. 340 Navodila za pr everj anje pr avilnost i volilnih imenikov, podana v besedilu naloge, so nekoliko razvlečena in kar zapletena. Podatek , ki bistveno vpliva na zasnovo rešitve, pa je omenjen že na začetku : vsaka oseba je enolično opisana s št irimest no ident ifikacijsko št evilko. Potencialni h volivcev torej ni več kot 10000. Rešitev bomo sprogramirali v program skem jeziku C, brez težav pa jo bo moč predelat i t udi v pascal in druge sorod ne jezike. Zmerno število volivcev nam omogoča , da v program u seznam volivcev in oba volilna imenika predst avimo s t remi tabelami sez, i mel in i me2, ki bodo vse imele po 10000 element ov. Če bi bilo potencialnih volivcev več , bi s tako zastavljeno rešitvijo lahko zašli v težave zara di pomanjkanja pomnilnika. Vrednost i elementov t ab el bodo le O, 1 ali 2. Element z ind eksom i bo imel vrednost O, če osebe z identi fikacijsko št evilko i ne bo v seznamu volivcev oziroma v pripadajočem volilnem imeniku, vrednost 1, če se bo v seznamu oziroma imeniku poj avila natanko enkra t , in vrednost 2, če se bo poj avila večkrat . Da ne bomo preveč potratni s pomnilnikom , bodo element i tabele t ipa char (v C-ju se tudi znaki obnašajo kot majhna števila). Opi šimo še, kako poteka preverjanje seznama volivcev in obeh volilnih imenikov. Najprej v zanki preberemo identi fikacijske številke volilnih upravičencev . Upo ra bili bomo zanko do . Seznam številk se konča z vrednostjo - 1, zato tedaj , ko preberemo to vrednost , z br eak končamo zanko. Ident ifikacijsko številko preberemo v spremenljivko oseb a . Če ima sez [oseba] vrednost O, to vre dnost le popravimo na 1. Če ima sez [oseba] vrednost 1, vrednost povečamo na 2, hkrat i pa tudi izpišemo obvest ilo, da je volivec večkrat pr ijav ljen . Kadar ima sez [oseba] vre- dnost 2, ne storimo ničesar (obvest ilo o večkratni prij avi smo že izpisali pri spremembi vrednost i z 1 na 2, ponovljenih obvest il pa ne smemo izpisovati ). Na enak način preberemo t udi podat ke o osebah iz volilnih imenikov za Spo dnji in Zgornji Kašelj. Razlika je le pri preverj anju in izpisovanju opozoril. Tokrat izpišemo opozorilo, ko prvič naletimo na osebo , ki ni na seznamu volivcev (vrednost s ez [oseba] je enaka O, pa tudi imel [oseba] oziroma i me2 [oseba] mora imet i vrednost O) . Ko so vsi podatki prebran i, opravimo še preost ala št iri preverjanj a . Vsako od njih je sestavljeno iz zanke for , v kateri spremenljivka oseba preteče vse možne identi fikacijske številke. Pogoji , ki jih pri posameznem preho du preverjamo, so: I Računalništvo - Rešitve nalog kaj pr everj amo sez [oseba] ime1 [oseba] ime2 [oseba] ose ba, prijavljen a != O != O != O v obeh Kaš ljih oseb a, večkrat prijavljena != O 2 O-- -- v Spod njem Kaš lj u oseb a , večkrat pr ij avlj en a != O O 2-- -- v Zgornjem Kašlj u vo livci , ki ni so vpisan i != O O O-- -- v no benem Kaš lju Program v C-ju je nekoliko daljši, kot so običajno rešitve v Preseku, a programersko ni posebej zahteven: #include #define MAX 10000 1* zgornja meja za število vol i vce v *1 #define NI Zl "Oseba 'lo04d iz 'los nima volilne pravice .\n" #define NI Z2 "Volivec 'lo04d je 'los.\n" int main(void) { char sez [MAX] int oseba; {O}, imel [MAX] {O} , ime2 [MAX] {O}; do { 1* Pregled seznama vol i vcev . *1 scanf("'lod", &os eba ); if (os eba == -1) break; 1* konec seznama volivcev *1 if (s ez [os eba] == O II sez[oseba] == 1) { ii (s ez [oseba] == 1) printf (NIZ2 , oseba, "prijavlj en vel:krat" ) : sez[oseba]++: } } "hile (1); do { 1* Pregled volilnega imenika za Spodnji Kaš e l j. *1 scanf (lI'l.d" , &:oseba); if (oseba == -1 ) break; 1* konec i menika *1 if ( ime l [os eba] == O II imel[oseba] == 1) { if (sez[oseba] == O && i mel[oseba] == O) printf (NIZ1 , oseba, "Spodn j ega Kašlja"); imel [oseba]++; } } "hile (1) ; Računalništvo - Rešitve nalog I do { 1* Pregled volilnega imenika za Zgornji Kašelj . *1 scanf("%d", &oseba); if (oseba == -1) break; 1* konec imenika *1 if ( ime2 [os eba] == O I I ime2[oseba] == 1) { if (sez[oseba] == O && ime2[oseba] == O) printf (NIZ1, oseba, "Zgornjega Kašlja" ) ; ime2 [oseba] ++; } } "hile (1 ) ; 1* Poiš~emo osebe, ki so prijavljene v Spodnjem in Zgornjem Kašlju. *1 for (os eba = O; oseba < MAX; oseba++) . if (sez [oseba] ! = O && amet Ioseba] != O && ime2 [oseba] ! = O) printf(NIZ2, os eba, "prijavljen v Spodnjem in Zgornjem Kašlju"); 1* Iš~emo ve~kratne prijave v imenik za Spodnji Kašelj. *1 for (oseba = O; oseba < MAX; oseba++) if (sez[oseba] != O && imel[oseba] == 2 && ime2[oseba] == O) printf (NIZ2, oseba, "v Spodnjem Kašlju prijavljen ve~krat") ; 1* Iš~emo ve~kratne prijave v imenik za Zgornji Kašelj . *1 for (oseba = O; oseba < MAX ; oseba++) if (s ez [os eba] != O && ime2[oseba] == 2 && imel[oseba] == O) printf(NIZ2, oseba, "v Zgornjem Kašl j u prijavljen ve~krat " ); 1* Iš~emo volivce , ki niso vpisani ne venem ne v drugem Kašlju. *1 for (os eba = O; oseba < MAX; oseba++) ii (sez [oseba] ! = O && imel [oseba] == O && ime2 [oseba] == O) printf("Volivec %04d ni vpisan v noben volilni imenik .\n" , oseba) ; return O; } Ker ima revij a Presek majhne strani , smo si pri vrs ti cah , ki vsebujejo dalj še izpise, pomagali s simboličnima konstantama NIZi in NIZ2 in tako malce skrajšali t e vrsti ce. Program bere pod atke s standardnega vhoda. Če ga želite pr eizkusiti z večj o količino pod atkov, te najprej pripravite na datot eki , nato pa prevedeni pr ogram poženite iz ukazn e vrstice in vhod pr eusmerite na dato teko (npr. volitve