读书人

新Josephus排列有关问题用C++该如何

发布时间: 2012-08-17 02:08:34 作者: rapoo

新Josephus排列问题,用C++该怎么做???
新Josephus排列问题定义如下:假设n个人排成一个环形,给定一个正整数m,从第1
个人开始,沿环计数,每遇到第m个人就让其出列,这时计算器m自动加一,且计数继续进
行下去。这个过程一直进行到所有的人都出列为止,最后出列者为赢家。设这n个人的编号
分别为1~n,每次从编号为1 的竞赛者开始计数,那么每个人出列的次序定义为整数1~n
的一个排列。这个排列称为一个(n,m)Josephus排列。
例如,(7,3)Josephus 排列为3,7,6,2,4,1,5。
对于给定的1,2,…,n中的k个数,Josephus想知道是否存在一个正整数m使得
(n,m)Josephus排列的前k个数恰为事先指定的这k个数。

编程任务:
(1)用抽象数据类型表设计一个求(n,m)Josephus排列的算法。
(2)试设计一个算法,对于给定的正整数n和1,2,…,n中的k个数。求正整数m,使
(n,m)Josephus排列的前k个数恰为事先指定的这k个数(顺序必须完全一样)。

数据输入:
由文件input.txt给出输入数据。第一行有2 个正整数n和k,分别表示有n个人和指定
的人数k。接下来的k行中,每行有1 个数,表示事先指定的k个人在排列1,2,…,n中的
位置。再接下来的n行是按照顺序1,2,…,n排列的n个人的名字。


这个问题用C++来做,要怎么指定啊?“试设计一个算法,对于给定的正整数n和1,2,…,n中的k个数。求正整数m,使
(n,m)Josephus排列的前k个数恰为事先指定的这k个数(顺序必须完全一样)。”

一头雾水……

有哪位高人能为我指点迷津??万分感谢!!!


[解决办法]
厄……貌似楼上的例子无解。

无解也是解。像这样无论怎么调整m,都只得到几种循环的不含期望值状态的情况可以判断为无解。

读书人网 >C++

热点推荐