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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Tata20
0 / 0 / 0
Регистрация: 06.12.2012
Сообщений: 17
#1

Списки - C++

21.04.2013, 23:14. Просмотров 523. Ответов 0
Метки нет (Все метки)

Здравствуйте, помогите, пожалуйста, реализовать программу.
Вот такая задача.
По кругу расположено 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, но вот как дальше заполнить в произвольном порядке?
И еще не совсем понятны пункты а) и б).
Или может сделать все возможные перестановки и проверять каждую?
Подскажите, пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2013, 23:14
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Списки (C++):

Списки, как склеить списки между собой? - C++
Ребят, привет всем, есть код, в классе которого описаны несколько методов: добавление элемента в список, удаление и просмотр списка, дак...

Списки - C++
Всем привет!) У меня есть вопрос..как создать два списка? Просто мне нужно из списка В переместить содержимое в список А. Как это сделать и...

C++ списки - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;list&gt; using namespace std; int main(void) { list&lt; int &gt; l,...

списки - C++
написать функцию, удаляющую первый отрицательный элемент списка.

Списки в С++ - C++
#include&lt;iostream.h&gt; #include &quot;time_1.h&quot; #include&lt;time.h&gt; #include&lt;windows.h&gt; char* Rus (const char* text); class List { ...

Списки в C++ - C++
Нужно написать программу которая создает список и упорядочивает его элементы по возрастанию.

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.04.2013, 23:14
Привет! Вот еще темы с ответами:

Списки - C++
Здравствуйте! Помогите пожалуйста с программой.... Надо вывести список поездов , а потом вывести поезда которые отправляются в...

Списки С++ - C++
Помогите,пожалуйста......в списке продублировать все отрицательные элементы(одна функция) и удалить из списка все чётные элементы(другая...

Списки - C++
Помогите пожалуйста с задачей: В списке L найти такой элемент &quot;y&quot; (если существует), что &quot;y&quot; больше всех предыдущих и меньше всех...

Списки - C++
Работа со списками( объединение, удаление, вставка и.т.п). при запуске выдает ошибки. :-| устала уже с ней( С++, Builder 6 ...


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

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

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