Задачка по информатике про Героев, обалдел - когда прочитал |
Здравствуйте, гость ( Вход | Регистрация )
Задачка по информатике про Героев, обалдел - когда прочитал |
15 Jan 2008, 16:16
Сообщение
#1
|
|
Князь Бореи Сообщений: 5 171 Спасибо сказали: 1349 раз |
Нашел на одном из форумов по программированию, просто поразило, что уже и про любимую игру начали задачки детям придумывать:
"Вобщем, эта задча была дана ученикам на одной из олимпиад по информатике (так в журнале написанно). В журнале также есть решение этой задачи, но на языке pascal. Вот и сама задача. Входной фаил - f.in Выходной фаил - f.out Для игры "Heroes of Might and Magic III" генератор случайных карт создает острова, на которых изначально будут расположены герои. Но при случайной генерации карты острова получаются разными по величине. Назовем коэффициентом несправедливости (это выражение мне особо нравится) отношение площади наибольшего острова к площади наименьшего. Необходимо посчитать этот коэффициент. Карта представляет собой прямоугольник, в каждой клетке которого записан 0(вода) или 1(земля). Островом считается множество клеток, содержащих 1, таких, что от любой до любой из них можно пройти по клеткам этого множества, переходя только через их стороны. Входные данные: В первой строке входного файла содержатся числа N и M(размеры карты). В следующих M строках записано по N чисел (разделенных пробелами), каждое из которых 0 или 1 В выходной фаил вывести коэффициент несправедливости с 5 знаками после запятой. Если на карте нет ни одного острова, то вывести 0. Ну вот и все, господа программеры Эта задача, как я считаю - хорошая мозгочистка. Приятных решений, тупиков... и еще стальных вам нервов " |
|
|
15 Jan 2008, 16:33
Сообщение
#2
|
|
Batequeed Peatacille Сообщений: 8 892 Спасибо сказали: 5583 раза |
Прочитал, скрипнул своими филологическими мозгами... и ушел пить чай...
-------------------- |
|
|
15 Jan 2008, 16:43
Сообщение
#3
|
|
Князь Бореи Сообщений: 5 171 Спасибо сказали: 1349 раз |
я кстате забыл сказать, что написал ее не для решения (ну если кто хочет то пожалуста), а просто что людей проинформировать...
Если модеры посчитают, то ее моно удалить или перенести. |
|
|
15 Jan 2008, 16:45
Сообщение
#4
|
|
Сообщений: 29 680 Спасибо сказали: 18134 раза |
не удалять не переонить не надо.. пусть повисит и сама заглохнет.
что касается самой темы - забавно. всё-таки ещё раз убеждаюсь,что герои 3 это классика. воспринимается людьми уже как игра в карты или шахматы.. |
|
|
15 Jan 2008, 16:57
Сообщение
#5
|
|
Batequeed Peatacille Сообщений: 8 892 Спасибо сказали: 5583 раза |
Не... карты немножко не то имхо... Вот шахматы это верно...
-------------------- |
|
|
15 Jan 2008, 16:57
Сообщение
#6
|
|
пират с чёрной меткой Сообщений: 23 630 Спасибо сказали: 12911 раз |
А алгоритм там не приводится? Случайно? Не помешал бы...
-------------------- Давший быка на убой не выпросил и печень на жаркое.
|
|
|
15 Jan 2008, 16:59
Сообщение
#7
|
|
Князь Бореи Сообщений: 5 171 Спасибо сказали: 1349 раз |
Нет, но вроде написано, что В ЖУРНАЛЕ приведено решение на Паскале, но что это за журнал не нашел...
|
|
|
15 Jan 2008, 17:01
Сообщение
#8
|
|
Сообщений: 29 680 Спасибо сказали: 18134 раза |
Цитата Не... карты немножко не то имхо... Вот шахматы это верно... ну там от карт я имею в виду случайность.. то бишь какой выпадет артефакт или герой в таверне.. это как раз как в картах - какая попадёт - козырная или нет |
|
|
15 Jan 2008, 21:05
Сообщение
#9
|
|
Яблочный произвол! Сообщений: 11 080 Спасибо сказали: 3988 раз |
А на самом деле это легкая задачка.
Добавлено ([mergetime]1200420334[/mergetime]): Могу рассказать как решается. |
|
|
15 Jan 2008, 22:08
Сообщение
#10
|
|
Князь Бореи Сообщений: 5 171 Спасибо сказали: 1349 раз |
Давай
|
|
|
16 Jan 2008, 00:23
Сообщение
#11
|
|
В миру GrayFace Сообщений: 2 528 Спасибо сказали: 816 раз |
Да, не сложная. Хотя легкой тоже не назвать.
-------------------- ДНК банана на 50% состоит из человека.
|
|
|
16 Jan 2008, 04:54
(Сообщение отредактировал NickLee - 16 Jan 2008, 04:57)
Сообщение
#12
|
|
Master Сообщений: 277 Спасибо сказали: 18 раз |
Цитата(gamecreator @ 15 Jan 2008, 22:05) А на самом деле это легкая задачка. Согласен Сводится к тому, что необходимо посчитать количество 1 в прямоугольном массиве. Единственный интерес вызывает составление алгоритма определения неразрывности однушек (земли)... Решается просто путем нескольких вложенных циклов, только не указано - сколько непрерывных единиц считать островом ? -------------------- |
|
|
16 Jan 2008, 10:21
Сообщение
#13
|
|
В миру GrayFace Сообщений: 2 528 Спасибо сказали: 816 раз |
А мне, кроме рекурсии, ничего в голову не идет.
-------------------- ДНК банана на 50% состоит из человека.
|
|
|
16 Jan 2008, 16:42
Сообщение
#14
|
|
пират с чёрной меткой Сообщений: 23 630 Спасибо сказали: 12911 раз |
Рекурсия логичнее всего. А считается за остров наверное даже 1 клеточка. Или самые большие площади по количеству игроков. Т.е. из 15 островов считаются 5, потому что 5 игроков.
-------------------- Давший быка на убой не выпросил и печень на жаркое.
|
|
|
16 Jan 2008, 16:43
Сообщение
#15
|
|
Immortal Сообщений: 2 472 Спасибо сказали: 21 раз |
Мне тоже
|
|
|
18 Jan 2008, 19:38
Сообщение
#16
|
|
Яблочный произвол! Сообщений: 11 080 Спасибо сказали: 3988 раз |
На самом деле все решается графами. каждую клетку считаем за вершину. если соседние клетки обе земля, то они связаны. потом ищем количество компонент связности (например, можно закрашивать вершины).
|
|
|
19 Jan 2008, 12:35
Сообщение
#17
|
|
Immortal Сообщений: 2 415 Спасибо сказали: 60 раз |
Цитата(izrukvruki @ 15 Jan 2008, 16:16) Островом считается множество клеток, содержащих 1, таких, что от любой до любой из них можно пройти по клеткам этого множества, переходя только через их стороны. задача действительно простая, насчет перехода по сторонам, разве в героях нельзя ходить по диагонали на соседние клетки?(в том числе на отдельно стоящие) -------------------- |
|
|
19 Jan 2008, 14:46
Сообщение
#18
|
|
Immortal Сообщений: 1 137 Спасибо сказали: 269 раз |
Да, есть такая несостыковочка.
А от того, что назвать это все графом, легче имхо не становится.... разве что есть уже написанный алгоритм или код, работающий с графами. -------------------- |
|
|
19 Jan 2008, 19:15
Сообщение
#19
|
|
Яблочный произвол! Сообщений: 11 080 Спасибо сказали: 3988 раз |
Цитата(Irh @ 19 Jan 2008, 14:46) разве что есть уже написанный алгоритм или код, работающий с графами. ну определение компонент связности это просто |
|
|
03 Mar 2009, 09:02
Сообщение
#20
|
|
good news, everyone! Сообщений: 918 Спасибо сказали: 93 раза |
Замечу, что любую рекурсию можно заменить циклом
-------------------- этъя опять
|
|
|
Текстовая версия | Сейчас: 19 April 2024 - 08:44 |
Copyright by Алексей Крючков
Programming by Degtyarev Dmitry |