Интересные задачи по программированию и логике
Создана: 09 Августа 2009 Вск 17:07:11.
Раздел: "Интернет-флейм"
Сообщений в теме: 585, просмотров: 200588
-
-
Пусть у Вас есть "черный ящик", т.е. устройство которое выполняет определенную операцию над входными данными и отдает их на выход
Известно, что "черный ящик" реализует функцию преобразования бита информации.
Бит это одноразрядное двоичное число, либо 0, либо 1.
Всего можно задать четыре различные функции над такими числами
f1(0)=0, f1(1)=0
f2(0)=1, f2(1)=1
f3(0)=0, f3(1)=1
f4(0)=1, f4(1)=0
Задача нахождения функции решается просто за два испытания. На вход подается сначала число 0, а потом единица.
Вопрос. Можно ли решить задачу используя только одно испытание ? -
Пусть у нас имеется полупрозрачное зеркало. То есть половина фотонов падающих на него отражается, а половина проходит сквозь него.
Мы построили оптическую систему состоящую из двух зеркал и двух полупрозрачных зеркал.
На каком выходе окажется фотон который вошел с нулевого входа ?
-
Задачка по комбинаторике.
Есть свокупность 16 бит (ячеек)...или любое другое кол-во в которой например 7 ячеек содержит "1" а остальные 9 ячеек - "0".
Тупо подсчитать кол-во всех возможныхперестановок(комбинаций) внутри данной совокупности.
Можно увеличить кол-во возможных значений ячеек более двух, т.е. не только "0" и "1" а "0","1","2" и т.д. (но это уже полная жесть))))
Иногда даже профессиональные программисты корчаться от мозговой боли ))))
Задача имеет несколько алгоритмов решений различающихся эфективностью и красотой. -
Ну это конечно так, но имелось в виду решить задачу именно перебором комбинаций -
11 августа. Индийский математик Винэй Деолаликар представил доказательства решения одной из так называемых задач тысячелетия, — ученый опубликовал 100-страничную статью, в которой сделан вывод, что классы сложности P и NP не равны.
Как сообщает Lenta.Ru, вопрос о равенстве классов сложности P и NP можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Эта задача чрезвычайно важна для компьютерных вычислений и прикладных наук, в частности для наук о шифровании данных. Например, если можно быстро проверить, является ли введенный шифр правильным, то можно ли достаточно быстро взломать этот шифр?
Доказательство, что классы сложности P и NP не равны, означает, что ответы на представленные выше два вопроса будут отрицательными. Иными словами, проверка шифра и его подбор являются задачами разного класса сложности.
В настоящее время экспертное сообщество не вынесло однозначного мнения по поводу статьи Деолаликара. Стоит ожидать, что оценки других математиков относительно строгости и правомерности доказательства начнут появляться после того, как будет опубликован окончательный вариант статьи. Планируется, что это произойдет в течение недели.
Задачи тысячелетия — это семь задач, за решение каждой из которых математический институт Клэя предлагает приз размером в один миллион долларов. Одной из таких задач было доказательство гипотезы Пуанкаре. Приз за решение этой задачи был присужден российскому математику Григорию Перельману, который, однако, отказался от денег, аргументировав это тем, что не согласен с решением института Клэя.
Подробнее: [внешняя ссылка] -
чётта я торможу. если случайно взятая и взвешенная монета оказалась настоящей, то третья и четвёртая от неё в любую сторону будут фальшивыми. но если она оказалась фальшивой, то я так и не нашёл верного способа вынуть ещё одну фальшивую из круга. где косяк?karaganda писал : Есть 7 монет
Известно что 4 из них фальшивые и фальшивые монеты легче настоящих.
Монеты разложены по кругу так, что фальшивые монеты раполагаются подряд.
Нужно за 1 взвешивание найти 2 фальшивые монеты. -
ulgent07 писал : В коридоре находится 3 выключателя, а в комнате соответственно 3 лампочки от них.
Нужно определить какой выключатель для какой лампочки.
В комнату можно зайти только 1 раз!!
Запоминаем последовательность включения-выключения выключателей.
Первый выключатель включаем, ждем некоторое время, выключаем. Второй просто включаем. Третий не трогаем. Заходим в комнату и смотрим. 2 лампы выключены, одна горит. Подходим и трогаем лампы. Одна из них будет теплая...