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

Списки - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Заполение структур http://www.cyberforum.ru/cpp-beginners/thread844723.html
Есть программа #include <iostream> #include <stdio.h> #include <string.h> #include <limits.h> #define CLR while (getchar()!='\n') #define Kmax 10 #define Lmax 81
C++ Ввод чисел через пробел Доброго времени суток! Подскажите как правильно сделать. Есть односвязный список. Нужно вводить числа через пробел, а по нажатию на Enter программа должна выводить этот список. Какое условие должно... http://www.cyberforum.ru/cpp-beginners/thread844719.html
Написать логическую функцию, которая возвращает true, если сумма чисел - положительное число C++
Неплохие задачи по С++! Подзабыл его( выручайте, буду очень благодарен 3. Даны два целых числа. Написать логическую функцию, которая возвращает true, если сумма чисел - положительное число, и...
C++ Электронные весы
Неплохие задачи по С++! Подзабыл его( выручайте, буду очень благодарен 4. Ваша задача - грамотно запрограммировать электронные весы. Пользователь вводит вес, максимум 1000 грамм. Необходимо...
C++ Описать класс, обеспечивающий представление матрицы http://www.cyberforum.ru/cpp-beginners/thread844698.html
Ребята, убедительная просьба, нужно срочно сделать лабораторную работу, задание для которой звучит следующим образом: Описать класс, обеспечивающий представление матрицы произвольного размера с...
C++ Напишите функцию Otrezok (x1, y1, x2, y2), которая находит длину отрезка AB по заданным координатам Неплохие задачи по С++! Подзабыл его( выручайте, буду очень благодарен 1. Даны координаты двух точек A(x1, x2) и B(x2, y2) вещественного типа. Напишите функцию Otrezok (x1, y1, x2, y2), которая... подробнее

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

Списки - C++

21.04.2013, 23:14. Просмотров 548. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru