Задача на логику - Форум администраторов игровых серверов
Форум администраторов игровых серверов StormWall - Защита от DDos атак
Регистрация Мнения Справка Пользователи Календарь Все разделы прочитаны
Вернуться   Форум администраторов игровых серверов > Полезное / Common > Программирование / Programming

Программирование / Programming
Ищете помощи в написании программы, есть сложность в выполнении задания (в институте и т.д.), пожалуйста, спросите у нас в данном форуме и мы обязательно вам поможем.

Ответ
Опции темы
Непрочитано 30.05.2014, 11:58   #1
Аватар для Clown
Пользователь

Автор темы (Топик Стартер) Задача на логику

Всем привет!
Собственно, снова понадобилась помощь дружного коллектива
На носу всеми любимой летней сессии задали задания на UVA, которые обязательно нужно решить . Сказано - сделано. Практически все задачи были сделаны (язык программирования характерный - С++ или Java), а вот одно задание - хоть убей, не пойму.
Нужна помощь с алгоритмом, если кто поможет - добра и счастье тебе, друг . А вообще - всем того же

http://uva.onlinejudge.org/index.php...m&problem=3937 Сама задача.

UPD:
Нашел код на сишке, но не могу понять алгоритма, может кто понял и объяснит, так же был бы крайне благодарен... По сути, мне важен именно алгоритм решения, ибо написать могу и сам .
https://github.com/marioyc/Online-Ju...0-%20Stars.cpp

C Уважением.

Добавлено через 2 часа 49 минут
Ну хоть предположения
__________________
// GPRS удалил подпись пользователя

Последний раз редактировалось Clown; 30.05.2014 в 14:47. Причина: Добавлено сообщение
Clown вне форума Ответить с цитированием
Непрочитано 30.05.2014, 14:51   #2
Пользователь

По умолчанию Re: Задача на логику

Для скорейшего понимания написали бы суть задания на русском, а то на английском ро ссылке тяжело вникать.
flopix вне форума Ответить с цитированием
Сказали спасибо:
Непрочитано 30.05.2014, 16:15   #3
Аватар для Clown
Пользователь

Автор темы (Топик Стартер) Re: Задача на логику

"Фернандо получил компас на день рождения, и теперь его хобби - рисовать звёзды. Сначала он делает N отметок на окружности, разделяя её на N равных дуг, потом соединяет каждую точку с каждой К-той точкой, и так до тех пор, пока не вернётся к первой точке2"
"В зависимости от значения К, Фернандо может достичь\не достичь всех точек на окружности; когда это случается - звезда называется завершённой. Например, когда N=8, возможные звёзды показаны на фигуре ниже. Звёзды а и с - завершённые, б и д - напротив, нет.
В зависимости от значения N, есть вероятность нарисования всеразличных звёзд, Фернандо попросил тебя написать программу, которая при заданном значении N определяет количество возможных законченных звёзд, которые он может нарисовать."
"Ввод:
Ввод содержит несколько тестовых вариантов. Каждый тестовый вариант содержит одну линию (строку), включающую в себя число типа integer, =диапазон для N даётся=, указывая число дуг, на которые окружность была поделена.
Вывод:
Для каждого тестового варианта твоя программа должна вывести одну строку (линию), содержащую одну же линию с числом типа integer (=дословно: одну линию содержащуюю один инт=), показывая количество законченных звёзд, которые могут быть нарисованы.
__________________
// GPRS удалил подпись пользователя
Clown вне форума Ответить с цитированием
Непрочитано 30.05.2014, 18:16   #4
Пользователь

По умолчанию Re: Задача на логику

k - это количество пропускаемых точек, при построение очередного отрезка, k = 0 .. N-1


Одним из признаков, что звезда получилась является:

1. построение звезды закончилось в той же точке где и началось
2. количество отрезков равно количеству точек на окружности

Но это не достаточное условие, нужно как то исключить попадание в одни и те же точки, надо подумать как.

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

Последний раз редактировалось flopix; 30.05.2014 в 18:30. Причина: Добавлено сообщение
flopix вне форума Ответить с цитированием
Сказали спасибо:
Непрочитано 30.05.2014, 18:29   #5
Аватар для Clown
Пользователь

Автор темы (Топик Стартер) Re: Задача на логику

Цитата:
Сообщение от flopix Посмотреть сообщение
k - это количество пропускаемых точек, при построение очередного отрезка, k = 0 .. N-1


Одним из признаков, что звезда получилась является:

1. построение звезды закончилось в той же точке где и началось
2. количество отрезков равно количеству точек на окружности

Но это не достаточное условие, нужно как то исключить попадание в одни и те же точки, надо подумать как.

И кстати пример по вашей ссылке вряд ли является корректным решением этой задачи так как N по условию может быть очень большим числом и задан лимит в 2 секунды на работу программы.
Но могу ошибаться, там основной цикл идет от 2 до корень из N.
Я , честно говоря, не очень понял алгоритм по которому реализован тот пример. Можете объяснить, если разобрали? Вообще - данное решение (по той ссылке) - верное. Тестировал - выполнение ~ за 1,5-1,7 s на все тесты. Не пойму сей логики кода, хотя пропускал пошагово выполнение. (Сам код то элементарен, а вот алгоритм - извольте, хотя, вероятно, больше здесь "не в тыкаю" я).
__________________
// GPRS удалил подпись пользователя
Clown вне форума Ответить с цитированием
Непрочитано 30.05.2014, 18:30   #6
Пользователь

По умолчанию Re: Задача на логику

Пример глдянул только мельком, так не интересно


Добавлю еще условие 3.

3. если мы попали в исходную точку раньше времени (количество отрезков звезды < N) значит звезда не получилась.

Думаю этого достаточно, теперь думаем как это решить быстро и элегантно.
flopix вне форума Ответить с цитированием
Сказали спасибо:
Непрочитано 30.05.2014, 18:34   #7
Аватар для Clown
Пользователь

Автор темы (Топик Стартер) Re: Задача на логику

Цитата:
Сообщение от flopix Посмотреть сообщение
Пример глдянул только мельком, так не интересно


Добавлю еще условие 3.

3. если мы попали в исходную точку раньше времени (количество отрезков звезды < N) значит звезда не получилась.

Думаю этого достаточно, теперь думаем как это решить быстро и элегантно.
Да, уже заметил и плюсанул в репу, огромное Вам спасибо! теперь хоть алгоритм решения стал понятен и , в принципе, если не выплывет никаких подводных камней - можно спокойно реализовать. Но на счет примера - актуально. Не в плане того, что мне хотелось бы его взять (это я и так бы мог сделать не прося помощи), а в плане, что интересно само решение, которое нет смысла пропускать и опускать на будущее, ведь плохо то, что я не понял его. Так что разобраться было бы не лишним, что, к сожалению, у меня не очень хорошо получается на данный момент, разве что понял, что мы доходим до первой точки , а вот дальше.
__________________
// GPRS удалил подпись пользователя
Clown вне форума Ответить с цитированием
Непрочитано 30.05.2014, 18:47   #8
Пользователь

По умолчанию Re: Задача на логику

А как там пошагово запустить код на исполнение? Нужно регаться?
flopix вне форума Ответить с цитированием
Непрочитано 30.05.2014, 18:49   #9
Аватар для Clown
Пользователь

Автор темы (Топик Стартер) Re: Задача на логику

Цитата:
Сообщение от flopix Посмотреть сообщение
А как там пошагово запустить код на исполнение? Нужно регаться?
Не, не, не, юзаю Visual Studio. Можно с Вами как-то связаться? Думаю, так бы было удобнее. А как итог я приложу сюда и попрошу закрыть тему, вдруг, кому-то тоже понадобится.
__________________
// GPRS удалил подпись пользователя
Clown вне форума Ответить с цитированием
Непрочитано 30.05.2014, 18:51   #10
Пользователь

По умолчанию Re: Задача на логику

Да я не эксперт в алгоритмах. Возможно я вам совсем не оптимальный вариант решения предложил. Погодите разберусь в примере кода.
flopix вне форума Ответить с цитированием
Сказали спасибо:
Ответ


Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 
Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вот такая вот задача Asmodiel Курилка / Yak floor 5 12.01.2013 15:52
Задача на VBA Nowell Программирование / Programming 2 10.06.2010 09:24


© 2007–2024 «Форум администраторов игровых серверов»
Защита сайта от DDoS атак — StormWall
Работает на Булке неизвестной версии с переводом от zCarot
Текущее время: 23:00. Часовой пояс GMT +3.

Вверх