Рандом из павно

papercut

Участник
Автор темы
90
13
Ситуация такая: Стол казино, на нем выпадает некая последовательность, выдаваемая павновским рандомом (известная функция). Этот рандом независим ни от чего другого. То есть последовательность выдаваемых чисел на столе 100% принадлежит только этому столу.
Проблема в том, что между выпадениями производится некоторое количество вызовов рандома впустую. У меня явно не хватает теоретических математических знаний

Вопрос: Как возможно найти эту последовательность и вычислить случайное количество пропусков?

Сейчас я написал скрипт, который использует базу из 300 выпавших на одном столе подряд значений. Проблема скрипта в том, что я вручную указываю максимальное количество пропусков между двумя числами. На данный момент при максимальном значении пропусков = 100 у меня находится одна единственная последовательность. Но нет гарантии, что максимум пропусков не могло быть больше 100. Повторюсь, число пропусков неизвестно.

А еще прикол в том, что как только база выпавших значений становится достаточно большой, скрипт перестает находить хотя бы одно совпадение. Делаем вывод, что использовано неверное максимальное число пропусков. Увеличиваю число и моментально находятся десятки возможных вариантов. Это, по моему, бесконечный (на практитке. В теории-то, конечный) цикл.

Сам сакрипт, если кому интересно:
#include <limits.h>
#include <stdio.h>
#include <time.h>

//https://github.com/pawn-lang/compiler/blob/master/source/amx/amxcore.c
#define INITIAL_SEED  0xcaa938dbL
static unsigned long IL_StandardRandom_seed = INITIAL_SEED; /* always use a non-zero seed */
#define IL_RMULT 1103515245L
static long random()
{
    unsigned long lo, hi, ll, lh, hh, hl;
    unsigned long result;

    lo = IL_StandardRandom_seed & 0xffff;
    hi = IL_StandardRandom_seed >> 16;
    IL_StandardRandom_seed = IL_StandardRandom_seed * IL_RMULT + 12345;
    ll = lo * (IL_RMULT  & 0xffff);
    lh = lo * (IL_RMULT >> 16    );
    hl = hi * (IL_RMULT  & 0xffff);
    hh = hi * (IL_RMULT >> 16    );
    result = ((ll + 12345) >> 16) + lh + hl + (hh << 16);
    result &= ~LONG_MIN;        /* remove sign bit */

    return result;
}

int myrand()
{
    return random() % 37;
}

#define N 312
#define X 100

int main()
{
    int nums[N] = { 26,34,1,8,7,29,19,21,24,34,24,21,4,0,23,9,17,21,9,15,31,28,14,16,31,29,4,25,10,10,17,31,30,15,28,4,1,16,21,22,19,24,35,19,4,13,3,18,7,20,9,3,20,6,33,31,33,31,1,35,8,31,30,34,24,36,24,32,8,29,11,13,33,3,16,5,30,30,35,3,4,14,0,17,8,34,29,19,28,2,3,25,10,33,4,31,6,4,22,32,11,32,24,12,33,15,14,19,25,14,21,28,31,14,19,32,4,24,26,11,29,19,1,26,26,6,1,7,24,2,12,12,13,27,28,26,18,10,16,36,12,10,36,0,19,20,15,7,25,10,18,14,28,19,26,25,3,31,26,28,33,28,16,33,35,28,17,27,10,2,26,9,6,1,15,30,18,4,35,33,23,15,33,21,19,13,4,21,32,13,28,7,23,6,10,12,32,31,32,12,5,11,18,36,9,19,29,21,36,27,18,27,35,23,12,23,36,24,14,28,7,15,19,3,15,11,16,6,25,19,14,3,9,20,21,18,27,22,35,14,18,26,11,8,14,9,23,34,35,12,32,5,13,12,22,25,14,31,13,19,25,29,11,19,34,32,24,34,28,15,25,33,0,33,26,22,17,30,17,3,1,21,32,2,13,1,3,26,11,14,19,17,31,14,18,12,11,18,13,34,8,8,9,34,18,28,26,11,36,21,1};
    printf("Calculating...\n");
    clock_t start;
    start = clock();

    int maxskips = X;
    int minskips = 0;
    int willfind = 3;
    for(int i = 0; i < willfind; i++)
    {
        int skipsarr[N];
        int pointer = 0;
        int skips = 0;
        long seed = 0;
        while(pointer < N)
        {
            if(myrand() == nums[pointer] && skips > minskips)
            {
                if(pointer == 0)
                    seed = IL_StandardRandom_seed;
                skipsarr[pointer] = skips;
                pointer++;
                skips = 0;
            }
            skips++;
            if(skips > maxskips)
            {
                pointer = 0;
                skips = 0;
            }
        }
        printf("Found skips. Seed: %u\n", seed);
        IL_StandardRandom_seed = seed;
        for(int x = 0; x < N; x++)
        {
            
            printf("%3d (%3d),", skipsarr[x], random());
        }
            
        printf("\n\n");
    }
    // seed  3733827859
    printf("found %d", willfind);
    getchar();
    return 0;
}