Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 5.00
Mandy
0 / 0 / 0
Регистрация: 27.12.2007
Сообщений: 4
#1

Перемещение фишек - C++

20.12.2008, 11:54. Просмотров 1388. Ответов 1
Метки нет (Все метки)

помогите мне пожалуйста, очень нужно, осталась одна задача до зачета. если что, есть вебмани.
«Фишки»

Последовательность клеток занумерована числами от 1 до N. В каждой клетке стоит либо черная, либо белая фишка. Группой назовем набор подряд стоящих фишек одного цвета, ограниченный с обеих сторон фишками другого цвета или концами последовательности. Следует переместить фишки так, чтобы они образовали не более двух групп.
Перемещение фишек описывается с помощью плана обмена, в котором используются понятия операция обмена и шаг. Операция обмена меняет местами две соседние группы фишек. Шаг состоит не более чем из K одновременно выполняемых обменов. Обмены можно совершать одновременно только тогда, когда в них участвуют разные группы. После каждого шага группы одного цвета, оказавшиеся рядом, объединяются. План обменов содержит описания шагов, выполняемых последовательно.



Напишите программу, определяющую план обменов, с помощью которого за наименьшее число шагов получается последовательность, состоящая не более чем из двух групп.
Формат входных данных
В первой строке входного файла записаны числа N и K (1 <= N <= 100000 и 1 <= K <= 10000). Исходная расстановка фишек задается в последующих строках, содержащих N чисел (0 или 1), разделенных пробелами или переводами строк. При этом 0 соответствует черной фишке, 1 - белой.
Формат выходных данных
Выходной файл должен содержать описание шагов плана, по одному шагу на строке. Описание шага начинается с числа L - количества обменов на этом шаге. Затем для каждого обмена указывается минимальный номер клетки, в которой стоит фишка, участвующая в этом обмене. Последняя строка плана должна содержать одно число 0.
Примеры
fishes.in
9 3
1 0 0 1 1 0 1 1 0
fishes.out
2 1 6
1 1
0
fishes.in
3 1
1 1 0
fishes.out
0
Примечание
Требуется найти план, содержащий наименьшее число шагов, при этом общее число обменов может быть не минимальным.




Решение:

Заметим, что количество фишек в одной группе не имеет никакого значения, т.к. за один обмен мы из 3 или 4 групп получаем 2. Получается, что нам нужно хранить количество фишек в группе только для того, чтобы правильно выводить позицию, с которой начинается группа, участвующая в обмене.
Необходимо завести массив A от одного до N (т.к. все группы могут состоять из одного символа) и хранить в нем позицию, с которой начинаются символы i-ой группы. Это сделать несложно - читаем последовательно символы последовательности и если символ не равен предыдущему, то сохраняем в A[i] позиция, на которой находиться данный символ (отсюда начинается новая группа) и увеличиваем i. Общее количество групп обозначим за M.
Теперь необходимо разработать алгоритм перестановки групп, чтобы добиться желаемого эффекта за наименьшее количество шагов. Будем выполнять действия до тех пор, пока количество групп не станет равным 2. Наша последовательность представляет собой последовательность групп вида 010101. Разобьем нашу последовательность на тройки и в каждой тройке произведем обмен первого элемента со вторым и в итоге, для данного примера, получим последовательность 101, а на следующем шаге 01.
Определим количество операций обмена, которые мы совершим на данном шаге: оно равно минимуму из K и количеством троек, на которые можно разбить нашу последовательность. Обозначим его за C. Теперь мы будем совершать операции обмена, меняя в каждой тройке первый и второй элементы. Эти обмены необходимо совершать только в последних C тройках нашей последовательности, оставляя первые Z = M - C * 3 элементов неизменными.
Займемся обменами элементов в последних C тройках. Пусть j - элемент, с которого начинается изменение последовательности, j = M - C * 3 + 1. Теперь, перебирая все i от C до 1, выводим все A[q], где q = M - i * 3 + 1 (начало первой группы в тройке), вывод такого число обозначает, что мы поменяли группу q с группой q + 1, это значит, что объединились группы q - 1 и q + 1, а также группы q и q + 2. Необходимо внести соответствующее изменение в массив: A[j] := (A[q + 2] - A[q + 1]) + A[q], где (A[q + 2] - A[q + 1]) - длина последовательности q + 1, которая теперь встала перед q. После этого необходимо увеличить j на 1. Отдельно рассматривается случай, когда q = 1: здесь вместо четырех участвуют три группы и поэтому менять следует не первую группу со второй, а вторую с третьей, т.е. предварительно увеличить j на 1.
Такой, казалось бы, сложный и запутанный способ решения задачи избавляет нас от использования списков или многократного присваивания массивов. Надеюсь, при внимательном прочтении и рисовании возможных вариантов и последовательности действий на бумаге все станет понятно.

0
Миниатюры
Перемещение фишек  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2008, 11:54
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Перемещение фишек (C++):

Перемещение фигуры - C++
Реализовать отображение на экране геометрической фигуры с возможностью перемещать ее с помощью клавиш(стрелки) и изменение цвета фигуры...

Перемещение формы С++ - C++
Помогите пожалуйста создал форму FormBorderStyle с параметром None так как хочу сделать свой дизайн формы но перемещать мышкой не могу я...

Гексагональная сетка, перемещение фишек. - C++ Builder
Есть гексагональная сетка на паинтбоксе, на ней фишки (по сути это картинки и булевы переменные, привязанные к массиву). Если зажать...

Перемещение ярлыка - C++ Builder
В папку проекта кинул файл- ярлычок. Вопрос каким кодом программно его поместить на рабочий стол?

перемещение компонентов - C++ Builder
Здравствуйте. Ни как не могу догадаться, как заставить загруженный рисунок перемещаться по горизонтали (или по вертикали) нажимая на кнопки...

Перемещение шашки - C++ Builder
Не получается прописать функцию перемещения шашки,пишу в FormMouseMove, но может надо создавать отдельную функцию? и еще нужна функция для...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ECDWILY
Сообщений: n/a
12.03.2011, 12:15 #2
А код на С++ слабо скинуть?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2011, 12:15
Привет! Вот еще темы с ответами:

Перемещение Image - C++ Builder
Нужно,чтобы шашки перемещались. Файл cpp //--------------------------------------------------------------------------- #include...

Перемещение контрола - C++ Builder
Как перемещать контрол (TPaintBox) по форме при помощи мышки, чтобы перемещение было плавным, и контрол не дёргался (сейчас перемещаю...

перемещение кнопки - C++ Builder
есть кнопка, при нажатии на нее она должна плавно пеместится в другое место (имеется ввиду за некоторое время). Вроде бы легко сделать...

Рандомное перемещение фишек по квадратной матрице (клеточный автомат) - C++
В квадратной таблице размера NxN в левом верх-нем и правом нижнем углу стоят фишки. За одну секунду каждая фишка случайным образом...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru