Алгоритмическая задачка.

и задачки для интервью.
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Алгоритмическая задачка.

Post by alex1979 »

Есть функция rnd7() которая выдаёт равномерно распределённые случайные числа в интервале [0..6].

Надо придумать алгоритм для функции rnd10() генерирующую равномерно распределённые случайные числа в интервале [0..9] при том что источником случайности можно использовать только rnd7().

Дополнительный вопрос. Если надо сгенерировать много rnd10(), например, миллион, придумать алгоритм чтобы позвать rnd7() как можно меньше раз.
User avatar
Сева
Уже с Приветом
Posts: 2619
Joined: 24 Feb 2022 20:31
Location: 20yrs:USA->Россия

Re: Алгоритмическая задачка.

Post by Сева »

rnd7() выдаёт только целые числа, то есь без дробей, или может выдавать 0.3, 5.1 и т.д. ?
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

Сева wrote: 09 Jul 2024 09:32 rnd7() выдаёт только целые числа, то есь без дробей, или может выдавать 0.3, 5.1 и т.д. ?
Только целые числа, и rnd7() и rnd10().
User avatar
Сева
Уже с Приветом
Posts: 2619
Joined: 24 Feb 2022 20:31
Location: 20yrs:USA->Россия

Re: Алгоритмическая задачка.

Post by Сева »

1) round(float(rnd7() * rnd7()) / 3.6) например
или round(float(rnd7() + rnd7()) / 1.2)

2) Так сразу приходит в голову нечто распростецкое, типа
а) Создаём массив AR из тысячи целых
б) заполняем его значениями типа rnd7() * rnd7() * rnd7() * rnd7() или суммами нескоьких rnd7()
в) Генерим миллион как
float(rnd7() * AR[i % 1000 ] ) / (6 * AR[i % 1000 ] /10)
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

Сева wrote: 10 Jul 2024 13:50 1) round(float(rnd7() * rnd7()) / 3.6) например
или round(float(rnd7() + rnd7()) / 1.2)

2) Так сразу приходит в голову нечто распростецкое, типа
а) Создаём массив AR из тысячи целых
б) заполняем его значениями типа rnd7() * rnd7() * rnd7() * rnd7() или суммами нескоьких rnd7()
в) Генерим миллион как
float(rnd7() * AR[i % 1000 ] ) / (6 * AR[i % 1000 ] /10)
>round(float(rnd7() + rnd7()) / 1.2)

Так не получится равномерное распределение. Вероятность получить 5 гораздо больше чем 0 или 9. Причём сколько не складывай таким образом, математически точно равномерное распределение не получится, а это условие задачки. То же самое если делать rnd7() * rnd7().

Сделаю подсказку.

Если бы, например на входе было rnd11() и надо было бы сделать rnd10(), то можно было бы сгенерировать rnd11(), и если число меньше 10, то это и есть результат rnd10(). Если было 10, то просто повторять пока не будет <10. И это будет точно равномерное распределение.
User avatar
Сева
Уже с Приветом
Posts: 2619
Joined: 24 Feb 2022 20:31
Location: 20yrs:USA->Россия

Re: Алгоритмическая задачка.

Post by Сева »

Я первое, о чём подумал, были вот такие отсечения. Но отверг этот метод.
Равномерного распределения при этом не получится.
У нас же rnd7() - равномерное, а не нормальное распределение.
Если отсекать и повторять, то оно перестанет быть равномерным.

оба round(float(rnd7() * rnd7()) / 3.6) и round(float(rnd7() + rnd7()) / 1.2) гарантированно останутся равномерными.
Единственная поправочка, которую я-бы пожалуй внёс, это добавление единицы к rnd7() для умножения.
Пусть станет равномерным от 1 до 7, зато умножением точно не будет обнулать второе случайное число, сим гарантировав равномерность

То есть при умножении имеем round(float( (rnd7() + 1) * (rnd7() +1) ) / 4.9)
User avatar
SVK
Уже с Приветом
Posts: 8422
Joined: 23 Jul 2003 03:53
Location: SPb - KW - NY - CT - MD

Re: Алгоритмическая задачка.

Post by SVK »

rnd7() - равномерно от 0 до 6
( rnd7()*10 + rnd7() ) - равномерно от 0 до 66
(float( rnd7()*10 + rnd7() ) / 67.) - равномерно между [0; 1)
(float( rnd7()*10 + rnd7() ) / 6.7) - равномерно между [0; 10)
int( float( rnd7()*10 + rnd7() ) / 6.7) - равномерно от 0 до 9
LG - Life's good.
But good life is much better.
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

SVK wrote: 10 Jul 2024 18:57 rnd7() - равномерно от 0 до 6
( rnd7()*10 + rnd7() ) - равномерно от 0 до 66
(float( rnd7()*10 + rnd7() ) / 67.) - равномерно между [0; 1)
(float( rnd7()*10 + rnd7() ) / 6.7) - равномерно между [0; 10)
int( float( rnd7()*10 + rnd7() ) / 6.7) - равномерно от 0 до 9
> ( rnd7()*10 + rnd7() ) - равномерно от 0 до 66

Нет, не равномерно. Например, вероятность получить 8 или 9 равна нулю.
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

ОК, ещё подсказка. Используя rnd7() сделать rnd49() которое генерирует целые числа с равномерный распределением в интервале [0,48]
DropAndDrag
Уже с Приветом
Posts: 6239
Joined: 11 Mar 2011 05:36

Re: Алгоритмическая задачка.

Post by DropAndDrag »

первое rnd7() заполняет от 0 до 6
второе rnd7()+7 заполняет от 7 до 14
выкинуть все что от 10
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

DropAndDrag wrote: 11 Jul 2024 04:46 первое rnd7() заполняет от 0 до 6
второе rnd7()+7 заполняет от 7 до 14
Непонятно что значит "одно заполняет от 0 до 6, другое заполняет от 7 до 14".

Если вы имеете в виду сложить два rnd7(), то получится число от 0 до 12 включительно. И распределение будет очень неравномерным.

n = rnd7() + rnd7()

n p(n)
0 1/49
1 2/49
2 3/49
3 4/49
4 5/49
5 6/49
6 1/7
7 6/49
8 5/49
9 4/49
10 3/49
11 2/49
12 1/49
User avatar
SVK
Уже с Приветом
Posts: 8422
Joined: 23 Jul 2003 03:53
Location: SPb - KW - NY - CT - MD

Re: Алгоритмическая задачка.

Post by SVK »

int( float( rnd7()*7 + rnd7() ) / 4.9 )

Правда, равномерность опять под вопросом.
49 равномерных значений никак не перекладываются на 10 равномерных же...

Можно попробовать (в терминах Си):
rnd7()*7 + rnd7() - от 0 до 48
rnd7()*7 + rnd7() + (rnd7() == 1) - от 0 до 49
(float)( rnd7()*7 + rnd7() + (rnd7() == 1) ) / 5.0 - от [0.0; 9.8]
(int)( ( (float)( rnd7()*7 + rnd7() + (rnd7() == 1) ) / 5.0 ) - от 0 до 9

Или лучше так:
rnd7()*7 + rnd7() - от 0 до 48
rnd7()*7 + rnd7() + (rnd7() + rnd7() < 7) - от 0 до 49 (т.е. добавить 1 с вероятностью 1/2)
(float)( rnd7()*7 + rnd7() + (rnd7() + rnd7() < 7) ) / 5.0 - от [0.0; 9.8]
(int)( ( (float)( rnd7()*7 + rnd7() + (rnd7() + rnd7() < 7) ) / 5.0 ) - от 0 до 9
LG - Life's good.
But good life is much better.
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

SVK wrote: 11 Jul 2024 13:13 rnd7()*7 + rnd7() - от 0 до 48
Вот смотрите, из всего перечисленного это единственное что даёт равномерное распределение. 49 вариантов каждый с вероятностью равной 1/49.

Можно это совместить со второй подсказкой и "выкинуть" какое-то количество вариантов чтобы потом оставшиеся разложились поровну в 10 кучек?
User avatar
SVK
Уже с Приветом
Posts: 8422
Joined: 23 Jul 2003 03:53
Location: SPb - KW - NY - CT - MD

Re: Алгоритмическая задачка.

Post by SVK »

while( (x = rnd7()*7 + rnd7() ) > 39 );
x = (int)( (float)x / 4.0 );


По правде, "очень далеки они от народа"(C).
И от реальных потребностей.
LG - Life's good.
But good life is much better.
User avatar
Сева
Уже с Приветом
Posts: 2619
Joined: 24 Feb 2022 20:31
Location: 20yrs:USA->Россия

Re: Алгоритмическая задачка.

Post by Сева »

Сперва бы конечно освежить наши институтские познания теории вероятности )
Как там ведут себя произведения и суммы нормального распределения?
User avatar
SVK
Уже с Приветом
Posts: 8422
Joined: 23 Jul 2003 03:53
Location: SPb - KW - NY - CT - MD

Re: Алгоритмическая задачка.

Post by SVK »

Вообще-то, в том же Си повсеместно предлагается генерировать случайные числа, к примеру, в диапазоне [1; 20000] таким способом:

int rand20000 = rand() % 20000 + 1;

И совершенно никто не заморачивается, что диапазон [1; 10000] появляется примерно вдвое чаще, чем [10001; 20000] :pain1:
LG - Life's good.
But good life is much better.
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

SVK wrote: 12 Jul 2024 12:29 while( (x = rnd7()*7 + rnd7() ) > 39 );
x = (int)( (float)x / 4.0 );
Получилось !

Теперь можно попробовать решить вторую половину задачки, чтобы сгенерировать много rnd10() и минимизировать количество rnd7(). Сразу могу дать подсказку что минимум ограничен теорией информации. Позвав rnd7() мы "получаем" энтропии log2(7), а сгенерировав rnd10() мы отдаём энтропии log2(10).
По правде, "очень далеки они от народа"(C).
И от реальных потребностей.
Так в разделе "головоломки" много других задачек которые далеки от потребностей :)
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

Сева wrote: 12 Jul 2024 13:17 Сперва бы конечно освежить наши институтские познания теории вероятности )
Как там ведут себя произведения и суммы нормального распределения?
Распределение суммы - тоже нормальное распределение (посмотрите ЦПТ)

Распределение произведения - там как-то сложно, в "институте" не учили :)
DropAndDrag
Уже с Приветом
Posts: 6239
Joined: 11 Mar 2011 05:36

Re: Алгоритмическая задачка.

Post by DropAndDrag »

alex1979 wrote: 11 Jul 2024 05:41
DropAndDrag wrote: 11 Jul 2024 04:46 первое rnd7() заполняет от 0 до 6
второе rnd7()+7 заполняет от 7 до 14
Непонятно что значит "одно заполняет от 0 до 6, другое заполняет от 7 до 14".

Если вы имеете в виду сложить два rnd7(), то получится число от 0 до 12 включительно. И распределение будет очень неравномерным.

n = rnd7() + rnd7()

n p(n)
0 1/49
1 2/49
2 3/49
3 4/49
4 5/49
5 6/49
6 1/7
7 6/49
8 5/49
9 4/49
10 3/49
11 2/49
12 1/49
нет.
0 = rnd7()
next = rnd(7()+7 if < 10 else miss
next = rnd7()
next = rnd(7()+7 if < 10 else miss
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

DropAndDrag wrote: 13 Jul 2024 03:48 нет.
0 = rnd7()
next = rnd(7()+7 if < 10 else miss
next = rnd7()
next = rnd(7()+7 if < 10 else miss
Всё равно не понятно. Напишите программу на каком-нибудь языке программирования.

Вот, например, решение которое описал SVK на питоне.

Code: Select all

def rnd10():
    while True:
        n = rnd7()*7+rnd7()
        if n<40:
            return n//4
DropAndDrag
Уже с Приветом
Posts: 6239
Joined: 11 Mar 2011 05:36

Re: Алгоритмическая задачка.

Post by DropAndDrag »

давно уже не писал на текстовом языке. также можно как-то код вставлять, но не знаю как.
типа так:
int * rnd10( int iCount){
int * array = new [] (iCount);
int type = 0;
for( int i = 0; i < iCount;}{
if( type == 0){
array[ i] = rnd7(); i++; type = 1;
}else{
int temp = rnd7() + 7;
if( temp < 10){
array[ i] = temp; i++;
}
type = 0;
}
}
return array;
}
alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

DropAndDrag wrote: 13 Jul 2024 05:32 давно уже не писал на текстовом языке. также можно как-то код вставлять, но не знаю как.
Надо в квадратнык скобках написать "code" и "/code" точно так же как и "quote" и "/quote". Кнопка рядом с кавычками.

Получается вот так:

Code: Select all

int * rnd10( int iCount){
    int * array = new [] (iCount);
    int type = 0;
    for( int i = 0; i < iCount;}{
         if( type == 0){
             array[ i] = rnd7(); i++; type = 1;
         }else{
             int temp = rnd7() + 7;
             if( temp < 10){
                  array[ i] = temp; i++;
             }
             type = 0;
         }
    }
    return array;
}

alex1979
Новичок
Posts: 31
Joined: 05 Jul 2024 21:17

Re: Алгоритмическая задачка.

Post by alex1979 »

alex1979 wrote: 13 Jul 2024 08:45
DropAndDrag wrote: 13 Jul 2024 05:32 давно уже не писал на текстовом языке. также можно как-то код вставлять, но не знаю как.
Надо в квадратнык скобках написать "code" и "/code" точно так же как и "quote" и "/quote". Кнопка рядом с кавычками.

Получается вот так:

Code: Select all

int * rnd10( int iCount){
    int * array = new [] (iCount);
    int type = 0;
    for( int i = 0; i < iCount;}{
         if( type == 0){
             array[ i] = rnd7(); i++; type = 1;
         }else{
             int temp = rnd7() + 7;
             if( temp < 10){
                  array[ i] = temp; i++;
             }
             type = 0;
         }
    }
    return array;
}

Это не правильно.

Первый элемент (array[0]) имеет равномерное распределение [0,6], а надо [0,9].
User avatar
SVK
Уже с Приветом
Posts: 8422
Joined: 23 Jul 2003 03:53
Location: SPb - KW - NY - CT - MD

Re: Алгоритмическая задачка.

Post by SVK »

Code: Select all

int rnd10()
{
   int x, y;
   while( (x = rnd7() ) > 5 );
   while( (y = rnd7() ) > 4 );
   return (int)( (float)( x * 7 + y ) / 4.0 );
}
LG - Life's good.
But good life is much better.
DropAndDrag
Уже с Приветом
Posts: 6239
Joined: 11 Mar 2011 05:36

Re: Алгоритмическая задачка.

Post by DropAndDrag »

alex1979 wrote: 13 Jul 2024 09:01
alex1979 wrote: 13 Jul 2024 08:45
DropAndDrag wrote: 13 Jul 2024 05:32 давно уже не писал на текстовом языке. также можно как-то код вставлять, но не знаю как.
Надо в квадратнык скобках написать "code" и "/code" точно так же как и "quote" и "/quote". Кнопка рядом с кавычками.

Получается вот так:

Code: Select all

int * rnd10( int iCount){
    int * array = new [] (iCount);
    int type = 0;
    for( int i = 0; i < iCount;}{
         if( type == 0){
             array[ i] = rnd7(); i++; type = 1;
         }else{
             int temp = rnd7() + 7;
             if( temp < 10){
                  array[ i] = temp; i++;
             }
             type = 0;
         }
    }
    return array;
}

Это не правильно.

Первый элемент (array[0]) имеет равномерное распределение [0,6], а надо [0,9].
и что?
все элементы меньше 7 имеют равномерное распределение с вероятностью попадания 0.7.
все элементы от 8 до 10 имеют равномерное распределение исходя из равномерного распределения от 8 до 13 с вероятностью попадания 0.3.
и где неравномерность? кстати, можно упростить код и вызывать rnd7() один раз - нет требования случайного распределения.

Return to “Головоломки”