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

Списки - 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 программа должна выводить этот список. Какое условие должно быть в цикле while в main'е, чтобы при переходе на новую строку совершался выход из цикла? #include "stdafx.h" #include <iostream> using namespace std; http://www.cyberforum.ru/cpp-beginners/thread844719.html
Написать логическую функцию, которая возвращает true, если сумма чисел - положительное число C++
Неплохие задачи по С++! Подзабыл его( выручайте, буду очень благодарен 3. Даны два целых числа. Написать логическую функцию, которая возвращает true, если сумма чисел - положительное число, и false в обратном случае. (2 балла)
C++ Электронные весы
Неплохие задачи по С++! Подзабыл его( выручайте, буду очень благодарен 4. Ваша задача - грамотно запрограммировать электронные весы. Пользователь вводит вес, максимум 1000 грамм. Необходимо написать функцию, которая правильно отображает введенный вес на дисплее. Например, "121 грамм", "2 грамма", "517 граммов". Используйте остаток от деления на 10. При остатках 0, 1 выводите слово "грамм",...
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), которая находит длину отрезка AB по заданным координатам. Формула нахождения длины отрезка: AB = sqrt((x1-x2)^2+(y1-y2)^2) 2. Используя данную функцию, найти длины отрезков KL и KM, задавая координаты точек K,... подробнее

Показать сообщение отдельно
Tata20
0 / 0 / 0
Регистрация: 06.12.2012
Сообщений: 17
21.04.2013, 23:14     Списки
Здравствуйте, помогите, пожалуйста, реализовать программу.
Вот такая задача.
По кругу расположено 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, но вот как дальше заполнить в произвольном порядке?
И еще не совсем понятны пункты а) и б).
Или может сделать все возможные перестановки и проверять каждую?
Подскажите, пожалуйста.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 03:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru