第四讲线性表

第四讲线性表

一、概述

在处理实际问题时,大量的是表格处理.例如,一个班级50名学生的某门考试的成绩表.

这类表通常称为“线性表”.每个表是一个整体，同时,它们又都是由多个互相独立的成分(或元素)

有序(线性)地组成的，各个成分的类型均相同，这种表在PASCAL语言中通常用数组来实现其组织和加

工.

线性表是最常用且最简单的一种数据结构.简而言之,一个线性表是N个数据元素的有限序列.至于

每个数据元素的具体含义,在不同的情况下各不相同,它可以是一个数,或一个符号，也可以是一页书,甚

至其它更复杂的信息.例如由每个英文字母组成的字母表：(A,B,C,……,Z)是一个线性表，表中的数据

元素是单个字符.又如某校从1993年至1998年各种型号计算机的拥有量的变化情况,可以用线性表的形

式给出(16,27,38,60,102,198)，表中的数据元素是自然数，线性表的特点是:

①存在唯一的一个被称作“第一个”的数据元素：

②存在唯一的一个被称为“最后一个”的数据元素；

③除第一个元素外,线性表中的每个数据元素均只有一个前驱；

④除最后一个元素之外，每个数据元素均只有一个后继.

综上所述,线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性，因此

属于同一类数据对象.

对线性表可进行的运算种类繁多，其中包括：

①确定表的长度n,即求表中数据元素的个数；

②从左到右(或从右到左)读表，即按山箱2…，a”(或如，a„.ia,)读取数据元素的值；

③存、取表中第i个数据元素IlWiWn),即改变或检查第i个数据元素的值；

④在第i-1个和第i个数据元素之间(IWiWn)插入一个新的数据元素，使原来的第i,i+I,

n个数据元素变成为第i+1,i+2,…，n,n+1个数据元素；

⑤删除第i个数据元素IlWiWn),使原来的第i+1,i+2,…，n个数据元素变成为第i,i+1,…，

n-1个数据元素.

⑥检索线性表，即在表中查找具有某个特征值的数据元素；

⑦对表排序，即按某个特征值递增(或递减)的顺序对表中的数据元素重新排列。

对一个线性表，同时要求进行上述的所有运算，这在计算机的应用中是很少有的。实际上，在很多

情况下，只需要完成其中的一局部运算就够了。

二、线性表的存储结构

在计算机内，线性表可以用不同的方式表示，即有多种存储结构可供选择。对于完成某种运算来说,

不同的存储方式，其执行效果是不一样的，为了使所要进行的运算得以有效地执行，在选择存储结构时,

必须考虑要施行的是哪些运算，对选定的存储结构，应估计这些运算执行时间的量级，以及它对存储容

量的要求。本讲只介绍数组形式存储的线性表。

在计算机内，存储线性表的最简单和最自然的方式，是把表中的数据元素一个接一个地放进一组连

续的存储单元之中，也就是说，把表中相邻的数据元素存放在内存中邻接的存储单元里，这种存储方法

叫做顺序分配(SequentialAllocation),又称顺序映象(SequentialMapping),其特点是：逻辑上相邻的数

据元素，它们的物理次序也是邻接的。

假设每个数据元素占用L个存储单元，那么相邻的两个数据元素5与ag在机器内的存储地址LOC

(ai)与LOC®+i)将满足下面的关系：

LOC(aj+i)=LOC(aj+L

而的存储地址LOC(a；)为:

LOC(ai)=LOC(aj+(i-1)*L

线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短。

三、线性表的插入和删除

假设插入是在表的末尾进行，即在长度为n的线性表(aba2,a3,an)的第n个元素之后，添

加一个新元素，使长度变为n+1的表(a,a2,a3,…，a„,a„J,这很简单，只要在表的第n+1个位置

上写入新元素即可。

假设插入是在表的中间进行，即在长度为n的线性表(aba2,a3,an)的第iCWiWn)个

元素之前插入一个新元素，使长度变为n+1的表(a.,a：,,a„,须“)，此时的情况要程复杂一点,

因为顺序分配是把表中的元素依次放在一组连续的存储单元中，也就是说，表中的元素在机黯内是一个

紧接着一个，没有“空隙”。为了能在第i个元素之前插入一个新元素，就必须把从第i个到第n个之

间的元素依次向后挪动一个位置，腾出一个空位给插入的元素。

所以，在一般情况下，顺序分配的线性表的插入算法为：

①把ai到&，的元素后移一个位置，腾出空位。

②往第i个位置上写入新值。

现用一个过程描述如下：

procedureinsert(varv:arraytype;varn:integer：i:integer;x:elementtype);

varj:integer;

begin

forj:=ndowntoidov[j+l]:=v[j];

v[i]:=x;

n:=n+l

end;

同样，假设删除是在表的末尾进行，也很简单，只要把表的长度n减1即可。

当删除是在表的中间进行，那么也要引起表中元素移动。假设要删除长度为n的线性表中第i(1

<iWn)个元素，那么必须把表中第i+1到n之间的元素依次向前挪动一个位置，以覆盖掉第i个位置

上的存储单元。

在一般情况的线性表的删除算法如下：

proceduredelete(varv：Erraytype;varn:integer;i:integer);

varj:integer;

begin

forj:=itondov[j]:=v[j+l];

n:=n-l

end;

四、线性表应用举例

[例4-1]编码问题：设有一个数组A：ARRAY(O..N-1]OFINTEGER；数组中存储的元素为0-N-1之间

的整数，且(当IWJ)时。

例如：N=6时，有：(4,3,0,5,1,2)

此时，数组A的编码定义如下：

A[0]的编码为0：

A山的编码为：在A[0],A[l],……中比A[I]的值小的元素的个数(1=1,2,……N-1)

所以上面数组A的编码为:B=(0,0,0.3,l,2)

程序要求解决以下问题

①给出数组A后，求出其编码：

②给出数组A的编码后，求出A的原数据。

[算法设计]问题①比拟简单，只要统计一下即可。问题②是一个线性表的删除问题，将0到N-1之间

的N个整数顺序放在一个线性表C中，取出编码数组B中的最后一个元素那么C中的第b[N-l]

个元素为数组A的最后一个元素，取出该元素后从C中删除之，再取编码数组B中的前一个元素，重

复上述操作，直到数组A的所有元素都得到为止。

[程序清单]

programex4_l(input,output);

constmaxn=50;

typearrayiype=array[0..maxn]ofinteger;

varn,select:integer;

a,b:arraytype;

procedureinit(varv:armytype);

vari:integer;

begin

write('Inputn:');

readln(n);

write(,Input',n,'integernumber:*);

fori:=0ton-ldoread(v[i]);

readIn

end;

procedureprint(v:arraytype);

vari:integer;

begin

fori:=0ton-ldowrite(v[i],*');

writein

end;

proceduretaskl;

vari,j:integer;

begin

init(a);

fori:=0ton-ldo

begin

b[i]:=0;

forj:=0toi-ldo

ifa[i]>a[j]thenb[i]:=b[i]+l;

end;

writeIn('ThecodeofarrayAis:');

print(b)

end;

proceduredelete(varv:arraytype;varn:integer;i:integer);

varj:integer;

begin

forj:=iton_2dov[j]:=v[j+l];

n:=n-l

end;

proceduretask2：

vari,len:integer;

c:arraytype;

begin

init(b);

fori:=0ton-1doc[i]:=i;

lcn:=n;

fori:=n-ldownto0do

begin

a[i]：=c[b[i]];

delete(c,len,b[i])

end;

writeIn(,ArrayAis:');

print(a)

end;

begin

writelnf':20,T—TaskT);

writelnC*':20,'2—Task2');

write(>20,'Inputyourselect(1or2):');

readln(select);

ifselect=lthentasklelsetask2

end.

[例4-2]M只猴子要选大王，选举方法如下：所有猴子按1...M编号围坐一圈，从第1号开始按顺序

1,2,…,N报数,凡报到N的猴子退出到圈外,如此循环报数，直到圈内只剩下一只猴子时,这只猴子就是

大王.M和N由键盘输入,打卬出最后剩下的那只猴子的编号.

这个例题是由古罗马著名史学家Josephus提出的问题演变而来的,所以通常称为Josephus(约瑟夫)

问题.

在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素

的数组monkey来实现.利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=l表示第

k只猴子仍在圈中,monkey[k]=0那么表示第k只猴子已经出圈.程序采用模拟选举过程的方法，开始时将

报数变量count置为1,用变量current表示当前报数的猴子的编号，也置为1,变量out记录出圈猴子数.

当报数到达n时，对当前报数的猴子作出圈处理，即monkey[current]置0,count置0,out增加1.然后

继续往下报数,直到圈中只剩一只猴子为止.

[程序清单]

programex4_2(input,output);

constmaxm=100;

vari,m,n,count,current,out:integer;

monkey:array[1..maxm]ofinteger;

begin

write(,Inputm,n:');readln(m,n);

fori:=1tomdomonkey[i]:=1;

out:=0;count:=1;current:=1;

whi1eout<m-ldo

begin

whilecount<ndo

begin

repeat｛寻找圈上的下一只猴子｝

current:=current+l;

ifcurrent=m+lthencurrent:=1

untilmonkey[current]=1;

count:=count+l

end;

monkey[current]:=0;out:=out+l;count:=0

end:

fori:=1tomdo

ifmonkey[i]=lthenwritclnC*Themonkeykingisno.',i)

end.

[运行程序]下划线表示输入

Inputm,n:83

Themonkeykingisno.7

在组织数据时，也可以考虑只记录仍在圈中的猴子的情况.用一个线性表按编号由小到大依次记录

圈中所有猴子的编号，每当有猴子出圈时，即从线性表中删除对应元素，表中元素减少一个.程序中用变

量rest表示圈中剩余的猴子数,即线性表中元素的总数.

programex422(input,output);

constmaxm=100;

vari,m,n,current,rest:integer;

monkey:array[1..maxm]ofinteger;

begin

write(*Inputm,n:');readIn(m,n);

fori:=1tomdomonkey[i]:=i;

rest:=m;current:=1;

whilerest>ldo

begin

current:=(current+n-1)modrest;

ifcurrent=0thencurrent:=rest;

fori:=currcnttorest-1domonkey[i]:=monkoy[i+1];

rest:=rest-l

end;

writein(*Themonkeykingisno.*,monkey[1])

end.

［洌4-3］对任意给定的一个自然数n(n<=100),将分母小于等于n的不可约的真分数按上升的次序排序,

并且在第一个分数前加上0/1,而在最后一个分数后加上1/1,这个序列称为n级法雷序列，以Fn表示.

例如,F8为:

0/1,1/8,1/7,1/6,1/5,1/4,2/7,1/3,3/8,2/5,3/7,1/2,4/7,3/5,5/8,2/3,5/7,3/4,4/5,5/6,6/7,7

/8,1/1.

编程求出n级法雷序列,每行输出10个分数.

[算法设计]由于程序要求以分数的形式输出法雷序列，对每个真分数必需分别存放其分子分母,这就

要用两个线性表来实现.开始时线性表中只有两个元素,分别是0/1和1/1,线性表用两个数组fF和

fq来表

示,fp存放分子,fq存放分母.所有的真分数用一个两重循环来产生,每次将当前产生的真分数p/q插入

到线性表中去.为了保证线性表中所有元素在插入新元素后仍然按从小到大的次序排列，首先要从表

中找出第一个不小于p/q的元素，如果该元素等于p/q,那么说明p/q不是不可约的真分数,p/q无需插

入,否则p/q应插入在表中第一个大于它的元素的位置.当向线性表中插入新元素时,如果该线性表是用

数组实现的，那么插入新元素之前要将从插入位置直到最后的所有元素都后移一位，然后再插入新元

素.删除线性表中元素时，只要将从删除位置之后的那个元素直到最后的所有元素都前移一位即可.由

于对实数要防止等或不等的比拟,程序中在对两个分数进行比拟时,将它们化成了乘式进行.

[程序清单]

programex4_3(input,output);

constmaxn=100;

typearraytype=array[1..maxn*maxn]ofinteger;

vari,k,n,p,q,total:integer;

fp,fq:arraytype;

begin

write(,Inputn:');readln(n);

fp[l]:=0;fq[l]:=1;fp[2]:=1;fq[2]:=1;total:=2;

forq:=2tondo｛列举分母｝

forp:=ltoq-1do1列举分子｝

begin

k:=l;

whilep*fq[k]>q*fp[k]dok:=k+1;｛寻找插入位置｝

ifp*fq[k]Oq*fp[k]then｛p/q不在表中｝

begin

fori:二totaldowntokdofp[i+l]:=fp[i];

fori:=totaldowntokdofq[i+l]:=fq[i];

fp[k]：=P；fq[k]:=q;total:=total+l

end

end;

fori:=1tototaldo

begin

write(fp[i],V*,fq[i],*');

ifimod10=0thenwriteIn

end;

end.writeIn

［运行程序］下划线表示输入

Inputn:15

0/11/151/141/131/121/111/101/91/82/15

1/72/131/62/111/5S/142/93/131/44/15

3/112/73/104/131/35/144/113/85/132/5

5/123/74/95/116/137/151/28/157/136/11

5/94/77/123/58/135/87/119/142/39/13

7/105/78/1111/153/410/137/911/144/59/11

5/611/136/713/157/88/99/1010/1111/1212/13

13/1414/151/1

［例4-4］N阶C数列是一个严格潴增的自然数数列，所谓严格递增指的是C

NNNN

数列中每个数都不相同，且Ci<Cj(i<j)o如果某个自然数K能够分解成K=P-Q=S-T,

其中P#S,P、Q、S、T均为自然数，那么K是N阶C数列的一个元素，否则那么不是N阶C

数列的元素。如24=52—12=72—52,24是二阶C数列的元素。再如，45=72-22=92-62=

232-222,45也是二阶C数列的元素。而5不是二阶C数列的元素。

编程求N(2WNW4)阶C数列中第M个元素，该元素不超过长整型数，且在它满足的分解式中P和S

都不超过10000。M、N从键盘输入。

［算法设计］S3-t3的表

st123456789101112131415

27

32619

4635637

51241179861

621520818915291

7342335316279218127

8511504485448387296169

9mi702665604513386217

10999992973936875784657488271

11133013231304126712061115988819602331

1217271720170116641603151213851216ESB|397

132196218921702133207219811854168514681197866469

14274327362717268026192528240122322015174414131016547

153374336733483311325031593032286326462375204416471178631

1640954088406940323971388037533584336730962765236818991352721

从表中可以看出每一行中的元素从右到左是严格递增的，开始时将对角线上的所有元素放进一个线

性表中，这些元素都是每行中最小的元素，然后从线性表中找出所有元素中的最小值min,如果线性表

中有两个或两个以上的元素与min相等，那么表示找到了一个C数列中的元素，并且这样找到的C数

列中的元素一定是从小到大依次排列的。然后将线性表中凡与min相同的元素全部删除，用上表中的与

被删除元素同一行中的左边一个元素(如果有的话)替代它，如果没有替代元素的话，那么表头指针head

加1,口示原head所指的行已经处理完毕，由于开始时线性表中后面的元素很大，实际上没有必要一开

始就将它放在线性表中，为了提面程序运行的速度，程序中设一表尾指针tail,如果表尾指针tail所指

元素的下一个元素小于等于线性表中(从head到tail之间的一段)更新后的最小元素(second),那么该

元素进表，然后重复上述操作，直到第m个C数列中的元素坡找到为止。另外利用上表对角线上的元

素可以递推出上表中的所有元素，递推方法为：S11—（t-l）n=（s"-廿）+（1/—（1一1尸），

其中等式左边与等式右边的第一项为相邻两项，前者出线性表时，后者就替代前者；等式右边的第二项

为对角线上的元素。下面是找出三阶C数列中第一个元素的示意图，表中每一列代表一个当前线性表，

全部表格反映了当前线性表的变化过程，表中每列中的字母H和T代表了当前线性表的表头与表尾指

针。

7HT

1919HT26HT

37373737HT56HT63H63H

616161616161T98T98H98H117H124H

9191919191919191T152T152T152T152H152H

127127127127127127127127127127127127T218T

189H189H208H215H

218218218218218H218H279H279H316H316H335H335H342H

169T296T296T296T296296296296296387387387387

217217217217217T386T386386386386386386386

271271271271271271271T488T488T488T488488488

331331331331331331331331331331331T602T602T

387H387H448H448H485H485H504H504H511H

386513513513513513513513513513H604H604H604H

488488488488488488488657657657657657657

602T602T602602602602602602602602602602819

397397397T728T728728728728728728728728728

469469469469469T866T866T866T866T866T866866866

547547547547547547547547547547547T1016T1016T

665H665H665H702H721H

657657784784784

819819819819819

728728728728728

866866866866866

10161016101610161016

631T1178T1178T1178T1178

721721721721721T

［程序清单］

programex44(input,output);

constmax=5000;

maxlongint=2147483647;

vari,j,m,n,col,row,head,min,maxtail,order,second,tail,total:longint;

overf1ow:boo1ean;

p:array[1..max]ofinteger;

val,list:array[1..max]oflongint;

subscript:array[1..max]ofinteger;

functionf(s,t:longint):longint;｛求Ss-Ts)

ari,temp,v:longint

gi

v:=l;temp:=l;i:=1

while(i<n)and(v>0)do

begi

temp:=temp*t

if(max1ongint-temp)/s>=v

thenv:=v*|+temp

elsev:=0

i:=i+

end;

begin

write(,Inputn,m:');

readln(n,in);

fori:=2tomaxdop[i]:=i-l;

i:=2;overflow:=faIse;

whi1e(i<=max)andnot(overflow)do

begin

val[i]:=f(i-1,i);

ifval[i]>0thenmaxtai1:=ielseoverflow:=true;

i:=i+l

end;

total:=0;

head:=2;tail:=2;

list[head]:=val[head];

min:=list[head];order:=1;

subscript[1]:=head;

repeat

iforder>=2thentotal:=total+l;

iftotaKmthen

begin

fori:=1toorderdo

begin

row:=subscript[i];

p[row]:=p[row]-l;

col:=p[row];

ifcol>0

thenifmaxlongint-1ist[row]>=val[col+1]

thenlist[row]:=1ist[row]+val[col+1J

elselist[row]:=0

elsehead:=head+l;

end;

if(head二tail)or(taiKmaxtai1)then

begintail:=tail+l;list[tail]:=val[tail]end;

min:=list[head];order:=1;subscript[1]:=head;

fori:=head+ltotaildo

if(list[i]>0)and(1ist[i]<=min)then

ifmin=list[i]

thenbeginorder:=order+l;subscript[order]:=iend

elsebeginmin:=list[i];subscript[1]:=i;

order:=1encl;

if(taiKmaxtail)and(val[tail+l]<=min)then

bogin

tai1:=tai1+1;

list[tail]:=val[tail];

ifmin=list[tail]

thenbeginorder:=order+l;

subscript[order]:=tailend

elsebeginmin:=list[tail];

subscript[1]:=tai1;order:=lend

end

end

until(total=m)or(tail=head+l)and(val[head]=0);

iftotal=mthen

begin

write(min);

fori:=1toorderdo

write(，=*,subscript[i],J7,n,p[subscript[i]],',n);

end

elsewrite(,Noanswerinlonginteger!*);

writein

end.

Inputn,m:210

45=7"2-22=9"2-6"2=23"2-22~2

Inputn,m:2100

237=4r2-38'2=119*2-118-2

Inputn,m:21000

1R60=46.2-16"2=9R-2-RR*2=158-2-152*2=466*2-464,2

Inputn,m:31

721=9*3-2*3=16-3-15*3

Inputn,m:310

9919=22-3-9*3=58'3-57"3

Inputn,m:3100

389016=73*3-1*3=150*3-144*3

Inputn,m:31000

27624753=337〃3-220-3=1016八3-1007-3

Inputn,m:41

300783360=133.4-5914=158.4-134M

Inputn,m:43

607570800=157^-7-4=239^4-227~4

到目前为止,我们所知道的描述线性表的方法只有数组，利用数组描述线性表时，其优点是对线性表

中任一元素都可随机存取，具体反映为通过改变下标的值可以对线性表中的任一元素进行访问和修改.

其缺点是在向线性表中插入和删除元素时，必须移动表中的局部元素.插入元素时,要将从插入位置直至

最后的所有元素后移一个位置,如上例所示.删除第i个元素时,需将第i+1至最后一个元素依次向前移

动一个位置.

约瑟夫环的变种1

何题描述：k个男生和k个女生站成一列，前面k个是男生，后面k个是女生，从第一个男生开始报数,报到队

列最后一个同学，循环到队首继续报，并且如果一个同学报到的数是m,这个同学就出歹人然后后面的同学

继续从1开始报数,现在求一个数m,使k个女生全部出列,而男生没有出列的.

输入:男生女生的个数k(男生女生人数相等都为k),输出:m值

例：输入2输出：7

输入:3,输出:5

问题描述：n个人(编号。〜(n-1)),从0开始报数，报至和(m・2)的退出，剩下的人继续从。开始报数。求胜利者

的编号。

这里只谈数学解法：第一次，很容易知道出列的人是m%n-2和m%n-1(如果该值为负，那么加一个m使值为止)而后，

何题变成了n-2个人做同样的事情，只是每个人的序号变了：令1<=^1%[1]就是出列两人后的下一个人)，那么从k开始,

报数的情况就是0,1,2,。。。。。，所以，映射成一个新的环便是：

k―0

k+1——1

k+2——2

k-3——n-3

这样，可以看出这个新问题其实除了人数和序号变了以外，其他都是一样的。也很容易看出来，生存下来的人的新的编

号变成原来的编号的方法就是(x+k)%n,这是不是很像递归？

Descriptions

生存是件很残酷的事情！当佳佳坐在这里想到的只有这一句话。这时有编号为1,2,...n的n个人按

顺时针方向围坐一圈,从1号开始1、2.1、2报数.报2的人独出去砍了！从他的顺时针方向上的下一

个人开始从1报数，如此下去，直到留卜.1个人。他将继续生存。佳佳希望生存下去，你需要尽快帮他解

决这个棘手的问题。到底座在第几号位置佳佳才能幸免？

Input

输入有多个数据。每行一个数据n(lWng100000)最后一行为。表示输入结束。

Output

每行输出佳佳需要座的位置编号k

SampleInput

1

10

0

SampleOutput

1

5

Hint

当有10个人时候，处死的人的编号顺序为2,4,6,8,10,3,729,因此5号位置的人幸免！

8.16,32

这是Josephus问题的一个变种，解题公式如下：

假设有n个人(n>=2),设i是使2的i次品小于等于n的最天整数。令j=n-(2的i次基)，存活的人的

编号为J(n)=2*j+1。

programysfh12;

var

k,rcst,s,i,bcforc,t:longint;

b:boolean;

begin

assign(input,'ysfh12.in');reset(input);

assign(output/ysfh12.out,);rewrite(output);

rcadln(k);

whilek<>0do

begin

fori:=2tokdo

s:=(s+2)modi;

wrileln(s+l);

readln(k);

end;

close(input);close(output);

end.

k个男生和k个女生站成一列，前面k个是男生，后面k个是女生，从第一个男生开始报

数，报到队列最后一个同学，循环到队首继续报，并且如果一个同学报到的数是m,这个

同学就出列，然后后面的同学继续从1开始报数，现在求一个数m,使k个女生全部出列,

而男生没有出列。

输入：男生女生的个数k(男生女生人数相等都为k,输出：m值

例：输入：2,输出：7

输入：4,输出：30

此题是约瑟夫环变形先引入Joseph递推公式,设有n个人(0,...,n-1)，数m,那

么第i轮出局的人为f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0;f(i)表示当前子序列中要退出的那个

人(当前序列编号为0~(n・i));

拿个例子说：K=4,M-30;

f(0)=0；

f(1)=(f(0)+30-1)%8=5；序列(0,12345,6,7)中的5

f(2)=(f(1)+30-1)%7=6；序列(0,1,2,3,4,6,7)中的7

f(3)=(f(2)+30-1)%6=5;序列(0,1,2,346)中的6

f(4)=(f(3)+30-1)%5=4;序列91,2,3,4)中的4

依据题意，前K个退出的人必定是后K个人，所以只要前k轮中只要有一次f(i)vk那

么此m不符合题意。

注意：

此题有几点需要注意，否则很容易超时；第一、运用公式j=(j+m-1)%(n-i),推导出

下一个出现的元素在第几号位置，如果jvk的话，不符合题意。

第二点。就是m,当只剩下k+1个数的时候，那么上一个消失的数一定是在目前仅剩

的bad左边或者是右边，所以m%(k+1)==0或者1

有了这两个条件，可以加快程序的速度。。。

完整的实现代码如下：

[cpp]viewplaincopy

1.#include"stdio.h"

2.#include"stdlib.h"

3.

4.intx[15];

5./*

6.运用公式j=(j+m-l)%(len-i);推导出下一个出现的元素在第几号位置，如果j〈k的话，不符合题意。

7.假设有7个人，报到3的人依次出列

8.第•次j=(j+m-l)%(len-i)=(0+3-l)%(7-0)=2下标为2的3出列新序列为124567

9.第二次j=(j+m-l)%(lPn-i)=(2+3-l)%(7-l)=4下标为4的6出列新序列为124S7

10.第三次j=(j+m-l)%(len-i)=(4+3-l)%(7-2)=l下标为1的2出列新序列为1457

11.第四次j=(j+m-l)%(len-i)=(l+3-l)%(7-3)=3下标为3的7出列新序列为145

12.第五次j=(j+m-l)%(len-i)=(3+3-l)%(7-4)=2下标为2的5出列新序列为14

13.第六次j=(j+m-l)%(len-i)=(2+3-l)%(7-5)=0下标为0的1出列新序列为4

14.第七次j=(j+m-l)%(len-i)«(0+3-l)%(7-6)=0下标为0的4出列新序列为空，至此，所有人已经全

部出列，出列的顺序为：3627514

15.*/

16.inttest(intk,intm)

17.(

18.inti,j=0,len=k*2;

19.for(i=0;i<k;i++)

20.(

21.j=(j+m-l)%(len-i);〃约瑟夫环公式

22.if(j<k)

23.return0;〃遇到前k轮中有小于k的直接返回0

24.}

25.return1;

26.}

27./♦

28.接下来说说m的取值范围：我们考察一下只剩下k+1个人时候情况，即坏人还有一个未被处决，

29.那么在这一轮中结束位置必定在最后一个坏人，那么开始位置在哪呢？这就需要找K+2个人的结束位置，

30.然而K+2个人的结束位置必定是第K+2个人或者第K+1个人，这样就出现两种顺序情况：

GGGG....GGGXB或GGGG.....GGGBX(X表示有K+2个人的那一轮退出的人)所以有K+1个人的那一轮

的开始位置有两种可能即最后一个位置或K+1的那个位置，限定m有两种可能：

31.GGGG....GGGBX假设K+2个人的结束位置在最后一个(第K+2个)，那么m%(k+l)==0

32.GGGG....GGGXB假设K+2个人的结束位置在倒数第二个(第K+1个),那么m%(k+l)==l

33.*/

34.void3oseph(void)

35.{

36.intm,k;

37.for(k=l;k<15;k++)

38.{

39.m=k+l;

40.while(l)

41.{

42.if(test(k,n))//m%(k+l)==。的情况

43.{

44.x[k]=m;

45.break;

46.)

47.if(test(k,n+l))//m%(k+l)==l的情况

48.{

49.x[k]=m<-l;

50.break;

51.)

52.m+=k+l;

53.｝

54.)

55.)

56.

57.intmain(void)

58.｛

59.intk;

60.Joseph。；

61.while(scan-f:("%d",&l<),l<)

62.printf("%d\n",x[k]);

63.system("pause");

64.｝

******************************************************************************

programysfli1;

var

k,ans,restJ,before,t:longint;

b:boolean;

begin

assign(input,'ysfli1.in');resct(input);

assign(outpul,*ysfh1.out');rewriteioutput);

rcadln(k);

b:=false;

ans:=k;

repeat

inc(ans);

rest:=k+k;｛总人数为2*k｝

i：=l；｛从第一轮开始｝

bcforc:=0;

t:=(before+ans-l)mod(2*k-i+l);｛公式｝

while(t>k-l)do｛踢的人在范围内｝

begin

inc(i);

dcc(rest);｛剩下的人数每次少一人)

ifrest=kthen｛正好踢掉k人那么退出｝

begin

b:=true;

break;

end;

before:=t;｛before为上一次踢掉的人｝

t:=(before+ans-1)mod(2*k-i+l);｛判断这次踢掉的人是否超过一半的位子｝

end;

untilb;

writeln(ans);

close(input);close(output);

encl.

1012Joseph（约瑟夫问题）【注意数学公式】

发表于2年前（2012-08-0514:13］阅读（1479）|评论（1）3人收藏此文章，我要收藏

题目：

有k个坏人k个好人坐成一圈，前k个为好人（编号1〜k）,后k个为坏人（编号k+1〜2k）,现在有一

个报数m,从编号为1的人开始报数，报到m的人就要自动死去。问当m为什么值时，可以使得在出

现好人死亡之前，k个坏人先全部死掉？

模拟算法（约瑟夫问题）

:模拟的约瑟夫问题，没怎么优化，可以算到卜=10的情况（提交超时）

优化1：从倒数第二个坏人到最后一个坏人的时候，可以得知m%（k+1）==0否则矛盾，从

而减少了m的取值

1#include<stdio.h>

2SdefineMAX40

3

4intmain()

5{

6ints[MAX];

7intk;

8unsignedm,count;

9inti;

10intpre,cur;

11

12

13while(1)

14{

15scanf(〃％d”,&k);

16if(!k)

17bre2k;

18

19m=k+1;

20while(1)

21(

22pre=cur=1;

23court=1;

24

25for(i=1;i<=2*k;i++)

25s[i]=i+1;

27s[i-1]=1；

28

29for(i=0;i<k;i++)

30(

31whi1e(count<m)

32(

33count++;

34pro=cur;

35cur=s[pre];

36}

37if(cur<=k)

38break;

39s[pre]=s[cur];

40cur=s[pre];

41court=1;

42)

43if(i==k)

44break;

45m+=1;

46

47)

48printf(，z%d\n*,m);

49}

50return0;

51I

数学方法；

递推公式为：

ans[i];//第i轮杀掉对应当前轮的编号为ans[i]的人(是当前该轮的编号！=最开始的编号)

ans[O]=O;

ans[i]=(ans[i-l]+m-l)%(n-i+l);(i>l,总人数n=2k那么为第i轮剩余的人数)

(m-1)编号是。〜那么在判断的时候是(0〜k•工为好人)

(m)编号为工〜m判断的时候是(工〜k为好人)

?

1