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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Подпрограммы сложения и умножения целых чисел, представленных в системах счисления с любым основанием от 2 до 10 http://www.cyberforum.ru/cpp/thread18874.html
1. Определить подпрограммы сложения и умножения целых чисел, представленных в системах счисления с любым основанием от 2 до 10. результаты проверять на десятичных числах. 2. Напишите программу создания n-символьной последовательности состоящей из совокупности 3 символов.... например 1,2,3 или a,b,c... в которой нет двух смежных идентичных последовательностей . для n=11 последовательность имеет...
C++ Русификатор С++ Слышал есть русификатор на С++, хотелось бы к 6 версии, но если нет то можно к любой. http://www.cyberforum.ru/cpp/thread18821.html
Объединение, пересечение, разность множеств C++
Это вполне стандартный алгоритм,может есть у кого готовый? Объединение, пересечение, разность множеств. Поверка на включение одного множества в другое.
С++ для чайников C++
Люди помогите скачал книгу "С++ для чайников" там написано как создавать проги а на чем,не написано...Помогите...на каком текстовом редакторе лучше прогроммировать!!!
C++ Найти в заданном тексте, состоящем из n строк, все слова палиндромы и числа палиндромы http://www.cyberforum.ru/cpp/thread18332.html
Сроки жутко горят :( поэтому надеюсь на вашу помощь: Задача: Найти в заданном тексте, состоящем из n строк, все слова палиндромы и числа палиндромы.(в словах допускается перенос на другую строку) Палиндром-слово которое можно читать как слева направо так и наоборот : ШАЛАШ,ПОП или например фраза А РОЗА УПАЛА НА ЛАПУ АЗОРА. Или числа 1441, 121 и т.д. Очень прошу помощи!!!:help:
C++ Создание электронных часов в графическом режиме Borland C++ Как создать электронные часы в графическом режиме Borland C++ ? подробнее

Показать сообщение отдельно
Mandy
0 / 0 / 0
Регистрация: 27.12.2007
Сообщений: 4

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

20.12.2008, 11:54. Просмотров 1374. Ответов 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.
Такой, казалось бы, сложный и запутанный способ решения задачи избавляет нас от использования списков или многократного присваивания массивов. Надеюсь, при внимательном прочтении и рисовании возможных вариантов и последовательности действий на бумаге все станет понятно.

Миниатюры
Перемещение фишек  
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru