Извините за наглость, но

← →
ProgRAMmer Dimonych © (2007-02-22 01:00) [0]

объясните, пожалуйста, русским языком задачу про монеты. Сижу, читаю одну книжечку - ужас: кроме 5 данных в условии переменных добавлено ещё 3, из этих 8 переменных говорящего имени нет ни у одной, последовательность изложения - я лучше просто промолчу.

Кто не понял, о чём идёт речь: По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по ходу часовой стрелки, переворачиваем каждую S-ю монету. В первый раз счёт начинается с герба. В каком порядке надо расставить монеты, чтобы после K ходов стало L монет, лежащих гербами вверх.

Заранее спс.

← →
Petr V. Abramov © (2007-02-22 01:22) [1]

:)))
ты алгоритм словами изложи, хоть криывми, тогда и имена переменных подскажем

← →
Германн © (2007-02-22 01:35) [2]

> Petr V. Abramov © (22.02.07 01:22) [1]
>
> :)))
> ты алгоритм словами изложи, хоть криывми, тогда и имена
> переменных подскажем

Дык имена ему подсказывать и не нужно :) Он просит чтобы кто-нибудь ему "алгоритм словами изложил" :)

← →
Real © (2007-02-22 01:37) [3]

а в чем прикол? берем любые данные да и все. Это что задача или конкурс телепатов? Например, можно взять значение переменной N=<любое целое>, L=N, а все остальные = 0... или первое берем за 0, M=<любое целое>, S=1, K=M, L=M... Мало ли решений, если все учавствующие значения - неопределенны? Например, тебя смутит вот такое уравнение:

x1+x2+x3+x4=y1+y2+y3+y4

Это по сути тоже самое, что привел и ты, и тоже 8 неизвестных. О чем речь - мне лично вообще неясно

← →
Petr V. Abramov © (2007-02-22 01:40) [4]

похоже на какую-то переборную задау, причем безнадежную :)
могу ошибаться...

← →
ProgRAMmer Dimonych © (2007-02-22 09:12) [5]

В том-то и прикол, что не переборная. Она в принципе не очень сложная, но вот в той книжке её ну оч-ч-чень криво объясняют.

> Real © (22.02.07 01:37) [3]
> а в чем прикол? берем любые данные да и все. Это что задача
> или конкурс телепатов? Например, можно взять значение переменной
> N=<любое целое>, L=N, а все остальные = 0... или первое
> берем за 0, M=<любое целое>, S=1, K=M, L=M... Мало ли решений,
> если все учавствующие значения - неопределенны? Например,
> тебя смутит вот такое уравнение:
>
> x1+x2+x3+x4=y1+y2+y3+y4
>
> Это по сути тоже самое, что привел и ты, и тоже 8 неизвестных.
> О чем речь - мне лично вообще неясно

Не любые данные. Значения переменных вводятся пользователем с клавиатуры.

← →
TUser © (2007-02-22 09:44) [6]

Положи L монет гербами вверх и сделай K ходов назад.

← →
ProgRAMmer Dimonych © (2007-02-22 09:54) [7]

> TUser © (22.02.07 09:44) [6]
> Положи L монет гербами вверх и сделай K ходов назад.
Можно было бы, но начинать нужно с герба, а ещё не факт, что после такого движения назад мы получим монету с номером Nomer1-S+1 вверх гербом, т.е. не факт, что начав с герьа попадём в последовательность, от которой начали скакать.

← →
default © (2007-02-22 09:56) [8]

что-то я слабо понимаю
если нужно добрать гербы, то нужно через расстояние S решки разложить
если добрать решки, то гербы...

← →
default © (2007-02-22 09:58) [9]

хотя нет там же K задано:)

← →
default © (2007-02-22 10:01) [10]

кстати S должно быть взаимно простое с (N+M) чтобы все монеты участвовали в переворачивании иначе хрен

← →
default © (2007-02-22 10:10) [11]

а где гарантия что в твоей книжечке она не просто перебором решается?
тебе не дано сюда скриншот из книги кинуть с объяснением и с кодом?

← →
alien1769 © (2007-02-22 10:17) [12]

Есть такая детская игра -СЧИТАЛКА, она тебе поможет.

← →
default © (2007-02-22 10:37) [13]

вот есть монеты ГГГГРРР, S=M+N=7 и нужно получить 7 гербов
какое бы ты K ни выбрал никогда не получить 7 гербов

← →
default © (2007-02-22 10:38) [14]

и какое бы расположение монет также, так что уточняй условие

← →
ProgRAMmer Dimonych © (2007-02-22 10:39) [15]

> default © (22.02.07 10:10) [11]
> а где гарантия что в твоей книжечке она не просто перебором
> решается?
Гарантия уже в том, что я не первый и не пятый год программированием занимаюсь и перебор от красивого решения отличить умею.

Цитата из книги:

Монеты лежат на N+M позициях. Пронумеруем эти позиции по порядку по контуру от 1 до N+M.

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

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

До этого места, короче говоря идёт объяснение и обсасывание того, что умеет делать даже программер-первогодка. А вот дальше...

← →
ProgRAMmer Dimonych © (2007-02-22 10:45) [16]

Предположим, что после 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.

Это уже с напрягом. Дальше - веселее...

← →
ProgRAMmer Dimonych © (2007-02-22 10:52) [17]

Итак, в случае 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 разбирается аналогично.

← →
ProgRAMmer Dimonych © (2007-02-22 10:57) [18]

Вообще говоря, задачу-то решать я же начал, но это скорее не решение, а разбор текста на отдельные слова, извлечение из них по чайной ложке в час хоть какой-то смысловой нагрузки.

Короче говоря, получается автоматический разбор текста. Вот до чего техника дошла... :(

← →
default © (2007-02-22 11:14) [19]

ProgRAMmer Dimonych © (22.02.07 10:57) [18]
если не уходить в детали, то верно всё

← →
default © (2007-02-22 11:16) [20]

Димоныч это не чистое программирование ниразу, это логика в большей степени
программирование тут простое, что ты прямо так стремишься к программированию этой задачи-то?
пойми просто решение и всё, ни вижу интереса её программировать

← →
default © (2007-02-22 11:20) [21]

что тебе непонятно?

> default © (22.02.07 11:20) [21]
> что тебе непонятно?
Даже не могу толком понять, что именно. Так вроде бы усилием мысли заставил себя вникнуть в общих чертах. Написал жуткую программу: if на if"е сидит и if"ом погоняет - только не пашет и всё тут.

Рисую первоначальную картину: первая монета вверх, остальные три - вниз. S=2, делаю два хода, получаю три вверх, одну вниз. Задаю получившейся программе числа N=1, M=3, S=2, K=2, L=3. Пишет, что решений нет (т.е. в соответствии с условиями, черпанутыми из вышеприведённого текста). Самое интересное, что, кажется, ответ всегда такой. Чего к чему?

Хм, добился того, чтобы он писал, что все должны быть вниз. Но тогда за два хода будет только 2 монеты вверх, а не 3, как нужно.

ProgRAMmer Dimonych © (22.02.07 11:26) [22]
ну не знаю, решение верное приведено может ты чего напутал
проверь неравенства все внимательно может описки какие в тексте
так по логике всё верно

Ладно, буду пробовать. Вон прога мне уже предлагает 1 и 3 монеты вверх положить. Всё равно неправильно, но... может чаво-нибудь придумаем.

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

тут ошибка была как я понимаю

> default © (22.02.07 11:51) [26]
> б) Если же A[1]=1, то среди p монет должна быть по крайней
> мере одна, которую необходимо положить гербом ВНИЗ, иначе,
> опять же, рахзмещение невозможно.
>
> тут ошибка была как я понимаю
У меня или у "аффтара" книги? У меня местах в 5 - 10 очепятки и ашипки. А это условие вроде как вообще проверять необязательно: оно наоборот мешает нормальной работе. Вроде получилось написать, на моих тестах работает. Без этой дополнительной проверки.

ProgRAMmer Dimonych © (22.02.07 12:49) [27]
можно выделять две группы позиций монет: те, что с единицами(монеты в этих позициях сменят сторону после K ходов) и те, что с нулями(монеты сторону не меняют в этих позициях)
внутри каждой из групп позиций монеты можно переставлять как угодно без изменения суммарного количества гербов после K ходов
на первой позиции по условию должен быть герб
если первая позиция имеет 1, то эту монету можно переставить с любой монетой которая стоит в позиции имеющей единицу
если первая не герб, нужна монета в позиции с единицей и притом гербом вверх(то есть монета которая после K ходов станет решкой) и вот если такая монета есть нужно обменять местами её с первой монетой и тогда на первом месте будет герб как и требуется по условию задачи
это необходимо учитывать

ProgRAMmer Dimonych © (22.02.07 12:49) [27]
рассмотрим этот пункт б)

можно выделять две группы позиций монет: те, что с единицами(монеты в этих позициях сменят сторону после K ходов) и те, что с нулями(монеты сторону не меняют в этих позициях)
внутри каждой из групп позиций монеты можно переставлять как угодно без изменения суммарного количества гербов после K ходов
на первой позиции по условию должен быть герб

теперь рассмотрим смысл пункта б)
если первая позиция имеет 1, то монету в первой позиции можно переставить с любой монетой которая стоит в позиции имеющей единицу

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

если первая не герб, нужна монета в позиции с единицей и притом гербом вверх и вот если такая монета есть(это монета и есть из тех монет которую необходимо положить гербом вниз) нужно обменять местами её с первой монетой и тогда на первом месте будет герб как и требуется по условию задачи
это необходимо учитывать

p.s. решил попонятнее написать

> default © (22.02.07 13:23) [29]
Спасибо, на досуге сделаю ещё один подход к решению задачи уже на уровне понимания (на уровне автомата программу написал, насколько правильно - не знаю).

Извините за наглость, но Найти похожие ветки