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

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

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

Аватара пользователя
Veonos
Сообщения: 54
ОС: Gentoo

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

Сообщение Veonos »

Посоветуйте плз. Заранее благодарен.
Спасибо сказали:

Konstantyn
Сообщения: 47
ОС: Gentoo Linux 2008.0

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

Сообщение Konstantyn »

М.В. Мозговой - 85 нетривиальных проектов, решений и задач.djvu
иСКУССТВО ПРОГРАММИРОВАНИЯ гЕРБЕРТ шИЛДТ :crazy:
мерзкий тип....
Спасибо сказали:

Аватара пользователя
wzrd
Сообщения: 323
ОС: Debian Lenny

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

Сообщение wzrd »

задачи не зависят от языка. разве что на каждом языке можно по своему написать. если вы хотите закрепить знания языка, то возмите кернигана и ритчи, там после каждой главы (или пункта) есть простенькие упражнения. а если вы хотите что-то более сложное, то подойдут олимпиадные задачи. вот то что вам надо.
Спасибо сказали:

Konstantyn
Сообщения: 47
ОС: Gentoo Linux 2008.0

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

Сообщение Konstantyn »

Да олимпиадные задачи то что надо а приложить пару книжек варезных это не противоречит правилам форума?)Могу приложить)Помню хорошее время было школа) задачи :mellow:
мерзкий тип....
Спасибо сказали:

Аватара пользователя
Veonos
Сообщения: 54
ОС: Gentoo

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

Сообщение Veonos »

Konstantyn, wzrd большущее спасибо!
Konstantyn, к сожалению прротиворечит :( Но зато можно слать в приват :) Если пошлете - буду очень благодарен :)
wzrd, просто хотелось бы на всякий случай что бы были и решения.
Спасибо сказали:

Konstantyn
Сообщения: 47
ОС: Gentoo Linux 2008.0

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

Сообщение Konstantyn »

Veonos писал(а):
27.05.2008 00:17
Konstantyn, wzrd большущее спасибо!
Konstantyn, к сожалению прротиворечи{т :( Но зато можно слать в приват :) Если пошлете - буду очень благодарен :)
wzrd, просто хотелось бы на всякий случай что бы были и решения.

Хорошо пришю но утром уже у меня на отрубленом винте всё если найду то там с рашеними в общем всё бенч
мерзкий тип....
Спасибо сказали:

Konstantyn
Сообщения: 47
ОС: Gentoo Linux 2008.0

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

Сообщение Konstantyn »

Размер файлов большой слишком в личку напиши мне мыло я тебе на мыло кину,Нашёл книжки класные очень
мерзкий тип....
Спасибо сказали:

Аватара пользователя
MadDog
Бывший модератор
Сообщения: 2298
Статус: Добрый банщик

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

Сообщение MadDog »

Konstantyn писал(а):
26.05.2008 23:56
а приложить пару книжек варезных
Сейчас как приложу... мало не покажется.

Тема закрыта.

UPD. По просьбе топикстартера Veonos'а тему открываю, но до первого рецидива с последующей раздачей плюшек. Так же напоминаю, что личную переписку (аська не работает и т.п.) переносите в личку.
MadDog's Blog
Внимательно читать: Как правильно задавать вопросы
No fate but what we make
Спасибо сказали:

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

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

Сообщение Stauffenberg »

Кто может еще что-нибудь посоветовать, кроме 2х уже упомянутых?

* М.В. Мозговой - 85 нетривиальных проектов, решений и задач
* ИСКУССТВО ПРОГРАММИРОВАНИЯ ГЕРБЕРТ ШИЛДТ

Не обязательно C/С++. Просто задачники по программированию.
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)
Спасибо сказали:

sciko
Сообщения: 1744
Статус: Ъ-участник
ОС: Debian/Ubuntu/etc

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

Сообщение sciko »

Stauffenberg писал(а):
10.01.2012 18:24
Кто может еще что-нибудь посоветовать, кроме 2х уже упомянутых?
Выбираешь любой opensource проект, идёщь в раздел ToDo и вот они! А ещё тебе решение этих задачек проверят, когда будешь патч возвращать.
Спасибо сказали:

Аватара пользователя
Stauffenberg
Сообщения: 2023
Статус: ☮ 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)
Спасибо сказали:

NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

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

Сообщение NickLion »

Stauffenberg
Какого уровня задачки? Для учащегося программированию или для развития навыка алгоритмизации?
Спасибо сказали:

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

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

Сообщение Stauffenberg »

NickLion
Скорее для развития навыков алгоритмизации. Интересует все, что делает из программиста... хорошего программиста ;)
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)
Спасибо сказали:

inhabt
Сообщения: 13

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

Сообщение inhabt »

Кто может еще что-нибудь посоветовать, кроме 2х уже упомянутых?

* М.В. Мозговой - 85 нетривиальных проектов, решений и задач
* ИСКУССТВО ПРОГРАММИРОВАНИЯ ГЕРБЕРТ ШИЛДТ

Не обязательно C/С++. Просто задачники по программированию.

Как насчёт этого: Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 2004?
Спасибо сказали:

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

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

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

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

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

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

Сообщение Stauffenberg »

sash-kan писал(а):
11.01.2012 17:23
Stauffenberg писал(а):
10.01.2012 20:22
Скорее для развития навыков алгоритмизации. Интересует все, что делает из программиста... хорошего программиста
Кнута не предлагать?

Уже читаю. Вчера нашел. Все равно спасибо ;)
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)
Спасибо сказали:

FlySnake
Сообщения: 992
ОС: openSUSE

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

Сообщение FlySnake »

Stauffenberg писал(а):
10.01.2012 20:22
NickLion
Скорее для развития навыков алгоритмизации. Интересует все, что делает из программиста... хорошего программиста ;)

Задача:
На вход (read() по 1 байту из некого места) приходит 1 байт. Этот байт - последовательность битов, захваченная на неком последовательном интерфейсе. Нужно набирать приходящие байты в буфер и находить в нём последовательность 01111110. Как только эта последовательность найдена - начинать запись данных в массив. Передача побитная, но биты упакованы в байты и передаются просто последовательно без разбора. Граница байт данных не обязательно совпадает с принятым по read() байтом. Как только снова попалась последовательность 01111110 - прекратить запись, поставить флаг завершения приёма, записать массив принятого и его длину в FIFO. Максимальная длина сообщения для записи - 32 байта. В сообщении не допускается больше 5 единиц подряд. Если оказалось больше 5 единиц или длина превысила 32 байта - "сбросить гистерезис", т.е. если был принят байт 01111110 и начали запись данных, но в процессе обнаружили нарушение ограничений на длину сообщения или более 5 единиц - значит этот байт был не началом нового сообщения, а концом предыдущего и соответственно следующий такой байт будет означать не конец текущего сообщения (не верного), а начало следующего. Приём данных синхронный, чтение из FIFO асинхронное. Фишка в том, что байт начала/конца сообщения 01111110 не обязательно придёт целым байтом, т.е. это может быть 2 байта: 11110111 11101111 . У них в серединке образовалась нужная последовательность, при этом 4 бита на хвосте второго байта - это уже данные, и все остальные данные из этого сообщения будут сдвинуты на 4 бита. Т.е. если следующий байт был 0001011, то собственно байт, который нужно записать в массив на 0 позицию будет 11110001 - 4 младших бита от предыдущего байта и 4 старших битов от текущего байта. Байты данных передаются начиная с младшего бита, т.е. в данном примере в массив нужно записать не 11110001, а 1000111 - перевернули порядок битов. Символы начала/конца (01111110) могут идти подряд без промежутков один за другим или с произвольными промежутками. Допускается использовать только логику и сдвиги, никаких memmem() и аналогичного.

Возможное решение: биты буферизуем в uint16_t, затем в цикле по i от 0 двигаем этот uint16 на i вправо и сравниваем с символом начала/конца. как только совпало - запоминаем i, возвращаемся к исходному буферу и запоминаем биты что правее (16-i) - это начало данных, вычисляем сколько бит от следующего принятого байта пристыковать для получения байта данных, сдвиг, лог. или, запись в массив. etc. Кто скажет как эффективнее/проще/лучше это сделать тот молодец :)
Спасибо сказали:

NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

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

Сообщение NickLion »

Ну, если речь о классических книгах, то естественно стоит упомянуть Кормена (ссылка на озон - так все реквизиты, у меня правда бумажная версия похожа на вот эту, но более поздняя). Очень приятная книга и в конце каждой темы есть задачки для решения. Также есть сайтики с олимпиадными задчками - поворочать мозги подходят - http://acm.timus.ru/, есть ещё классический http://acm.uva.es/problemset/, но там сейчас белиберда какая-то :)
Спасибо сказали:

Аватара пользователя
bormant
Сообщения: 1336

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

Сообщение bormant »

Вот тут можно чего-нибудь порешать: http://www.diofant.ru/
Спасибо сказали:

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

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

Сообщение Stauffenberg »

FlySnake писал(а):
11.01.2012 21:30
Stauffenberg писал(а):
10.01.2012 20:22
NickLion
Скорее для развития навыков алгоритмизации. Интересует все, что делает из программиста... хорошего программиста ;)

Задача:
На вход (read() по 1 байту из некого места) приходит 1 байт. Этот байт - последовательность битов, захваченная на неком последовательном интерфейсе. Нужно набирать приходящие байты в буфер и находить в нём последовательность 01111110. Как только эта последовательность найдена - начинать запись данных в массив. Передача побитная, но биты упакованы в байты и передаются просто последовательно без разбора. Граница байт данных не обязательно совпадает с принятым по read() байтом. Как только снова попалась последовательность 01111110 - прекратить запись, поставить флаг завершения приёма, записать массив принятого и его длину в FIFO. Максимальная длина сообщения для записи - 32 байта. В сообщении не допускается больше 5 единиц подряд. Если оказалось больше 5 единиц или длина превысила 32 байта - "сбросить гистерезис", т.е. если был принят байт 01111110 и начали запись данных, но в процессе обнаружили нарушение ограничений на длину сообщения или более 5 единиц - значит этот байт был не началом нового сообщения, а концом предыдущего и соответственно следующий такой байт будет означать не конец текущего сообщения (не верного), а начало следующего. Приём данных синхронный, чтение из FIFO асинхронное. Фишка в том, что байт начала/конца сообщения 01111110 не обязательно придёт целым байтом, т.е. это может быть 2 байта: 11110111 11101111 . У них в серединке образовалась нужная последовательность, при этом 4 бита на хвосте второго байта - это уже данные, и все остальные данные из этого сообщения будут сдвинуты на 4 бита. Т.е. если следующий байт был 0001011, то собственно байт, который нужно записать в массив на 0 позицию будет 11110001 - 4 младших бита от предыдущего байта и 4 старших битов от текущего байта. Байты данных передаются начиная с младшего бита, т.е. в данном примере в массив нужно записать не 11110001, а 1000111 - перевернули порядок битов. Символы начала/конца (01111110) могут идти подряд без промежутков один за другим или с произвольными промежутками. Допускается использовать только логику и сдвиги, никаких memmem() и аналогичного.




Базз, Вуди, Рекс и Хэмм убегают от Зурга (это персонажи из мультфильма «Игрушечная история 2» (Toy Story 2)). . Им осталось лишь перейти последний мост, и они будут свободны. Однако мост очень ветхий и сможет одновременно выдержать только двух из них. Также, чтобы перейти мост и не попасть в ловушки и ямы в нём, нужен фонарик. Проблема в том, что у наших четырёх друзей всего один фонарик, а заряда батареи в нём осталось лишь на 60 (шестьдесят) минут. Игрушкам требуется различное время, чтобы перейти мост в одну сторону:

Код: Выделить всё

Игрушка      Время
Базз         5 минут
Вуди         10 минут
Рекс         20 минут
Хэмм         25 минут
Так как одновременно на мосту могут находиться только две игрушки, они не могут перейти мост сразу все вместе. Поскольку для перехода через мост им нужен фонарик, кому-то из двоих, перешедших через мост, нужно будет вернуться к оставшимся игрушкам, чтобы отдать им фонарик.

Итак, задача такова: в каком порядке эти четыре игрушки должны пересечь мост (затратив не более 60 минут), чтобы спастись от Зурга?
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
fprog.ru почитываем?
_darkus_ из lj почитайте — у него и ежемесячные конкурсы есть, с призами·
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:

Аватара пользователя
drBatty
Сообщения: 8735
Статус: GPG ID: 4DFBD1D6 дом горит, козёл не видит...
ОС: Slackware-current

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

Сообщение drBatty »

нужна коллекция из N эл-тов.
1. время поиска уникального эл-та O(log(N))
2. время вставки/удаления O(log(N))
Дополнительное условие: все элементы упорядочены, т.е. всегда определено соотношение E(j) >= E(k). По этой причине все эл-ты можно "пронумеровать", и обойти по порядку, от самого "малого", до самого "большого".
Требуется за время O(log(N)) отыскать эл-т с заданным номером в этой последовательности. (естественно п1 и п2 не должны пострадать, и остаются в силе)

Число N не должно быть искусственно ограничено.
http://emulek.blogspot.ru/ Windows Must Die
Учебник по sed зеркало в github

Скоро придёт
Осень
Спасибо сказали:

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

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

Сообщение Stauffenberg »

sash-kan писал(а):
10.02.2012 18:21
Stauffenberg
fprog.ru почитываем?

Это один из моих любимых русскоязычных журналов :happy:
Жду 8 номера.

sash-kan писал(а):
10.02.2012 18:21
_darkus_ из lj почитайте — у него и ежемесячные конкурсы есть, с призами·

Ну раз даже с призами, то конечно стоит заглянуть :)
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)
Спасибо сказали:

NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

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

Сообщение NickLion »

Stauffenberg писал(а):
10.02.2012 17:19
Итак, задача такова: в каком порядке эти четыре игрушки должны пересечь мост (затратив не более 60 минут), чтобы спастись от Зурга?

Если предлагается решить, то решил. Решение и ответ интересует или просто для разминки? :)
Спасибо сказали:

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

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

Сообщение entada »

Почему же это задача по программированию?
Скорее — задача на смекалку.
Спасибо сказали:

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

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

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

NickLion писал(а):
11.02.2012 15:40
Если предлагается решить, то решил
на c или на c++?

entada писал(а):
11.02.2012 20:10
Почему же это задача по программированию?
Скорее — задача на смекалку.
считаете, что для написания программы достаточно лишь смекалки?
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:

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

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

Сообщение entada »

sash-kan писал(а):
11.02.2012 21:21
считаете, что для написания программы достаточно лишь смекалки?

А зачем здесь писать программу?
Разве только для проверки решения — но для этого достаточно либо калькулятора, либо клочка бумаги (смотря что окажется рядом).
Спасибо сказали:

NickLion
Сообщения: 3408
Статус: аватар-невидимка
ОС: openSUSE Tumbleweed x86_64

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

Сообщение NickLion »

sash-kan писал(а):
11.02.2012 21:21
на c или на c++?

Угу, на C++, хотя почти на Си решение есть.

entada писал(а):
11.02.2012 22:15
А зачем здесь писать программу?
Разве только для проверки решения — но для этого достаточно либо калькулятора, либо клочка бумаги (смотря что окажется рядом).

Решение в виде программы отличается тем, что оно универсально. Например, то, что я накалякал почти не задумываясь спокойно находит минимальное затрачиваемое время и сам способ для любого числа "игрушек". Ну, правда там экспоненциально растёт число состояний для поиска, поэтому без применения эвристик где-то до 19-20 за разумное время ещё считать будет, дальше и память и время слишком требует. Хотя если подумать, то может и проще решение найдётся. Но лень.
Спасибо сказали:

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

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

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

entada писал(а):
11.02.2012 22:15
А зачем здесь писать программу?
интересный вопрос, заданный в теме Сборник задач по C/C++
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали:

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

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

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

NickLion
не хотите принять участие в ежемесячных конкурсах, которые устраивает _darcus_?
февральский, по-моему, ещё продолжается·
Писать безграмотно - значит посягать на время людей, к которым мы адресуемся, а потому совершенно недопустимо в правильно организованном обществе. © Щерба Л. В., 1957
при сбоях форума см.блог
Спасибо сказали: