Форум программистов, компьютерный форум, киберфорум
Теория программирования
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.95/622: Рейтинг темы: голосов - 622, средняя оценка - 4.95
Эксперт С++
 Аватар для Phantom
3189 / 869 / 39
Регистрация: 29.12.2008
Сообщений: 951

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

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

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

Начну пожалуй с задачи, которая уже встречалась на этом форуме и стала уже классической:
#0. Поменять значения двух целочисленных переменных одного типа, не используя дополнительной переменной.
#1 Написать самую короткую программу без операторов ввода и операторов работы с файлами, которая в точности выводит на экран (или на печать) свой собственный текст (исходный код).
#2 Вводятся три числа A, B и C. Нужно распечатать их по убыванию. В программе использовать только один оператор switch и ничего больше.
первая взята с форума, вторая здесь, третья моя, недавно родилась, позабавил друзей.
12
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
17.06.2009, 21:49
Ответы с готовыми решениями:

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

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

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

132
Временно недоступен
 Аватар для #pragma
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
12.11.2009, 21:08
Студворк — интернет-сервис помощи студентам
cristaloleg,
чисто предположение
а что если просто поделить одно на другое?правда со знаком надо что-то решить..это не шутка случаем ?
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21285 / 8310 / 637
Регистрация: 30.03.2009
Сообщений: 22,671
Записей в блоге: 30
12.11.2009, 21:09
С асмом не катит. Возьми какой-нибудь сигнальный процессор - так там сразу есть операция нахождения максимума
0
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
12.11.2009, 22:50
Цитата Сообщение от cristaloleg Посмотреть сообщение
Задачка: найти большее из 2 чисел не использую ни ветвления, ни ф-ций(любых), ни циклов и тп
Решение уже читал в одном месте, но, видимо, многие не знают, пока не пишу.
Цитата Сообщение от Evg Посмотреть сообщение
В каких случаях, на ваш взгляд, эти два фрагмента кода будут исполняться по-разному
Думаю,
типа такого

В случае с unsigned результат i - 10 будет UINT_MAX - 10.
В случае с unsigned short результат i - 10 равен UINT_MAX - 10 по C99 в случае, если не любой unsigned short влезет в int (sizeof(short)==sizeof(int); i приводится к unsigned согласно 6.3.1.1, затем 10 приводится к unsigned согласно 6.3.1.8), и -10 в противном случае (в любом случае по C90, а также по C99, если большой int).
1
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21285 / 8310 / 637
Регистрация: 30.03.2009
Сообщений: 22,671
Записей в блоге: 30
12.11.2009, 23:00
Somebody,
по поводу твоего ответа
про C99 - надо будет стандарт почитать и поэкспериментировать. Я только на "обычном" Си проверял. Однако могу сказать сразу: не "UINT_MAX - 10", а "UINT_MAX - 9". При этом в битовом представлении значение этой константы совпадает с битовым представлением константы (int)-10. Я в точности не смог понять объяснение, видимо ты торопился и проглатывал слова, но если оно базируется на том, что UINT_MAX-9 и (int)-10 - разные константы, то это не так
0
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
12.11.2009, 23:12
Cut

Ну да, имел в виду UINT_MAX - 9. А вариант с C99 хочется на практике проверить, но надо чем-то скомпилировать с поддержкой C99, но чтобы размер int был равен short. Я не очень представляю, чем так можно.
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21285 / 8310 / 637
Регистрация: 30.03.2009
Сообщений: 22,671
Записей в блоге: 30
13.11.2009, 11:16
Somebody,
qqq
Проверил для C99 - утверждение "i приводится к unsigned" НЕ верно. В любом случае, даже если оно и было бы верно, то твои пояснения неправильные (о чём я в 84-м посте упомянул)


Подсказка
Разные результаты будут, например, в 64-битном режиме, когда sizoef(int)==4 - т.е. по сути дела в "нормальной" настроке под 64-битный режим. Первый вариант (unsigned) будет ломаться, второй (unsigned short) будет нормально проходить
0
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
13.11.2009, 16:38
Что не так?

Цитата Сообщение от Evg Посмотреть сообщение
но если оно базируется на том, что UINT_MAX-9 и (int)-10 - разные константы, то это не так
А это не разные константы - вроде одна unsigned, другая int? Я думал, p[-10] - это однозначно *(p-10), а p[UINT_MAX-9] это undefined behavior из-за переполнения.
Цитата Сообщение от Evg Посмотреть сообщение
Проверил для C99 - утверждение "i приводится к unsigned" НЕ верно
Тогда что я упустил?
По 6.3.1.8 the integer promotions are performed on both operands. При этом по 6.3.1.1
If an int can represent all values of the original type (что в данном случае не так), the value is converted to an int;
otherwise, it is converted to an unsigned int. These are called the integer
promotions.
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21285 / 8310 / 637
Регистрация: 30.03.2009
Сообщений: 22,671
Записей в блоге: 30
13.11.2009, 16:56
Едем дальше
Цитата Сообщение от Somebody Посмотреть сообщение
А это не разные константы - вроде одна unsigned, другая int?
Мыслишь в верном направлении. Но не до конца.

Цитата Сообщение от Somebody Посмотреть сообщение
Я думал, p[-10] - это однозначно *(p-10), а p[UINT_MAX-9] это undefined behavior из-за переполнения.
Тоже верно. Но скомпиляй это - и у тебя отработает одинаково. На всех "нормальных" архитектурах арифметика работает в двоичном дополнительном коде, а потому там, где по стандарту написано "неопределено", в реальной жизни у всех всё определено и вполне конкретно. Хотя с этой позиции у меня получается, что задача по сути имеет некорректный исходник, этот момент я как-то упустил

Цитата Сообщение от Somebody Посмотреть сообщение
If an int can represent all values of the original type (что в данном случае не так), the value is converted to an int;
Всё, понял, что речь шла о случае, когда sizeof (int) == sizeof (short). В этом месте кастательно промоушена справедливо. Далее получаем твоё предыдущее утверждение, что в обоих случаях получаем разные константы (int)(-10) и (unsigned)(-10) и во втором случае формально непоределённая по стандарту ситуация. Этот ответ принимается. Но он больше теоретический, исходя из того, что в реальной жизни (unsigned)(-10) - это вполне определённое значением, и этим свойством все пользуются направо и налево.

В общем, получается так, что задача не до конца продумана. В любом случае подсказка висит, правда для тебя это уже будет не подсказка, а очевидный ответ. Но если интересно - подумай. Есть более "жизненный" ответ (собственно, задачу не из головы придумал, а на освновании ситуации, с которой столкнулись в жизни)
0
LMY
18.11.2009, 09:30
Цитата Сообщение от Evg Посмотреть сообщение
Задача не по программированию, но все те, кому её задавал, были очень рады. Задача хороша тем, что легко запоминается и решается в уме



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

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

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

Q: а задача решается?
A: да
А результат в десятеричном или в другом исчислении?
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21285 / 8310 / 637
Регистрация: 30.03.2009
Сообщений: 22,671
Записей в блоге: 30
18.11.2009, 09:32
> А результат в десятеричном или в другом исчислении?

В десятиричном. Я ж написал "Задача не по программированию"
0
LMY
18.11.2009, 14:28
Цитата Сообщение от Evg Посмотреть сообщение
Задача не по программированию, но все те, кому её задавал, были очень рады
Да, хороший примерчик! Часа два поглумился он надо мной!
6 / 6 / 0
Регистрация: 27.06.2009
Сообщений: 16
18.11.2009, 22:10
наибольшее из двух чисел
(a+b+(a-b)*(((a-b)or 1)mod 2)) div 2
1
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21285 / 8310 / 637
Регистрация: 30.03.2009
Сообщений: 22,671
Записей в блоге: 30
18.11.2009, 22:40
NuM, а можешь математику этой формулы пояснить?

Добавлено через 1 минуту
Хотя кажись понял... надо на свежую голову поразмыслить
0
6 / 6 / 0
Регистрация: 27.06.2009
Сообщений: 16
18.11.2009, 22:53
формула
формула получается из обычной (a+b+abs(a-b))/2, если расписать abs(x) = x*((x or 1)mod 2), т.е. сначала делаем число нечетным, потом берем остаток от деления на 2, который будет равен 1, если число положительное и -1, если отрицательное
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21285 / 8310 / 637
Регистрация: 30.03.2009
Сообщений: 22,671
Записей в блоге: 30
18.11.2009, 22:56
Собственно, интересовал только
этот
abs(x) = x*((x or 1)mod 2
момент
0
 Аватар для taras atavin
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
19.12.2009, 08:12
Цитата Сообщение от Evg Посмотреть сообщение
В математике нет понятие целочисленное или нецелочисленное, знаковое или беззнаковое, 32-битное или 64-битное, в прямом коде или в дополнительном. В математике есть просто деление
В математике есть деление нацело с остатком и деление действительных чисел. Это две разные операции. Остальных атрибутов деление в математике не имеет.
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21285 / 8310 / 637
Регистрация: 30.03.2009
Сообщений: 22,671
Записей в блоге: 30
19.12.2009, 11:06
Цитата Сообщение от taras atavin Посмотреть сообщение
В математике есть деление нацело с остатком и деление действительных чисел. Это две разные операции. Остальных атрибутов деление в математике не имеет.
С этой точки зрения деление нацело с остатком - это макрооперация над делением действительных чисел (т.к. целое число - это частный случай действительного числа)
0
 Аватар для Jekidollar
3 / 3 / 0
Регистрация: 26.03.2009
Сообщений: 50
01.02.2010, 13:30
C++
1
2
3
int i = 5; 
i = ++i + ++i;
i = ?
0
Эксперт С++
 Аватар для CyBOSSeR
2348 / 1721 / 149
Регистрация: 06.03.2009
Сообщений: 3,675
01.02.2010, 13:42
Jekidollar, это не задача по программированию. Это абсолютно идиотическое задание на "знание" приоритета операций в языке, которым некоторые работодатели пугают незадачливых кандидатов.
0
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21285 / 8310 / 637
Регистрация: 30.03.2009
Сообщений: 22,671
Записей в блоге: 30
01.02.2010, 13:51
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Jekidollar, это не задача по программированию. Это абсолютно идиотическое задание на "знание" приоритета операций в языке, которым некоторые работодатели пугают незадачливых кандидатов.
Это задача на знание стандарта Си, согласно которому пример содержит side-effect'ы и является undefined behaviour. Но совершенно точно НЕ является "нетривиальной задачей"
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
01.02.2010, 13:51

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
100
Ответ Создать тему
Новые блоги и статьи
Модель по догадкам
anaschu 25.08.2026
Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .
Запись в регистр сведений независимо от заполненности табличной части
Maks 25.08.2026
Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .
Ноутбук Альфария
kumehtar 24.08.2026
Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?
Мастера простых решений
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
Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru