i
i
“2-4-Batagelj-Obracanje” — 2010/5/5 — 14:50 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 2 (1974/1975)
Številka 4
Strani 166–167
Vladimir Batagelj:
OBRAČANJE KONČNIH ZAPOREDIJ
Ključne besede: bolj za šalo kot zares, matematika, rekreacijska ma-
tematika, končna zaporedja, sortiranje.
Elektronska verzija: http://www.presek.si/2/2-4-Batagelj.pdf
c© 1975 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.
Pmvimo , da slto zaporedj e B t e v i l  o b m i l i  , Ee Elene zapiHm 
v obratnem vretnam mdu, T W  j e  na primer obrat eapoxedjs 
3 , 7 , 1 ¶ 5 , 8  
=pared j e 
8 ¶ 5 * 1 , 7 . 3 '  
Obr&anje zaporedij j e  osnova narrlednji nalogi, ki m i  ja je ne- 
d a m  sastavi l  nek xnanec. 
Dano je raporedje 
8 3 1 4 5 2 7 9 6  
Z njim lahko storiiH dvoje: 
- a l i  eaporedja razdalfg na dva dsla i n  m i  del obrne6 
- ali pa celotno raporedje obrnel. 
Tako dobiš novo zaporedje. Postopek nadaljuješ tako dolgo, dokler
ne dobiš zaporedja
1 2 3 4 567 8 9
Rešitev: Naloga ni posebno težka in hitro odkrijemo postopek, ki
vodi do rešitve.
1) 8 3 1 4 5 2 7 ef] 6
2 ) [lJ 7 2 5 4 1 3 8 6
3 ) 6 m 3 1 4 5 2 7 9
4) ~ 6 3 1 4 5 2 7 9
5) []J 2 5 4 1 3 6 8 9
6) m 3 1 4 5 2 7 8 9
7) 2 IT] 4 1 3 6 7 8 9
8 ) ru 2 4 1 6 7 . 8 9
9) 3 1 [ij 2 S 6 7 8 9
10) [ij 1 3 2 S 6 7 8 9
11) 2 [lJ 1 4 S 6 7 8 9
12) [lJ 2 1 4 S 6 7 8 9
13) 1 2 3 4 S 6 7 8 9
Pazljiv bralec je najbrž že sam opazil pravila postopka. Za-
poredje razdelimo na levi neurejeni in desni ur-e j erd, del. Spo-
četka je lahko celo zaporedje neurejeno. Urejeni del je označen
z debelej šim tiskom. Največji člen v neurejenem delu (označeni
so s kvadratkom) obrnemo na ·začetek zaporedja in od tu, v nasled-
njem koraku, na začete~ urejenega dela .•. To ponavljamo toliko
časa, dokler ni vse zaporedje urejeno.
Naloga postane zanimivejša, če se vprašamo: Koliko najmanj
obračanj je potrebnih za ureditev tega zaporedja?
Poskusite urediti še zaporedje
3,6,2,7,4,8,1,9,5
Možni sta tudi varianti z nekoliko spremenjenimi pravili:
1 .varianta: pravili sta: ali zaporedje razdeliš na dva dela in
oba dela obrneš ali pa celotno zaporedje obrneš.
2.varianta: pravilo je: obrneš lahko poljuben del (podzaporedje)
danega zaporedja.
VLadimir Batagelj
167