[已解决]猴子排序算法中随机数问题

Crazyeye

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int in_order(int array[], int length);
void shuffle(int array[], int length);
void bogo_sort(int array[], int length);

int in_order(int array[], int length)
{
        int i = 0;

        while (array <= array[i+1] && ++i < length - 1)
                ;

        if (i == length - 1)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}

void shuffle(int array[], int length)
{
        int index, temp, i;
        static int t1, t2;

        srand(t1);//这里t1作为种子
        t1 = rand();//再把随机数赋值给t1，下次再循环种子（t1）就变了，这样每一次调用 srand(t1) 都会产生一个不一样的随机数种子

        t2 = time(NULL);//NULL这里取当前时间应该是一秒一变（+1），那这个t2有啥意义么？前面的t1已经很随机了。
        srand(t1+t2);
那这个种子就是一个一秒一变的数+随机数产生的随机种子的随机数，有人说为了避免伪随机，因为种子出来的随机数是均匀分布的，
那整体的看先看t2，相对时间一秒一变，cpu运算那么快，一秒之内这就是个定值！再看t1，虽然每一次调用 srand(t1) 都会产生一个不一样的随机数种子，
但是，这个还是均匀分布的啊，这个种子产生的随机数是一定的，他作为种子产生的随机数也是一定的啊，一直循环下去还是均匀分布的，
然后再加一个t2整体都加了一个定值的数，这怎么避免伪随机了？如果只为了随机产生数，t2的意义是啥？我的问题重点就是t2存在的意义，没有行不行，
或者说没有了会影响执行速度么？


        for (i = 0; i < length; i++)
        {
                index = rand() % (length - i) + i;//（第二个问题）为啥不直接用 rand() % length，也会影响速度么？怎么影响的
                if (index != i)
                {
                        temp = array;
                        array = array[index];
                        array[index] = temp;
                }
        }
}

void bogo_sort(int array[], int length)
{
        while (!in_order(array, length))
        {
                shuffle(array, length);
        }
}

int main(void)
{
        int array[] = {73, 108, 111, 118, 101, 70, 105, 104, 67};
        int i, length;
        time_t begin, end;

        begin = time(NULL);

        length = sizeof(array) / sizeof(array[0]);
        bogo_sort(array, length);

        printf("排序后的结果是：");
        for (i = 0; i < length; i++)
        {
                printf("%d ", array);
        }
        putchar('\n');

        end = time(NULL);
        printf("总共耗时：%ld秒\n", end - begin);

        return 0;
}

最佳答案

月排行榜 / 总排行榜

永恒的蓝色梦想

2020-8-25 18:57:58

qq1256740918 发表于 2020-8-25 15:38
不对，t1 是 static int 类型，是以 0 值初始化的。

没注意，疏忽了……

---

这样一来，t2 的作用就十分重要了。如果没有 t2，当 t1 初始值为 0 时，后面几次产生的随机数都是可以通过计算的出来的。

跳转到最佳答案楼层

永恒的蓝色梦想

多行注释是 /**/，不是 //

Crazyeye

永恒的蓝色梦想 发表于 2020-5-31 12:40
多行注释是 /**/，不是 //

我知道怎么了。。。。就是为了问问题啊，我//一行到底不好看就换了几行，好看点啊。懒得打/*

永恒的蓝色梦想

Crazyeye 发表于 2020-5-31 12:44
我知道怎么了。。。。就是为了问问题啊，我//一行到底不好看就换了几行，好看点啊。懒得打/*

那这个种子就是一个一秒一变的数+随机数产生的随机种子的随机数，有人说为了避免伪随机，因为种子出来的随机数是均匀分布的，
那整体的看先看t2，相对时间一秒一变，cpu运算那么快，一秒之内这就是个定值！再看t1，虽然每一次调用 srand(t1) 都会产生一个不一样的随机数种子，
但是，这个还是均匀分布的啊，这个种子产生的随机数是一定的，他作为种子产生的随机数也是一定的啊，一直循环下去还是均匀分布的，
然后再加一个t2整体都加了一个定值的数，这怎么避免伪随机了？如果只为了随机产生数，t2的意义是啥？我的问题重点就是t2存在的意义，没有行不行，
或者说没有了会影响执行速度么？

你愿意直接 srand(t1) 都行，未初始化内存块的值本身就随机

Crazyeye

永恒的蓝色梦想 发表于 2020-5-31 12:47
你愿意直接 srand(t1) 都行，未初始化内存块的值本身就随机

哦，就是没啥影响。。。怎么折腾都没啥大区别。。。

学生YT

为什么小甲鱼老师的程序执行不出来？

qq1256740918

永恒的蓝色梦想 发表于 2020-5-31 12:47
你愿意直接 srand(t1) 都行，未初始化内存块的值本身就随机

不对，t1 是 static int 类型，是以 0 值初始化的。

永恒的蓝色梦想

qq1256740918 发表于 2020-8-25 15:38
不对，t1 是 static int 类型，是以 0 值初始化的。

没注意，疏忽了……

---

这样一来，t2 的作用就十分重要了。如果没有 t2，当 t1 初始值为 0 时，后面几次产生的随机数都是可以通过计算的出来的。

风过无痕1989

主函数中调用函数 bogo_sort(array, length); 这里的 array 是以数组名作为实参传递给 bogo_sort 函数的形参，它传递的只是 array[] 这个数组的首地址，而不是 array[0] 的值，所以后面的 array <= array[i + 1] 就报错了，导致了内存不可读

风过无痕1989

int in_order(int array[], int length)
{
        int i = 0;

        while (array <= array[i+1] && ++i < length - 1)
                ;
        ......

将所有函数里的 array 替换成 array[ i ] 之后调试，系统的报错没有了，但新的问题出现了，整个程序进入了死循环，原因是 in_order() 这个函数用 while 循环了半天，什么都没做，仅仅是返回 1，返回 0 而已