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

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

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

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

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

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

@NuM · 29.06.2009, 11:53

Humanitis,

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

Код

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

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, спасибо за пояснение сложности алгоритмов. Все непонятки из-за этого. Где можно почитать про это? В викепедии нифига не понял.

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

@Sergei 1513 / 780 / 103 Регистрация: 22.04.2008 Сообщений: 1,610
	28.06.2009, 12:28	42
	А как на счет задачи Эйнштейна кто ее решил или сможет решить??? С одной стороны улицы подряд стоят пять домов, каждый — своего цвета. В каждом живёт человек, все пять — разных национальностей. Каждый человек предпочитает уникальную марку сигарет, напиток и домашнее животное. Кроме того: Англичанин живёт в красном доме. Швед держит собаку. В зелёном доме пьют кофе. Датчанин предпочитает чай. Зелёный дом — по соседству слева от белого. Курильщик «Pall Mall» разводит птиц. В жёлтом доме курят «Dunhill». Молоко пьют в доме посередине. Норвежец живет в первом доме. Человек, курящий «Marlboro», живёт рядом с хозяином кошки. Дом, где курят «Dunhill», — рядом с тем, где держат лошадь. Любитель «Winfield» пьёт пиво. Немец курит «Rothmans». Норвежец живёт рядом с синим домом. Тот, кто курит «Marlboro», живет рядом с тем, кто пьет воду. Вопрос: У кого живёт рыбка? 0

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

Evg 21280 / 8304 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	28.06.2009, 12:48	44
	Сообщение от Sergei А как на счет задачи Эйнштейна кто ее решил или сможет решить??? По этому поводу под DOS'ом существовала игрушка Sherlock. Она была обличена в несколько другую графическую форму, но суть именно такая (т.е. логические единицы те же самые). С очки зрения убивалки времени игрушка куда более интересна, чем пасьянсы 0

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	29.06.2009, 11:53	46
	Humanitis, оригинально, я до такого не додумался, могу предложить тогда решить задачу в более общем случае, когда размеренности не хватит т.е. задание то же, но начальный код Код for i:=1 to 100 do begin if i mod 2=0 then writeln(128) else writeln(1); end; 0

@Phantom 3189 / 870 / 39 Регистрация: 29.12.2008 Сообщений: 952
		1
	Нетривиальные задачи по программированию 17.06.2009, 21:49. Показов 121412. Ответов 132 Метки нет (Все метки) Наверное каждый из нас сталкивался с нетривиальными задачами (на олимпиадах, в Интернете, подкидывали друзья, может у кого-то родилась своя). Речь идет не о каких-то сложных задачах, а о интересных головоломках, которые решались бы с помощью какого-нибудь нетривиального трюка, требовали соображалки и вызывали бы интерес и улыбку. Эти задачи не забываются и я предлагаю вспомнить и выложить их здесь. Таким образом, возможно, соберется небольшой "задачник" для уважаемых форумчан. Это будет полезно. Каждый сможет размять мозг и проверить знания, решая такие задачки. В конце концов это просто забавно Чтобы не было флуда и беспорядка, попробую набросать правила топика: * Задача должна быть действительно оригинальной и интересной, своеобразной головоломкой. * Автор, который публикует задачу, должен располагать её решением. * Решение задачи не должно быть слишком большим, а задача - слишком трудоемкой и требующей много времени. * Допускаются известные и классические задачи. * Публиковать любые решения в топике только под тегом CUT. Начну пожалуй с задачи, которая уже встречалась на этом форуме и стала уже классической: #0. Поменять значения двух целочисленных переменных одного типа, не используя дополнительной переменной. #1 Написать самую короткую программу без операторов ввода и операторов работы с файлами, которая в точности выводит на экран (или на печать) свой собственный текст (исходный код). #2 Вводятся три числа A, B и C. Нужно распечатать их по убыванию. В программе использовать только один оператор switch и ничего больше. первая взята с форума, вторая здесь, третья моя, недавно родилась, позабавил друзей. 12

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

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

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

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	29.06.2009, 14:52	50
	Сообщение от Evg Про abs на форуме уже было можете дать ссылку на тему? 0

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

Evg 21280 / 8304 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	29.06.2009, 15:11	53
	Сообщение от NuM можете дать ссылку на тему? Гоню. Было найти минимальное из двух чисел без использования сравнений. А вот abs использовался в решении. Поискал - найти не смог (хоть убей не помню ни одной ключевой фразы) 0

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

Evg 21280 / 8304 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	29.06.2009, 15:31	55
	Сообщение от 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". В зависимости от этого печатать энтер по-человечески или по виндузовому. 0

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	29.06.2009, 16:18	56
	Сообщение от Evg Но тогда додумались до решения без abs'а, но при этом учитывалось разрядность числа кажется нашел ту тему, да если знать разрядность то можно по значению знакового бита найти модуль числа, интерес в том чтобы сделать это же не зная разрядность числа. p.s. можно использовать только эти операции: +, -, *, div, mod, and, or, xor, not, shr, shl 0

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

Evg 21280 / 8304 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	12.10.2009, 13:57	59
	Сообщение от snake32 Не понял как можно это сделать за один проход. O(N) НЕ означает за один проход, а означает линейное время по отношению к количеству элементов. Т.е. проходов у тебя может быть и 10 и 20, но их количество не зависит от N. O(N) по большому счёту означает, что циклы по N могут быть только одинарные (т.е. без вложенностей), но количество циклов фиксировано (или их более некотрого константного количества) и не зависит от N А вот, например, при сортировке пузырьком появляются два вложенных цикла по N, в результате чего алгорим является квадратичным, т.е. O(N^2) 1

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