23 / 23 / 6
Регистрация: 11.12.2011
Сообщений: 300
|
|
1 | |
Как подойти к решению задачи17.07.2013, 19:27. Показов 1675. Ответов 14
Метки нет Все метки)
(
Кода и готового решения не прошу!!!
Есть задачка грубо говоря звучит так: есть аудитория в которой сидят 30 человек, 1 за одной партой. У каждого есть максимум 4 соседа: спереди, справа, сзади, слева (но может и не быть некоторых из соседей, например человек сидит за первой партой во втором ряду у него нету соседа спереди). У каждого вначале есть 1000 бумажек с написанным на них порядковым уникальным номером (Назовем их марки). Когда звучит звонок, каждый студент дает каждому из своих соседей 100 марок и так же получает от своих соседей по 100 их марок. Вопрос: После скольких звонков у всех студентов будут минимум по одной марке от других студентов ? Мне вот почему-то сходу в голову бросилась мысль, что надо решать данную задачу через Графы. С графами знаком поверхностно и потому прошу совета правильно ли я мыслю. Если да, то буду изучать графы, а если нет, то подскажите в какую сторону смотреть для решения данной задачи.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
|
|
17.07.2013, 19:27 | |
Ответы с готовыми решениями:
14
как подойти к решению задачи? Создание анкеты: как подойти к решению задачи |
![]() |
|
17.07.2013, 19:44 | 2 |
Ответ: не через сколько, так как при таких условиях задачи люди могут циклически обмениваться бумажками. Например, мы с вами обменялись по 100 бумажек, а при следующем звонке обменялись прежними бумажками
2
|
23 / 23 / 6
Регистрация: 11.12.2011
Сообщений: 300
|
|
17.07.2013, 19:49 [ТС] | 3 |
А если с учетом, что при каждой передаче присутствует минимум 1 экземпляр моей марки (То есть каждый в любом случае отдает минимум одну свою марку) ?
0
|
![]() |
|
17.07.2013, 20:04 | 4 |
ответ тот же. у вас 1000 бумажек со значением u, у меня - с v.
вы мне 100 u, я вам 100 v, потом, опять, вы мне 100 u, я вам 100 v и т.д. остальные как меняются пока не важно. после 10 звонков у вас 1000 v, у меня 1000 u. и все...далее условия задачи нарушаются.
0
|
23 / 23 / 6
Регистрация: 11.12.2011
Сообщений: 300
|
|
17.07.2013, 20:14 [ТС] | 5 |
Ок, тогда меняем условие так: при звонке, каждый студент отдает каждому соседу часть своих марок, при этом ОБЯЗАТЕЛЬНО должен отдать минимум по 1 марке из каждых разновидностей, что у него есть. То есть если у него есть 3 марки V и 3 соседа, то он должен каждому дать по 1 такой марке.
Ну вообще я понял вашу логику и, но подскажите если знаете, если у данной задачи(возможно с немного измененным условием) 100% будет решение, то все-таки через графы надо его искать или через, что-то другое!?
0
|
![]() |
|
17.07.2013, 20:17 | 6 |
в условии задачи не сказано, что нет пары студентов, у которых более одного соседа. эта пара студентов может обмениваться по этому алгоритму. пока не вижу 100%-го решения задачи, то есть не вижу корректных условий, чтобы выбрать направление решения.
а так, это более комбинаторика, возможно и графы можно использовать
0
|
23 / 23 / 6
Регистрация: 11.12.2011
Сообщений: 300
|
|
17.07.2013, 20:23 [ТС] | 7 |
Я забыл дописать, что так как это аудитория, то все парты стоят например в 5 рядов по 6 парт в каждом и за каждой партой сидит человек. То есть выходит, что у каждого из студентов минимум 2 соседа и максимум 4.
0
|
![]() |
|
17.07.2013, 20:29 | 8 |
хорошо, сидят студенты
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
|
23 / 23 / 6
Регистрация: 11.12.2011
Сообщений: 300
|
|
17.07.2013, 20:32 [ТС] | 9 |
Ок, тогда студентам перед каждым новым ходом добавляются еще 500 марок. То есть свои марки у них не кончатся никогда
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
17.07.2013, 20:46 | 11 |
это же задача на моделирование?
если так, то предлагаю создать класс СТОПКА МАРОК, который хранит коллекцию марок (массив из 1000 эл-тов для номера каждой марки (вначале у каждого студента массив забит одним значением - порядковым номером студента) или массив из 30 эл-тов - счетчики каждого вида марок или оба представления сразу (тут все зависит от способа обмена марок)) и умеет проверять сколько видов марок в нем содержится, и класс, который будет менять марки из стопок (дружественный по отношению к СТОПКЕ). создаем матрицу стопок марок для каждого студента (размер матрицы по количеству рядов и парт в ряду) запускаем цикл звонков, в котором: - увеличиваем счетчик звонков (вначале = 0) - пробегаемся по матрице и попарно меняем марки в стопках (могу предложить менять так: идем слева направо и сверху вниз по матрице и обмениваемся марками с правым и нижним(задним) соседями) - считаем для каждой стопки кол-во видов марок: если у каждого по 30 видов, то выходим из цикла выводим значение счетчика (если вообще выйдем из цикла, тут все зависит от решения непоняток (ниже)) Непонятки: 1. в каком порядке студенты меняются марками 2. перемешивают ли студенты стопку марок после обменов с соседями 3. может что-то еще упустил, т.к. без написанной программы трудно всё учесть как-то так. но можно наверно что-то оптимизировать
0
|
23 / 23 / 6
Регистрация: 11.12.2011
Сообщений: 300
|
|
18.07.2013, 00:00 [ТС] | 12 |
Ну как же. Я ведь писал выше, что если у студента есть чужие марки, то он должен их отдавать дальше миниму 1 марку от каждой разновидности.
Как вариант можно использовать чучуть другую задачу в которой каждый студент должен разделить все, что у него есть на количество его соседей и передать марки им Добавлено через 2 часа 32 минуты ya_noob, Спасибо большое за направление, я понял, что графы тут ни к чему (хотя тема сама по себе интересна, я немного сегодня ознакомился). Условия задачи чуть прояснились. Я ниже напишу их. Плюсануть карму почему-то не могу вам ![]() Добавлено через 10 минут Таксссс, видоизмененное условие (где-то упростил и плюс условия добавились проясняющие неясности): имеем 9 парт в 3 ряда по 3 парты в ряду. За каждой партой сидит студент. У каждого студента 100 марок (марка - бумажка с порядковым номером студента). При звонке студент должен отдать порцию марок каждому соседу. Порция - это 1 марка на каждых 10 (если есть 10 марок с числом 1, то должен отдать всем соседям по 1 марке с числом 1, так же справедливо для марок с другими номиналами: насобирал 10, отдал по 1). Ворос: количество звонков когда у каждого студента будет по 1 марке от других студентов. В принципе путь для решения уже ясен, а условие написал, что бы убрать неясности. Ну и может кому будет интересно попробовать сделать такую задачу. Добавлено через 26 минут По сути выходит, что для каждого студента перед звонком надо рассчитывать количество марок которые он отдаст другим и где-то хранить эти данные, что бы не считались новоприбывшие марки. Попробовал в экселе посчитать на 9 человек схемку, так на 3 звонке почти у каждого (пока не уверен) студента будет 5 разных видов марок
0
|
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
|
|
18.07.2013, 08:56 | 13 |
непонятки остаются, а именно: не ясно какими марками должен делиться студент (любыми, которых > 10, или же всеми, которых > 10)
предположим, что всеми, которых > 10. в принципе, предложенный мною алгоритм еще в силе, но с небольшими уточнениями: в классе СТОПКА МАРОК марки будут храниться в массиве счетчиков каждого вида марок + еще один такой же массив, но уже для вновь полученных видов марок. этот второй массив вначале пуст, а во время обменов заполняется полученными марками. таким образом имеющиеся и только что полученные марки не перемешиваются. а перед запросом количества видов марок у объекта класса СТОПКА содержимое второго массива надо перенести в первый, а второй соответственно обнулится и будет готов для следующей порции обменов. это ни о чем не говорит. попробуйте лучше так: пусть только у одного студента (Х) есть марки и он сидит в углу (т.е. у него только 2 соседа). надо посчитать через сколько звонков хоть одна марка достигнет диагонально противоположного угла. я тут прикинул, что ближайшие 10 звонков марки не уйдут дальше 2-х ближайших соседей Х. а потом они будут расходиться мееедленно по другим студентам волной. получается какой-то волновой процесс ![]() ну а теперь можно каждому студенту дать марки и каждый начнет "гнать свою волну". характер волн будет зависить от того где сидит студент в углу / на краю / в середине. получается жуть, тут даже для матрицы 3х3 тяжело считать, т.к. кол-во вариантов развития событий возрастает очень быстро. Добавлено через 51 секунду Добавлено через 24 минуты кстати, я тут понял, что алгоритм можно ускорить примерно в 4 раза и уменьшить потребление памяти тоже в 4 раза. достаточно выдать марки только ~25% студентов. подумайте как это сделать.
0
|
23 / 23 / 6
Регистрация: 11.12.2011
Сообщений: 300
|
|
18.07.2013, 13:16 [ТС] | 14 |
Важно: Я немного утрировал саму задачу, чтобы разобраться в какую сторону смотреть решение (вот поэтому куча неточностей в условии)! По сути оригинальная задача звучит примерно так: Есть группы студентов с одинаковыми марками (ну пусть будет 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
|
23 / 23 / 6
Регистрация: 11.12.2011
Сообщений: 300
|
|
21.07.2013, 01:05 [ТС] | 15 |
Ну, что же. Эту задачку у меня получилось реализовать. Все никак полностью в голове не укладывался алгоритм и пару дней только крутил и мусолил все в голове. Сегодня вот часиков за три неспешного кодинга вроде добился работоспособности задачи.
!!! Кстати в условии все-таки обязательно должна быть полностью заполненная матрица, то есть если 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
|
21.07.2013, 01:05 | |
Помогаю со студенческими работами здесь
15
Подскажите пожалуйста как подходить к решению этой задачи Какое регулярное выражение может подойти для решения этой задачи?
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |