Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.91/11: Рейтинг темы: голосов - 11, средняя оценка - 4.91
lena 11
0 / 0 / 0
Регистрация: 17.11.2012
Сообщений: 101
1

Как муравьям максимально равномерно распределиться по поверхности?

20.10.2014, 21:04. Просмотров 2025. Ответов 40
Метки нет (Все метки)

1)Дана прямоугольная плоская поверхность, разделенная на равные прямоугольники. Прямоугольники разделены веревкой, которую муравьям неприятно переползать. В один из прямоугольников высыпается куча муравьев. Муравьям очень не нравится толчея и они хотят равномерно распределиться по поверхности. Муравьи в данном прямоугольнике имеют возможность оценить количество муравьев в четырех соседних прямоугольников, после чего отправить в них сколько-то муравьев. Совещаться между собой или передавать информацию муравьи с разных прямоугольников не могут. Муравьи являются дружным коллективом, поэтому они не противодействуют муравьям, пришедшим с соседних прямоугольников. Помогите муравьям составить алгоритм, действуя по которому они смогут максимально равномерно распределиться по поверхности. Решение обязано сходиться за конечное число шагов. Написание программы является плюсом.

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

0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2014, 21:04
Ответы с готовыми решениями:

Электрическое поле создано равномерно заряженным по поверхности
Здравствуйте! Помогите, пожалуйста с задачей! Электрическое поле создано...

Сколькими способами могут распределиться медали
Сколькими способами на первенстве мира по футболу могут распределиться медали,...

Сколькими способами 20 человек могут распределиться по 4 аудиториям?
Вступительные экзамены сдают 20 человек, сколькими способами они могут...

Количество способов, которыми могут распределиться призы
В группе из 30 человек разыгрывается 4 различных приза. Призы могут достаться...

Сколькими способами могут распределиться между остановками 8 пассажиров
Здравствуйте помогите решить задачи. Пожалуйста с решением. №3. Лифт...

40
mporro
306 / 101 / 18
Регистрация: 04.07.2014
Сообщений: 571
02.11.2014, 22:29 21
Цитата Сообщение от pycture Посмотреть сообщение
и что это меняет?
Муравей не будет переползать верёвку, если он находится в клетке один. Муравьи не отправят одного из своих в соседнюю клетку, если количество муравьёв в ней ровно на один меньше.
0
pycture
1173 / 561 / 85
Регистрация: 20.09.2012
Сообщений: 1,818
Завершенные тесты: 3
03.11.2014, 05:46 22
Цитата Сообщение от mporro Посмотреть сообщение
Муравей не будет переползать верёвку, если он находится в клетке один
с чего бы? у них какая задача?
Цитата Сообщение от lena 11 Посмотреть сообщение
максимально равномерно распределиться по поверхности
а не остаться одному в клетке. значит должны перелезать даже если один.
0
mporro
306 / 101 / 18
Регистрация: 04.07.2014
Сообщений: 571
03.11.2014, 07:50 23
pycture, Вы не умеете читать условия.

Составить алгоритм для равномерного расползания муравьёв -- это некоторая общая задача.
Но есть ограничения. Муравьи могут анализировать только соседние клетки. Муравьям не нравится толчея и не нравится переползать через верёвку.

Если условие про верёвку выкинуть, то завершаемый алгоритм не удастся построить. Так как один единственный муравей будет бесконечно прыгать по пустой плоскости.

Добавлено через 3 минуты
P.S. Если же Вам просто хочется "потроллить", то можете притвориться, что не поняли задание даже после объяснения.
0
pycture
1173 / 561 / 85
Регистрация: 20.09.2012
Сообщений: 1,818
Завершенные тесты: 3
03.11.2014, 08:21 24
Цитата Сообщение от mporro Посмотреть сообщение
Вы не умеете читать условия
какие условия, такое и понимание. как грится адекватно сформулированная задача это половина ответа. граммотно сформулированное и непротиворечивое условие не требует никакого "объяснения"
Если условие про верёвку выкинуть, то завершаемый алгоритм не удастся построить.
вернемся к веревке. она делит поверхность на 21 прямоугольник в один ряд. в левый прямоугольник высыпаем 3-х муравьев. они смогут равномерно разместиться в этом ряду из 21-го прямоугольника? не смогут, а значит условие "максимально равномерно распределиться по поверхности" не выполнимо хоть с вревкой хоть без нее.

Не по теме:

p.s. вы случаем не автор этой задачи? а то давать разъяснения к невнятно выраженным условиям обычно в традиции авторов

0
mporro
306 / 101 / 18
Регистрация: 04.07.2014
Сообщений: 571
03.11.2014, 08:57 25
pycture,
какие условия, такое и понимание
Это не задача научного характера, которую Вы сами поставили и потом решили. Это не задача от технического писателя, который сформулировал для вас чёткую схему вариантов использования ПО.

Это олимпиадная задача, где условие несколько запутанно намерено, чтобы участники сами составили модель задачи, сами создали формальные разрешимые требования. Такие задачи никогда не бывают полностью ясными.

Что касается линии из большого числа прямоугольников и малого количества муравьёв, то можно указать формальное условие неразличимости прямоугольников с числом муравьёв, отличающимся на единицу.
0
pycture
1173 / 561 / 85
Регистрация: 20.09.2012
Сообщений: 1,818
Завершенные тесты: 3
03.11.2014, 09:30 26
Цитата Сообщение от mporro Посмотреть сообщение
Это олимпиадная задача, где условие несколько запутанно намерено, чтобы участники сами составили модель задачи, сами создали формальные разрешимые требования. Такие задачи никогда не бывают полностью ясными.
я как бы участвовал в олимпиадных задачах и ни разу еще не видел настолько кривых условий. более того олимпиадные задачи (адекватные) всегда предлагают варианты входных и выходным тестовых примеров, дабы кривизну мышления мышления автора можно было сгладить разбором этих тестовых примеров. здесь ничего этого не присуствует. так что если это олимпиадная задача то ее надо дисквалицифировать (а это тоже нормальная практика) за невнятность условий
0
_Ivana
3236 / 1864 / 235
Регистрация: 01.03.2013
Сообщений: 5,108
Записей в блоге: 5
03.11.2014, 12:22 27
Цитата Сообщение от mporro Посмотреть сообщение
Так как один единственный муравей будет бесконечно прыгать по пустой плоскости
Если позволите позанудствовать, то не будет. И веревка никакая не нужна. Если, допустим, логика будет - отправлять в соседнюю клетку целую часть от половины разницы количеств.
0
Mr.X
Эксперт С++
3183 / 1710 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
03.11.2014, 12:54 28
Понятие "максимально равномерно" в условии не определено. Значит настолько равномерно, насколько позволит решение. У кого равномернее, тот и победил.
0
mporro
306 / 101 / 18
Регистрация: 04.07.2014
Сообщений: 571
03.11.2014, 13:16 29
_Ivana, если "позанудствовать", то не получится удовлетворить условию о "тесноте". Предположим, что муравьи видят, что в соседней клетке меньше муравьёв, чем в их собственной. Тогда они точно видят, что в соседней клетке "свободнее", и хотят отправить туда муравья. =)

Лично мне эта задача до боли напоминает классическую задачу об утилизации ядерных отходов в капсулах. Я убеждён, что порождена задача про муравьёв ровно из этой самой задачи.
0
_Ivana
3236 / 1864 / 235
Регистрация: 01.03.2013
Сообщений: 5,108
Записей в блоге: 5
03.11.2014, 13:22 30
mporro, еще 2 раза перечитал условие, и не обнаружил в нем требования обязательно отправлять муравья в клетку, где количество меньше. По-моему это как раз ваше выдуманное требование. Именно что
Цитата Сообщение от lena 11 Посмотреть сообщение
Муравьи в данном прямоугольнике имеют возможность оценить количество муравьев в четырех соседних прямоугольников, после чего отправить в них сколько-то муравьев.
Вот они оценивают и не отправляют.
0
mporro
306 / 101 / 18
Регистрация: 04.07.2014
Сообщений: 571
03.11.2014, 14:00 31
_Ivana, может быть это и вправду моё предвзятое мнение.

В задачах параболического типа, чтобы ограничить область "прогревания" как раз вводят минимальную эффективную порцию и затем решают клеточным автоматом. Соединяя вместе как раз получается: верёвка -- барьер, не нравится толчея -- градиентный перенос.

Наиболее разумное мнение, конечно, высказал Mr.X. Нужно предъявить некий алгоритм и доказать завершаемость. У кого меньше вариация -- тот и молодец.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
03.11.2014, 16:03 32
Цитата Сообщение от pycture Посмотреть сообщение
Igor3D, предположим прямоугольник 1 х 21. в левый угол высыпаем 3-х муравьев. какая вероятность при использовании вашего алгорима что они будут распределены по поверхности равномерно? т.е. в позициях 4,11,18, а не застрянут все в яйчейках 1,3,5, что само собой не является равномерным распределением.
А почему в 4, 11 и 18? Чем это "равномернее" чем, скажем, 1, 10 и 21? Равномерность можно измерить отношением кол-ва мин заполненной к макс заполненной. Если клеток больше чем муравьев, она всегда = 0

Цитата Сообщение от _Ivana Посмотреть сообщение
Если муравьи могут делиться по частям, то вполне работает
И не могут - тоже. Известно сколько всего нужно послать в соседние, ну округлим где надо. Кстати посылать можно практически как угодно, лишь бы это улучшало равномерность. Влияет только на скорость сходимости.
0
_Ivana
3236 / 1864 / 235
Регистрация: 01.03.2013
Сообщений: 5,108
Записей в блоге: 5
03.11.2014, 18:24 33
Цитата Сообщение от Igor3D Посмотреть сообщение
И не могут - тоже.
Понимаете, при бесконечной делимости муравьев задачка достаточно тривиальна, и вы правильно заметили, что
Цитата Сообщение от Igor3D Посмотреть сообщение
посылать можно практически как угодно
, я на паяльниках проверял. Но с целыми муравьями задача не имеет решения в заданной постановке. Моооожет быть в отдельных случаях она имеет решение, если в каждом квадрате лежит бумажка с историей - сколько на каком шаге из этого квадрата куда отправлялось и сколько откуда приходило, и муравьи могут ее читать - но тогда задачка перестает быть томной А простейшие алгоритмы, которые видны невооруженным взглядом (и ваш в том числе), не осилят не только пример pycture, но и линию
2 1 1 1 0 или
5 4 3 2 1 0 0 0
0
pycture
1173 / 561 / 85
Регистрация: 20.09.2012
Сообщений: 1,818
Завершенные тесты: 3
04.11.2014, 05:41 34
Цитата Сообщение от Igor3D Посмотреть сообщение
А почему в 4, 11 и 18? Чем это "равномернее" чем, скажем, 1, 10 и 21?
да без разницы. ваш алгоритм ни того ни другого не решает
Равномерность можно измерить отношением кол-ва мин заполненной к макс заполненной.
проблема в том, что в условии требуется равномерность не "по кол-ву" в клетках, а равномерно "по поверхности", так что нельзя. было бы по "кол-ву" даже вопрсов не было б, а так задача не решаемая
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
04.11.2014, 17:23 35
Цитата Сообщение от _Ivana Посмотреть сообщение
А простейшие алгоритмы, которые видны невооруженным взглядом (и ваш в том числе), не осилят не только пример pycture, но и линию
2 1 1 1 0 или
5 4 3 2 1 0 0 0
Это легко проверить. Возьмем первую ячейку. Сумма 2+1 = 3 на 2 ячейки, среднее 1.5 ("полтора землекопа" в старом мультике). Но расчленять муравьев никто не хотел, поэтому берем просто целую часть 1. Имеем 2, значит одного бойца посылаем в правую ячейку. Так что осилит, а Вы глаз-то вооружайте

Цитата Сообщение от pycture Посмотреть сообщение
проблема в том, что в условии требуется равномерность не "по кол-ву" в клетках, а равномерно "по поверхности", так что нельзя. было бы по "кол-ву" даже вопрсов не было б, а так задача не решаемая
Продолжим эти рассуждения: есть аж ОДИН муравей на 100 клеток. Ну как же его "равномерно" распределить? Как видите, мы быстро пришли к полному абсурду

Чему посвящены 2 листа постов? В основном - упорному доказательству того что "задача нерешаема". Зачем? Если "даже вопрсов не было б" - то почему бы сначала не предложить решение, а потом уж, если так интересно, ковыряться в частном случае (о котором никто не спрашивал)
0
pycture
1173 / 561 / 85
Регистрация: 20.09.2012
Сообщений: 1,818
Завершенные тесты: 3
05.11.2014, 05:47 36
Цитата Сообщение от Igor3D Посмотреть сообщение
Продолжим эти рассуждения: есть аж ОДИН муравей на 100 клеток. Ну как же его "равномерно" распределить?
очевидно что посередине (+- клетка не имеет значения). т.е. равно удаленно от границ. никакого абсурда не наблюдается
Если "даже вопрсов не было б" - то почему бы сначала не предложить решение
и зачем предлагать решение для задачи которую никто не спрашивал? никому не требуется равномерное размещение по кол-ву. в задаче другое условие. если ктото хочет решать другую задачу чем в условии, никто не запрещает, но выдавать это за решение исходной задачи ни есть правильно

Не по теме:

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

0
Mr.X
Эксперт С++
3183 / 1710 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.11.2014, 07:54 37
Цитата Сообщение от Igor3D Посмотреть сообщение
Зачем? Если "даже вопросов не было б" - то почему бы сначала не предложить решение
Условие задачи неопределенное, а такая задача определенного решения в принципе иметь не может. Типичное олимпиадное мозгозасир@тельство.
0
mporro
306 / 101 / 18
Регистрация: 04.07.2014
Сообщений: 571
05.11.2014, 08:46 38
Mr.X, всё уже было всем объяснено и разжёвано. Просто pycture упорно продолжает троллить условие. И про намёки в условии говорили, и на олимпиадный характер указывали. Кто хотел, тот разобрался, кто не хочет -- тот не хочет.
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
05.11.2014, 10:12 39
Цитата Сообщение от pycture Посмотреть сообщение
очевидно что посередине (+- клетка не имеет значения). т.е. равно удаленно от границ.
А может это называется "симметрично"? Впрочем уже давно толчем воду в ступе, позвольте Вам больше не отвечать.

Цитата Сообщение от Mr.X Посмотреть сообщение
Условие задачи неопределенное, а такая задача определенного решения в принципе иметь не может. Типичное олимпиадное мозгозасир@тельство.
Напротив, прекрасная задачка. Цель не "определенное решение", требуется "разработать локальную стратегию" (как ни помпезно звучит). В жизни это встречается часто, напр когда "клетки" (или их аналоги) надо обсчитывать параллельно. И приходится смириться с неточностью/не-аналитичностью решения т.к. оно должно быть локально. Преодолеть этот барьер в сознании не так уж легко - как видно из обсуждения
0
Mr.X
Эксперт С++
3183 / 1710 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.11.2014, 12:21 40
Цитата Сообщение от Igor3D Посмотреть сообщение
Цель не "определенное решение", требуется "разработать локальную стратегию" (как ни помпезно звучит)
Да-да, вся "помпёздность" в том и состоит, что непонятно стратегию чего. Ребята уже мозги сломали. А так ничего задачка. Как там у Зощенко в его рассказе про крупу "Геркулес": есть можно, единственно только глотать нельзя.
0
05.11.2014, 12:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2014, 12:21

Найти сумму максимально отрицательного и максимально положительного элемента массива
Ребята, помогите, плиз)) найти суму максимально отрицательного и максимально...

Что такое максимально полные и максимально пустые подграфы?
Что такое максимально полные и максимально пустые подграфы?

Подобрать максимально возможный и максимально совместимый процессор
Имеется ноутбук (Futjitsu Siemens esprimo mobile v 5535) сокет mPGA 478MN....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru