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

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

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

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

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

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

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

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

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

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

@Puporev · 28.06.2009, 12:19

Понял, это все равно неверное решение.

@Sergei · 28.06.2009, 12:28

А как на счет задачи Эйнштейна кто ее решил или сможет решить???

С одной стороны улицы подряд стоят пять домов, каждый — своего цвета. В каждом живёт человек, все пять — разных национальностей. Каждый человек предпочитает уникальную марку сигарет, напиток и домашнее животное. Кроме того:
Англичанин живёт в красном доме.
Швед держит собаку.
В зелёном доме пьют кофе.
Датчанин предпочитает чай.
Зелёный дом — по соседству слева от белого.
Курильщик «Pall Mall» разводит птиц.
В жёлтом доме курят «Dunhill».
Молоко пьют в доме посередине.
Норвежец живет в первом доме.
Человек, курящий «Marlboro», живёт рядом с хозяином кошки.
Дом, где курят «Dunhill», — рядом с тем, где держат лошадь.
Любитель «Winfield» пьёт пиво.
Немец курит «Rothmans».
Норвежец живёт рядом с синим домом.
Тот, кто курит «Marlboro», живет рядом с тем, кто пьет воду.

Вопрос:
У кого живёт рыбка?

@NuM · 28.06.2009, 12:31

у кого живет рыбка

у немца вроде, очень старая задача

Evg · 28.06.2009, 12:48

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

А как на счет задачи Эйнштейна кто ее решил или сможет решить???

По этому поводу под DOS'ом существовала игрушка Sherlock. Она была обличена в несколько другую графическую форму, но суть именно такая (т.е. логические единицы те же самые). С очки зрения убивалки времени игрушка куда более интересна, чем пасьянсы

@Humanitis · 29.06.2009, 10:17

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

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

Так?

Pascal
1
2
3
4
for i:=1 to 6 do
begin
  writeln((10794 shr i) and 129);
end;

@NuM · 29.06.2009, 11:53

Humanitis,

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

Code
1
2
3
4
5
6
7
for i:=1 to 100 do
begin
  if i mod 2=0 then
    writeln(128)
  else
    writeln(1);
end;

Evg · 29.06.2009, 12:58

NuM, а оригинальный ответ выложи (или в личку кинь)

@NuM · 29.06.2009, 13:10

ответ который я придумал

(127*x)and 129

вот еще одна задачка:
записать функцию abs(x) используя тот же набор операций, желательно использовать как можно меньше операций. решение не должно зависеть от разрядности чисел

Evg · 29.06.2009, 14:28

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

Про abs на форуме уже было

@NuM · 29.06.2009, 14:52

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

Про abs на форуме уже было

можете дать ссылку на тему?

@Phantom · 29.06.2009, 15:03 **[ТС]**

В эту же тему другая задача вспомнилась:

Дано целое положительное число. Определить, является ли оно целой степенью 2, не используя циклов, рекурсий и операций с плавающей точкой.

Так она звучит. Т.е. условия похожи на те как в задачах NuM.

Pascal
1
2
3
4
5
6
7
var x: integer;
begin
  readln(x);
  if (<выражение>) then writeln('является степенью двойки')
  else writeln ('не является степенью двойки');
  sleep(1000);
end.

естественно, по возможности, короче

@NuM · 29.06.2009, 15:08

степень двойки

x and(x-1)=0
но эта задача на мой взгляд является частным случаем задачи "быстро посчитать количество единичных битов в числе"

Evg · 29.06.2009, 15:11

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

можете дать ссылку на тему?

Гоню. Было найти минимальное из двух чисел без использования сравнений. А вот abs использовался в решении. Поискал - найти не смог (хоть убей не помню ни одной ключевой фразы)

@NuM · 29.06.2009, 15:13

вы про ((a+b)-abs(a-b))div 2?
p.s. по поводу abs в формуле нельзя использовать sqrt и другие функции, т.е. решение sqrt(x*x) не подойдет

Evg · 29.06.2009, 15:31

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

вы про ((a+b)-abs(a-b))div 2?

Что-то типа того. Но тогда додумались до решения без abs'а, но при этом учитывалось разрядность числа

Добавлено через 15 минут 28 секунд

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

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

При первом прочтении как-то пропустил. Задачку делал несколько лет назад. Если кому-то надо, вот решение. Хз насколько оно минимальное. Ну и мои тогдашние комментарии

fractal1.c - показан приницп работы. "Нечестность" примера в том,
что строгий стандарт не позволяет энтеры внутри кавычек.

fractal2.c - более честный. Однако тут тоже есть три момента:
1. По стандарту гарантируется правильное построение строковой
константы не более 509 символов - это дело легко исправляется
тем, что убираются лишние пробелы.
2. Используются ASCII-коды в операциях putchar. Не знаю
на сколько это является читом. Может быть тут даже всё честно
3. Под виндами энтер печатается в виде двух символов.
Теоретически можно добавить распознавалку: открывать файл
в режиме "w", записать туда энтер, а потом считать его
в режиме "rb". В зависимости от этого печатать энтер
по-человечески или по виндузовому.

@NuM · 29.06.2009, 16:18

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

Но тогда додумались до решения без abs'а, но при этом учитывалось разрядность числа

кажется нашел ту тему, да если знать разрядность то можно по значению знакового бита найти модуль числа, интерес в том чтобы сделать это же не зная разрядность числа.
p.s. можно использовать только эти операции: +, -, *, div, mod, and, or, xor, not, shr, shl

Evg · 12.08.2009, 12:32

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

Задачку делал несколько лет назад. Если кому-то надо, вот решение. Хз насколько оно минимальное. Ну и мои тогдашние комментарии

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

@snake32 · 12.10.2009, 13:40

Дан массив из N целых чисел 1..M. Все числа разные, кроме двух, т.е. одно число повторяется. Найти это число за время O(N).

PS: Эту задачку предложили решить на тесте - я не справился. Не понял как можно это сделать за один проход.

Evg · 12.10.2009, 13:57

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

Не понял как можно это сделать за один проход.

O(N) НЕ означает за один проход, а означает линейное время по отношению к количеству элементов. Т.е. проходов у тебя может быть и 10 и 20, но их количество не зависит от N. O(N) по большому счёту означает, что циклы по N могут быть только одинарные (т.е. без вложенностей), но количество циклов фиксировано (или их более некотрого константного количества) и не зависит от N

А вот, например, при сортировке пузырьком появляются два вложенных цикла по N, в результате чего алгорим является квадратичным, т.е. O(N^2)

@snake32 · 12.10.2009, 15:57

Не по теме:

Evg, спасибо за пояснение сложности алгоритмов. Все непонятки из-за этого. Где можно почитать про это? В викепедии нифига не понял.

Новые блоги и статьи Все статьи Все блоги /
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .

@Puporev Почетный модератор 64320 / 47616 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	28.06.2009, 12:19
	Понял, это все равно неверное решение. 0

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	28.06.2009, 12:31
	у кого живет рыбка у немца вроде, очень старая задача 0

Evg 21285 / 8310 / 637 Регистрация: 30.03.2009 Сообщений: 22,671 Записей в блоге: 30
	29.06.2009, 12:58
	NuM, а оригинальный ответ выложи (или в личку кинь) 0

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	29.06.2009, 13:10
	ответ который я придумал (127*x)and 129 вот еще одна задачка: записать функцию abs(x) используя тот же набор операций, желательно использовать как можно меньше операций. решение не должно зависеть от разрядности чисел 2

Evg 21285 / 8310 / 637 Регистрация: 30.03.2009 Сообщений: 22,671 Записей в блоге: 30
	29.06.2009, 14:28
	Матчасть с ходу не просёк. Всмысле математически доказать смогу, но на подсознательном уровне задачу не чувствую. Про abs на форуме уже было 0

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	29.06.2009, 15:08
	степень двойки x and(x-1)=0 но эта задача на мой взгляд является частным случаем задачи "быстро посчитать количество единичных битов в числе" 0

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	29.06.2009, 15:13
	вы про ((a+b)-abs(a-b))div 2? p.s. по поводу abs в формуле нельзя использовать sqrt и другие функции, т.е. решение sqrt(x*x) не подойдет 0

@snake32 3599 / 1731 / 236 Регистрация: 26.02.2009 Сообщений: 8,798 Записей в блоге: 5
	12.10.2009, 13:40
	Дан массив из N целых чисел 1..M. Все числа разные, кроме двух, т.е. одно число повторяется. Найти это число за время O(N). PS: Эту задачку предложили решить на тесте - я не справился. Не понял как можно это сделать за один проход. 0

@snake32
	12.10.2009, 15:57
	Не по теме: Evg, спасибо за пояснение сложности алгоритмов. Все непонятки из-за этого. Где можно почитать про это? В викепедии нифига не понял. 0