Сборник задач по C/C++

Обсуждение различной литературы о Linux

Модератор: Модераторы разделов

entada
Сообщения: 223
ОС: Debian stable, IceWM

Re: Сборник задач по C/C++

Сообщение entada »

sash-kan писал(а):
12.02.2012 12:49
entada писал(а):
11.02.2012 22:15
А зачем здесь писать программу?
интересный вопрос, заданный в теме Сборник задач по C/C++

Вопрос был посвящён не всей теме, а конкретной задаче.

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

Данная задача породила программу, как утверждает NickLion, с алгоритмом экспоненциальной сложности (переборным?).
При этом если рассматривать её именно как задачу «на смекалку», правильное решение находится со второго раза (а у более сообразительного человека, чем я, возможно, и с первого), и это решение вроде бы даже можно обосновать и обобщить на случай N игрушек (при этом получается алгоритм линейной сложности, который, опять-таки, можно без проблем реализовать и без компьютера).
Спасибо сказали:
NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

Re: Сборник задач по C/C++

Сообщение NickLion »

sash-kan писал(а):
12.02.2012 12:55
NickLion
не хотите принять участие в ежемесячных конкурсах, которые устраивает _darcus_?
февральский, по-моему, ещё продолжается·

Боюсь ФП не самая моя сильная сторона :) Просто напросто почти не заниался данной темой.

entada писал(а):
12.02.2012 16:57
Мне казалось, что в данной теме логично было бы описывать задачи, которые красиво решаются с помощью программы и не столь красиво — ручным счётом.

Понимаете в чём дело, на малой размерности многие задачи проще решить вручную нежели программно.

entada писал(а):
12.02.2012 16:57
Данная задача породила программу, как утверждает NickLion, с алгоритмом экспоненциальной сложности (переборным?).

Не совсем переборный. Просто пострение пространства поиска, а потом Дейкстра. Примитивное, но рабочее решение.

entada писал(а):
12.02.2012 16:57
При этом если рассматривать её именно как задачу «на смекалку», правильное решение находится со второго раза (а у более сообразительного человека, чем я, возможно, и с первого), и это решение вроде бы даже можно обосновать и обобщить на случай N игрушек (при этом получается алгоритм линейной сложности, который, опять-таки, можно без проблем реализовать и без компьютера).

Вот именно это самое "обосновать" мне делать было лень. А пока решение не доказано, то это ещё не решение. Впрочем, я не отрицаю, что решение оптимальнее пострения состояний существует.
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

NickLion писал(а):
12.02.2012 20:54
Боюсь ФП не самая моя сильная сторона
используйте наиболее удобную вам парадигму·
насколько я помню, _darkus_ ни в одном из конкурсов не сужал требований в отношении парадигмы/языка·
а (по крайней мере) в одном — так даже подчеркнул:
QUOTE (http://users.livejournal.com/_darkus_/592464.html) писал(а):Однако я введу дополнительное условие — расчёт необходимо сделать на своём любимом языке программирования.
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
Hephaestus
Сообщения: 3728
Статус: Многоуважаемый джинн...
ОС: Slackware64-14.1/14.2

Re: Сборник задач по C/C++

Сообщение Hephaestus »

NickLion писал(а):
11.02.2012 15:40
Если предлагается решить, то решил.
Интересно.
Я в уме прикинул - не получилось. Больше 60 минут выходит.
Возможно, я что-то не так понял.
Озвучьте, пожалуйста, Ваш результат.


Stauffenberg писал(а):
10.02.2012 17:19
Игрушка Время
Базз 5 минут
Вуди 10 минут
Рекс 20 минут
Хэмм 25 минут
Суммарное время всех игрушек - 60 минут.
Учитывая, что какая-то игрушка должна пройти больше одного раза - уже больше 60 минут.

Если же проходить будут по две игрушки, то всё равно с учётом возвращений назад - больше 60 минут.
Пускай скрипят мои конечности.
Я - повелитель бесконечности...
Мой блог
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

fflatx
10 минут : базз+вуди→
5 минут : ←базз
25 минут : рэкс+хэмм→
10 минут : ←вуди
10 минут: базз+вуди→
-----
60 минут

но вообще-то нужно написать программу, которая найдёт решение (и, конечно, в общем случае)·

p.s. второй и четвёртый пункты можно поменять местами — суть не изменится·
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

sash-kan писал(а):
02.03.2012 13:28
мартовский конкурс фп·
кстати, принял участие·
отчёт·
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
Stauffenberg
Сообщения: 2041
Статус: ☮ PEACE ☮
ОС: открытая и свободная

Re: Сборник задач по C/C++

Сообщение Stauffenberg »

sash-kan писал(а):
12.03.2012 13:40
sash-kan писал(а):
02.03.2012 13:28
мартовский конкурс фп·
кстати, принял участие·
отчёт·

Вот этот подарок - реальный стимул к победе :)

Изображение

Источник
Labor omnia vincit

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” (Brian Kernighan)
Спасибо сказали:
Аватара пользователя
diesel
Бывший модератор
Сообщения: 5989
ОС: OS X, openSuSE, ROSA, Debian

Re: Сборник задач по C/C++

Сообщение diesel »

Stauffenberg писал(а):
17.04.2012 19:31
sash-kan писал(а):
12.03.2012 13:40
sash-kan писал(а):
02.03.2012 13:28
мартовский конкурс фп·
кстати, принял участие·
отчёт·

Вот этот подарок - реальный стимул к победе :)
...
Источник

надеюсь книжко более удобоваримая для человеков чем предыдущие две книги про Haskell на русском :)
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

Stauffenberg
кстати, если первое моё участие было спонсировано желанием выпендриться «на-баше-рядом-с-дюже-вумнымы-хаскелистами», то следующее участие будет продиктовано желанием получить эту книгу в электронном виде (в бумажном мне книги и даром не нужны, поэтому надеюсь на наличие элверсии)·
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
diesel
Бывший модератор
Сообщения: 5989
ОС: OS X, openSuSE, ROSA, Debian

Re: Сборник задач по C/C++

Сообщение diesel »

sash-kan писал(а):
17.04.2012 23:08
Stauffenberg
кстати, если первое моё участие было спонсировано желанием выпендриться «на-баше-рядом-с-дюже-вумнымы-хаскелистами», то следующее участие будет продиктовано желанием получить эту книгу в электронном виде (в бумажном мне книги и даром не нужны, поэтому надеюсь на наличие элверсии)·

даёшь unixforum team на The ICFP Programming Contest
Спасибо сказали:
Аватара пользователя
Stauffenberg
Сообщения: 2041
Статус: ☮ PEACE ☮
ОС: открытая и свободная

Re: Сборник задач по C/C++

Сообщение Stauffenberg »

sash-kan писал(а):
17.04.2012 23:08
Stauffenberg
кстати, если первое моё участие было спонсировано желанием выпендриться «на-баше-рядом-с-дюже-вумнымы-хаскелистами», то следующее участие будет продиктовано желанием получить эту книгу в электронном виде (в бумажном мне книги и даром не нужны, поэтому надеюсь на наличие элверсии)·

Желаю удачи. Надеюсь, что в случае победы поделитесь эл. версией книги ;)
Мне пока рановато участвовать в конкурсе - все еще знакомлюсь с Common Lisp по книге о Scheme :)
Labor omnia vincit

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” (Brian Kernighan)
Спасибо сказали:
Аватара пользователя
Stauffenberg
Сообщения: 2041
Статус: ☮ PEACE ☮
ОС: открытая и свободная

Re: Сборник задач по C/C++

Сообщение Stauffenberg »

sash-kan
Кстати, Александр. Благодаря Вам (просто ссылка на странцу о конкурсе ФП и несколько постов на форуме) заинтересовался и начал изучать Haskell. Очень много нового сразу (параллельно пытаюсь мастерить на Lisp), к тому же читаю книгу по компиляторам (книга дракона), но очень интересно...
Вроди бы программистом работаю уже не первый год, и знаю "не один" язык программирования, но такое ощущение, что только сейчас начал потихоньку вникать в эту тему. Как я писал до этого? И ведь не просто писал, а отправлял патчи в некоторые проекты... и их даже принимали в основные ветки... сейчас бы я оформил код иначе.
Labor omnia vincit

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” (Brian Kernighan)
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

майский конкурс в разгаре·
моё решение: https://gist.github.com/2606409 (sed+bc+клей из bash-а)

надеюсь, по лаконичности я побью всех хаскелистов как детей (улыбка)
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
Reboot
Сообщения: 321
Статус: Красен глаз -- темна душа

Re: Сборник задач по C/C++

Сообщение Reboot »

sash-kan писал(а):
06.05.2012 04:12
майский конкурс в разгаре·
моё решение: https://gist.github.com/2606409 (sed+bc+клей из bash-а)

надеюсь, по лаконичности я побью всех хаскелистов как детей (улыбка)

Круто =)
Мой компьютер зовут Марвин
Спасибо сказали:
Аватара пользователя
Stauffenberg
Сообщения: 2041
Статус: ☮ PEACE ☮
ОС: открытая и свободная

Re: Сборник задач по C/C++

Сообщение Stauffenberg »

sash-kan писал(а):
06.05.2012 04:12
майский конкурс в разгаре·
моё решение: https://gist.github.com/2606409 (sed+bc+клей из bash-а)

надеюсь, по лаконичности я побью всех хаскелистов как детей (улыбка)

Обеспечивает больше 55%?
Labor omnia vincit

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” (Brian Kernighan)
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current

Re: Сборник задач по C/C++

Сообщение drBatty »

sash-kan
э... я либо что-то не распарсил, либо вопрос довольно тупой... может разъясните, в чём суть?
такие задачи я решаю за деньги, причём с 146% результатом... Данную задачу решить не смог, ибо капчу подбирать мне лень - там оно кривое.
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

Stauffenberg писал(а):
06.05.2012 13:46
Обеспечивает больше 55%?
скрипт выдаёт все сто тысяч чисел·
понятно, что правильность я смог проверить лишь для сотни, может двух (по ходу написания паттернов)·
возможно, где-то будут неправильные решения·
но решены все сто тысяч задач·
drBatty
вот бесплатная ссылка без капчи и эсэмэс: http://barak.in/dl/FPC_May2012_tsk.zip
надеюсь, увидев содержимое файла, вопросы о сути у вас отпадут·
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

краткая суть для остальных:
в файле сто тысяч строк (тот, кому лень скачивать и распаковывать файл, может увидеть примеры по ссылке на условие конкурса
в каждой строке есть два натуральных числа, окружённые словами·
на основании этих слов надо сделать вывод, какое из арифметических действий (+, -, *, /) надо применить к этим двум числам·
это самое главное, ибо правильный порядок операндов для вычитания и деления определить элементарно: слева должно быть большее из двух чисел·
вытаскивает из строки числа и определяет, какое действие требуется, gnu sed·
меняет местами операнды (при необходимости) и производит арифметическое действие gnu bc·
а gnu bash просто связывает их воедино·
вот такая суть…
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
Stauffenberg
Сообщения: 2041
Статус: ☮ PEACE ☮
ОС: открытая и свободная

Re: Сборник задач по C/C++

Сообщение Stauffenberg »

sash-kan писал(а):
06.05.2012 04:12
надеюсь, по лаконичности я побью всех хаскелистов как детей (улыбка)

Вне всяких сомнений.
Главное теперь, чтобы эти хаскелисты не побили Вас по функциональности ;)
Labor omnia vincit

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” (Brian Kernighan)
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

Stauffenberg писал(а):
06.05.2012 18:57
sash-kan писал(а):
06.05.2012 04:12
надеюсь, по лаконичности я побью всех хаскелистов как детей (улыбка)

Вне всяких сомнений.
Главное теперь, чтобы эти хаскелисты не побили Вас по функциональности ;)
а не выйдет!
функциональщина — это лишь подвид декларативщины (wikipedia://declarative programmin
так что мы ещё посмотрим, кто главнее — gnu sed или microsoft haskell !

(улыбка)
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

sash-kan писал(а):
06.05.2012 04:12
моё решение: https://gist.github.com/2606409
дополнил комментариями, кратко поясняющими суть работы скрипта·
первоначальное лаконичное решение конечно же всё ещё доступно: https://gist.github.com/2606409/6bc1b0b8ee5...c4ff6877ce846b4
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
Stauffenberg
Сообщения: 2041
Статус: ☮ PEACE ☮
ОС: открытая и свободная

Re: Сборник задач по C/C++

Сообщение Stauffenberg »

Я в шоке от результатов...
Labor omnia vincit

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” (Brian Kernighan)
Спасибо сказали:
Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current

Re: Сборник задач по C/C++

Сообщение drBatty »

sash-kan
ну решённую задачу я уже и не буду решать. Могу только сказать, что я решил-бы её также.


ЗЫЖ для тех, кто мне скажет "спервадобейся" есть таки http://drbatty.ru/sed/ch04.html
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

Stauffenberg писал(а):
11.05.2012 02:40
Я в шоке от результатов
в чём шок?
мой прогноз про лаконичность (в отношении haskell) полностью подтвердился·
по краткости сопоставимо лишь ещё одно решение на sed (но там, как мне кажется, очень неэлегантно вклинен awk с четырьмя клаузами)·
все остальные обременены как минимум вагоном языковых конструкций·
а как максимум, просто являются километровыми наборами if-then-else·

p.s. я, как один из участников, конечно, пристрастен·
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
Crazy
Сообщения: 862
Статус: Адепт Дзен.
ОС: Mint, Win7.

Re: Сборник задач по C/C++

Сообщение Crazy »

sash-kan писал(а):
11.05.2012 11:07
а как максимум, просто являются километровыми наборами if-then-else·

а как же pattern matching?

Desipere in loco
Спасибо сказали:
Аватара пользователя
Stauffenberg
Сообщения: 2041
Статус: ☮ PEACE ☮
ОС: открытая и свободная

Re: Сборник задач по C/C++

Сообщение Stauffenberg »

sash-kan писал(а):
11.05.2012 11:07
Stauffenberg писал(а):
11.05.2012 02:40
Я в шоке от результатов
в чём шок?
мой прогноз про лаконичность (в отношении haskell) полностью подтвердился·
по краткости сопоставимо лишь ещё одно решение на sed (но там, как мне кажется, очень неэлегантно вклинен awk с четырьмя клаузами)·
все остальные обременены как минимум вагоном языковых конструкций·
а как максимум, просто являются километровыми наборами if-then-else·

Так вот и я о том. Более короткого решения никто не предложил, но в комментах почему-то про короткое решение говорят о других участниках и голосуют как за "самое короткое решение" за других.
В общем, не понятно мне... :umnik2:
Labor omnia vincit

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.” (Brian Kernighan)
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

Stauffenberg писал(а):
11.05.2012 16:53
sash-kan писал(а):
11.05.2012 11:07
Stauffenberg писал(а):
11.05.2012 02:40
Я в шоке от результатов
в чём шок?
мой прогноз про лаконичность (в отношении haskell) полностью подтвердился·
по краткости сопоставимо лишь ещё одно решение на sed (но там, как мне кажется, очень неэлегантно вклинен awk с четырьмя клаузами)·
все остальные обременены как минимум вагоном языковых конструкций·
а как максимум, просто являются километровыми наборами if-then-else·

Так вот и я о том. Более короткого решения никто не предложил, но в комментах почему-то про короткое решение говорят о других участниках и голосуют как за "самое короткое решение" за других.
В общем, не понятно мне... :umnik2:
ну, наверно я перестарался·
в своём комменте я написал, что первоначальная версия доступна по такой-то ссылке, а текущая версия — с комментариями, объясняющими суть·
но в итоговой таблице ссылка на последний коммит, и длиннющие комментарии (которые я и добавил-то, чтоб заработать лишних очков) создают иллюзию «ой, очень длинно»·
в общем, перестарался…
не надо было комментариев вставлять — никто из участников этого не сделал, а оценщики, видимо, не оценили…
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:
Аватара пользователя
sash-kan
Администратор
Сообщения: 13939
Статус: oel ngati kameie
ОС: GNU

Re: Сборник задач по C/C++

Сообщение sash-kan »

узнал вовремя про августовский конкурс и, поучаствовав, занял почётное второе место·
первым (неозвученным в задании) ключевым критерием оказалась реализация на prolog-е·
тем более радует, что я с gnu make-ом втиснулся между двумя prolog-овыми решениями·
благодарить следует gnu make, который позволил использовать кириллические имена (это второй неозвученный критерий)·

p.s. кстати, всё-таки, к чему ближе язык make-файлов — к функциональной или к логической парадигме?

p.p.s. ещё кстати: те решения, которые заняли 5-е - 17-е места, участвуют в конкурсе зрительских симпатий·
смотрите их код (ссылка в графе «язык») и голосуйте!
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали: