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

Задачу rndthree() считаю недобитой - лежит стонет в кювете.

Сделать алгоритм общим, где rndthree() будет только частным случаем.

В реализации использовать Пахин код (там требуются минимальные поправки).

На этом можно будет успокоиться.

Лохмастерье писал : Задачу rndthree() считаю недобитой - лежит стонет в кювете.

Сделать алгоритм общим, где rndthree() будет только частным случаем.

В реализации использовать Пахин код (там требуются минимальные поправки).

На этом можно будет успокоиться.

Код:

int rndthree() {    a = rndtwo();    b = rndtwo();    if( (a == 0) && (b == 0) )    {       return 0;    }    else if( (a == 1) && (b == 1) )    {       return 1;    }    else if( (a == 1) && (b == 0) )    {       return 2;    }    else if( (a == 0) && (b == 1) )    {       return rndthree();    }    else    {       return -1;    } }

неужели настолько большое отличие "старой школы" от современной?

Код:

Begin f3:=3; while f3=3 do f3:=random(1)+random(1)*2; End;

Код:

int rndthree() {    a = rndtwo();    b = rndtwo();    if( (a == 0) && (b == 0) )    {       return 0;    }    else if( (a == 1) && (b == 1) )    {       return 1;    }    else if( (a == 1) && (b == 0) )    {       return 2;    }    else if( (a == 0) && (b == 1) )    {       return rndthree();    }    else    {       return -1;    } }

просто Паха писал : неужели настолько большое отличие "старой школы" от современной?

Я код просто не заметил

Лохмастерье писал :Сделать алгоритм общим, где rndthree() будет только частным случаем.

Ну, в целом для Z, генерить n битов (где n - количество знаков двоичного числа, необходимое и достаточное для записи Z в двоичном коде, разрядность в общем, [(log2Z)+1] ). Ну и далее точно так же как для случая с "тройкой".
Правда вот для алгоритма с "тройкой" среднее количество применения однобитного ранодмайзера будет равно 2,(6) для количества опытов стремящегося к бесконечности. А вот для больших Z возможна совсем плохая ситуация - особенно ярко это видно на примере чисел являющихся степенью двойки плюс один (или немножко бОльших) - когда в половине (!) вариантов цикл будет вынужден гоняться о кругу за счет появившегося "лишнего" разряда числа.

В общем случае ожидаемое число обращений к однобитовому рандомайзеру составит 2n, где n=[(log2Z)+1]. Наверное как-то можно оптимизировать.

Количество необходимых бит можно вычислить так:

Код:

unsigned bits (unsigned number) { unsigned m=1; unsigned nbit; for(nbit=0; m<number; nbit++)  {   m=(m<<1);  } return nbit }

================
Ладненько, с чудо-монетой покончено.

Выводы:
1) С помощью монетки можно организовать рандомайзер на любое количество чисел, используя некое подобие демона Максвелла, выпускающее из ящика только "горячие" числа.
2) КПД такого рандомайзера для некруглых значений (не являющиеся степенью двойки) будет вальсировать от чуть больше 1/2 до чуть меньше единицы. В среднем КПД будет всё так же = 3/4. Не вижу способа - как его улучшить, оставаясь в рамках такой схемы генерации случайного числа. Наверное, это невозможно. /Точно невозможно/

О небоскрёбе и шарах.
Задача всё-таки программистская - пришлось чего-то ваять.
Идея следующая: для данной стратегии m (где m первоначальный шаг) вычисляется максимальное количество операций, требующееся для определения числа n (n может быть любым от 1 до 100). Затем сравниваются эти стратегии по этим максимальным значениям в поисках минимума.

Код:

unsigned number_of_operations (unsigned n, unsigned m) { return (n%m? (n/m)+1+(n%m): (n/m)+m); /* m>1 */ } /* —————————————————————- */ main () { #define MAX_N 100 unsigned n; unsigned m; unsigned maxi; unsigned mini; mini=10000; /*заведомо завышенный минимум*/ for(m=2; m<=MAX_N; m++) {   maxi=0; /*заведомо заниженный максимум*/   for(n=1; n<=MAX_N; n++)   {    maxi=max(maxi, number_of_operations(n,m));   }   printf ("m=%u maxi=%u \n",m, maxi);   mini=min(mini, maxi); } printf ("mini=%u \n", mini); }

Минимальное количество проб за которое гарантировано можно найти n (n может быть любым от 1 до 100) равно 20.

Так как более ни о чём не спрашивалось, то это ответ.

Но интересно было бы узнать, как (при каком m) он достигается.
Паха на коне! Такое достигается при шести различных значениях m ={8-13}. Пахина десятка там тоже есть.

==================
Но это не является оптимальной стратегией. А её и не требовалось найти. Но можно сделать и это. /m в задаче нахождения оптимальной стратегии не обязано совпадать с m в задаче на нахождение минимального количества проб, гарантирующего нахождение n./
Оптимальной будем считать стратегию, требующую в среднем минимальное количество проб для нахождения n

Код:

main () { #define MAX_N 100 unsigned n; unsigned m; unsigned sum; unsigned mini; mini=10000;/*заведомо завышенный минимум*/ for(m=2; m<=MAX_N; m++) {   sum=0;   for(n=1; n<=MAX_N; n++)   {    sum+=number_of_operations(n,m);   }   printf ("m=%u sum=%u \n",m, sum);   mini=min(mini,sum); } printf ("mini=%u \n", mini); }

Тут уже только два значения m (10 и 11) с минимальным ожидаемым количеством проб равным 11.

Паха и тут на коне.
========

Если бы решали эту задачу аналитически, то стопудово пришли бы к чему-то вроде:
1) Минимальное количество проб за которое гарантировано можно найти n (n может быть любым от 1 до 100) равно 2*sqrt(N), где N этажность небоскрёба.
2) Соответствующая п. 1 стратегия m = sqrt(N)
3) Так как реальная функция дискретная (причём, во все стороны - и по аргументам, и по значениям функции), то результаты также могут включать в себя значения отличные от заявленных - в ту или иную сторону, но группирующиеся вокруг центра - аналитически вычисленного значения m. Что видно на примере - m={8-13}, где центром живописной композиции является Пахина десятка.


Паха ваще попал в десятку. С таким даром тока в казино играть.

Лохмастерье писал :1) С помощью монетки можно организовать рандомайзер на любое количество чисел, используя некое подобие демона Максвелла, выпускающее из ящика только "горячие" числа

Хороший, кстати, вывод

А где, ёпть, остальной народ? Задачков накидайте!

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

userlogoff писал ... :
3) Есть 2 одинаковых шара, сделанных из стекла. За какое мин. число бросков можно гарантированно определить, при падении с какого этажа стоэтажного здания шарики начинают разбиваться.

чего то вы тут намудрили. по-моему суть проблемы в том, что если разбить оба шарика до того как выясним какой этаж крайний это фейл. Если бы у нас был один шарик, то нужно было бы начинать бросать с первого этажа, затем со второго и так до тех пор пока не разобьется. В худшем случае это было бы 100 раз если крайним оказался бы сотый этаж. Если у нас есть 2 шарика мы опять должны начинать бросать снизу, но не обязательно с каждого этажа, так как у нас есть запасной шарик. Опять в худшем случае шарик разбивается с верхнего этажа. Какая стратегия? Мы бросаем со второго этажа, если разбивается бросаем второй шарик с первого. Если же не разбивается со второго этажа, бросаем второй раз с четвертого. Развивается с 4ого, бросаем запасной шарик с 3ого, иначе продолжаем бросать через этаж. Минимальное количество бросков гарантирующих установление этажа в худшем случае, когда это сотый или 99 этаж будет 51. Потому что на 50м броске с 100 этажа он разобьётся и нужно будет проверить 99 этаж запасным шариком.
Хотя если в условии будет сказано, что как минимум с 100 этажа он разбивается, то достаточно 50 раз, т.е после 98 этажа кидать с 99 и все.

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

Лохмастерье писал ... :1) С помощью монетки можно организовать рандомайзер на любое количество чисел, используя некое подобие демона Максвелла, выпускающее из ящика только "горячие" числа

Хороший, кстати, вывод

Учитывая встретившееся некоторое непонимание, и даже неприятие, сути механизма, какой бы очевидной и простой она ни казалась - это просто необходимый вывод Вывод как вывод.

Лохмастерье писал :Паха ваще попал в десятку. С таким даром тока в казино играть.

спасибо, не надо. а минимальным количеством бросков будет 14. т.е. первая группа - 14 этажей. если не проканало, следующая группа - 13 этажей и т.д. уменьшая на единицу каждую следующую группу.
то, что я прикинул сразу (группы по 10 этажей) - это 19 бросков.

bouchon писал(а) ? :

Ты расписал вариант с первоначальным шагом 2.
m=2 maxi=52
Не самый лучший вариант.
=========

Задача ещё не решена. Я накосячил с функцией number_of_operations - она начинает подвирать,- слегка, но упорно,- при m>N/2 (нет смысла тестировать этаж >N - его нет) и при N%m != 0 (аналогично)
N - количество этажей в здании.

Код:

unsigned number_of_operations (unsigned n, unsigned m) { return (n%m? (n/m)+1+(n%m): (n/m)+m); }

/number_of_operations призвана возвращать количество операций, необходимых для того, чтобы засечь число n/


В итоге лишняя операция. Десятка, думаю, так и останется в фаворитах, но вот за судьбу её соседок {8-13} я уже начинаю переживать.

Надо править number_of_operations. Помогите!

просто Паха писал : а минимальным количеством бросков будет 14. т.е. первая группа - 14 этажей. если не проканало, следующая группа - 13 этажей и т.д. уменьшая на единицу каждую следующую группу.
то, что я прикинул сразу (группы по 10 этажей) - это 19 бросков.

Ты уже трогаешь за вымя другое семейство функций. Звучит заманчиво, надо подумать.

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

просто Паха писал ... : а минимальным количеством бросков будет 14. т.е. первая группа - 14 этажей. если не проканало, следующая группа - 13 этажей и т.д. уменьшая на единицу каждую следующую группу.
то, что я прикинул сразу (группы по 10 этажей) - это 19 бросков.

Ты уже трогаешь за вымя другое семейство функций. Звучит заманчиво, надо подумать.

тут математика примерно такая 1+2+3+..+n. как только сумма превысит нужное количество этажей - n и будет стартовая группа и минимальное количество бросков.