Skakačev obhod: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
Brez povzetka urejanja |
m drobni popravki, +en: in odstranjen angleški termin iz samega besedila |
||
Vrstica 13:
}}
'''Skakačev obhod'''
Problem, ki so ga proučevali mnogi matematiki, tudi [[Leonhard Euler|Euler]], lahko posplošimo v več smeri:▼
▲'''Skakačev obhod''' (ang. Knight's Tour) je [[matematika|matematični]] [[problem]] s [[Skakač (šah)|skakačem]] na [[standard|standardni]] [[šahovnica|šahovnici]] (8x8). Skakača postavimo na poljubno začetno polje in z njim obiščemo vsa ostala polja na deski.
▲Problem, ki so ga proučevali mnogi matematiki, tudi [[Euler]], lahko posplošimo v več smeri:
*iščemo zaključene obhode (po zadnji potezi skakač skoči na začetno polje),
*uporabimo različne velikosti (in oblike) šahovnice,
Vrstica 24 ⟶ 22:
Obstajajo tudi [[igra|igre]] za enega ali več igralcev s to tatiko.
Skakačev obhod je primer bolj
▲Skakačev obhod primer bolj spošnega iskanja [[William Rowan Hamilton|Hamiltonove]] [[Hamiltonova pot|poti]] v [[teorija grafov|teoriji grafov]], ki je [[NP-polnost|NP-poln]]. Zaključen skakačev obhod pa je primer [[Hamiltonov cikel|Hamiltonovga cikla]].
==Program v paskalu==
Vrstica 32 ⟶ 29:
==Glej tudi==
*[[Problem osmih dam]]
Vrstica 41 ⟶ 37:
* [http://www.ktn.freeuk.com/index.htm Skakačev obhod](v angleščini)
[[en:Knight's Tour]]
[[ja:ナイト・ツアー]]
| |||