LINUX.ORG.RU
ФорумTalks

Нужно придумать что-то вроде олимпиадной задачи


0

0

1. Суть вот в чем. Нужна такая постановка задачи, которая не имеет явного 100% верного решения. Такое иногда бывает на олимпиадах (типа "придумайте алгоритм, находящий кратчайший путь ...") --- придумать-то можно, но всегда найдется тест, для которого условие не будет выполняться.

Вот. Это первое условие. Уже непросто, но дальше еще хуже.

2. Надо, чтобы программа имела практическую ("десктопную") направленность. То есть не абстрактный лабиринт пройти, а что-то вполне "приземленное" сделать. Подозреваю даже, что это условие невыполнимо --- не сильно-то в повседневной жизни изощренные алгоритмы используются.

3. Ну и последнее, что совсем все портит --- она должна быть такой сложности, чтобы решить ее особого труда не составляло (не до конца, конечно --- см пункт 1, но хотя бы какой-то результат нужен). Это отсекает всякие системы распознавания речи и прочее. Для школьника должна быть задачка.

Я поимаю, что никому за меня думать нафиг не надо, но вдруг кто-то заинтересуется или уже знает ответ. Сам, похоже, ниасилю --- вторую неделю уже мучаюсь.

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

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

anonymous

Re: Нужно придумать что-то вроде олимпиадной задачи

хотел написать задачу, но потом решил, что пойду ка я лучше покушаю, т.к. с утра ничего не ел
exuse me :)

skyfisher ()

Re: Нужно придумать что-то вроде олимпиадной задачи

:) Серьезно что-то придумал или так, стебешься?

Если первое, то поделись скорее. Учитывая, что мне ее еще решать и отчет строчить гигантский --- совсем времени нет.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

Пакетный менеджер для слаки с расчетом зависимомтей.

kaktyc ★★★★ ()

Re: Нужно придумать что-то вроде олимпиадной задачи

задача на логику
расстояние 1000км. Водитель стартует из точки А в точку Б. (на машине). бензобак машины - 40 литров. есть канистра на 20 литров. На одном литре он может проехать 10 км. 1 литр = 1$. с собой у него есть пакеты, которые он может оставлять на дороге, слив в них бензин. Ехать с наполнеными пакетами нельзя. (с канистрой можно).
Задача - добраться до точки Б за как можно меньшую сумму

skyfisher ()

Re: Нужно придумать что-то вроде олимпиадной задачи

>Пакетный менеджер для слаки с расчетом зависимомтей.

Дык первое условие не выполняется. Если косяков в описании зависимостей нет, то алгоритм элементарный: не хватает чего-то -> нашел, скачал, поставил. Нет тут простора для бесконечного поиска лучших решений.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

>Превратить слаку в debian? Нафига?

Блин, да я готов ее в винду превратить, лишь бы со всем этим разобраться.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

>задача на логику ...

Спасибо за помощь, но это как раз-таки "олимпиадная" задача. Мне надо что-то такое, что будет _полезно_ человеку, имеющему дело с компом.

Повторюсь, пока кажется, что именно это условие и делает все невозможным.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

Задача больно обширная. В debian пакетный менеджер уже сколько лет делают... apt всё ещё версии 0.6 - никак не дойдёт до 1.0

Xellos ★★★★★ ()

Re: Нужно придумать что-то вроде олимпиадной задачи

Получается, что программа должна быть не большой (см. 3), но сложной (см. 1). Но в то же время позволять "частичное" решение (1).

Вот только как тут "полезность" прикрутить..

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

Задача 1.
Последовательность из англиских букв строиться следующим образом.
На нулевом шаге она пуста. На каждом последующем шаге
 последовательность удваевается, после чего к ней слева дописывается
 очередная буква английского алфаавита (a,b,c,....). Ниже приведены
 первые шаги построения последовательности:
 Шаг 0: Пустая строка
 Шаг 1: a
 Шаг 2: baa
 Шаг 3: cbaabaa
 Шаг 4: dcbaabaacbaabaa

Задача состоит в том , чтобы по заданному N определить символ,
который соит на N-ом месте в последовательности, получившейся после
 26-го шага.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

>В debian пакетный менеджер уже сколько лет делают... apt всё ещё версии 0.6 - никак не дойдёт до 1.0

Показатель версии не всегда показатель качества.

kaktyc ★★★★ ()

Re: Нужно придумать что-то вроде олимпиадной задачи

> Такое иногда бывает на олимпиадах (типа "придумайте алгоритм, находящий кратчайший путь ...") --- придумать-то можно, но всегда найдется тест, для которого условие не будет выполняться.

как это такое может быть? кратчайший путь он или есть, или их несколько, или алгоритм неполиномиальный.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

>Последовательность из англиских букв..

Не удовлетворяет второму условию. Да и первому, похоже (лень разбираться), --- нельзя ее решить "наполовину".

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

> Мне надо что-то такое, что будет _полезно_ человеку, имеющему дело с компом.

не знаю насколько это может быть полезно как "конечный продукт", но вот например такая задача:

имеется директория с файлами; файлы, скажем, текстовые и могут содержать ссылки на другие файлы (например в виде имени файла, отделённого от остального текста пробелами)

требуется вывести файлы в порядке аналогичном make -- т.е. чтобы файл на который ссылаются предшествовал файлу со ссылкой; если есть циклические зависимости -- сообщать об ошибке и показывать подробно весь цикл ссылок (файлы, номера строк)

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

>как это такое может быть? кратчайший путь он или есть, или их несколько, или алгоритм неполиномиальный.

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

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

Или даже по-другому можно задачу сформулировать --- надо найти маршрут от одной точки до другой. И чем он будет меньше --- тем лучше.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

Задача 2:
В длинную деревянную рейку вбили несколько гвоздей,по прямой линии.
Некоторые пары гвоздей связываются веревочками так, чтобы выполнялись
следующие условия:
1) к каждому гвоздю была привязяна хотя бы одна веревочка;
2) сумарная длина веревочек была бы минимально возможной.

написать программу , которая связывает пары гвоздей веревочками как 
описано выше.
Входные данные:
Число гвоздей, их кординаты
Выходные данные;
Мининмальная суммарная длина и пары координат соединяемых гвоздей

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

Задача 3:
Линия называтся уникурсальной, если ее можно начертить, не отрывая
карандаша от бумагы и не проходя два раза одно и то же ребро.
Линии , содержащей N вершин , можно сопоставить квадратную матрицу
 порядка N - матрицу соединений, элемент a(i,j) которой равен 1, 
если вершина i соединена с j некоторым ребром,и 0 в противном случае 
(i,j = 1,2,...,N). 

 Задание: Дана матрица с N вершинами. По матрице программа должна
 выяснить является ли линия уникурсальной и выводить на экран
 последовательность номеров вершин, которые образуют требуемый путь.

Известно, что линия уникурсальна  тогда и только тогда , когда она
 связна и число тех ее вершин , из которых выходит нечетное число
 ребер, не больше двух.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

Товарищ, ну сам подумай. Насколько упростит твою жизнь решение этих задач?

Я ж говорю --- олимпиадные не подходят. А то давно бы что-нибудь выбрал.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

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

это попросту неверное решение, и это не значит что "настоящего" решения вообще не существует.

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

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

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

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

Не берусь оценить сложность такого алгоритма т.к. не представляю его.

>это возможно если граф не задан явным образом

Графа нет. Есть "карта", по которой мы движемся, обходя препятствия.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

Была у нас на городской олимпиаде такие задачки...

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

В 100 этажном здании имеется один лифт. Лифт может двигаться с ускорением a , при чем половину пути между этажами он разгоняется, вторую половину - тормозит. Пользователи вызывают лифт нажатием кнопки с номером этажа (еще до входа в лифт), одновременно несколько человек. Лифт в случайном положении, без движения. спроектировать оптимальную логику работы лифта.

Там еще 8 штук было, но по прошествии 7 лет я их уже не помню (как и решения).

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

> Не берусь оценить сложность такого алгоритма т.к. не представляю его.

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

> Графа нет. Есть "карта", по которой мы движемся, обходя препятствия.

граф надо придумать; например вершины -- возможные положения на карте, рёбра -- возможные переходы.

(не очень понял о какой карте речь, вроде ничего такого не упоминалось)

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

>граф надо придумать; например вершины -- возможные положения на карте, рёбра -- возможные переходы.

Координаты --- числа с плавающей точкой, шаг переменной длины. Вершин бесконечно много, выходит.

>(не очень понял о какой карте речь, вроде ничего такого не упоминалось)

Про граф тоже ничего не было. Речь идет о перемещении робота по обычной поверхности.

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

>где про "робота по поверхности"?

В задаче, в которой требовалось найти путь минимальной длины от точки А до точки Б (первый пост). Видимо, я непонятно выразился.

Блин. Мыслей о самой задаче у меня так и не появилось. А времени почти не осталось..

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

портировать malloc из openbsd в linux, чтобы firefox память системе отдавал. правда, здесь этим уже занимаются...

hatefu1_dead ()

Re: Нужно придумать что-то вроде олимпиадной задачи

Задача составления расписания уроков для классов и преподавателей.

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

Да, для того чтобы им было интересно, эта задача не для человека, а для группы.

Мне кажется, вполне подходит.

// satanic-mechanic

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

господам 'придумавшим задачи' на топологическую сортироку и паросочетания, срочно учить теорию графов и её приложения...

MKuznetsov ★★★★★ ()

Re: Нужно придумать что-то вроде олимпиадной задачи

> господам 'придумавшим задачи' на топологическую сортироку и паросочетания, срочно учить теорию графов и её приложения...

см. выше: "такой сложности, чтобы решить ее особого труда не составляло", "Для школьника должна быть задачка"

а командовать кому что учить будешь у себя в свинарнике

anonymous ()

Re: Нужно придумать что-то вроде олимпиадной задачи

>Это отсекает всякие системы распознавания речи и прочее

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

ival ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.