Эффективный алгоритм подсчета частоты чисел в интервалах

Question

Мне нужно построить столбчатую диаграмму, иллюстрирующую распределение псевдослучайных чисел, определяемое линейным конгруэнтным методом.

Xn+1 = (a * Xn + c) mod m
U = X/m

на интервале [0,1]

Например:

Interval           Frequency     
[0;0,1]            0,05
[0,1;0,2]          0,15
[0,2;0,3]          0,1
[0,3;0,4]          0,12
[0,4;0,5]          0,1
[0,5;0,6]          0,15
[0,6;0,7]          0,05
[0,7;0,8]          0,08
[0,8;0,9]          0,16
[0,9;1,0]          0,4

Я использовал такой метод:

float mas[10] = {0,0,0,0,0,0,0,0,0,0};
void metod1()
{
    int x=-2, m=437, a=33, c=61;
    float u;
    for(int i=0;i<m;i++){
        x=(a*x + c) % m;
        u=(float)x/(float)m;
        int r;
        r = ceil(u*10);
        mas[r] = mas[r] + 1;
    }
    for(i=0;i<10;i++) cout<<"["<<(float)i/10<<";"<<(float)(i+1)/10<<"]"<<" | "<<mas[i]<<"\n-----------------"<<endl;
    return;
}

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

Answer 1

Ваш код в настоящее время имеет гораздо большую проблему эффективности. Предполагая, что вы определили mas как-то так int mas[10];имеет неопределенное поведение.

Чтобы увидеть проблему, давайте изменим ваш код, чтобы распечатать значения r что он генерирует:

void metod1() {
    int mas[11] = { };
    int x = -2, m = 437, a = 33, c = 61;
    float u;
    for (int i = 0; i < m; i++) {
        x = (a*x + c) % m;
        u = (float)x / (float)m;
        int r;
        r = ceil(u * 10);
        //mas[r] = mas[r] + 1;
        std::cout << r << '\t';
    }
//    for (i = 0; i < 10; i++) cout << "[" << (float)i / 10 << ";" << (float)(i + 1) / 10 << "]" << " | " << mas[i] << "\n-----------------" << endl;
    return;
}

Тогда давайте посмотрим на результаты:

0       -2      -7      -4      -7      -7      -6      0       -6      -1
-5      -6      -1      -9      -7      -2      -7      -3      0       -6
0       -8      -5      -6      -8      -6      -7      0       -2      -6
-7      -6      -2      -4      -9      0       -4      -5      -1      -2
-5      0       -2      -1      -4      -8      -5      -2      -8      -5
-9      -4      -5      -7      -9      -8      -3      -9      -9      -9
-3      -4      -5      -3      -9      -6      -5      -3      -1      0
-5      -5      -6      -7      -9      -5      -4      -1      -5      -1
-9      -2      0       -9      -6      -7      -5      -5      -3      -3
-9      -3      0       -4      -1      -1      0       -8      -4      -4
-2      -7      0       -6      -6      -8      -4      -8      -2      -8
-8      -2      -4      -7      -1      -6      -1      -3      -7      -3
-5      -9      -8      -5      -8      -7      -4      -1      -8      -7
-7      -2      -9      -5      -3      0       2       8       8       2
6       8       7       1       5       2       8       4       1       5
10      1       3       6       4       10      5       6       6       10

[более элитный]

Не похоже, что вы запланировали тот факт, что вы будете производить отрицательные числа, и если вы этого не сделаете, результатом будет неопределенное поведение, когда вы будете индексировать за пределами mas,