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

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

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

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

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

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

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

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

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

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

Evg · 12.10.2009, 16:46

Не по теме:

Саша, где почитать - хз. У Кнута вроде бы было что-то умное по этому воподу

@Somebody · 12.10.2009, 17:50

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

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

N большое или "в разумных пределах"?

Evg · 12.10.2009, 19:38

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

N большое или "в разумных пределах"?

Если ты хочешь сделать битовую маску, то мне кажется, что такую задачу не стали бы давать на олимпиаде

@snake32 · 12.10.2009, 19:50

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

N большое или "в разумных пределах"?

Честно, я не знаю...но думаю 100-500 элементов хватит. Это в "в разумных пределах"?

Evg · 12.10.2009, 19:52

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

Честно, я не знаю...но думаю 100-500 элементов хватит. Это в "в разумных пределах"?

ТОгда задача попросту смысл теряет. Олимпиада какого уровня?

@snake32 · 12.10.2009, 22:02

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

Олимпиада какого уровня?

Женя, это не олимпиада. Это тестовое задание от работодателя, точнее одно из нескольких. Пытался устроится на работу - не получилось.

Evg · 12.10.2009, 22:05

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

Женя, это не олимпиада. Это тестовое задание от работодателя, точнее одно из нескольких. Пытался устроится на работу - не получилось.

А... чёрт... а скакого хера я решил, что это олимпиада... Тогда и вправду особенно умного ничего нет
Заводишь массив из M элементов и обнуляешь его. Дальше идёшь по основному массиву из N элементов и найденные числа отмечаешь в первом массиве. Собственно, линейный алгоритм

@snake32 · 12.10.2009, 22:06

Я думаю то фишка в том что числа то положительные [1..M]. Вот от этого и надо плясать, только как? Огранечение O(N) как-то сковывает...

Добавлено через 1 минуту
А всё...

@NuM · 13.10.2009, 20:25

а условие точно правильное? если повторяются все числа кроме одного, то решение прстое:

решение

нужно поочередно ксорить все числа, результатом будет нужное число

Добавлено через 15 минут
если в массиве встречаются ВСЕ числа от 1 до M, то решение похожее:

решение

сначала ксорим все натуральные числа от 1 до M, потом ксорим все числа в массиве, потом ксорим два полученных результата

@Veyron · 13.10.2009, 20:49

Если ограничение только по времени, то проблемы собсно нету. Можно например завести дополнительный массив bool, заполнить его false, затем при проходе основного массива проверить значение ячейке дополнительного массива с индексом, равным текущему элементу в основном массиве. Если там фолс - обратить в Тру. Если там Тру - ответ нашли.

@NuM · 13.10.2009, 21:10

небольшое дополненние ко второму решению из моего предыдущего поста

дополнение

ксор всех нат. чисел от 1 до m можно посчитать формулой
m % 2 - (m % 4) / 2 + (m + m % 4) * (1 - m % 2)

Evg · 13.10.2009, 23:29

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

если повторяются все числа кроме одного

Как из предложения "Все числа разные, кроме двух" можно было сделать подобное заключение?
Хотя при твоей постановке задачи решение красивое

Добавлено через 1 минуту

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

если в массиве встречаются ВСЕ числа от 1 до M

Опять-таки "Дан массив из N целых чисел 1..M". Такое ощущение, что условие тебе всё-таки лень было прочесть

@NuM · 13.10.2009, 23:39

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

Evg · 13.10.2009, 23:42

Ну ты даёшь...

@CheshireCat · 13.10.2009, 23:55

Да задачка-то тьфу, чиха не стоит. И единственный смысл ее, насколько я могу понять - работодатель хочет узнать, знает ли кандидат, что такое "сложность алгоритма O(N)" (т.е. то, что описал Evg в посте #59). Все. Иного смысла тратить время на эту "задачку" я не вижу.

@cristaloleg · 11.11.2009, 21:55

Задачка: найти большее из 2 чисел не использую ни ветвления, ни ф-ций(любых), ни циклов и тп

Она решается...

Evg · 12.11.2009, 17:04

Даны две записи (отличаются только типом переменной i):

C
1
2
3
4
char buff[256];
char *p = &buff[127];
unsigned i = 0;
p[i - 10] = 0;

C
1
2
3
4
char buff[256];
char *p = &buff[127];
unsigned short i = 0;
p[i - 10] = 0;

В каких случаях, на ваш взгляд, эти два фрагмента кода будут исполняться по-разному. Тех, кто знает ответ, попрошу воздержаться и дать другим подумать. И ещё раз хочется попросить прятать ответы

@Phantom · 12.11.2009, 20:40 **[ТС]**

cristaloleg,

кажется, решил :)

Пусть x - первое число, y - второе. Тогда (x+y+|x-y|):2 это будет б0льшим числом из двух.

Evg · 12.11.2009, 20:55

Phantom, вычисление модуля - это всё-таки функция. С Пупоревым мы в своё время по этому поводу спорили (применительно к этой же самой задаче), но тогда в постановке задачи было написано лишь "без ветвлений", а использование модуля формально можно было под это подогнать

@Goodwin98 · 12.11.2009, 21:05

cristaloleg, а ничего, если я тут с

асмом

Assembler
1
2
3
4
5
mov eax,[first] ; первое число
mov ebx,[second] ; второе
cmp eax,ebx
cmovс eax,ebx
mov [big],eax ; полученное число

влезу ?

Новые блоги и статьи Все статьи Все блоги /
Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .	Цена ошибки DevAlt 23.08.2026 Человек я беспокойный и потому заинтересовался OCaml, в чате форсили функторы модулей как суперфичу. Пытаясь отдуплить концепт, наткнулся на тутор с простым примером. А главный принцип обучения от. . .	Сегодня суббота, 22.08.2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. zorxor 22.08.2026 Сегодня суббота, 22. 08. 2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. Кто Я, откуда Я пришел и куда Я иду? Эти вопросы не оставляют меня ни на секунду. Жизнь на планете Земля. . .	Жизня: рисунок укладки багажа, сделанный клодом anaschu 21.08.2026 Сделал 15 снимков, он по снимкам сделал схему.
Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .

Evg
	12.10.2009, 16:46
	Не по теме: Саша, где почитать - хз. У Кнута вроде бы было что-то умное по этому воподу 0

@snake32 3591 / 1721 / 236 Регистрация: 26.02.2009 Сообщений: 8,735 Записей в блоге: 5
	12.10.2009, 22:06
	Я думаю то фишка в том что числа то положительные [1..M]. Вот от этого и надо плясать, только как? Огранечение O(N) как-то сковывает... Добавлено через 1 минуту А всё... 0

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	13.10.2009, 20:25
	а условие точно правильное? если повторяются все числа кроме одного, то решение прстое: решение нужно поочередно ксорить все числа, результатом будет нужное число Добавлено через 15 минут если в массиве встречаются ВСЕ числа от 1 до M, то решение похожее: решение сначала ксорим все натуральные числа от 1 до M, потом ксорим все числа в массиве, потом ксорим два полученных результата 0

@Veyron 107 / 107 / 9 Регистрация: 02.06.2009 Сообщений: 578
	13.10.2009, 20:49
	Если ограничение только по времени, то проблемы собсно нету. Можно например завести дополнительный массив bool, заполнить его false, затем при проходе основного массива проверить значение ячейке дополнительного массива с индексом, равным текущему элементу в основном массиве. Если там фолс - обратить в Тру. Если там Тру - ответ нашли. 0

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	13.10.2009, 21:10
	небольшое дополненние ко второму решению из моего предыдущего поста дополнение ксор всех нат. чисел от 1 до m можно посчитать формулой m % 2 - (m % 4) / 2 + (m + m % 4) * (1 - m % 2) 1

@NuM 6 / 6 / 0 Регистрация: 27.06.2009 Сообщений: 16
	13.10.2009, 23:39
	условие я прочитал, просто при такой постановке задачи чувствуется, что красивое решение врядли есть, а та задачка, которую я написал, стандартная, поэтому я предположил, что возможна ошибка в условии. 0

Evg 21285 / 8310 / 637 Регистрация: 30.03.2009 Сообщений: 22,671 Записей в блоге: 30
	13.10.2009, 23:42
	Ну ты даёшь... 0

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	13.10.2009, 23:55
	Да задачка-то тьфу, чиха не стоит. И единственный смысл ее, насколько я могу понять - работодатель хочет узнать, знает ли кандидат, что такое "сложность алгоритма O(N)" (т.е. то, что описал Evg в посте #59). Все. Иного смысла тратить время на эту "задачку" я не вижу. 0

@cristaloleg 149 / 50 / 3 Регистрация: 21.12.2008 Сообщений: 960
	11.11.2009, 21:55
	Задачка: найти большее из 2 чисел не использую ни ветвления, ни ф-ций(любых), ни циклов и тп Она решается... 0

@Phantom 3189 / 869 / 39 Регистрация: 29.12.2008 Сообщений: 951
	12.11.2009, 20:40 [ТС]
	cristaloleg, кажется, решил :) Пусть x - первое число, y - второе. Тогда (x+y+\|x-y\|):2 это будет б0льшим числом из двух. 0

Evg 21285 / 8310 / 637 Регистрация: 30.03.2009 Сообщений: 22,671 Записей в блоге: 30
	12.11.2009, 20:55
	Phantom, вычисление модуля - это всё-таки функция. С Пупоревым мы в своё время по этому поводу спорили (применительно к этой же самой задаче), но тогда в постановке задачи было написано лишь "без ветвлений", а использование модуля формально можно было под это подогнать 0