C, PHP, VB, .NET

* Засичащи се фигури

Публикувано на 19 февруари 2009 в раздел Математика.

16 коментара

1. Су До Ку

2. Е, не е точно судоку, но прилича :)

3. 3
   A B C D
   C D A B
   D C B A
   B A D C

4. Много старомодни задачи: 8 царици!!! Дрън-дрън!
   Че и да се бият. Я сложи по-добре 8 манекенки с прашки на подиума по-добре.

5. 3 1 2 4
   2 4 3 1
   4 2 1 3
   1 3 4 2
   сигурно не е единствено решение

6. втора задача е некоректна - например за n=2 или n=3 няма решение

7. По втората точка ми е интересно само какво разбираш под "n" на брой итерации. Защото повечето алгоритми, които решават тази задача са с рекурсия. Там итерации дефакто няма, освен ако всяко връщане назад в рекурсията не се смята за итерация. Хайде давай решението :)

8. Мертол - Не е некоректна. Това, което си открил е част от решението.

   Светльо Антонов - Връщането от рекурсията определено си е итерация в рекурсивния алгоритъм. Въпросът е да напишете алгоритъм със сложност "n" (решението, което всеки може да измисли веднага е със сложност n^2).

   Hint: Започнете от малки дъски и постепенно ги увеличавайте. Намерете някаква зависимост между позициите, на които поставяте цариците и числото n... Аз лично когато писах такава програма си рисувах на ръка :)

9. айде давай решението със сложност n

10. 1. При n=1 е ясно, че има само една царица и има решение.

    2. При n=2 очевидно няма решение.

    3. При n=3 също няма решение

    4. При n=4 има (даже не единствено). Аз ще взема само едното от тях:

     x x o x
     o x x x
     x x x o
     x o x x

    Виждате, че по колони поставих царица на 2ра и 4та позиция и на 1ва и 3та позиция. Нека продължим напред...

    5. При n=5 решението е следното:

     x x o x x
     o x x x x
     x x x o x
     x o x x x 
     x x x x o

    По колони сложих на 2ра, 4та, 1ва, 3та и 5та позиции. Изключително много прилича на предишното решение, не е ли така?

    6. При n=6 правя следното:

     x x x o x x 
     o x x x x x 
     x x x x o x 
     x o x x x x 
     x x x x x o 
     x x o x x x 

    Отново е много близко решение - 2ра, 4та, 6та, 1ва, 3та и 5та позиции. Ще проверя още веднъж и ще се опитам да направя заключение по индукция.

    7. При n=7:

     x x x o x x x
     o x x x x x x
     x x x x o x x
     x o x x x x x
     x x x x x o x
     x x o x x x x
     x x x x x x o

    Изключителна прилика - 2ра, 4та, 6та, 1ва, 3та, 5та и 7ма...

    Така смело бих обобщил алгоритъм - като се местите по редове, слагайте по една царица през две позиции надолу (2ра, 4та, 6та, 8ма,...) докато не стигнете края на дъската. След това се върнете в началото и започвайки от 1ва позиция слагайте отново през две надолу (1ва, 3та, 5та, 7ма, 9та, ...) и така до достигане на последната колона.

    Трудността на алгоритъма е точно "n", защото се извършват точно "n" на брой поставяния на царица. Тук обаче по стар спомен мисля, че може би имаше и частен случай. Пробвайте го на компютър и намерете дали няма изключителна ситуация при определени числа "n". Не съм убеден - просто проверете и споделете...

11. Ами алгоритъмът ти се дъни още на първия случай който не си разгледал. При n = 8
    0 0 0 0 x 0 0 0
    x 0 0 0 0 0 0 0
    0 0 0 0 0 x 0 0
    0 x 0 0 0 0 0 0
    0 0 0 0 0 0 x 0
    0 0 x 0 0 0 0 0
    0 0 0 0 0 0 0 x
    0 0 0 x 0 0 0 0

    По второстепенния диагонал две царици се засичат.
    Не се заяждам, но без доказателство че си намерил решение, само по интуиция, не може да се смята че е верен алгоритъм. Аз например се опитвах точно с този метод да го решавам още от първия път, но за класическата шахматна дъска с 8х8, и веднага знам че по този начин не става. Подобна задача е например "Да се обходи стандартна шахматна дъска с ход на коня без да се повтаря два пъти нито едно поле".
    Относно рекурсията, в уикипедия има много обстойна статия как се решава тази задача, и какви оптимизации могат да се правят. Но според мен, така както го дефинираш, рекурсията не е решение от n-ти ред. Там разглеждат случая за n царици. Но алгоритъм с толкова ниска стойност като че ли никой досега не е намерил :)

12. Светослав Антонов - не случайно казах, че има частен случай - получава се при n = k.8, k=1,2,3... При него има друго - сходно алтернативно решение...

13. venelin - ще отговоря със задача - аз съм точно на два пъти повече години, отколкото си ти :)

14. po na kolko godini ste shtoto as sam na 13 i ot vas mai razbrah nqkolko dumi kakvo uzna4avat blagodarq vi vse pak

15. Задачата за н-те царици няма обща формула на броя на решенията, но пък може да се атакува с много разнообрани подходи - backtracking, constraint programming, рекурсии и т.н. Аз я използвах за тренирова, когато се учех на базовите елементи на програмирането

16. Лъчезар П. Томов - Пак казвам - тук не се търси изчерпване на решенията, а просто едно решение. Вече съм го описал по-горе.