i
i
“1384-Lokar-Tezave” — 2010/7/30 — 10:47 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 26 (1998/1999)
Številka 6
Stran 342
Matja Lokar:
TEŽAVE POSTAJNEGA NAČELNIKA
Ključne besede: računalništvo, kombinatorika, permutacije, razpore-
ditve vagonov, računalniški programi.
Elektronska verzija: http://www.presek.si/26/1384-Lokar.pdf
c© 1999 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 - Naloge I
TEŽAVE POSTAJNEGA NAČELNIKA
V mestu PopPush je znamenit a železniš ka post aja , zgrajena še v prejšnje m
st olet ju . Žal so bila sredstva za grad njo takrat zelo omejena. Zato je
post aj a na slepem tiru , do katerega vodi t ir iz smeri A, iz njega pa izhaj a
t ir v smeri B (glej sliko) .
B
POSTAJA
A
o o o
Lokaln a tradicija je, da vsak vlak , ki pride iz smeri A, nad aljuje
pot v sm eri B z na določen način pr eur ejenim vrstnim redom vagonov.
Predpostavi, da ima vlak, ki prihaja iz smeri A, N :::; 1000 vagonov,
oštevilčenih naraščajoče: 1, 2, ... , N. Postajni načelnik mora vedet i, ali
je vagone, ki prihajajo iz smeri A, mož no preuredi ti tako, da bo nj ihov
vrstni red v smeri B enak al , a2, .. . , aN . Enega ali več vagonov lahko z
vlaka odpnejo in zapeljejo na postaj o, od tam pa na izhodni t ir v smeri
B. V vsa kem t renutku je na postaji lah ko poljubno mnogo vagonov . Ko
vagon pride na post aj o, se ne more več vrnit i na t ir v smeri A. Prav tako
se vagon ne more vrniti nazaj na post aj o, ko jo enkrat zapusti v smer i B.
Pomagaj postajnemu načelniku in sestavi program, ki določi , ali je
možno dobiti želeni razpored vagonov. Na pri mer , za podatke 1 3 4 5 2
bo odgovor pritrdilen (Da) , za podatke 1 3 5 2 4 pa nikalen (Ne) .
Malija Lokar
I Računalništvo - Rešitve nalog
TEŽAVE POSTAJNEGA NAČELNIKA­
R ešitev s st r . 342
Ideja rešit ve je, da simuliramo sestavljanje preurejenega vrstnega reda va-
gonov . Denimo, da na izhodnem t iru (smer B) pot rebujemo vagon številka
k . Na postaji so čakajoči vagoni vedno ur ejeni padajoče . Ker moram o s
post aj e najprej pr em akniti prvi čakajoči vagon , pogledamo sa mo tega. Če
to ni vagon številka k , je možno , da je iskani vagon še vedno sest avni del
vlaka na vhodnem t iru (smer A) . Če vagona tam ni , želene razporeditve ni
moč dobiti. Ker so vagon i na tiru A ur ejeni po vrsti , t udi tam pogledamo
le pr vega . Če ima številko manjšo ali enako k , pr epeljemo vse vagone do
k-tega na postajo.
Poglejm o primer. Denimo, da bi rad i dosegli razporedi tev 1 3 4 5 2.
Na jprej pr ep eljemo vagon šte vilka 1 na izhodni tir. Na naslednjem koraku
potrebujemo vagon številka 3. Zato vagona 2 in 3 zapeljemo na postajo
in dobimo po ložaj, ki je prikazan na spo dnji sliki.
B
Vagon št evilka 3 odpeljemo na izhodni tir , nato pa nanj pr epeljemo še
vagona številka 4 in 5, prav na zadnje pa s post aj e odpeljemo še vagon
številka 2. Če pa bi bila želena razporeditev 1 3 5 2 4, pač ne bi šlo.
Začeti bi morali tako kot pr ej . Ko bi na tir B pr ep eljali vagon številka 5,
bi bili vagoni razporejeni t ako, kot kaže spodnja slika .
B A
CD
== postaja[na_postaji - 1] )
1* Vagon gre s postaje na tir B. *1
1* želene razporeditve ni mogoce dobiti! *1
Računalništvo - Rešitve nalog I
Iz tega položaja pa vagona šte vilka 2 ni mogoče dobiti pred številko 4.
#include <stdio.h>
1* Ugotovi, ali je s pomo~jo slepega tira vagone mogo~e
preurediti v želeni vr s t ni red. *1
#define MAXN 1000 1* najve~ja dolžina vlaka *1
int main(void)
{
int N; 1* dejanska dolžina vlaka - število vagonov *1
int vagon [MAXN]; 1* želena razporeditev vagonov na tiru B *1
int postaja[MAXN]; 1* vagoni , ki ~akajo na postaji *1
int na_tiru_A; 1* številka prvega vagona na tiru A *1
int na_postaji ; 1* število vagonov na postaji *1
int i, j;
printf("\nVnesi dolzino vlaka: Ol) ; scanf("%d", &N);
printf( "Vnesi zeleno razporeditev vagonov na izhodnem tiru:\n");
for (i = O; i < N; i++) {
printf(" st . %d. vagona: Ol, i + 1);
scanf("%d", &vagon[i]);
};
na_tiru_A = 1;
1* Na za~etku so vs i vagoni na tiru A, *1
na_postaji = O; 1* postaja pa je prazna . *1
for (i = O; i < N; i++) { 1* Na tir B moramo dati vagon [i ] . *1
if (na_tiru_A <= vagon[i]) {
1* Vagoni do vagon[i] morajo iti na postajo . *1
for ( j = na_tiru_A ; j < vagon[i] ; j++) {
postaja[na_postaji] = j;
na_postaji++ ;
} ;
1* vagon j i.] "prepeljemo " , prvi na tiru A je vagon j i.] + 1. *1
na_tiru_A = vagon[i] + 1;
}
else if (vagon [i ]
na_postaji-- ;
else break ;
} 1* for *1
if (i == N) printf("\nGre!\n") ; else printf("\nNe gre!\n");
return O;
}
Pri pisanju programa smo pr ivzeli, da bodo vhodni podatki vnešeni
pravilno in da bodo res predst avljali neko permutacijo števil od 1 do N.
Dopoln ite program tako, da bo pr i napačnem vnosu "protest iral" .
Matija Lokar