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

@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_

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

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

Новые блоги и статьи Все статьи Все блоги /
[golang] Алгоритм «Хак Госпера» alhaos 17.05.2026 Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .	Рисование бинарного древа до 6-го колена на js, svg. russiannick 17.05.2026 <svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;	FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .	Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .
[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .

@snake32 3522 / 1705 / 236 Регистрация: 26.02.2009 Сообщений: 8,595 Записей в блоге: 6
	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 21281 / 8305 / 637 Регистрация: 30.03.2009 Сообщений: 22,660 Записей в блоге: 30
	08.12.2012, 17:55
	Блин, я думал там квадратные скобки в описании massiv, а там круглые... 0

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