Разрезание шахматной доски
Помогите, пожалуста, с задачей(нужен алгоритм, или хотя бы идея):
Цитата:
[SIZE=2]Разрезание шахматной доски.
Написать программу нахождения всех способов разрезания шахматной доски с числом клеток nxn (n-четное) на две одинаковые по форме части (не считая вращений и отражений).[/SIZE]
Написать программу нахождения всех способов разрезания шахматной доски с числом клеток nxn (n-четное) на две одинаковые по форме части (не считая вращений и отражений).[/SIZE]
Как я понимаю, доска должна быть разрезана на 2 равные части так, чтоб они накладывались друг на друга.
Помогите, пожалуста.
Перед тем как создаавать тему надо прочитать Правила и Дополнения.
Цитата:
Разрезание шахматной доски.
Написать программу нахождения всех способов разрезания шахматной доски ...
Написать программу нахождения всех способов разрезания шахматной доски ...
На каком языке написать ? На любом пойдет ? [COLOR="Red"]За небрежное оформление темы - предупреждение.[/COLOR]модератор.
Цитата: Kostyan777
Помогите, пожалуста, с задачей:
Как я понимаю, доска должна быть разрезана на 2 равные части так, чтоб они накладывались друг на друга.
Помогите, пожалуста.
Как я понимаю, доска должна быть разрезана на 2 равные части так, чтоб они накладывались друг на друга.
Помогите, пожалуста.
Отрезанная часть обязательно должна быть связной?
Цитата:
Отрезанная часть обязательно должна быть связной?
Да, должны быть 2 неразрывные части.
Решение задачи для n=4:
Цитата:
1100
1100
1100
1100
1000
1100
1100
1110
0000
1100
1100
1111
0000
0100
1101
1111
0000
0101
0101
1111
0001
0101
0101
0111
Подскажите как решать? Если только перебором, то как перебирать?
Уже неделю голову ломаю((
Какое ограничение на размер ? Если 8 то доска идентифицыруется 64-разрядным числом.
Тогда можно пробовать брать для начала розрез пополам и рекурсивно пробовать менять по 1 клетке. При изменении клетки проверять связность куска, пробовать отражать (тут нужно правило которое определяет который из вариантов отражения принимать за основной) и если все гуд и вариант нас устраивает и еще не встречался идти дальше по рекурсии.
Найденные варианты надо хранить в масиве, который будем сортировать и проверять по нем результат бинарным поиском.
Хотя чтото мне самому ета идея не нравится.
Тогда можно пробовать брать для начала розрез пополам и рекурсивно пробовать менять по 1 клетке. При изменении клетки проверять связность куска, пробовать отражать (тут нужно правило которое определяет который из вариантов отражения принимать за основной) и если все гуд и вариант нас устраивает и еще не встречался идти дальше по рекурсии.
Найденные варианты надо хранить в масиве, который будем сортировать и проверять по нем результат бинарным поиском.
Хотя чтото мне самому ета идея не нравится.
надо попробовать...
тут еще вопрос возникает: сколько таких матриц хранить придется?
тут еще вопрос возникает: сколько таких матриц хранить придется?
ИМХО, делать надо примерно так: Каждый разрез должен проходить сквозь ценир доски. Оттуда и будем плясать. Первый - вертикально вверх или вправо(если хочешь учесть и с поворотом), и центрально симметрично ему. Дальше - влево, прямо или вправо(от предыдущего направления). Перебираешь все комбинации при помощи возвратного алгоритма, не забывая следить за самопересечениями.
Цитата: wanja
ИМХО, делать надо примерно так: Каждый разрез должен проходить сквозь ценир доски......
Респект. Признаю свою идею плохой.
Цитата: wanja
Перебираешь все комбинации при помощи возвратного алгоритма, не забывая следить за самопересечениями.
Возвратный алгоритм - это какой? По-видимому тут должна быть рекурсия (потому что лаба на тему "Рекурсия").
Перебирать половину доски или четверть несложно.
Но главный вопрос: как перебрать все варианты, не повторяясь, чтобы в конце концов получить спираль?
С рекурсией. Двигаемся вперед по массиву, заполняем его минимальными(влево, прямо, вправо) подходящими элементами, пока не дойдем до края, или не зайдем в тупик. Дойдя до края, выдаем решение, и меняем последний элемент на следующий по порядку(влево - на прямо, прямо - на вправо), и пытаемся идти дальше. Если не получается - сдвигаемся по массиву влево.
что-то я не понимаю...
Объясни, пожалуста, на примере, если не трудно.
Объясни, пожалуста, на примере, если не трудно.