.otázka z minulého týždňa
Koľko dám sa dá umiestniť na prázdnu šachovnicu tak, aby sa navzájom neohrozovali? .odpoveď
Osem. To, že ich je najviac osem, je jasné okamžite – nijaké dve dámy nemôžu stáť na tom istom stĺpci (alebo riadku) a keďže stĺpcov (aj riadkov) je osem, môže byť dám maximálne osem. To, že sa ich naozaj dá umiestniť osem, z nijakej jednoduchej úvahy nevyplýva. Treba to jednoducho začať skúšať a ak postupujeme rozumne a systematicky, po určitom čase riešenie nájdeme.
V skutočnosti existuje 92 rôznych riešení tejto úlohy, z ktorých iba 12 sa považuje za naozaj rôznych (tie ostatné totiž vzniknú z tých dvanástich otočením šachovnice alebo urobením zrkadlového obrazu). Jedno z riešení je napríklad: a1, b7, c4, d6, e8, f2, g5, h3.
Na tejto úlohe a na jej zovšeobecnení zo šachovnice
8 x 8 na šachovnicu n x n je najzaujímavejšie práve to rozumné a systematické hľadanie. Povedané vedeckejšie, zaujímavé je hľadanie algoritmu, ktorý vedie čo najúčinnejšie k nájdeniu všetkých riešení. Úloha sa často používa ako test účinnosti rôznych algoritmov. Ako špeciálne účinný sa napríklad ukazuje nasledovný algorimus: Na začiatok rozmiestnime dámy tak, aby v každom riadku aj stĺpci bola práve jedna dáma. Potom nájdeme dámu, ktorá ohrozuje najväčší počet iných dám a presunieme ju na jej stĺpci na pole, z ktorého ohrozuje najmenší počet dám. V ďalšom kroku urobíme to isté, a tak pokračujeme až dovtedy, kým nedospejeme k riešeniu. Ukazuje sa, že tento algoritmus je schopný nájsť riešenie pre milión dám na šachovnici milión x milión v priemere na 50 krokov.
Zaujímavé sú aj rôzne variácie tejto úlohy, napríklad problém deviatich dám a jedného pešiaka: umiestnite na šachovnicu 8 x 8 deväť dám a jedného pešiaka tak, aby sa navzájom neohrozovali. .otázka na tento týždeň
Na obrázku je prúžok papiera s vystrihnutým kruhovým otvorom a dvoma nastrihnutými čiarami. Cez vystrihnutý krúžok a nastrihnuté čiary je prevlečený špagátik, na koncoch ktorého sú navlečené dva gombíky. Ako sa dá oddeliť špagátik od papiera bez toho, aby sme gombíky zvliekli alebo čokoľvek roztrhli?
Koľko dám sa dá umiestniť na prázdnu šachovnicu tak, aby sa navzájom neohrozovali? .odpoveď
Osem. To, že ich je najviac osem, je jasné okamžite – nijaké dve dámy nemôžu stáť na tom istom stĺpci (alebo riadku) a keďže stĺpcov (aj riadkov) je osem, môže byť dám maximálne osem. To, že sa ich naozaj dá umiestniť osem, z nijakej jednoduchej úvahy nevyplýva. Treba to jednoducho začať skúšať a ak postupujeme rozumne a systematicky, po určitom čase riešenie nájdeme.
V skutočnosti existuje 92 rôznych riešení tejto úlohy, z ktorých iba 12 sa považuje za naozaj rôznych (tie ostatné totiž vzniknú z tých dvanástich otočením šachovnice alebo urobením zrkadlového obrazu). Jedno z riešení je napríklad: a1, b7, c4, d6, e8, f2, g5, h3.
Na tejto úlohe a na jej zovšeobecnení zo šachovnice
8 x 8 na šachovnicu n x n je najzaujímavejšie práve to rozumné a systematické hľadanie. Povedané vedeckejšie, zaujímavé je hľadanie algoritmu, ktorý vedie čo najúčinnejšie k nájdeniu všetkých riešení. Úloha sa často používa ako test účinnosti rôznych algoritmov. Ako špeciálne účinný sa napríklad ukazuje nasledovný algorimus: Na začiatok rozmiestnime dámy tak, aby v každom riadku aj stĺpci bola práve jedna dáma. Potom nájdeme dámu, ktorá ohrozuje najväčší počet iných dám a presunieme ju na jej stĺpci na pole, z ktorého ohrozuje najmenší počet dám. V ďalšom kroku urobíme to isté, a tak pokračujeme až dovtedy, kým nedospejeme k riešeniu. Ukazuje sa, že tento algoritmus je schopný nájsť riešenie pre milión dám na šachovnici milión x milión v priemere na 50 krokov.
Zaujímavé sú aj rôzne variácie tejto úlohy, napríklad problém deviatich dám a jedného pešiaka: umiestnite na šachovnicu 8 x 8 deväť dám a jedného pešiaka tak, aby sa navzájom neohrozovali. .otázka na tento týždeň
Na obrázku je prúžok papiera s vystrihnutým kruhovým otvorom a dvoma nastrihnutými čiarami. Cez vystrihnutý krúžok a nastrihnuté čiary je prevlečený špagátik, na koncoch ktorého sú navlečené dva gombíky. Ako sa dá oddeliť špagátik od papiera bez toho, aby sme gombíky zvliekli alebo čokoľvek roztrhli?
Ak ste našli chybu, napíšte na web@tyzden.sk.