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

просто Паха писал :

Лохмастерье писал:for(i=0; i<sequence; i++) bits=(bits<<1)+1;

bits=(1<<sequence)-1;
сорри, не удержался

Я всегда за конструктивные поправки. Спасибо, Паха. Никогда не держись
Меня ещё (n&bits) != bits смущает - коряво как-то.

Лохмастерье писал :Меня ещё (n&bits) != bits смущает - коряво как-то.

(n&bits) < bits - всего две ассемблерных инструкции
хотя и в исходном варианте будет так же. нечего тут оптимизировать

bouchon писал(а) :Эрх, есть места где программисты получают по $400к в год, но это не чистое программирование, а финансовый анализ

Это считается много или мало?

Эрхафан писал :

bouchon писал(а) ... :Эрх, есть места где программисты получают по $400к в год, но это не чистое программирование, а финансовый анализ

Это считается много или мало?

Для программиста это много. Мой друг работает в блумберге сейчас уже за $125к и постоянно ходит на интервью в голден сакс и другие богатые конторы где платят больше. Мечтает, о $300-400 к




P.S. Знаешь что такое CFA ?

Эрхафан писал : Предлагаю усложнить задачку с шарами до поисков алгоритма для числа шаров b (варьирующегося между 1 и числом этажей)

N - высота небоскрёба.
n - высота, эквивалентная предельной прочности шара (- 1).
b - чиcло шаров.

Задача по-моему эквивалентна следующей.
Есть произвольное целое число n изменяющееся от 0 до N-1
Мы хотим записать его в системе счисления с основанием S чтобы потребовалось разрядов не более чем b.

Сколько максимально измерений потребуется для преобразования величины n в эту систему счисления?
Похоже что S*b.

Чему равно S?
На первый взгляд N^(1/b) (корень степени b из N).

То есть потребуется b * N^(1/b) измерений.

Какая процедура измерения?
Каждый разряд в новой системе счисления начиная со старшего заканчивая младшим увеличиваем от 0 до S-1 с шагом 1 пока полученное число меньше n.

Как это использовать для шаров?
Сначала проводим испытания с шагом S^(b-1) пока не разобьём шар, затем с шагом S^(b-2) от последнего успешного испытания пока не разобьём шар, ..., в конце с шагом 1 (S^0) пока не разобьём последний шар.

Гораздо интереснее оценить среднее число испытаний, но для этого нужно знать распределение целочисленной случайной величины n.

bouchon писал(а) :P.S. Знаешь что такое CFA ?

Я знаю, Бушон. Но к финансам у меня душа не лежит и $400К в год я не хочу.

GENA_DJ писал :Мы хотим записать его в системе счисления с основанием S чтобы потребовалось разрядов не более чем b.

Это подход "в лоб" (как раз пример с десятками в задаче про 100 этажей и 2 шара). Но "14" показало неэффективность такого подхода с использованием разрядов целиком.

GENA_DJ писал :Гораздо интереснее оценить среднее число испытаний, но для этого нужно знать распределение целочисленной случайной величины n.

Если не указывается иное, то распределение равномерное. Т.е. любое допустимое значение n равновероятно.

========
Сложно излагаете. Паха, кажись, просто сформулировал: при определении интервала, содержащего число n - начинаем стоять перед той же задачой, но уже в миниатюре (небоскрёб пониже предыдущего). И так далее. Рекурсия наклёвывается, причем оправданная.

========
Среднее число испытаний можно получить довольно просто, а вот как с "социалкой" быть - не знаю (Получившийся подинтервал(ы) может оказаться любым). При b=2 было просто - фиксаж в 14 при первоначальном шаге, откуда следовало, что "социалка"=14.
Не допираю. Хелп!

Лохмастерье писал :Рекурсия наклёвывается, причем оправданная.

да

Эрхафан писал : Но "14" показало неэффективность такого подхода с использованием разрядов целиком.

А если основание s сделать нецелым?

Эрхафан писал : Но к финансам у меня душа не лежит и $400К в год я не хочу.

Мало?

MAGAZINE писал(а) : Переделал по новому, теперь среднем нужно подкинуть монетку 25 раз, чтоб выпала решка. Осталось проверить на практике

8 и 25 не правильно

Muammar писал(а) :Мало?

Не мало и не много. Просто не хочу

суеверный

bouchon писал(а) :

MAGAZINE писал(а) ... : Переделал по новому, теперь среднем нужно подкинуть монетку 25 раз, чтоб выпала решка. Осталось проверить на практике

8 и 25 не правильно

Наверное, где в районе 14 с половиной. /И тут число 14/

Лохмастерье писал :
Наверное, где в районе 14 с половиной. /И тут число 14/

Ага, 14 ровно. То решение которое я выше привел дает точный ответ и для среднего и для всех моментов распределения.

Самое интересное, что некоторые могут решить эту задачу в голове, я не могу

Ее как раз дают на интервью на работу с зарплатой $400к