Интересные задачи по программированию и логике 

Евгенчик писал :

Лохмастерье писал ... :

karaganda писал ... : Да. Весы чашечные

Правильное решение у Вас

Не, косяк есть - сравнивать надо 1-ю и 3-ю монеты.
Не. таки 1-ю и 4-ю

чего то ничего так не получается

Что именно не получается?
Задачу решил Просто Паха. А взвешивание даст в руки либо сразу 4 фальшивые монеты с вероятностью 1/7 (это бонус), либо даст точку отсчёта - координату одной из настоящих монет (а там уже смотри мессиджи от Просто Паха).

to Амонлюза

Зеркало половину пропускает, половину отражает. По теории вероятностей фотоны на обоих выходах должны быть.

userlogoff писал :
1) Дан набор файлов с именами, скажем, от 1 до 1000. Один из этих файлов удаляется. Нужно определить, какой именно.

Не понял. Поясниет, пожалуйста..

userlogoff писал :
2) Есть функция rndtwo(), равновероятно возвращающая однобитовое бинарное число (0 или 1). С помощью этой функции необходимо реализовать новую функцию rndthree(), которая равновероятно будет возвращать 0, 1 или 2.

Для населения Омска и омской области поясняю:
Есть монетка. Да, есть. Как с помощью этой монетки соорудить рандомайзер, выдающий на гора три равновероятных результата. Программирование тут упомянуто, боюсь, только для форсу бандитского. Квадратура круга, однако.

Лохмастерье писал :Программирование тут упомянуто, боюсь, только для форсу бандитского

Там все 4 (кроме, возможно, непонятной 1ой) к программированию никакого отношения не имеют Так что ждем разъяснения про удаленный файл.

У меня есть версия, что найти надо в минимальное количество операций. Если так, то задача примерно подобна дроблению диапазона (/2) сравнений и логика ее решения схожа с решением задачи про падающие стеклянные шары. Но это в том случае, если УЖЕ существует некое подобие нумерованного массива с названиями файлов (требуется пояснение - что такое "набор файлов"), а это связано с конкретной ОС и конкретной файловой системой. То бишь опять на программирование не сильно похоже

Можно сказать, что большинство таких задач - оно наполовину на логическое мышление. Но и на вторую половину, где алгоритм нужно запрограммировать.
На первую задачу решение крайне занимательное. Более того, файлов может быть не 1000, а 10000 и более..
Итак. Если приглядеться, то этот набор файлов - арифметическая прогрессия. Первый член - 1, последний - 1000 (или 10000, или еще чего-то)., шаг равен 1. Сумма такой прогрессии вычисляется по формуле (a1 +an)*N/2, где а1 - первый член прогрессии, an - последний, N - количество членов. Т.о., мы можем посчитать сумму исходной прогрессии и вычесть из этой суммы сумму прогрессии, получившейся после удаления файла. Разность - и есть имя исходного файла.
Код на питоне:
from os import listdir
from time import sleep
#получаем и суммируем имена файлов
sum1 = sum(int(filename) for filename in listdir('./q1'))
#предположим, что за 10 секунд какой-то файл удалили
sleep(10)
#снова вычисляем сумму
sum2 = sum(int(filename) for filename in listdir('./q1'))

#наконец, определяем, какой файл был удален
deleted = sum1 - sum2

if deleted: print '%s was recently deleted ' % deleted
else: print 'all's ok, go ahead and delete something'

karaganda писал : to Амонлюза

Зеркало половину пропускает, половину отражает. По теории вероятностей фотоны на обоих выходах должны быть.

это говорит математика или физика?

userlogoff писал : Можно сказать, что большинство таких задач - оно наполовину на логическое мышление. Но и на вторую половину, где алгоритм нужно запрограммировать..... бла-бла-бла.

Ничего не понял. А если имена файлов формировались рандомно [0-9? a-z, A-Z, -infinity - + infinity ]? Это к тому, что Вы предлагали предполагать, что файл... не, не могу дальше ничего предполагать.

Вас стыд не душит? Меня душит. Стыдно, бл$дь.

тут речь про другой файл, но мне вспомнился случай, как мы файл мультифорой называли и ухохатывались, что никто не знает, что это.

userlogoff писал :На первую задачу решение крайне занимательное

Решение как решение Но лучше таки в следующий раз более точно условия давать. Спасибо!

Кто хотел - тот уточнил.
Почему-то я сразу понял, что они по порядку все.

Все эти задачи давались именно как "напишите программу".
По задачке с rnd есть две подсказки:
1) сначала реализовать функцию rndfour (random4())
2) время работы функции может быть недетерминированным.

Лохмастерье писал :

userlogoff писал : Можно сказать, что большинство таких задач - оно наполовину на логическое мышление. Но и на вторую половину, где алгоритм нужно запрограммировать..... бла-бла-бла.

Ничего не понял. А если имена файлов формировались рандомно [0-9? a-z, A-Z, -infinity - + infinity ]? Это к тому, что Вы предлагали предполагать, что файл... не, не могу дальше ничего предполагать.

Вас стыд не душит? Меня душит. Стыдно, бл$дь.

Почему меня должен душить стыд?
Я вам по сути сделал копипаст из уважаемого издания, по пути изменив некоторые словосочетания таким образом, чтобы их было тяжело загуглить.

Кстати, задачу про лампочки мне когда-то задавали на собеседовании в Люксофте. Ну это так, к слову )

userlogoff писал : Кстати, задачу про лампочки мне когда-то задавали на собеседовании в Люксофте. Ну это так, к слову )

Чудилы... зачем задавать вопросы, когда можно просто заглянуть в глаза?

Лохмастерье писал :

userlogoff писал ... : Кстати, задачу про лампочки мне когда-то задавали на собеседовании в Люксофте. Ну это так, к слову )

Чудилы... зачем задавать вопросы, когда можно просто заглянуть в глаза?

И что они должны там увидеть?
Решение задачи про лампочки, арифметические прогрессии или получение равновероятной функции?

P.P.S. В люксофт так и не взяли, чему я несказанно рад

userlogoff писал :По задачке с rnd есть две подсказки:
1) сначала реализовать функцию rndfour (random4())
2) время работы функции может быть недетерминированным.

Да в ней вообще всё понятно, чо И верно отмечено, что к программированию это отношение имеет совсем уж... никакое Точней имеет, но не к конкурсному программированию.

Давайте текстов с редкими красивыми олимпиадными задачками.

userlogoff писал :Почему-то я сразу понял, что они по порядку все.

Про порядок... В некоторых файловых системах рассечение будет более изящным и быстрым, чем "суммирование" имён. Даже при "по порядку все".