Форум программистов, компьютерный форум, киберфорум
Наши страницы
Теория и практика программирования
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.53/392: Рейтинг темы: голосов - 392, средняя оценка - 4.53
Phantom
Эксперт С++
3177 / 858 / 39
Регистрация: 29.12.2008
Сообщений: 952
1

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

17.06.2009, 21:49. Просмотров 74226. Ответов 132
Метки нет (Все метки)

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

Начну пожалуй с задачи, которая уже встречалась на этом форуме и стала уже классической:
#0. Поменять значения двух целочисленных переменных одного типа, не используя дополнительной переменной.
#1 Написать самую короткую программу без операторов ввода и операторов работы с файлами, которая в точности выводит на экран (или на печать) свой собственный текст (исходный код).
#2 Вводятся три числа A, B и C. Нужно распечатать их по убыванию. В программе использовать только один оператор switch и ничего больше.
первая взята с форума, вторая здесь, третья моя, недавно родилась, позабавил друзей.
11
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2009, 21:49
Ответы с готовыми решениями:

нетривиальные алгоритмы
Подскажите, пожалуйста, примеры нетривиальных алгоритмов. Алгоритмы многие мне известны, но вот...

задачи по программированию
Задача А. Правильное управление (Online) Задачу добавил: alef Успешно сдано решений: 6...

Задачи по программированию
Добрый вечер друзья, помогите пожалуйста с задачами по С++: 1)Дана матрица 6х6 целого типа....

Задачи по программированию в С++
Не могу никак понять программирование на С++ ! Помогите решите мне хоть одну из этих задач я...

Олимпиадные задачи по программированию
Пробуйте :) Окружной этап всероссийской олимпиады школьников по информатике Москва, 2 декабря...

132
snake32
1849 / 1159 / 205
Регистрация: 26.02.2009
Сообщений: 4,365
Записей в блоге: 5
01.02.2010, 13:52 101
Jekidollar, по-моему результат зависит от настроек оптимизатора. Стараюсь таких "запутанных" ситуаций избегать.
Может ошибаюсь.... поправте если так.
0
Evg
Эксперт CАвтор FAQ
20301 / 7828 / 602
Регистрация: 30.03.2009
Сообщений: 21,862
Записей в блоге: 30
01.02.2010, 13:53 102
Цитата Сообщение от snake32 Посмотреть сообщение
Jekidollar, по-моему результат зависит от настроек оптимизатора. Стараюсь таких "запутанных" ситуаций избегать.
Результат зависит от конкретного компилятора, ибо разные компиляторы в общем случае дадут разный результат
0
snake32
01.02.2010, 13:58
  #103

Не по теме:

Подобную задачу давали мне на собеседовании в NIX. В тот раз я не угадал =)

0
Day
1163 / 968 / 83
Регистрация: 29.10.2009
Сообщений: 1,386
01.02.2010, 14:12 104
В математике есть деление нацело с остатком и деление действительных чисел. Это две разные операции. Остальных атрибутов деление в математике не имеет.
Увы, в математике есть самые разнообразные объекты - поля и кольца.
И в этих объетах определяются свои операции - лишь бы они удовлетворяли аксиоматике
1
01.02.2010, 14:12
Dimazzzzzz
588 / 95 / 6
Регистрация: 24.01.2009
Сообщений: 379
19.11.2010, 02:45 105
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 минут
И еще одна маленькая цитата из вики:
Керниган говорит: «Си — инструмент, острый, как бритва: с его помощью можно создать и элегантную программу, и кровавое месиво»
0
CyBOSSeR
Эксперт С++
2318 / 1691 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
19.11.2010, 08:27 106
Цитата Сообщение от Dimazzzzzz Посмотреть сообщение
C++
1
2
3
int i = 5;
i = ++i + ++i;
i = ?
Dimazzzzzz, этот код приводит к undefined behavior - переменная i модифицируется более одного раза не переходя через точку следования. Подробнее здесь.
Поэтому ничего удивительного в этом вопросе нет - либо ты знаешь о точках следованиях, либо нет.
1
taras atavin
4199 / 1776 / 211
Регистрация: 24.11.2009
Сообщений: 27,563
08.12.2010, 07:19 107
Цитата Сообщение от Phantom Посмотреть сообщение
#1 Написать самую короткую программу без операторов ввода и операторов работы с файлами, которая в точности выводит на экран (или на печать) свой собственный текст (исходный код).
PureBasic
1
10 LIST
0
GenDalF90
0 / 0 / 0
Регистрация: 19.01.2011
Сообщений: 1
23.01.2011, 10:43 108
На экзамене мне преподаватель озадачил такой задачей: "Даны два заполненных стэка неизвестно чем и каким количеством, еще дан пустой стэк. Нужно с помощью этого буферного стэка и операций Push, Pop и "Пуст ли стэк" (типа условие выхода для стэка. У меня эта процедура реализована с помошью "Stack.Count!=0") поменять местами содержимое заполненных стэков не нарушая порядок и не используя переменные."

Решение я выложил тут... однако правильный ответ по мнению препода "Решения нет!"

 Комментарий модератора 
Ссылка на форум удалена
0
Xero201
65 / 63 / 19
Регистрация: 27.12.2008
Сообщений: 212
30.01.2011, 23:54 109
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 справа). Расстояние между шариками одинаковое. Столкновение абсолютно упруго и мгновенно (ну без всяких там физических подковырок короче). Нужно посчитать количество всех столкновений до того, как шарики разойдутся (задача имеет эвристическое решение).
1
Козырь
39 / 38 / 6
Регистрация: 11.05.2010
Сообщений: 141
01.09.2012, 09:06 110
задача про шарики:
hide
Видимо решение задачи, простое умножение кол-ва шариков слева на их кол-во справа. Полноценного доказательства у меня нет, но это работает, когда шариков 1,2,3 на любой из сторон. А когда происходит соударение, ситуация начинает приближаться к более простой.
0
Phantom
Эксперт С++
3177 / 858 / 39
Регистрация: 29.12.2008
Сообщений: 952
08.12.2012, 14:16  [ТС] 111
Не знаю, понравится или нет, просто в голову пришло:

C++
1
2
3
4
5
6
void main()
{   
    int massiv(3);
                                            // < написать тут один оператор, ...
    std::cout<<massiv[i];       // < чтобы здесь вывелось, например, 31337
}
0
Evg
Эксперт CАвтор FAQ
20301 / 7828 / 602
Регистрация: 30.03.2009
Сообщений: 21,862
Записей в блоге: 30
08.12.2012, 14:54 112
ы?
C
1
int i = ((massiv[0] = 31337) - 31337);
0
Phantom
Эксперт С++
3177 / 858 / 39
Регистрация: 29.12.2008
Сообщений: 952
08.12.2012, 15:33  [ТС] 113
Evg,
Если честно, под рукой нет любимой студии или другой IDE, но на их месте я бы сказал что-то вроде "subscript requires array or pointer type" Скорее всего - неверно, приду - проверю.
0
Evg
Эксперт CАвтор FAQ
20301 / 7828 / 602
Регистрация: 30.03.2009
Сообщений: 21,862
Записей в блоге: 30
08.12.2012, 17:55 114
Блин, я думал там квадратные скобки в описании massiv, а там круглые...
0
Somebody
3103 / 1624 / 251
Регистрация: 03.12.2007
Сообщений: 4,223
Завершенные тесты: 3
08.12.2012, 20:01 115
Цитата Сообщение от Phantom Посмотреть сообщение
void main()
Даже тут void main...
Типа того?
C++
1
unsigned i[] = {0, 0, 0, 31337};
0
Phantom
Эксперт С++
3177 / 858 / 39
Регистрация: 29.12.2008
Сообщений: 952
08.12.2012, 21:08  [ТС] 116
Somebody, да, типа того. Всё верно.

Не по теме:

Цитата Сообщение от Somebody Посмотреть сообщение
Даже тут void main...
Да, детишки, не пишите никогда void main. Эта конструкция характеризуется unidentified behavior, теоретически роняет скрипты, вызывающие программу, делает софт непереносимым, противоречит пункту 3.6.2 стандарта и заставляет дядю Бьёрна икать. Для войдмейнщиков уготован специальный котел в аду.

0
ExpressS
5 / 8 / 2
Регистрация: 30.07.2012
Сообщений: 235
15.12.2012, 19:51 117
Цитата Сообщение от Evg Посмотреть сообщение
Задача не по программированию, но все те, кому её задавал, были очень рады. Задача хороша тем, что легко запоминается и решается в уме



Наиболее часто задаваемые вопросы:

Q: а точно должно получиться 24?
A: да

Q: а в условии задачи нет ошибок?
A: нет

Q: а задача решается?
A: да
скажите ответ
вот что мне пришло на ум
1/5+6*4
0
Evg
Эксперт CАвтор FAQ
20301 / 7828 / 602
Регистрация: 30.03.2009
Сообщений: 21,862
Записей в блоге: 30
16.12.2012, 12:38 118
Цитата Сообщение от ExpressS Посмотреть сообщение
скажите ответ
вот что мне пришло на ум
1/5+6*4
Нетривиальные задачи по программированию
0
korvin_
2733 / 2008 / 360
Регистрация: 28.04.2012
Сообщений: 6,829
18.12.2012, 21:45 119
А вот так можно:
Кликните здесь для просмотра всего текста
65-41

? ^_^
0
Evg
Эксперт CАвтор FAQ
20301 / 7828 / 602
Регистрация: 30.03.2009
Сообщений: 21,862
Записей в блоге: 30
19.12.2012, 14:00 120
Цитата Сообщение от korvin_ Посмотреть сообщение
А вот так можно
В задаче написано "даны числа" (а не цифры)
0
19.12.2012, 14:00
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.12.2012, 14:00

Олимпиадные задачи по программированию
Здравствуйте, где можно найти задача по программирования и их решение.

Ищу задачи по программированию c++
Надо сборник задач по c++ Чтобы были задачи на циклы, масивы, функции. Желательно с объяснением...

Подскажите задачи по программированию
Всем, привет. Начал изучать C++ и qt. А задачи самому себе не придумать. Хоть тресни. Не подкинет...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
120
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru