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

@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 ; полученное число

влезу ?

Новые блоги и статьи Все статьи Все блоги /
мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .

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

@snake32 3594 / 1724 / 236 Регистрация: 26.02.2009 Сообщений: 8,758 Записей в блоге: 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