搜狗16招聘机试题 加密解密算法

搜狗16招聘机试题 加密解密算法

题目：下面程序中，shuffle函数用于把整数数列打散，函数参数seed是一个随机种子，同一个随机种子产生一个确定的随机序列。请为shuffle写一个还原函数（restore）。其输入是经过shuffle打散的整数数列a[]以及打散时使用的随机种子seed，功能时将a[]数列还原为打散前的内容。
注意：本题要求额外空间开销越小越好，时间复杂度相对不重要。
输入：seed N 数值1 数值2 …. 数值N
输出：succeed！或者Failed！

代码：

#include <stdlib.h>
#include <stdio.h>
#include <stack>
using namespace std;void shuffle(int a[], size_t n, unsigned int seed)
{srand(seed);for (; n > 1; n--){unsigned int r = rand()%n;  //注意此处求余的n在变化int tmp = a[n - 1];a[n - 1] = a[r];a[r] = tmp;}
}void restore(int a[], size_t n, unsigned int seed)
{stack<unsigned int> istack;unsigned int r;srand(seed);for (int i = n; i >1; --i)      //先记录下随机序列{r = rand()%i ;          istack.push(r );}for (int i=1;i< n;++i)          //逆序解密{int tmp = a[i];r = p();a[i] = a[r];a[r] = tmp;istack.pop();}
}int main(void)
{unsigned int seed;unsigned int n;unsigned int i;int *a, *b;scanf("%u", &seed);scanf("%u", &n);a = (int *)malloc(sizeof *a * n);b = (int *)malloc(sizeof *b * n);for (i = 0; i < n; i++){scanf("%d", &a[i]);b[i] = a[i];}shuffle(a, n, seed);restore(a, n, seed);for (i = 0; i < n; i++){if (a[i] != b[i])break;}if (i == n)printf("Success!n");elseprintf("Failed!n");free(a);free(b);return 0;
}

测试结果：