伪随机数的生成的一个算法的问题,怎么才能采用C程序的语言的办法来实现这个程序的设计的呢?

Problem Description
Access to high-quality randomness is very important for many applications, especially in cryptography. Radioactive decay is somtimes used as a source of 搕rue randomness? but this is a fairly slow procedure for getting random numbers. Also, in many applications it is important that the same 搑andom?sequence can be produced in two different places. For these reasons one often uses a pseudo-random sequence instead. A pseudo-random sequence is a sequence that is, in fact, not random, but very hard to distinguish from a truly random sequence. A pseudo-random sequence should also be difficult to predict, i.e., given the first few elements of the sequence it should be difficult do determine some later, yet unseen, number in the sequence.

The Association of Cryptographic Machinery (ACM) has devised an algorithm for generating pseudo-random number sequences, but they have no idea how good it really is.Therefore they want you to test it.

The algorithm to generate a sequence of integers, where each integer is between 0 and B − 1 inclusive, is as follows:
1. Start with any number (the seed) in base B. This number can contain hundreds of base B digits.
2. The last digit (least significant) is output as the next element of the sequence.
3. Create a new number by writing down the sum of all neighbouring digits from left to right. E.g., with B = 10, the number 845 would yield the number 129 (since 8 + 4 = 12 and 4 + 5 = 9).
4. Repeat steps 2 and 3 as many times as needed, or until the number has only one base B digit. You get one more pseudo-random digit between 0 and B − 1 each time.

If we have B = 10 and the seed number is 845, then the next numbers will be 129, 311 (1 + 2 = 3, 2 + 9 = 11), 42 (3 + 1 = 4, 1 + 1 = 2), and 6 (4 + 2 = 6). As 6 is a single digit base 10 number, the algorithm terminates. The pseudo-random digits generated are 5, 9, 1, 2 and 6.

You will be testing the generator as follows. You will be given the first L elements output by the generator and an integer T > L. You are supposed to decide if the first T elements are completely determined by the first L elements. To check the robustness of your testing procedure the ACM have slipped in some impossible sequences, i.e. sequences that cannot be generated by any initial seed.

Input
On the first line of the input is a single positive integer N, telling the number of test cases to follow. The first line of each test case consists of one integer B (2 <= B <= 1 000), the base. The second line consists of an integer L (1 <= L <= 100), followed by the L first elements of some sequence (the elements are written in base 10 and are between 0 and B − 1 inclusive). The third line consists of an integer T, (L < T <= 100 000), the element of the sequence to predict.

Output
For each test case output, on a line of its own:
?搃mpossible?if no seed number can produce the given sequence.
?搖npredictable?if there exists a seed number that produces the given sequence but the first T elements are not completely determined by the first L elements.
?the T:th element of the sequence in base 10, otherwise.

Sample Input
3
10
5 5 9 6 7 0
7
16
4 11 7 8 4
12
2
5 0 1 1 1 0
10

Sample Output
8
unpredictable
impossible

1个回答

the first line of the input is a single positive integer N, telling the number of test cases to follow. The first line of each test case consists of one integer B (2 <= B <= 1 000), the base. The second line consists of an integer L (1 <= L <= 100), followed by the L first elements of some sequence (the elements are written in base 10 and are between 0 and B − 1 inclusive). The third line consists of an integer T, (L < T <= 100 000), the element of the sequence to predict.

Output

shunfurh
shunfurh I wanna fuck your mother
5 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
c语言伪随机数产生程序的问题
哪位高手能讲一下在C语言中怎样用伪随机数产生程序生成随机的整数?
VB编写生成伪随机数的程序
用到混合同余法的递推公式rn[img=http://hiphotos.baidu.com/289719836/pic/item/abcd4883b2b7d0a201947c3ccbef76094a369a2f.jpg][/img]rn谢谢大家了
伪随机数生成的一个问题
程序如下:rn[code=C/C++]rn#include rn#include rn#include rnusing namespace std;rnrnunsigned long int next = 1;rnrnvoid mysrand(unsigned int seed)rnrn next = seed;rnrnrnint myrand()rnrn cout << "next: " << next << endl;rn next = next * 1103515245 + 12345;rn unsigned int ret = (unsigned int)(next / 65536) % 32768;rn return ret;rnrnrnint main()rnrn mysrand((unsigned int)time(0));rn for (int i = 0; i < 10; ++i)rn rn //mysrand((unsigned int)time(0));rn cout << myrand() << endl;rn rn rn return 0;rnrn[/code]rn为什么如果将 mysand((unsigned int)time(0)) 放在循环里,每次都到的伪随机数都是一样的rn把 mysand((unsigned int)time(0)) 放在循环外,这样只调用 mysrand 一次,循环里每次的 种子 都不一样了rn谁能解释一下?
c 语言 程序 设计
经典的课件,学习C语言必备。希望对学习有帮助
C语言设计------第二章 算法---程序的灵魂
第二章 算法—程序的灵魂 2.1
伪随机数的生成算法
1. 线性同余发生器
伪随机数生成算法
参考 Random number generation Pseudorandom number generator Linear congruential generator RANDU Randomness tests Randomness Tests: A Literature Survey Testing Pseudo-Random Number Generators Validatio...
伪随机数生成算法及比较
随机数的生成算法比较,包括一些代码,效率比较,以便实现蒙特卡罗法
怎么设计这个程序
我有5个变量,然后5个变量各可以取6个值,,在一次过程中可以得到一个结果,,rn我用五层循环来做,rnfor i=1:6rn for j=1:6rn for m=1:6rn ...rn可是最后我不知道如何来存储这个结果,,我的目标是观察这些变量变化时对结果的影rn响,
这个程序怎么设计
Helper类rnComonn 类字段ListrnMain窗体rn当Helper发生报警的时候,common的List加1,如果main窗体已经打开,触发窗体的tabControl1_SelectedIndexChanged事件,main窗体需要用到Comonn 类字段Listrn
这个小程序怎么设计呢?
一个小程序,使能够在屏幕特定位置定时,如1分钟执行鼠标左键点击操作。
怎么采用C语言的程序编写的过程实现序列的删除
Problem Description There is an undirected graph G with n vertices and m edges. Every time, you can select several edges and delete them. The edges selected must meet the following condition: let G′ be graph induced from these edges, then every connected component of G′ has at most one cycle. What is the minimum number of deletion needed in order to delete all the edges. Input There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case: The first line contains two integers n and m (1≤n≤2000,0≤m≤2000) -- the number of vertices and the number of edges. For the next m lines, each line contains two integers ui and vi, which means there is an undirected edge between ui and vi (1≤ui,vi≤n,ui≠vi). The sum of values of n in all test cases doesn't exceed 2⋅104. The sum of values of m in all test cases doesn't exceed 2⋅104. Output For each test case, output the minimum number of deletion needed.
c语言怎么生成一个位图按钮呢?
在c++中从cbutton继承一个救星,但是c语言怎么弄呢?rn3q
这个程序怎么才能运行
#include rn#include rn#include "glos.h"rn#include rnrnvoid main(void)rnrn auxInitDisplayMode(AUX_SINGLE|AUX_RGBA);rn auxInitPosition(0,0,500,500);rn auxInitWindow("mjken");rn glClearColor(0.0,0.0,0.0,0.0);rn glClear(GL_COLOR_BUFFER_BIT);rn glColor3f(1.0,0.0,0.0);rn glRectf(-0.5,-0.5,0.5,0.5);rn glFlush();rn _sleep();rnrn///rn这个是一个opengl的小程序rn但运行的时候老是有错误rn--------------------Configuration: opgl位图 - Win32 Debug--------------------rnCompiling...rnopgl位图.cpprnd:\program files\microsoft visual studio\vc98\include\gl\gl.h(1152) : error C2144: syntax error : missing ';' before type 'void'rnd:\program files\microsoft visual studio\vc98\include\gl\gl.h(1152) : error C2501: 'WINGDIAPI' : missing storage-class or type specifiersrnd:\program files\microsoft visual studio\vc98\include\gl\gl.h(1152) : fatal error C1004: unexpected end of file foundrnError executing cl.exe.rnrn我在project setting 那里设置了 把一些lib文件加进去了 但还是有问题 请大家帮帮忙 分析一下 rn等待 谢谢
C语言是怎么设计程序窗体的?
如题目,多谢。还有现在很少人用C编程序了吗??
语法分析器的设计与实现程序(c语言) 词法分析器的设计与实现程序(c语言)
赶快
来一个C程序
1.利用指向一维数组的指针作为函数参数具体实现:rn (1)求数组最大元素及其所在位置。函数首部为:void fun_max(int * x, int * max, int *p,int n),其中x为指向数组的指针,max为指向最大元素的指针,p为指向最大元素位置的指针,n为数组元素的长度。rn (2)利用选择排序对数组元素按照从小到大排序。rn 函数首部为:void sort(int * x, int n) ,其中x为指向数组的指针,n为数组元素的长度。
AutoCAD与C语言接口程序的设计与实现
AutoCAD与C语言接口程序的设计与实现
C语言汉字显示程序的设计实现
可以把此程序写成自己的函数... 在程序中直接调用此函数即可以随时实现汉字的显示
ping程序的设计与实现(C语言)
计算机 网络 课程设计 ping程序的设计与实现 (C语言)
怎么用c语言编译这个程序
/**对于任一整数n,符号函数sign(n)的定义如下:rnrsign(n)=-1(n<0);sign(n)=0(n=0);sign(n)nr=1. (n>0);nrn请编写程序计算该函数对任一输入整数的值。rnrn输入格式:rnrn输入在一行中给出整数n。rnrn输出格式:rnrn在一行中按照格式“sign(n) = 函数值”输出该整数n对应的函数值。rnrn输入样例1:rn10rnrnrn输出样例1:rnsign(10) = 1rnrnrn输入样例2:rn0rnrnrn输出样例2:rnsign(0) = 0rnrnrn输入样例3:rn-98rnrnrn输出样例3:rnsign(-98) = -1rn**/
怎么用C语言做这个程序
一班有10名学生,一学期有5门课程,编写程序实现如下功能:rn(1)录入每名学生的各科成绩rn(2)求出每名学生的平均成绩和总分rn(3)求每门课程的平均分、及格率、最高成绩和最低成绩rn(4)输出总成绩前5名的学生学号、各科成绩和总分rn(5)输出各科补考学生的学号和成绩rn要求:rn(1)编制一主函数来实现功能菜单的显示和各功能函数的调用;rn(2)程序设计各步骤的相关文档齐全、清晰。rn(3)在所有数据输入处理之前提供必要的提示
M序列生成程序 采用verilog语言
采用verilog语言 生成m序列 用用一位寄存器原理
自我复制数字的程序,这个算法怎么用C语言
Problem DescriptionrnSherlock is fond of playing with numbers. Two days ago he discovered that 9376^2 = 87909376 - the last four digits constitute 9376 again. He called such numbers self-replicating.rnrnMore precisely, an n-digit number is called self-replicating if it is equal to the number formed by the last n digits of its square. Now Sherlock often asks Xay to help him to find new such numbers. To make the things worse, Sherlock already knows what the scales of notation are, so he asks Xay to find, for example, hexadecimal or binary self-replicating numbers.rnrnXay wants to help Sherlock, but unfortunately he is very busy now: he is seriously preparing and training for the next ACM Regional Contest. So he asked you to write a program that for a given base b and length n will find all n-digit self-replicating numbers in the scale of notation with base b.rn rnrnInputrnthere are multiple test cases. one line of each test case contains two integer numbers b and n separated by a single space, the base b of the scale of notation (2 ≤ b ≤ 36) and the required length n (1 ≤ n ≤ 2000).rn rnrnOutputrnFor eacho test case, the first line contains K - the total number of self-replicating numbers of length n in base b. Next K lines contain one n-digit number in base b each. Uppercase Latin letters from A to Z must be used to represent digits from 10 to 35. The self-replicating numbers should be output int lexicographic order.rn rnrnSample Inputrn2 1rn10 4rn rnrnSample Outputrn2rn0rn1rn1rn9376
c 语言日志生成程序
c语言生成日志程序,可以实现简单的分级,日志纪要等
请教一个伪随机数生成问题。
假设网络中的一个计算机结合,现在需要每个计算机生成一个伪随机数(例如32位数),但是不想这些计算机间相互通信,有没有什么算法或思想使这些计算机生成的伪随机数不相互冲突(即在一段时间和网络范围内,生成的伪随机数个不相同,或相同的概率很小)rn?rn如果有什么相关的文献或思想,请赐教!rn谢谢!
c语言设计程序字符转换
输入一段字符串,输入句号如何将其中的中句号转换成感叹号,输入逗号转换成句号?n
C语言综合设计程序
C语言综合设计程序
C语言 菜单程序的设计
题目:rn编写一个基于菜单的C程序,列出下列菜单rn1.绘制矩形rn2.绘制正方形rn3.退出rnrn用VC++作,用C语言实现,可以用上下光标选择。rnrn请问如何做?rnrnrn
c语言的程序一个
c语言的程序一个
时钟设计程序 c语言
用c语言写的时钟设计电路 AT89C51
C语言设计WIN32程序
C语言设计WIN32程序,基于windows32位的C语言教程
C语言 程序 设计 doc
word 方便在安卓手机上查看
c语言设计的时钟程序
外形美观大方 时间准确 背景典雅 可做个人背景修改
求人看下 这个程序怎么实现呢
SET TALK OFFrnclose allrnCLEARrnSELE 1rnuse ylk.dbfrnSELE 2rnUSE 三库总合表.dbfrnrnrnGO 1rnDO WHILE .NOT.EOF()rn?recno()rna=身份证号rnb=姓名rnrnSELE 1rnloca for sfzh=a AND xm=BrnIF FOUND() rnrnsele 2rnrnrepl 是否在养老 with '是'rnELSErnrnSELE 2rnrepl 是否在养老 with '否' // 到这里还正确rn//对比不出身份和姓名同时一样的情况的 在 YLK.DBF中把名字一样的选出来 全部插到 当前后面 以便人员看比对rn下面就是rnsele 3rnrnsele * from ylk.dbf where xm=arnrngo 1rndo while .not.eof()rnc=sfzh //身份证号rnd=xm //姓名rnrnsele 2rnINSERT INTO 三库总合表.dbf(身份证号 , 姓名)VALUES(c,d)rnsele 3rnskiprnenddornrnendifrnrnrn//以上程序错误rnSELE 2rnSKIPrnenddornCLOS ALLrnSET TALK ON
伪随机数生成算法及比较.pdf
伪随机数生成算法及比较.pdf 分析了各种常见的伪随机数,并对其特征作了简要描述,并予以比较。
c语言折半算法程序
利用折半算法实现对数字的随机排序,有完整的实现的代码
PID算法程序C语言
PID程序源文件,实测可用,贴出来与大家共享,希望对大家有用
c语言 算法和程序 详细
详细 稀疏矩阵的三元组表示 链队列 循环队列 字符串 链表合并 多项式相加 二叉树
《c语言算法程序例程》
用C语言实现各种算法,包含了大量实现算法的例子,如链表等。
相关热词 c# 标准差 计算 c#siki第五季 c#入门推荐书 c# 解码海康数据流 c# xml的遍历循环 c# 取 查看源码没有的 c#解决高并发 委托 c#日期转化为字符串 c# 显示问号 c# 字典对象池