@skident

Кода и готового решения не прошу!!!

Есть задачка грубо говоря звучит так:
есть аудитория в которой сидят 30 человек, 1 за одной партой. У каждого есть максимум 4 соседа: спереди, справа, сзади, слева (но может и не быть некоторых из соседей, например человек сидит за первой партой во втором ряду у него нету соседа спереди). У каждого вначале есть 1000 бумажек с написанным на них порядковым уникальным номером (Назовем их марки). Когда звучит звонок, каждый студент дает каждому из своих соседей 100 марок и так же получает от своих соседей по 100 их марок.

Вопрос: После скольких звонков у всех студентов будут минимум по одной марке от других студентов ?

Мне вот почему-то сходу в голову бросилась мысль, что надо решать данную задачу через Графы. С графами знаком поверхностно и потому прошу совета правильно ли я мыслю. Если да, то буду изучать графы, а если нет, то подскажите в какую сторону смотреть для решения данной задачи.

0

@Thinker

Ответ: не через сколько, так как при таких условиях задачи люди могут циклически обмениваться бумажками. Например, мы с вами обменялись по 100 бумажек, а при следующем звонке обменялись прежними бумажками

2

@skident

А если с учетом, что при каждой передаче присутствует минимум 1 экземпляр моей марки (То есть каждый в любом случае отдает минимум одну свою марку) ?

0

@Thinker

ответ тот же. у вас 1000 бумажек со значением u, у меня - с v.
вы мне 100 u, я вам 100 v, потом, опять, вы мне 100 u, я вам 100 v и т.д. остальные как меняются пока не важно. после 10 звонков у вас 1000 v, у меня 1000 u. и все...далее условия задачи нарушаются.

0

@skident

Ок, тогда меняем условие так: при звонке, каждый студент отдает каждому соседу часть своих марок, при этом ОБЯЗАТЕЛЬНО должен отдать минимум по 1 марке из каждых разновидностей, что у него есть. То есть если у него есть 3 марки V и 3 соседа, то он должен каждому дать по 1 такой марке.

Ну вообще я понял вашу логику и, но подскажите если знаете, если у данной задачи(возможно с немного измененным условием) 100% будет решение, то все-таки через графы надо его искать или через, что-то другое!?

0

@Thinker

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

а так, это более комбинаторика, возможно и графы можно использовать

0

@skident

Я забыл дописать, что так как это аудитория, то все парты стоят например в 5 рядов по 6 парт в каждом и за каждой партой сидит человек. То есть выходит, что у каждого из студентов минимум 2 соседа и максимум 4.

0

@Thinker

хорошо, сидят студенты
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
...

студент 1 дает по 100 u марок студентам 2 и 7
студент 2 дает по 100 v марок v студентам 1, 2 и 8
и т.д.
далее тоже самое.

через 4 шага у студента 2 свои марки закончились и все...

0

@skident

Ок, тогда студентам перед каждым новым ходом добавляются еще 500 марок. То есть свои марки у них не кончатся никогда

0

@Thinker

все равно ответа нет. судите сами, каждый студент на каждом шаге своим соседям дает каждому ровно по 100 своих марок, а у соседей они просто накапливаются и они их дальше не передают.

0

@ya_noob

это же задача на моделирование?

если так, то предлагаю создать класс СТОПКА МАРОК, который хранит коллекцию марок (массив из 1000 эл-тов для номера каждой марки (вначале у каждого студента массив забит одним значением - порядковым номером студента) или массив из 30 эл-тов - счетчики каждого вида марок или оба представления сразу (тут все зависит от способа обмена марок)) и умеет проверять сколько видов марок в нем содержится, и класс, который будет менять марки из стопок (дружественный по отношению к СТОПКЕ).

создаем матрицу стопок марок для каждого студента (размер матрицы по количеству рядов и парт в ряду)

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

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

Непонятки:
1. в каком порядке студенты меняются марками
2. перемешивают ли студенты стопку марок после обменов с соседями
3. может что-то еще упустил, т.к. без написанной программы трудно всё учесть

как-то так. но можно наверно что-то оптимизировать

0

@skident

Ну как же. Я ведь писал выше, что если у студента есть чужие марки, то он должен их отдавать дальше миниму 1 марку от каждой разновидности.

Как вариант можно использовать чучуть другую задачу в которой каждый студент должен разделить все, что у него есть на количество его соседей и передать марки им

Добавлено через 2 часа 32 минуты
ya_noob, Спасибо большое за направление, я понял, что графы тут ни к чему (хотя тема сама по себе интересна, я немного сегодня ознакомился).

Условия задачи чуть прояснились. Я ниже напишу их.

Плюсануть карму почему-то не могу вам

Добавлено через 10 минут
Таксссс, видоизмененное условие (где-то упростил и плюс условия добавились проясняющие неясности):
имеем 9 парт в 3 ряда по 3 парты в ряду. За каждой партой сидит студент. У каждого студента 100 марок (марка - бумажка с порядковым номером студента). При звонке студент должен отдать порцию марок каждому соседу. Порция - это 1 марка на каждых 10 (если есть 10 марок с числом 1, то должен отдать всем соседям по 1 марке с числом 1, так же справедливо для марок с другими номиналами: насобирал 10, отдал по 1).

Ворос: количество звонков когда у каждого студента будет по 1 марке от других студентов.

В принципе путь для решения уже ясен, а условие написал, что бы убрать неясности. Ну и может кому будет интересно попробовать сделать такую задачу.

Добавлено через 26 минут
По сути выходит, что для каждого студента перед звонком надо рассчитывать количество марок которые он отдаст другим и где-то хранить эти данные, что бы не считались новоприбывшие марки. Попробовал в экселе посчитать на 9 человек схемку, так на 3 звонке почти у каждого (пока не уверен) студента будет 5 разных видов марок

0

@ya_noob

непонятки остаются, а именно: не ясно какими марками должен делиться студент (любыми, которых > 10, или же всеми, которых > 10)
предположим, что всеми, которых > 10.

в принципе, предложенный мною алгоритм еще в силе, но с небольшими уточнениями: в классе СТОПКА МАРОК марки будут храниться в массиве счетчиков каждого вида марок + еще один такой же массив, но уже для вновь полученных видов марок. этот второй массив вначале пуст, а во время обменов заполняется полученными марками. таким образом имеющиеся и только что полученные марки не перемешиваются. а перед запросом количества видов марок у объекта класса СТОПКА содержимое второго массива надо перенести в первый, а второй соответственно обнулится и будет готов для следующей порции обменов.

это ни о чем не говорит. попробуйте лучше так:
пусть только у одного студента (Х) есть марки и он сидит в углу (т.е. у него только 2 соседа). надо посчитать через сколько звонков хоть одна марка достигнет диагонально противоположного угла. я тут прикинул, что ближайшие 10 звонков марки не уйдут дальше 2-х ближайших соседей Х. а потом они будут расходиться мееедленно по другим студентам волной. получается какой-то волновой процесс . и чтобы волна пошла дальше, нужно приложить усилие в 10 марок (усилие имеет свойство накапливаться).

ну а теперь можно каждому студенту дать марки и каждый начнет "гнать свою волну". характер волн будет зависить от того где сидит студент в углу / на краю / в середине. получается жуть, тут даже для матрицы 3х3 тяжело считать, т.к. кол-во вариантов развития событий возрастает очень быстро.

Добавлено через 51 секунду


Добавлено через 24 минуты
кстати, я тут понял, что алгоритм можно ускорить примерно в 4 раза и уменьшить потребление памяти тоже в 4 раза. достаточно выдать марки только ~25% студентов. подумайте как это сделать.

0

@skident

По теме:
Важно: Я немного утрировал саму задачу, чтобы разобраться в какую сторону смотреть решение (вот поэтому куча неточностей в условии)!

По сути оригинальная задача звучит примерно так: Есть группы студентов с одинаковыми марками (ну пусть будет 2 группы красная и зеленая). Сидят они за 2-мя рядами парт, в каждом ряду по 4 парты.

1 2
К К
К К
З З
З З

У каждого из студентов по 100 марок их цвета, то есть у каждого К(красного) - 100 марок красных. В сумме дает нам 400 красных марок и 400 зеленых марок.

Ну и вот они начинают меняться между собой марками. Каждый из них обязан отдать на каждых 10 марок определенного цвета по 1 марке того же цвета соседям.

В итоге за первый ход каждый красный должен отдать по 10 красных марок соседу, а каждый зеленый студент по 10 зеленых марок.

То есть самые верхние красные и самые нижние зеленые студенты остаются с теми же 100 марками одного цвета. А вот уже средние К К и З З имеют в наличии по 10 марок другого цвета.

И вот уже при втором ходе эти средние К К и З З должны отдать по 9 марок своего цвета и по 1 марке не своего цвета всем своим соседям.
А значит за 2 хода у каждого из студентов будет по 2 вида марок.

Вывод: надо 2 хода(звонка)

Вроде ничего сложного, а вот в реальной задаче, может быть например вот такая ситуация:
1 2
К К
К
З З
З З

или
1 2
К К
К К
З З
З

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

Ну и еще плюс этих груп может быть 3, 4.... 20

то есть может задача выглядеть так красный(К), голубой(Г), зеленый(З), желтый(Ж), оранжевый(О):

1 2 3 4 5
К К К Г Г
К К К К Г
З З З З З
З Ж Ж Ж Ж
О О О

Добавлено через 32 минуты
По поводу решения думаю делать, что-то в таком роде:
1. Класс группы в котором содержатся:
а. массив из 4 ссылок на соседние группы (если нет каких-то из соседов, то ссылка NULL).
б. массив из ссылок на всех студентов в группе (наверное двухмерный, но еще не знаю точно)
2. Класс Студент, содержит:
а. массив из 4 ссылок на соседей
б. динамический массив в котором записаны все его марки
в. динамический массив в котором записано сколько и каких марок отдать при следующем ходе
г. метод проверки есть ли у пользователя все марки


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

0

@skident

Ну, что же. Эту задачку у меня получилось реализовать. Все никак полностью в голове не укладывался алгоритм и пару дней только крутил и мусолил все в голове. Сегодня вот часиков за три неспешного кодинга вроде добился работоспособности задачи.

!!! Кстати в условии все-таки обязательно должна быть полностью заполненная матрица, то есть если 4 парты в 2 ряда, то обязательно должны сидеть все 4 студента !!!

Количество звонков (шагов) для разных размеров массива с учетом, что у каждого студента свои марки:
1 Х 1 = обмен происходит за 1 шаг
2 Х 2 = обмен происходит за 2 шаг
3 Х 2 (2 Х 3) = обмен происходит за 35 шаг
3 Х 3 = обмен происходит за 146 шаг
3 Х 4 (4 Х 3) = обмен происходит за 318 шаг
4 Х 4 = 583 шага

Теперь стоит задача сделать обмен между группами студентов.

Чуть позже выложу весь код.

0