Нетривиальные задачи по программированию

@Phantom · Регистрация: 29.12.2008

Студворк — интернет-сервис помощи студентам

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

Чтобы не было флуда и беспорядка, попробую набросать правила топика:
* Задача должна быть действительно оригинальной и интересной, своеобразной головоломкой.
* Автор, который публикует задачу, должен располагать её решением.
* Решение задачи не должно быть слишком большим, а задача - слишком трудоемкой и требующей много времени.
* Допускаются известные и классические задачи.
* Публиковать любые решения в топике только под тегом CUT.

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

#0. Поменять значения двух целочисленных переменных одного типа, не используя дополнительной переменной.

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

#2 Вводятся три числа A, B и C. Нужно распечатать их по убыванию. В программе использовать только один оператор switch и ничего больше.

первая взята с форума, вторая здесь, третья моя, недавно родилась, позабавил друзей.

@snake32 · 01.02.2010, 13:52

Jekidollar, по-моему результат зависит от настроек оптимизатора. Стараюсь таких "запутанных" ситуаций избегать.
Может ошибаюсь.... поправте если так.

Evg · 01.02.2010, 13:53

Сообщение от snake32

Jekidollar, по-моему результат зависит от настроек оптимизатора. Стараюсь таких "запутанных" ситуаций избегать.

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

@snake32 · 01.02.2010, 13:58

Не по теме:

Подобную задачу давали мне на собеседовании в NIX. В тот раз я не угадал =)

Day · 01.02.2010, 14:12

В математике есть деление нацело с остатком и деление действительных чисел. Это две разные операции. Остальных атрибутов деление в математике не имеет.

Увы, в математике есть самые разнообразные объекты - поля и кольца.
И в этих объетах определяются свои операции - лишь бы они удовлетворяли аксиоматике

@Dimazzzzzz · 19.11.2010, 02:45

C++
1
2
3
int i = 5; 
i = ++i + ++i;
i = ?

Сообщение от snake32

Подобную задачу давали мне на собеседовании в NIX

Вставил это в программу - всё равно не пойму результат. Поэтому думаю вопрос в другом: стоит ли писать так? Если мне бы задали такое на собеседовании, я бы сильно удивился вопросу. Думаю, гораздо проще разделить эти операции (хотя в реальности они все равно будут сильно разделены друг от друга), чтобы потом неделями не ползать по всему коду и не искать еле уловимый баг.
А то великий и могучий Си-шный язык может позволить написать многое, только как потом читать такую программу самому программеру. Из "истории" создания языка: Затем Деннис и Брайан разработали по-настоящему извращенный диалект Паскаля, назвав его "A". Когда мы обнаружили, что другие действительно пытаются писать программы на A, мы быстро добавили еще парочку хитрых примочек, создав B, BCPL, и, наконец, Си. Мы остановились, добившись успешной компиляции следующего:

C
1
for(;P("\n"),R-;P("|"))for(e=C;e-;P("_"+(*u++/8)%2))P("| "+(*u/4)%2);

Добавлено через 15 минут
И еще одна маленькая цитата из вики:

Керниган говорит: «Си — инструмент, острый, как бритва: с его помощью можно создать и элегантную программу, и кровавое месиво»

@CyBOSSeR · 19.11.2010, 08:27

Сообщение от Dimazzzzzz

C++
1
2
3
int i = 5;
i = ++i + ++i;
i = ?

Dimazzzzzz, этот код приводит к undefined behavior - переменная i модифицируется более одного раза не переходя через точку следования. Подробнее здесь.
Поэтому ничего удивительного в этом вопросе нет - либо ты знаешь о точках следованиях, либо нет.

@taras atavin · 08.12.2010, 07:19

Сообщение от Phantom

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

PureBasic
1
10 LIST

23.01.2011, 10:43

На экзамене мне преподаватель озадачил такой задачей: "Даны два заполненных стэка неизвестно чем и каким количеством, еще дан пустой стэк. Нужно с помощью этого буферного стэка и операций Push, Pop и "Пуст ли стэк" (типа условие выхода для стэка. У меня эта процедура реализована с помошью "Stack.Count!=0") поменять местами содержимое заполненных стэков не нарушая порядок и не используя переменные."

Решение я выложил тут... однако правильный ответ по мнению препода "Решения нет!"

Комментарий модератора

Ссылка на форум удалена

@Xero201 · 30.01.2011, 23:54

Evg, я тоже был "рад" твоей задачке с 1,4,5,6. Удалось решить только когда пошел в атаку по следующему принципу:

Принцип решения

раз Evg не постеснялся дать такую задачу, значит решений типа:
a+b+c+d
a*b+c*d
a*b*c+d
(a*b+c)*d
быть не может, а может быть только какой-нибудь заковыристый вариант.
Таких вариантов придумал только два:
(a/b+c)*d = (ad+bcd)/b
и
a/(b+c/d) = (ad)/(bd+c)
более заковырестых выражений просто нет)), т.к. аппликации типа "возведение в степень", видел что не прокатывают))
не знаю почему, но я был уверен, что решение кроется в первом варианте и мусолил его довольно долго. А потом, присмотревшись ко второму понял, что ad очень похоже на 6*4, а нижнее выражение вполне может дать единицу. Подобрать соответствие по формуле совсем не трудно:
В числителе должно быть 6*4, т.е. единицей может быть либо "b", либо "c"
Если с=1, то знаменатель просто не получится сократить => b=1 => c=5

И еще, Sherlok - forever!)

Пополню коллекцию такой задачкой:

На встречу друг другу катятся шарики (13 слева и 17 справа). Расстояние между шариками одинаковое. Столкновение абсолютно упруго и мгновенно (ну без всяких там физических подковырок короче). Нужно посчитать количество всех столкновений до того, как шарики разойдутся (задача имеет эвристическое решение).

@Козырь · 01.09.2012, 09:06

задача про шарики:

hide

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

@Phantom · 08.12.2012, 14:16 **[ТС]**

Не знаю, понравится или нет, просто в голову пришло:

C++
1
2
3
4
5
6
void main()
{   
    int massiv(3);
                                            // < написать тут один оператор, ...
    std::cout<<massiv[i];       // < чтобы здесь вывелось, например, 31337
}

Evg · 08.12.2012, 14:54

ы?

C
1
int i = ((massiv[0] = 31337) - 31337);

@Phantom · 08.12.2012, 15:33 **[ТС]**

Evg,
Если честно, под рукой нет любимой студии или другой IDE, но на их месте я бы сказал что-то вроде "subscript requires array or pointer type"

Скорее всего - неверно, приду - проверю.

Evg · 08.12.2012, 17:55

Блин, я думал там квадратные скобки в описании massiv, а там круглые...

@Somebody · 08.12.2012, 20:01

Сообщение от Phantom

void main()

Даже тут void main...

Типа того?

C++
1
unsigned i[] = {0, 0, 0, 31337};

@Phantom · 08.12.2012, 21:08 **[ТС]**

Somebody, да, типа того. Всё верно.

Не по теме:

Сообщение от Somebody

Даже тут void main...

Да, детишки, не пишите никогда void main. Эта конструкция характеризуется unidentified behavior, теоретически роняет скрипты, вызывающие программу, делает софт непереносимым, противоречит пункту 3.6.2 стандарта и заставляет дядю Бьёрна икать. Для войдмейнщиков уготован специальный котел в аду.

@ExpressS · 15.12.2012, 19:51

Сообщение от Evg

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

Наиболее часто задаваемые вопросы:

Q: а точно должно получиться 24?
A: да

Q: а в условии задачи нет ошибок?
A: нет

Q: а задача решается?
A: да

скажите ответ
вот что мне пришло на ум
1/5+6*4

Evg · 16.12.2012, 12:38

Сообщение от ExpressS

скажите ответ
вот что мне пришло на ум
1/5+6*4

Нетривиальные задачи по программированию

@korvin_ · 18.12.2012, 21:45

А вот так можно:

Кликните здесь для просмотра всего текста

65-41

? ^_^

Evg · 19.12.2012, 14:00

Сообщение от korvin_

А вот так можно

В задаче написано "даны числа" (а не цифры)

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

@snake32 3586 / 1716 / 236 Регистрация: 26.02.2009 Сообщений: 8,685 Записей в блоге: 5
	01.02.2010, 13:52
	Jekidollar, по-моему результат зависит от настроек оптимизатора. Стараюсь таких "запутанных" ситуаций избегать. Может ошибаюсь.... поправте если так. 0

@snake32
	01.02.2010, 13:58
	Не по теме: Подобную задачу давали мне на собеседовании в NIX. В тот раз я не угадал =) 0

@Козырь 39 / 38 / 6 Регистрация: 11.05.2010 Сообщений: 141
	01.09.2012, 09:06
	задача про шарики: hide Видимо решение задачи, простое умножение кол-ва шариков слева на их кол-во справа. Полноценного доказательства у меня нет, но это работает, когда шариков 1,2,3 на любой из сторон. А когда происходит соударение, ситуация начинает приближаться к более простой. 0

@Phantom 3189 / 869 / 39 Регистрация: 29.12.2008 Сообщений: 951
	08.12.2012, 15:33 [ТС]
	Evg, Если честно, под рукой нет любимой студии или другой IDE, но на их месте я бы сказал что-то вроде "subscript requires array or pointer type" Скорее всего - неверно, приду - проверю. 0

Evg 21282 / 8307 / 637 Регистрация: 30.03.2009 Сообщений: 22,669 Записей в блоге: 30
	08.12.2012, 17:55
	Блин, я думал там квадратные скобки в описании massiv, а там круглые... 0

@korvin_ 4576 / 2775 / 491 Регистрация: 28.04.2012 Сообщений: 8,782
	18.12.2012, 21:45
	А вот так можно: Кликните здесь для просмотра всего текста 65-41 ? ^_^ 0