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

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

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

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

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

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

Факультативно, ради интереса.

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

задача не моя - была както на лекции по логике

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

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

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

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

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

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

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

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

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

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

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

=)))))))))))

Он что едет, по дороге находит пакеты, останавливается и сливает в них бензин?

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

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

т.е. не находит, а в свои сливает. Он чо бензин продает?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

> Речь идет о перемещении робота по обычной поверхности.

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

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

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

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

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

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

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

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

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

// satanic-mechanic

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

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

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

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

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

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