Санкт-Петербург

Россия

Написать программу, решающую любую из 3х задач:
1. Имеетсяклеточное поле размера M x N , в некоторых позициях ко- торого расставлены
черные фигуры, M – количество столбцов, а N – ко- личество строк. Расставить
минимальное число белых коней, чтобы про- бивались все свободные позиции.
Рекомендация: минимальное вершинное покрытие графа, вершинами которого будут
все свободные клетки, и будет существовать ребро (x,y), если при постановке
коня в клетку x будет пробиваться клетка y.
2. Имеется клеточное поле размера M x N , в некоторыхпозициях ко- торого расставлено K черных фигур. Необходимо расставить
максималь- ное число белых коней, чтобы они не били друг друга. Рекомендация:
двудольный граф, соответствующий нашей доске: вершины – клетки не занятые
черными фигурами, ребро между верши- ной А и В устанавливается в том случае,
если конь за один ход может по- пасть из вершины А в вершину B.
3. Имеетсяклеточное поле размера N x M , в некоторых позициях ко- торого расставлены
черные фигуры. Необходимо расставить на клеточ- ном поле всеми возможными
способами фишки таким образом, чтобы в каждой линии (горизонтальной,
вертикальной, диагональной) располага- лось четное число фишек. Рекомендация:
строим дерево перебора. Его вершиной будет комби- нация значений свободных переменных
из множества {0,1}. Корнем бу- дет комбинация всех свободных переменных,
приравненных нулю. На каждом шаге приравниваем текущую переменную нулю (левая
ветка) или единице (правая ветка). Всего вершин в дереве будет 2K . Высота де
рева составит k.
 
 

Написать программу, решающую любую из 3х задач:
1. Имеетсяклеточное поле размера M x N , в некоторых позициях ко- торого расставлены
черные фигуры, M – количество столбцов, а N – ко- личество строк. Расставить
минимальное число белых коней, чтобы про- бивались все свободные позиции.
Рекомендация: минимальное вершинное покрытие графа, вершинами которого будут
все свободные клетки, и будет существовать ребро (x,y), если при постановке
коня в клетку x будет пробиваться клетка y.
2. Имеется клеточное поле размера M x N , в некоторыхпозициях ко- торого расставлено K черных фигур. Необходимо расставить
максималь- ное число белых коней, чтобы они не били друг друга. Рекомендация:
двудольный граф, соответствующий нашей доске: вершины – клетки не занятые
черными фигурами, ребро между верши- ной А и В устанавливается в том случае,
если конь за один ход может по- пасть из вершины А в вершину B.
3. Имеетсяклеточное поле размера N x M , в некоторых позициях ко- торого расставлены
черные фигуры. Необходимо расставить на клеточ- ном поле всеми возможными
способами фишки таким образом, чтобы в каждой линии (горизонтальной,
вертикальной, диагональной) располага- лось четное число фишек. Рекомендация:
строим дерево перебора. Его вершиной будет комби- нация значений свободных переменных
из множества {0,1}. Корнем бу- дет комбинация всех свободных переменных,
приравненных нулю. На каждом шаге приравниваем текущую переменную нулю (левая
ветка) или единице (правая ветка). Всего вершин в дереве будет 2K . Высота де
рева составит k.

Алексей arnautov

Написать программу на С++ (задание 2 курса) !обязательно с++!