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

Списки - C++

Восстановить пароль Регистрация
 
Tata20
0 / 0 / 0
Регистрация: 06.12.2012
Сообщений: 17
21.04.2013, 23:14     Списки #1
Здравствуйте, помогите, пожалуйста, реализовать программу.
Вот такая задача.
По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по ходу часовой стрелки, переворачивает каждую S -тую монету. В первый раз счет начинается с герба. В каком порядке надо расставить монеты, чтобы после K ходов стало L монет, лежащих гербами вверх.
Нашла вот такое решение.
Монеты лежат на N+M позициях. Пронумеруем эти позиции по порядку по контуру от 1 до N+M.

Заведем массив A из N+M ячеек. Первоначально все ячейки нулевые. Начиная счет от первой ячейки, будем делать ход - отсчитывать S ячеек (считаем, что за N+M-ым элементом следует непосредственно 1-ый элемент массива) и заменять в этой ячейке число i на число 1-i (т.е. 0 на 1, а 1 на 0). После k-того хода остановимся.

Рассмотрим возникшую ситуацию. После каждого хода переворачивается одна монета, при этом разность количества монет, лежащих гербами вверх и количества монет, лежащих гербами вниз либо увеличивается, либо уменьшается на 2. Например, если переворачивается монета, лежащая гербом вверх, то при этом увеличивается на 1 количество монет гербом вниз и уменьшается на 1 количество монет гербом вверх.

Предположим, что после k ходов в массиве A стало p единиц т.е. p монет, по сравнению с начальным положением, будут перевернуты после k-ого хода.

В случае, если L>=N, то (L-N) монет, которые лежали гербами вниз, должны после k-ого хода быть перевернуты гербами вверх. (Если p<(L-N), то это, очевидно, невозможно сделать). Среди оставшихся p-(L-N) перевернутых монет должна быть половина гербами вверх и половина - вниз, чтобы при перевороте суммарное число монет гербами вверх и вниз не изменилось. Следовательно, число p-(L-N) должно быть четным, иначе условию задачи удовлетворить нельзя. Пусть p-(L-N) = 2v. Должно быть, очевидно, v<=N, v+(L-N)<=M.

Итак, в случае L>=N, если не выполняется хотя бы одно из неравенств

p-(L-N)=2v>=0,

v<=N,

v+(L-N)<=M,

то преобразование начальной конфигурации в конечнуюневозможно.

Иначе на (L-N) мест, помеченных в массиве A единицами, выставляем монеты гербами вниз. На оставшиеся 2v=p-(L-N) помеченных единицами позиций кладем v монет гербами вниз и v гербами вверх в произвольном порядке. На остальные позиции кладем оставшиеся монеты опять же в произвольном порядке, чтобы в общей сложности было N монет гербами вверх и M - гербами вниз.

Но мы еще не учли тот факт, что счет начинается с первой монеты гербом вверх:

а) Если в массиве A первый элемент нулевой, то в случае, если среди (N+M)-p монет есть хоть одна гербом вверх (что эквивалентно выполнению условия N-v>0), то ее и кладем в первую позицию. Если все (N+M)-p монеты - гербом вниз (т.е. N-v=0), то размещение монет невозможно.

б) Если же A[1]=1, то среди p монет должна быть по крайней мере одна, которую необходимо положить гербом вверх, иначе, опять же, размещение невозможно.

Случай N-L>0 разбирается аналогично.
Но не получается до конца запрограммировать.
Я создаю кольцевой односвязный список, делаю К шагов, проверяю условие L>=N, но вот как дальше заполнить в произвольном порядке?
И еще не совсем понятны пункты а) и б).
Или может сделать все возможные перестановки и проверять каждую?
Подскажите, пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2013, 23:14     Списки
Посмотрите здесь:

C++ C++ списки
C++ Списки в С++
C++ списки
Списки C++
C++ списки
С++ списки C++
C++ Списки
Списки в c++ C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 11:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru