根据公式产生随机数矩阵,怎么使用C语言的程序代码编写的过程有效的实现这个问题的算法的

Description

A Black Box algorithm supposes that natural number sequence u(1), u(2), ..., u(N) is sorted in non-descending order, N <= M and for each p (1 <= p <= N) an inequality p <= u(p) <= M is valid.

Making tests for this algorithm we have met with the following problem. For setting a random sequence {u(i)} a usual random data generator did not fit. As the sequence itself had been imposed certain restrictions, the method of choosing the next random element (in the interval defined by restrictions) did not give the random sequence as a whole.

We have come to a conclusion that the problem can be solved in the following way. If we arrange all possible sequences in certain order (for example, in lexicographical order) and assign each sequence its number, after choice of the random number it is possible to take the correspondent sequence for the random one. At the first glance it seems enough to make up a program generating all these sequences in such order. Alas! Even having not great values of M and N it would have taken any powerful modern computer centuries to enumerate all such sequences. It turned out it was possible to avoid generating all sequences if we managed to create required sequence according to its number immediately. But even this statement does not cover all. As the amount of sequences is quite large, the number can be a long one, composed of hundreds decimal digits, though our random data generator could give only normal numbers. We decided to produce a long random number from a real random number distributed in [0,1]. Namely, present the number in binary notation: 0.b(1)b(2)..., where all b(i) = 0 or 1. Let us set a regulation to associate such real number to an integer from [A,B] segment:
Formula 1:

Here we suppose, that A <= B, p >= 0, and ``div 2" is an integer division by 2.

Let M, N (1 <= N <= M <= 200) and a binary real number 0.b(1)b(2)...b(p) (1 <= p <= 400) be given. Write a program to find out the corresponding u(1), u(2), ..., u(N) sequence, i.e. to find a sequence with G(1,T,0.b(1)b(2)...b(p)) number in lexicographical order of all possible {u(i)} for the given M and N (T is the quantity of such sequences). Numeration begins with 1. Keep in mind that in lexicographical order {l(i)} proceeds {h(i)} if after omitting equal beginnings, the first number of {l(i)} tail is smaller than the first number or {h(i)} tail. Following example illustrates the list of all possible sequences for M = 4 and N = 3 in lexicographical order.

A note (it does not concern the solution of this task):

The choice of random binary vector 0.b(1)b(2)...b(p) does not give an absolute uniform random data generator if we use the Formula. However, taking into account the fact that [A,B] interval is big we shall obtain a distribution applicable in most cases.
Example

1, 2, 3

1, 2, 4

1, 3, 3

1, 3, 4

1, 4, 4

2, 2, 3

2, 2, 4

2, 3, 3

2, 3, 4

2, 4, 4

3, 3, 3

3, 3, 4

3, 4, 4

4, 4, 4

(here T=14)
Input

The first line of input contains M and N. The second line contains binary real number 0.b(1)b(2)...b(p) (without leading, trailing and other spaces).
Output

Write into the output the corresponding sequence u(1), u(2), ..., u(N). The sequence numbers should be separated with one space.
Sample Input

4 3
0.01101101011110010001101010001011010
Sample Output

2 2 4

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

3
php mt_rand()同一秒产生了相同的随机数,这是为什么?
2
C语言,根据rand()返回的位于整个值域内的数字,选择一个数字,来确定随机数字,怎么写这个程序
1
c语言如何生成(0,1)之间均匀分布的随机数?
1
哪位有带弃权概率的囚徒困境相关c语言的代码吗?
1
c语言中如何根据概率进行选择随机数?
1
javascpt语言多个结果取任意一个,随机数怎么得到并且设置选择框
1
求助:c++随机数四则运算10题程序
1
c#语言 完成随机点餐代码
1
伪随机数的生成的一个算法的问题,怎么才能采用C程序的语言的办法来实现这个程序的设计的呢?
0
C语言程序设计一个小学生四则运算系统
1
求助C语言的猜数字游戏
1
学弱求助C语言猜数字游戏
1
随机抽取备选数字代码
1
怎么检测每次获取的随机数是否满足随机性?
0
均匀的随机数的生成算子的实现,利用C语言的程序的编写的技术怎么实现
0
二进制随机的数字的一个计算结果,怎么采用C语言程序编写代码的方法来实现的输出呢?
0
到达第T棵树,一共有多少种行走方案数,怎么运用C语言的程序代码设计的思想去实现呢?
0
c语言编的粒子群算法,迭代过程中目标函数值一直不变
0
序列计算连续最大积,怎么使用C语言的程序编写代码方式有效加以实现的
0
以随机顺序逐点打分计算总分的范围,用C语言的程序编写代码的形式去解决的做法