当前位置：文档库 › ACM信道化滤波器设计中的陷波问题分析研究

ACM信道化滤波器设计中的陷波问题分析研究

第31卷第12期2010年12月

宇航学报

Journa l of A stronauti cs

V o.l 31Dece m ber

N o .12

2010

AC M 信道化滤波器设计中的陷波问题分析研究

杨君1,2

,袁嗣杰1

,吕镜清

(1.装备指挥技术学院航天测控工程研究中心,北京101416;

2.信息综合控制国家重点实验室,成都610036)

摘要:针对按照A C M (A djacent Channe lM erg i ng )条件生成和信道滤波器存在陷波现象的问题,对和信道滤波器的频率响应进行了推导分析,提出了低通原型滤波器阶数必须为划分的子信道数偶数倍的附加条件从根本上消除了和信道的陷波现象;并在此基础上提出了先设计和信道滤波器再直接逆推出低通原型的设计方法,计算机仿真结果表明,与原有的基于单参数优化的迭代搜索算法相比,该方法能更好地控制和信道的滤波性能,保证和信道与子信道滤波性能的一致性,且计算过程无需迭代更为简单高效。

关键词:信道化;调制滤波器组;频率特性;参数优化;L ag range 插值

中图分类号:TN 850 文献标识码:A 文章编号:1000 1328(2010)12 2764 07DO I :10.3873/.j issn .1000 1328.2010.12.021

Band N otch Proble m of AC M Channelization F ilter D esign

YANG Jun 1,2

,YUAN S i jie 1

,LV Ji n g qing

(1.TT &C Research C enter ,the Acade m y of Equ i pm ent Co mm and &T echnol ogy ,Beiji ng 101416,Ch ina ;

2.National Infor mati on C on trolLaboratory ,Chengdu 610036,C hina)

Abstrac t :To so l ve t he band notch prob l e m o fAC M (A djacent Channe lM e rg i ng )channelizati on filte rs ,the frequency response of t he me rg i ng channe l filter has been ana l ysed and an additi onal conditi on tha t t he order o f the pro totype filter must be even ti m es nu mber o f subchannels i s proposed ,thus co m plete l y avo i d i ng t he band notch proble m.O n the other hand the add itiona l conditi on causes a s i m p l e conve rsion re lati onship o f a m plitude frequency response bet ween m erg i ng channe l fi ter and the pro totype filter ,so tha t the m erg i ng channe l filter can be des i gned first ,and then t he proto t ype filter i s developed based on t he conversi on re l a ti onsh i p .In t h is way the fl a t ness o fm erg i ng channe l band can be i ns ured and a bet ter confor m ability of filteri ng performance bet w een the m erg i ng channel and subchanne l can be ach i eved .T he compu ter si m u l ation proves that t he new m ethod is mo re e fficien t than iterati ve search i ng based on sing le para m ete r opti m i zati on .

K ey word s :Channe liza tion ;Comp l ex modu lated filter bank ;F requency response ;P ara m eter opti m iza ti on

收稿日期:2010 01 04; 修回日期:2010 07 21

基金项目:国防科技重点实验室基金项目(9140C1006050703)

0 引言

信道化滤波

[1]

是宽带数字接收机的关键技术,

它利用滤波器组同时快速地分离出多个相互独立的子带信号以便于后续处理。该技术是实现接收机频域宽开的重要手段,被广泛应用在民用数字移动通信及军用侦察信号处理中。随着电磁环境的日益复杂,均匀信道化已经不能满足实际需要,如何高效实

现动态的非均匀信道化已成为研究的重点和热点。

传统的DDC

[2](数字下变频)及RF Eng i n es 公司提出的TPFT

[3]

(Tuneable Pipe li n ed Frequency

Transfor m )虽可以实现非均匀信道化,但前者计算量太大,后者存在滤波盲区 ,更为重要的是它们的滤波器一经设定工作时就无法改变,所以不能实现动态信道化。邻信道合并AC M (Ad jacent Channe l M erg i n g)思想

[4]

在信道化滤波中的应用为动态改变

调制滤波器组中子信道滤波器的带宽提供了有效方法。当调制滤波器组的低通原型满足AC M 条件时,将其相邻子信道滤波器的输出相加即可实现其通带合并,从而构造出不同带宽的和信道滤波器,由于带宽变化可以通过简单的相加实现,同时调制滤波器组可以通过FFT 或DCT 实现[5-6]

,所以满足AC M

条件的调制滤波器组可以简单高效地实现动态信道

化滤波

[7]

。

但是仿真发现通过设计低通原型滤波器来满足AC M 条件时,并不总能保证和信道滤波器具有良好的频率选择性,设计中有时会出现陷波现象,这种现象有时可以通过反复修改低通原型参数来消除,而有时则根本无法消除,极大地降低了设计效率和质量。本文的研究内容就是查找该现象存在的根本原因,提出更有效的低通原型滤波器设计方法。

大量仿真表明陷波现象出现在相邻子信道的交界处,且与滤波器阶数和划分的子信道数有密切关系。因此本文对这两个参数对和信道滤波器幅频响应的影响进行了分析推导,找出了根本原因,得出当低通原型h 0(n )的阶数为划分的子信道数的偶数倍时可以完全避免和信道的陷波现象,也就是本文提出的附加条件。另一方面在满足附加条件的情况下和信道与低通原型在幅频响应表达式上呈现出简单的调制关系,因此本文提出一种新的低通原型设计方法:先设计出高性能的和信道滤波器再逆推出低通原型,这样既可以保证和信道通带的平坦度又可以保证其与子信道滤波性能的一致性,从而提高非均匀信道化滤波的整体质量。1 调制滤波器组的AC M 条件

根据文献[4]论述,对于一个含2D 个子信道滤波器的调制滤波器组,要使任意相邻子信道滤波器相加得到的和信道滤波器仍然具有良好的频率选择性,则其低通原型h 0(n )的频率响应H 0(e j

)应满足如下两个条件:

|H 0(e j

)|2

+H 0(e j( -

D ))2

=1,

(0< <

) |H 0(e j )|=0,

( > D

)

条件保证和信道滤波器的通带平坦度;条件

限制低通原型的过渡带不超过其带宽的1/2。由于两滤波器时域相加将导致其整个频率响应相加而不仅仅是幅频响应相加,所以本文将AC M 条件更为严格的限制为:

|H 0(e j

)+H 0(e j( - D

)

)|=1,

(- 2D < <3

) |H 0(e j

)|=0,

(| |>

)这样AC M 条件对低通原型及其和信道滤波器幅频响应的要求如图1所示:

图1 AC M 条件F i g .1 AC M cond iti on

2 陷波现象分析

陷波现象表现如下:

取滤波器阶数M =200,划分信道数2D =8,采用高斯(G aussian)窗,A lpha 值取4,通带截止频率取1/8,产生低通原型滤波器,邻信道合并结果如图2所示。

图2 陷波现象

F i g .2 Band no tch prob l em

如图2所示,在子信道交界的地方出现了非常

2765

第12期杨君等:AC M 信道化滤波器设计中的陷波问题分析研究

明显的塌陷。更重要的是采用单参数优化迭代算法将AC M 条件作为误差函数,将这些陷波频点列入到训练样本中,以低通原型的截止频率为优化参数,用Parks M c C l e llan 算法进行迭代搜索,误差函数却始终无法收敛;反复调整低通原型也始终无法消除此现象。这就是本文所要解决的陷波现象。

考查和信道滤波器频率响应表达式。

设划分的子信道数2D,低通原型为h 0(n )为一个M 阶型FI R 线性相位滤波器(阶数M 为偶数,系数为偶对称),为满足AC M 条件其理想带宽为 /D,截止频率为 /2D,则其频率响应为

[8]

H 0(e j

)=e

-j M

n =0

h 0(n )cos ( (

-n ))(1) 各子信道滤波器的冲激响应及频率响应为:h k (n)=h 0(n )e

j k D

(k =0, ,2D -1;n =0, ,M )

(2)

H k (e j

)=H 0(e

j( -k D

)

-j M

( -

k ) M

n=0

(n )cos (( -

k D )(M

-n ))(3)

令F k (e j )=H k (e j )+H k+1(e j

),(k =0, ,2D -1),则根据(3)式,通过三角变换可以得到和信道幅频响应为:|F k (e j

)|=2

n =0

h 0(n)cos (M 2- n +(2k +1)n 2D )cos (n

2D )(4)

考察(4)式,当 =(2k +1) /2D,(k =0, ,2D -1)时,也就是相邻子信道的交界处,有:

F k (e

(2k+1)

n =0

h 0(n )cos (M (2k +1) 4D )cos (n 2D )(5)

若M /2D 为奇数,则M (2k +1)/2D 必定为奇数,则必有:cos (M (2k +1) /4D )=cos( /2)=0,这时不管低通原型h 0(n)取何值都有(5)式的结果都为0,因此M /2D 为奇数,就是图2中所示陷波现象始终无法消除的根本原因。3 附加条件

根据上节论述提出附加条件:低通原型h 0(n)

的阶数M 必须为划分的子信道数2D 的偶数倍。具体论证如下。

当取M 为2D 的偶数倍,则M (2k +1)/2D 也必定为偶数,此时必有:∣cos (M (2k +1) /4D )∣=1,从而使得:

F k (e

(2k+1)

)=2

n=0

(n )co s (n

=2rea l

n =0

(n)e

n 2D

=2rea l H 0(e j

2D )=2H 0(e j

2D )real e -j M 2

=2H 0(e j

2D )

(6)

其中rea l( )表示取实部,第四次恒等变形是将H 0(e jw

)分解成了幅频响应和相频响应。(6)式实际

上是h 0(n )在频点 /2D 上的幅频响应,由于要满足AC M 条件,所以h 0(n )该频点处的幅频响应必然不为0(实际中通常设计为约3dB )如图1所示,所以(6)式结果也必然不为0。另一方面根据(5)当M 与2D 为其它关系时仍然有可能在h 0(n)设计不当的情况下出现陷波现象,所以综上所述,作为AC M 条件的补充该附加条件从根本上消除了陷波现象。

4 低通原型滤波器设计

AC M 条件只需要考查两个方面:低通原型h 0(n )幅频响应|H 0(e j

)|以及第一、二子信道合并出的和信道幅频响应|H 0(e j

)+H 1(e j

)|(即(4)式中的F 0(e j

))是否满足图1特征。以往的思路是先设计出|H 0(e j

)|再考查其生成的F 0(e j

)是否满足图1特征,这样很难保证和信道与子信道滤波性能的一

致性,且设计过程本身效率并不高,而当上节所述的附加条件得到满足时,F 0(e j

)与|H 0(e j

)|将形成简单的调制关系,从而可以采取先设计F 0(e j

)再逆推出|H 0(e j

)|的思路,这样不仅可以精确地控制和信道滤波性能还可以很好地保证和信道与子信道滤波性能的一致性。具体论述如下。

根据(4)式有:|F 0(e j )|=2766 宇航学报

第31卷

当满足附加条件时,M 为2D 的偶数倍,所以(7)式可作恒等变形:|F 0(e j

)|=

2 M n=0h 0(n)cos M 2- n +n 2D +M 4D cos n

2D =2

M n=0

h 0(n )co s M 2

-n -

cos n

(8)

令:

a(n )=2h 0(n )cos n

2D (9)|A (e j

)|=

F 0e

j( +

)(10)

联合(8),(9),(10)式有:

|A (e j

)|=

M n =0a(n )cos M 2

-n (11)

对比(1)式可知,|A (e j

w )|是滤波器a (n )(在后续讨论中将a (n)称之为和信道低通原型)的幅频响应。根据(10)式可知|A (e jw

)|与|F 0(e jw

)|之间是 /2D 的频移关系,所以图1中对和信道幅频响应|F 0(e jw

)|的要求被等价转换为:设计一个a (n)使其幅频响应|A (e j

w )|具有图3所示特征。

图3

a (n )的幅频响应

F i g .3 T he frequency response o f a (n)

显然这是个普通的低通滤波器设计问题,有很多方法可以参考,如窗函数法[9]

、等波纹逼近法、约

束最小二乘法等。

设计出a(n )后即可根据(9)式逆推出h 0(n )。下面考查逆推出的h 0(n)是否满足图1特征:根据式(9)可知a (n)与h 0(n)实际是一种调制关系,调制频率为 /2D,不难证明其带宽必然相差 /D,且通带阻带特性及过渡带特性必然相同,因此若按图3设计得到a (n),则理想情况下逆推出的

h 0(n)必然具有如下特性:带宽为 /D ,过渡带宽为 /2D,且通带阻带特性与a (n)相同。因此逆推出的h 0(n)也满足图1所示特征。

综上所述该方法设计出的和信道滤波器及低通原型滤波器均满足图1所示AC M 条件,且很好地保证了和信道与子信道滤波性能的一致性。5 零值点问题

在由a(n )逆推出h 0(n )的过程中必须解决一

个零值点取值的问题。即根据(9)式逆推公式为:

h 0(n )=

a (n )2co s n

(n =0, ,M )

(12)

当n 为D 的奇数倍(如n =D,3D 等)时co s (n /2D )

=0,此时上式的结果为无穷大,实际中无法取无穷大,所以这些点上h 0(n)的取值是不确定的,这就是所谓的零值点问题。在零值点上若随意取值将破坏低通原型h 0(n )系数的连续性导致其滤波性能的严重下降,从而最终导致子信道滤波性能明显差于和信道滤波性能。有两种方法可以解决此问题:

插值

[10]

。利用零值点前后的值估计出该点

上h 0(n)的系数,以保持h 0(n)系数的连续性。例如采用拉格朗日(Lag range)插值法,具体公式如下:

h 0(n )=

n+D

2i=n-

D 2

h 0(i)

n+D 2

j=n-

D 2j i

n -i

i -j

(n 为零值点)(13)

求极限。这种方法要求用具有明确表达式的方法(如窗函数法)设计a (n)。此时a(n )必然满

足如下表达式

[6]

a (n )=

sin

D n -M

n -M 2

W (n )

(n =0, ,M )

(14)

其中W (n )为选用的窗函数。显然在零值点上(即n 为D 的奇数倍)a (n)为0,这样(12)式在零值点上形成了分子分母都为0的情况,这就可以根据洛比达法则用求极限的方法得到h 0(n)在零值点上的值,计算公式如下:

2767

第12期杨君等:AC M 信道化滤波器设计中的陷波问题分析研究

li m

n (2k+1)D

sin D n -M 2W (n)2 n -M 2cos n 2D =W (n)

n -M

2(-1)n-D

(n =(2k +1)D,k 为非负整数)

(15)

通过大量仿真本文推荐使用窗函数法产生和信道低通原型a (n),并用求极限的方式得到零值点的值,因为这样得到的低通原型h 0(n)系数连续性更好,其幅频特性也更好。

零值点取值问题的解决保证了子信道与和信道滤波性能的一致性。下面通过仿真h 0(n)和a(n )的通带阻带特性进行对比。仿真中用窗函数法(采用Ka iser 窗,取B eta

值为9)设计a (n),利用(12)式逆推出h 0(n),利用(15)式计算零值点取值;过渡带、通带波纹、阻带衰减对比时取归一化带宽为1/8。

图4

h 0(n )与a(n)的通带阻带特性对比

F i g.4 Co m parisi on of passband and atopband perfor m anc bet ween h 0(n )and a(n )

仿真结果表明零值点问题的解决保证了低通原型h 0(n )能够很好地继承a (n )的通带阻带特性从而兼顾了和信道和子信道滤波性能。关于本方法与单参数优化算法设计出低通原型的幅频特性对比见表1。

综上所述现将低通原型h 0(n )的设计步骤总结如下:

根据实际需要确定划分的子信道数2D;

设计出具有图3所示幅频响应特征的和信道低通原型a (n )(推荐使用窗函数法),使其具有良好的通带阻带特性,且a(n )的阶数M 为2D 的偶数倍;

利用(9)式逆推出h 0(n),利用(13)式或(15)式计算出零值点取值。

2768 宇航学报第31卷

6 仿真实例

通过仿真验证改进后的基于邻信道合并的信道化方法的有效性。

仿真参数:采样率f s =1H z ;划分子信道数2D =32;采用Chebyshev 窗,边带衰减值取100,用第4节所述方法设计448阶低通原型h 0(n ),零值点处的系数利用(15)式求极限得到。

仿真信号由以下四路信号相加得到(称为和信号):信号1为正弦信号,中心频率为f s /64(处于两子信道交界处);信号2为脉冲串,载波为正弦信号,中心频率为11f s /32,脉冲串为13位Bar ker 码(循环调制),占空比为0.5,码速率为f s /32;信号3为线性调频信号LF M,中心频率为f 0=7f s /64,带宽为3f s /32,时宽取2048/f s ;信号4为复正弦信号(含虚部),中心频率为17f s /32。

根据和信号中各子带信号带宽分布情况(如图5所示),邻信道合并分组为:第1,2,32子信道合并输出正弦信号;第4~8及26~30子信道合并输出线性调频信号;第11~13及21~23子信道合并输出脉冲串;第18子信道单独输出复正弦信号。合并后得到的和信道滤波器幅频响应如图5

所示。

图5 和信号、和信道滤波器幅频响应F i g.5 Am pli tude frequency response of m erg i ng

si gnal and m erg i ng channel filters

其中各子信道滤波器(包括低通原型)与各和信道滤波器的幅频特性对比如表1所示。

由表1中的仿真数据可见本方法与单参数优化算法设计出的信道滤波器性能基本相当,同时表现出以下两方面优点: 子信道与和信道的滤波性能

一致性更好; 单参数优化算法需要多次迭代才能达到要求,上例中176次迭代耗时约2分45秒,而本方法无迭代直接得到结果,同等条件下耗时不到1秒,更为简单高效。

表1 子信道与和信道滤波性能对比

(

本方法

单参数优化算法

)

T able 1

Co m pa risi on of filter i ng perfo r m ance bet w een subchanne l and m erg i ng channe l

滤波器过渡带宽

( f s )通带最大

波纹/dB 阻带衰减

/dB 子信道约0.01092约0.01229<1.49 10-5<1.32 10-5>113>120和信道

约0.00995约0.01831

<1.55 10-5<2.13 10-5

>115>110

注:单参数优化算法仿真中通带波纹门限取1.5 10-5,搜索步长取0.0001f s ,最终迭代176次得到以上结果。

最终信道化滤波结果如下

图6 信道化滤波结果F i g .6 Channe lization filter i ng resu lt

对比图5和图6可以看出改进后的信道化方法能有效地将各路信号从和信号中分离出来,并高质量地保持了其时域、频域信息。

7 结束语

本文提出的附加条件有效地避免了陷波现象,同时低通原型滤波器设计方法也有效地保证了子信道滤波器与和信道滤波器滤波性能的一致性,且较原有设计方法更为简单高效。大大提高了AC M 信道化滤波器的设计效率和质量,促进该方法在工程中的应用推广。

2769

第12期杨君等:AC M 信道化滤波器设计中的陷波问题分析研究

参考文献

[1] J a m es T s u.i宽带数字接收机[M].杨小牛,陆安南,金飚等

译.北京:电子工业出版社,2001:230-270.

[2] H arri s F J,D i ck C,RiceM.D i g i tal rece i vers and trans m itters u

si ng pol yphase filt er banks for w ireless co mmun ications[J].

I EEE T rans.M i cro w ave Theory and Tec hn iqu es,2003,51(4):

l395-1412.

[3] RF Engi n es Inc.TPFT t uneab l e p i p eli ned frequency trans f or m

[DB/OL].2003[2008].htt p://www.Rfe.l co m/do w nload/

W02003-Tuneab le PF T W h ite Paper.pd.f

[4] Lee J J,Lee B G.A design of nonun ifor m cosi ne m odulated filter

bank s[J].I EEE Trans.On C ircu its and Syste m s II-Anal og and

Digit al S ignal Proc.,1995,42(11):732-737.

[5] Zhang Z J,Shu i P L.E ffi cient desi gn of h i gh co m plexity cos i ne

m odu l ated filter b anks u si ng2M th b and cond itions[J].IEEE

Tran s.On S i gnal Processi ng.2008,56(11):5414-5426. [6] 王洪,吕幼新,汪学刚,W OLA滤波器组信道化接收机技术

[J].电子科技大学学报,2008,37(1):43-46.[W ang

H ong,Lv You x i n,W ang Xu gang.Ch anneliz ed recei ver w it h

WOLA filterbank s[J].J ournal of UEST of Ch i na,2008,37

(1):43-46.][7] 李冰,郑瑾,葛临东.基于非均匀滤波器组的动态信道化滤

波[J].电子与信息学报,2007,29(10):2396-2400.[L i

B i ng,Zheng Ji n,Ge J i n dong.Dyna m ic c h anneliz ati on based on

nonun if or m filterbanks[J].Journal of E lectron ics&I n for m ation

Technol ogy,2007,29(10):2396-2400.

[8] John G P,D i m i tris G M.数字信号处理[M].方艳梅,刘永清

等译.北京:电子工业出版社,2007:367-372.

[9] C ruz Rol d an F,M arti n M arti n P,Saez Landete J,et a.l A fast

w i ndo w i ng based techn i que exp l o i ti ng spli ne functi on s f or d es i g

n i ng modulat ed filter bank s[J].I EEE Tran sactions on C i rcu i ts

and Sys t e m s I,Regu l ar Pap ers,2009,56(1):168-178.

[10] K i an K T,Ibrah i m H,Bejo S K.Investi gati on on several basic

i nterpol ati on m et hods for the use i n re m ot e sens i ng app lication

[C].IEEE Con ference on Innovati ve T echnologies i n In telli gent

Sys t e m s and IndustrialA pp lications,Cyb erjaya,M a l aysia,J u ly

12-13,2008:60-65.

作者简介:杨君(1980-),男,助教,博士研究生,主要从事航

天器测量控制及侦察信号处理研究。

通信地址:北京怀柔3380信箱72号(101416)

E m ai:l yang j un_801222@126.co m

(编辑:余未)

2770 宇航学报第31卷

《ACM算法与程序设计》解题报告模板

电子科技大学期末解题报告课程：《ACM算法与程序设计》学院：学号：姓名：报告成绩：教师签名：

讨厌的青蛙 1、链接地址 https://www.wendangku.net/doc/4d11254459.html,/problem?id=2812 2、问题描述在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同，如图1所示。稻田里的稻子组成一个栅格，每棵稻子位于一个格点上，如图2所示。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去，如图3所示。问题描述

青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。可能会有多只青蛙从稻田穿越，有些水稻被多只青蛙踩踏，如图4所示。当然，农民所见到的是图5中的情形，看不到图4中的直线。根据图5，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3 棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3 棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径。在图5中，格点(2, 1)、(6, 1)上的水稻可能是同一只青蛙踩踏的，但这条线上只有两棵被踩踏的水稻，因此不能作为一条青蛙行走路径；格点(2, 3)、(3, 4)、(6, 6)在同一条直线上，但它们的间距不等，因此不能作为一条青蛙行走路径；格点(2, 1)、(2, 3)、(2, 5)、(2, 7)是一条青蛙行走路径，该路径不包括格点(2, 6)。请你写一个程序，确定在所有的青蛙行路径中，踩踏水稻棵数最多的路径上有多少棵水稻被踩踏。例如，图5的答案是7，因为第6 行上全部水稻恰好构成一条青蛙行走路径。

2015年算法分析与设计期末考试试卷B卷

西南交通大学2015 — 2016学年第(一)学期考试试卷课程代码 3244152课程名称算法分析与设计考试时间 120分钟阅卷教师签字： __________________________________ 填空题(每空1分，共15分) 1、程序是 (1) 用某种程序设计语言的具体实现。 2、矩阵连乘问题的算法可由 (2) 设计实现。 3、从分治法的一般设计模式可以看出，用它设计出的程序一般是 (3) 4、大整数乘积算法是用 (4) 来设计的。 5、贪心算法总是做出在当前看来 (5) 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 (6) o 6、回溯法是一种既带有 (7) 又带有 (8) 的搜索算法。 7、平衡二叉树对于查找算法而言是一种变治策略，属于变治思想中的 (9) 类型 8、在忽略常数因子的情况下，0、门和0三个符号中， (10) 提供了算法运行时间的一个上界。 9、算法的“确定性”指的是组成算法的每条 (11) 是清晰的，无歧义的。 10、冋题的(12) 是该冋题可用动态规划算法或贪心算法求解的关键特征。 11、算法就是一组有穷 (13)，它们规定了解决某一特定类型问题的 (14) o 12、变治思想有三种主要的类型：实例化简，改变表现， (15) o 、 ___________________________________________________________________________________ L 线订装封密线订装封密、 __________________ 二线订装封密级班选择题(每题2分，共20 分)

安徽ACM省赛试题

2018年安徽省机器人大赛程序设计竞赛

目录A．数7 B．编译错误 C．做操的时候要排好队D．判重 E．最长上升字串 F．雄伟的城堡 G．然后打5 H．运货卡车 I．最大矩形框 J．数列分段 K．数数字

A.数7 时间限制: 3s 描述求整数序列中位置L到位置R中一共有多少个7。对于每个数7的个数的定义为，十进制各个位置上一共有多少个7，以及能够被7整除的次数。输入第一行是一个整数T，代表测试数据的组数。每组数据中两个整数L,R。其中T≤50,L

B.编译错误时间限制: 3s 描述在程序员编写程序的时候，通常会引用其他文件，而引用的文件也会引用其它的头文件。但是出现循环引用的现象编译时便会报错。例如A引用了B，B引用了C，C引用了A，那么就产生了循环引用（Circular reference）。考虑另外一个情况，A引用了B和C，B引用D，C引用D，虽然D被引用了两次，但是没有出现循环引用。输入第一行是一个整数T，代表测试数据的组数。每组数据中第一行是一个整数n，代表有多少个引用关系。接下来n行每行有2个字符串a,b，用空格分隔，代表a引用了b。其中T≤50, n≤105，每个字符串长度不超过100。输出共T行。若不会产生编译错误则输出Passed，否则输出Failed。样例输入样例输出

C.做操的时候要排好队时间限制: 3s 描述同学们在做早操时，应该按照身高从低到高排好队。但是总是有人不好好排队，老师在审查时会对没有排好的队伍扣除一定的分数。扣的分数被定义为，找到三个人Ai,Aj,Ak，其中i

《算法分析与设计》期末复习题[1]

一、选择题 1．一个.java文件中可以有（）个public类。 A．一个B．两个C．多个D．零个 2．一个算法应该是（） A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C 3．用计算机无法解决“打印所有素数”的问题，其原因是解决该问题的算法违背了算法特征中的（）A．唯一性B．有穷性C．有0个或多个输入D．有输出 4．某校有6位学生参加学生会主席竞选，得票数依次为130，20，98，15，67，3。若采用冒泡排序算法对其进行排序，则完成第二遍时的结果是（） A．3，15，130，20，98，67B．3，15，20，130，98，67 C．3，15，20，67，130，98 D．3，15，20，67，98，130 5．下列关于算法的描述，正确的是（） A．一个算法的执行步骤可以是无限的B．一个完整的算法必须有输出 C．算法只能用流程图表示D．一个完整的算法至少有一个输入 6．Java Application源程序的主类是指包含有（）方法的类。 A、main方法 B、toString方法 C、init方法 D、actionPerfromed方法 7．找出满足各位数字之和等于5的所有三位数可采用的算法思路是（） A．分治法B．减治法C．蛮力法D．变治法 8．在编写Java Application程序时，若需要使用到标准输入输出语句，必须在程序的开头写上( )语句。 A、import java.awt.* ; B、import java.applet.Applet ; C、import java.io.* ; D、import java.awt.Graphics ; 9．计算某球队平均年龄的部分算法流程图如图所示，其中：c用来记录已输入球员的人数，sum用来计算有效数据之和，d用来存储从键盘输入的球员年龄值，输入0时表示输入结束。

山东科技大学第二届ACM程序设计大赛试题

山东科技大学第二届ACM程序设计大赛试题册试题共14页，题目共计12道

山东科技大学第二届ACM 程序设计大赛试题册 Problem A 简单计算 Description 给出n 个十进制的数，找出这n 个数的二进制表示中1的个数最少的数。 Input 输入的第一行为一个正整数T （1≤T ≤20）,代表测试数据组数。对于每组测试数据，输入的第一行为一个正整数n （1≤n ≤10000），第二行为n 个正整数A 1、A 2、…、A n （1≤A i ≤109 ），每个数之间以空格分隔。 Output 每组数据输出一行，先输出数据组数，再输出二进制中含1最少的数，如果存在多个数符合条件，输出最小的那个。具体输出格式见样例输出。 Sample Input Sample Output

山东科技大学第二届ACM 程序设计大赛试题册 Problem B 关键字搜索 Description 我们的新网站具有了全新的搜索功能，使用了2个通配符“*”和“？”，其中“*”表示0或者多个小写字母，“？”代表1个字母。当我们输入一个关键字的时候，我们在不确定的地方就使用通配符。我们在数据库里面有多条记录，每条记录都是由小写字母组成，现在给出一个关键字，你能告诉我数据库里面有多少条与关键字相匹配的记录吗？例如：如果关键字是j*y*m*y?，那么jiyanmoyu ，jyanmoyu ，jymyu 都是相匹配的记录。 Input 第一行输入一个T （T ≤20），表示有T 组测试数据。对于每组测试数据，第一行是输入的关键字，接下是数据库里面的所有记录的条数n ，1≤n ≤10000,每条记录的长度不超过50个小写字母。 Output 对于每组测试数据，输出与关键字相匹配的总记录条数，占一行。 Sample Input Sample Output

acm程序设计大赛

acm程序设计大赛一、参赛队的组成：每只队伍三名参赛队员组成，设队长一名。超过两名以上选手为女队员的参赛队可认为具有女队的资格。在解出同等题目的情况下，女队优先，然后再计算时间（争夺第一名时除外）。二、竞赛过程竞赛中命题 6 题，比赛时间为5个小时。比赛编程语言为C或C++。队员在接到题目后，编程进行解答，解答完每道题目，即可将程序通过网络提交，评委当场对提交的程序进行评判，并对提交的时间进行记录，经运行测试后由裁判判为正确或者错误，判决结果由系统自动反馈给参赛队伍。如果正确，就为该队挂上一个气球，不同颜色的气球代表不同的题目。为了增加比赛的紧张气氛，比赛结束前一个小时，停止公布所有的成绩。参赛队员有权提交解释请求，针对题目描述中的不明确或错误的部分提问。如果裁判确认题目中确实存在不明确或错误的部分，将会通告所有参赛队伍进行声明或更正。在竞赛中，参赛队员不得和同组成员以及竞赛组委会指定工作人员以外的人交谈；系统支持人员可以回答和系统相关的问题，例如解释系统错误信息。参赛队员不能携带任何电子设备。允许携带纸质材料，包括源代码，参考书，字典等。当参赛队伍出现妨碍比赛正常进行的行为时，诸如擅自移动赛场中的设备，未经授权修改比赛软硬件，干扰他人比赛等，都将会被竞赛组委会剥夺参赛资格。三、竞赛评分竞赛裁判主要负责当比赛选手对裁判系统的结果提出异议或题目需要人工判别时作出相应解释或判定。竞赛组委会主任在与竞赛裁判组协商后确定获胜队伍，有权根据由于不可预见的事件引起的问题，对结果进行调整，这个决定是最终的。比赛最终结果由每支队伍解决的题目以及解决时间来决定。解题多者获胜，如果有队伍解题数量相同，则根据总用时加上惩罚时间进行排名。总用时和惩罚时间由每道解答正确的试题的用时加上惩罚时间组成。每道试题用时将从竞赛开始到试题解答被判定为正确为止，期间每一次错误的运行将被加罚20分钟时间，未正确解答的试题不计时。

acm程序设计大赛题目

The Mailboxes Manufacturers Problem Time Limit:1000MS Memory Limit:65536K Total Submit:299 Accepted:227 Description In the good old days when Swedish children were still allowed to blowup their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k(1 ≤ k≤ 10) identical mailbox prototypes each fitting up to m(1 ≤ m≤ 100) crackers. However, he is not sure of how many firecrackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say, “Well,if I blow up a mailbox I can’t use it again, so if you would provide me with only k = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up ev en when filled with m crackers, I would need 1 + 2 + 3 + … + m = m ×(m+ 1) ? 2 crackers. If m = 100 that would mean more than 5000 fire-crackers!” “That’s too many,” he replies. “What if I give you more than k = 1 mailboxes? Can you find a strategy that requires less crackers?” Can you? And what is the minimum number of crackers that you should ask him to provide you with? You may assume the following: 1.If a mailbox can withstand x fire-crackers, it can also withstand x? 1 fire-crackers. 2.Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.

2017ACM比赛试题

2017年计算机ACM编程竞赛主办：计算机科学与技术学院时间：2017-11-22 18:00---20:00 地点：计算机学院奋进楼4楼5机房

竞赛规则 1、比赛时间为120分钟，从18:00开始，20:00结束。 2、比赛形式为上机编程，每个小组使用三台电脑，可任选语言，同一小组不同题目可使用不同语言； 3、比赛期间可以使用自己电脑，不可查阅书籍、但禁止查阅个人U盘，禁止使用手机、电脑进行上网查询，禁止使用现有代码，违者取消比赛资格；（正式ACM中是可以携带纸质材料的，但由于本次比赛，有大量题目参考书上例题，所以就不让携带了） 4、比赛期间，如遇到设备问题，可举手示意工作人员； 5、由于机房电脑系统有重启还原功能，比赛期间请勿轻易重启电脑； 6、【重要】比赛结束后，请确认将所要提交文件拷至工作人员U盘，否则成绩无效概不负责。提交方式 1、创建文件夹，文件夹命名格式为小组号-小组队长-组员1-组员2 2、将每一题的源程序文件夹以题目编号命名，拷贝至上述创建的文件夹中 3、在本文档中每题相应位置附上源码及截图（windows截图键:Alt+Prt sc sysrq）,拷贝至上述创建的文件夹中 4、比赛结束后将上述文件夹拷贝至工作人员U盘中，提交方算完成，提交完成前请勿重启电脑。注：本次比赛共14题，满分120分。没有完成题目，但有部分解题步骤者按完成度给分。每道题要有注释。

竞赛题目 1. 青年歌手大奖赛中，评委会给参赛选手打分。选手得分规则为去掉一个最高分和一个最低分，然后计算平均得分，请编程输出某选手的得分。输入数据有多组，每组占一行，每行的第一个数是n(2

河南省第四届ACM程序设计大赛原题

所有题目时间限制：1秒【T1】序号互换 Dr.Kong 设计了一个聪明的机器人卡多，卡多会对电子表格中的单元格坐标快速计算出来。单元格的行坐标是由数字编号的数字序号，而列坐标使用字符序号。观察字母序号，发现第1列到第26列的字母序号分别为A,B,……,Z,接着，第27列序号为AA，第28列为AB，以此类推。若给Dr.Kong的机器人卡多一个数字序号（比如32），它能很快算出等价的字母序号（即AF），若给机器人一个字母序号（比如AA），它也能很快算出等价的数字序号（27），你能不能与卡多比试比试，看谁能算得更快更准。【标准输入】第一行：N 表示有多少组测试数据。接下来N行，每行或者是一个正整数，或者是一个仅由大写字母组成的字符串。【标准输出】对于每一行测试数据，输出一行。如果输入为一个正整数序号，则输出等价的字母序号；如果输入为字符串，则输出等价的数字序号。【约束条件】输入保证，所有数字序号和字母序号对应的数字序号均<=2*10^9 【样例】【T2】节能 Dr.kong 设计的机器人卡多越来越聪明。最近市政府公司交给卡多一项任务，每天早晨5：00开始，它负责关掉ZK大道右侧上的所有路灯。卡多每到早晨5:00准会在ZK大道上某盏灯的旁边，然后他开始关灯。每盏灯都有一定的功率，机器人卡多有自觉的节能意识，它希望在关灯期间，ZK大道右侧上所有的路灯的耗电总量数是最少的。机器人卡多以1m/s的速度行走。假设关灯动作不需要花费额外的时间，因为当它通过某盏路灯时就

顺手将灯关掉。请编写程序，计算在给定路灯设置，灯泡功率以及机器人卡多的起始位置的情况下，卡多关灯期间，Zk大道上所有灯耗费的最小能量。【标准输入】第一行N 表示ZK大道右侧路灯的数量（2<=N<=1000）第二行V 表示机器人卡多开始关灯的路灯号。（1<=V<=N）接下来的N行中，每行包含两个空格隔开的整数D和W，用来描述每盏灯的参数 D表示该路灯与ZK大道起点的距离（用米为单位来表示） W表示灯泡的功率，即每秒该灯泡所消耗的能量数。路灯是按顺序给定的。（0<=D<=1000,0<=W<=1000）【标准输出】输出一个整数，即消耗总能量之和的最小值。注意结果小于200，000,000 【样例】【T3】表达式求值 Dr.Kong 设计的机器人卡多掌握了加减运算以后，最近又学会了一些简单的函数求值，比如，它知道函数min(20,23)的值是20，add（10,98）的值是108等等。经过训练，Dr.Kong 设计的机器人卡多甚至会计算一种嵌套的更复杂的表达式。假设表达式可以简单定义为： 1.一个正的十进制数x是一个表达式。 2.如果x和y是表达式，则函数min（x.y）也是表达式，其值为x，y中最小的数。 3.如果x和y是表达式，则函数max（x，y）也是表达式，其值为x，y中最大数。 4.如果x和y是表达式，则函数add（x，y）也是表达式，其值为x，y之和。例如，表达式max（add（1,2），7）的值为7. 请编写程序，对给定的一组表达式，帮助DrKong算出正确答案，以便校队卡多计算的正误。

ACM程序设计竞赛例题

备战ACM资料一：知识点数据结构： 1，单，双链表及循环链表 2，树的表示与存储，二叉树（概念，遍历）二叉树的应用（二叉排序树，判定树，博弈树，解答树等） 3，文件操作（从文本文件中读入数据并输出到文本文件中） 4，图（基本概念，存储结构，图的运算）数学知识 1，离散数学知识的应用（如排列组合、简单的图论，数理逻辑） 2，数论知识 3，线性代数 4，组合代数 5，计算几何二算法 1，排序算法（冒抛法，插入排序，合并排序，快速排序，堆排序） 2，查找（顺序查找，二分发） 3，回溯算法 4，递归算法 5，分治算法 6，模拟法 7，贪心法 8，简单搜索算法（深度优先，广度优先），搜索中的剪枝，A*算法 9，动态规划的思想及基本算法 10，高精度运算三、ACM竞赛的题型分析竞赛的程序设计一般只有16种类型，它们分别是： Dynamic Programming （动态规划） Greedy （贪心算法） Complete Search （穷举搜索） Flood Fill （不知该如何翻译） Shortest Path （最短路径） Recursive Search Techniques （回溯搜索技术） Minimum Spanning Tree （最小生成树） Knapsack （背包问题） Computational Geometry (计算几何学) Network Flow （网络流） Eulerian Path （欧拉回路） Two-Dimensional Convex Hull （不知如何翻译） BigNums （大数问题）

Heuristic Search （启发式搜索） Approximate Search （近似搜索） Ad Hoc Problems （杂题）四ACM竞赛参考书《实用算法的分析与程序设计》（吴文虎，王建德著，电子工业出版社，竞赛类的黑宝书）《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法和程序设计》（吴文虎，王建德著，清华大学出版社，参加竞赛组合数学必学）《计算机算法设计与分析》（王晓东编著，最好的数据结构教材）《数据结构与算法》（傅清祥，王晓东编著，我所见过的最好的算法教材）《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德著，清华大学出版社）《计算机程序设计技巧》 D.E.Kruth著，算法书中最著名的《葵花宝典》，大师的作品，难度大）《计算几何》周陪德著《ACM国际大学生程序设计竞赛试题与解析（一）》（吴文虎著，清华大学出版社）《数学建模竞赛培训教材》共三本叶其孝主编《数学模型》第二版姜启源《随机规划》《模糊数学》《数学建模入门》徐全智《计算机算法设计与分析》国防科大五常见的几个网上题库常用网站： 1）信息学初学者之家：https://www.wendangku.net/doc/4d11254459.html,/ （2）大榕树编程世界：https://www.wendangku.net/doc/4d11254459.html,/~drs/program/default.asp （3）中国教育曙光网：https://www.wendangku.net/doc/4d11254459.html,/aosai/ （4）福建信息学奥林匹克：https://www.wendangku.net/doc/4d11254459.html,/fjas/index.htm （5）第20届全国青少年信息学奥林匹克竞赛：https://www.wendangku.net/doc/4d11254459.html,/ （6）第15届国际青少年信息学奥林匹克竞赛：https://www.wendangku.net/doc/4d11254459.html,/ （7）全美计算机奥林匹克竞赛：https://www.wendangku.net/doc/4d11254459.html,/usacogate （8）美国信息学奥林匹克竞赛官方网站：https://www.wendangku.net/doc/4d11254459.html,/ （9）俄罗斯Ural州立大学：http://acm.timus.ru/ （10）西班牙Valladolid大学：http://acm.uva.es/problemset （11）ACM-ICPC：https://www.wendangku.net/doc/4d11254459.html,/icpc/ （12）北京大学：https://www.wendangku.net/doc/4d11254459.html,/JudgeOnline/index.acm （13）浙江大学：https://www.wendangku.net/doc/4d11254459.html,/ （14）IOI：http://olympiads.win.tue.nl/ioi/ （15）2003年江苏省信息学奥林匹克竞赛夏令营：https://www.wendangku.net/doc/4d11254459.html, （16）https://www.wendangku.net/doc/4d11254459.html, （17）https://www.wendangku.net/doc/4d11254459.html, （18）https://www.wendangku.net/doc/4d11254459.html, （19）https://www.wendangku.net/doc/4d11254459.html,/downldmanag/index.asp （20）https://www.wendangku.net/doc/4d11254459.html, colin_fox/colin_fox 五如何备战ACM/ICPC

历届程序设计acm试题

搜集的南开大学的ACM试题与你共享 [A]南开大学Onlinejudge 在线判题系统https://www.wendangku.net/doc/4d11254459.html, A.Lucy的新难题时间限制：2秒内存限制：32000KB 不知不觉，南开大学第三届“我为程序狂”又要拉开帷幕了。这天，Lucy也来到南开大学ACM协会，与大家共同欢庆NKPC的三周岁的日子。谈笑间，ACM协会的主席拿了圆形的生日蛋糕。大伙开心地唱完了生日歌，一起吹灭了蜡烛。要分蛋糕了，大家都很兴奋。本着公平的原则，每位到场的人员都要在蛋糕上切一刀。ACM协会的主席事先知道有n位朋友会参与这个欢庆宴会。为了方便大家切蛋糕，主席在订蛋糕的时候就嘱咐在蛋糕的边缘布置上2n朵小花。每个人切蛋糕都会从蛋糕的边缘的一朵小花笔直地切到蛋糕的另一端的小花，来表达自己对NKPC的祝福。为了尊重其他同学，每个人在切蛋糕一定不会和蛋糕上已有的切痕相交，也不会从别人已切过的小花作为切蛋糕的起点或终点。同时，每位同学在切蛋糕的时候，都要保证后面所有的同学都能够按照上述的规则切蛋糕。这样，蛋糕上就留下n条切痕。 Lucy眨巴眨巴眼睛，问，要是不考虑切蛋糕的先后顺序和谁切的哪一刀，这蛋糕切完了共有多少种切法呢？大家听了呵呵一笑，说，那就把这个问题留给NKPC3，作为《Lucy的新难题》吧。相信聪明的你，一定能够帮Lucy解答她的难题的，对吗？输入包括多组测试数据，你应当处理到输入结束为止。每组输入数据中，都只有一行，仅包含一个正整数n，且0

桂林电子科技大学ACM程序设计校内竞赛试题

桂林电子科技大学ACM程序设计校内竞赛试题 ▲此套试题共8道，请根据自己实际情况尽最大努力去完成。 ▲每位参赛的同学需在考试用机的工作盘上创建一个名为Exam2004的临时文件夹用以保存所有的工作文件。上机编程调试出正确结果。按照试题顺序把每题的运行结果、源程序和算法说明（即解题思路说明）合并到一个Word 文档。该Word文档的文件名按如下格式命名：学号+姓名最后将该文件拷至制定的服务器上。 1、请看如下图4*4的一个网格。你能告诉我网格中隐含了多少正方形？也许你能手工数出来，但是你能数100*100或者1000*1000的网格吗？请编写一个程序：输入：输入一个整数N(0<=N<=100),代表网格的边长输出：输出2维网格N*N中不同大小的正方形的数目S. 如以上4*4网格共有正方形30 2、对于一个8位二进制码，它的镜像就是将它的第n位于倒数第n位交换，使它的每一位都这样交换。例如，代表十进制数46的二进制数是00101110。它的镜像是二进制码01110100，即十进制数116。编写一个程序，输入一个整数N(如46)，输出其镜像M(如116)。 3、给你9个整数，这9个整数分别是x的8次方至0次方的系数，请你按照多项式的一般形式合理地构造（去除不必要的）。例如9个系数分别为0，0，0，1，22，-333，0，1，-1，你要构造并输出一行多项式: x^5+22x^4-333x^3+x-1。要求：可以输入多行系数，再显示结果。如输入： 0 0 0 1 22 -333 0 1 -1 0 0 0 0 0 0 6 88 0 E(输入结束标志) 输出： x^5+22x^4-333x^3+x-1 6x^2+88x 4、美国人的家族农夫John对他的奶牛继承关系非常认真。但是他不是一个很好的记录员，他以一种二叉树的方法来记录他奶牛的继承关系。他用字符串来记录一棵树的前序、中序遍历，而不是用图形方式来表示这棵树。你的任务是对于给出的奶牛继承关系的前序树和中序树表示，找出它的后序树表示。每个奶牛的名字用一个字母来代表。输入规范第一行输入中序序列第二行输入前序序列输出规范显示后序序列实例输入 In order: AEDFCHG // 中序序列输入

acm编程比赛题

比赛试题主办方：迅翔计算机协会

【问题描述】这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了6种钱币面值为2、5、10、20、50、100，用来凑15元，可以用5个2元、1个5元，或者3个5元，或者1个5元、1个10元，等等。显然，最少需要2个钱币才能凑成15元。你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。【要求】【数据输入】输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值M（1 <= M <= 2000，整数），接着的一行中，第一个整数K（1 <= K <= 10）表示币种个数，随后是K 个互不相同的钱币面值Ki(1 <= Ki <= 1000)。输入M=0时结束。【数据输出】每个测试用例输出一行，即凑成钱数值M最少需要的钱币个数。如果凑钱失败，输出“Impossible”。你可以假设，每种待凑钱币的数量是无限多的。【样例输入】 15 6 2 5 10 20 50 100 1 1 2 【样例输出】 2 Impossible

【问题描述】 Felicia 的生日是11月1日（和Kitty是同一天生的哦）。于是Feli请来Kitty一起过生日。Kitty带来了最新款的“Kitty猫”玩具准备送给Feli，不过她说，这份礼物可不是白送的。Feli要帮她一个忙，才能够得到心仪已久的玩具。Kitty说，“Kitty猫”玩具已经卖出了n!个，n<=10^100 *_*，Kitty想知道确切的数字，而不是无聊的“一个数加个感叹号”。Feli 听了大吃一惊。要知道，算出n!是一个无比艰巨的任务。Feli告诉Kitty，就算Feli算出n!，Kitty也看不下去，因为当n=20 时，计算机的长整型已经存不下了（Kitty只能接受1-9之间的数字）。于是Kitty说，你只要告诉我n!最后一位非0的数就可以了。Feli想了想，立刻动手写了个程序算出了正确的答案。现在，请你也试试看！注意哦，AC的男生将会得到一个“Hello Kitty”计算器（可编程，CPU 1THz，Mem 1TMB），AC的女生将会得到一个仿真“Hello Kitty”宠物（善解人意，无须喂养，智商1101，附带写情书功能）。【要求】【数据输入】每行一个n，直到输入数据结束【数据输出】对应输入的n，每行输出一个答案【样例输入】 1101 【样例输出】 8

ACM程序设计大赛(校级)

Problem A ISBN号码 Description 每一本正式出版的图书都有一个ISBN号码之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在该出版社的编号；最后一位为识别码。识别码计算方法如下：首位数字乘以1加上次位数字乘以2……以此类推，所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，分别乘以1，2.，……，9，再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11 的结果4作为识别码。你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。 Input 输入只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。 Output 输出共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定格式，输出正确的ISBN号码（包括分隔符“-”）。 Sample1 Input 0-670-82162-4 Sample2 Input 0-670-82162-0 Sample1 Output Right Sample2 Output 0-670-82162-4

2008年ACM大学生程序设计竞赛题

计算机科学系第二届大学生程序设计竞赛试题题目一大数乘法问题描述（Problem Description）：编程实现位数不超过300位的任意大的两个整数相乘。输入（Input）：提示用户输入第一个大数乘数和第二个大数乘数。输出（Output）：输出两个大数的乘积。输入示例（Sample Input）：请输入第一个乘数：123456789123456 请输入第二个乘数：123456789123456 输出示例（Sample Output）：两数的乘积是：15230578580673373689799383936

四三二五六一题目二排球队员站位问题问题描述（Problem Description）：左图为排球场的平面图，其中一、二、三、四、五、六为位置编号，二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，一、四号位放主攻手，二、五号位放二传手，三、六号位放副攻手。队员所穿球衣分别为１，２，３，４，５，６号，但每个队员的球衣都与他们的站位号不同。已知１号、６号队员不在后排，２号、３号队员不是二传手，３号、４号队员不在同一排，５号、６号队员不是副攻手。编程求每个队员的站位情况。输入（Input）：输出（Output）：输出每个队员球衣号码和所站的位置编号。输入示例（Sample Input）：输出示例（Sample Output）：球衣号码：1 2 3 4 5 6 位置编号：一二三四五六

题目三文件读写问题描述（Problem Description）： INI文件为一种广泛应用的储存程序配置的文件格式。要求不使用操作系统自带INI文件处理功能，用c++编写一个INI文件读取程序，并把结果输出到显示器及文件result.txt中。说明： INI文件的结构： [区名字] # 区名注释键名=键值 # 键值注释一个区里可以有几个不同键名的键值，例如：测试用INI文件test.ini： [section] #this is a section comment key=value #this is a key comment [section2] key2=value2 要求程序能读取section2区中键名为key2的值，以及section区中的键名为key的注释。输入（Input）：在Windows命令窗口里输入程序名称来运行程序，注意程序所带参数。输出（Output）：第一行输出section2区中键名为key2的值。第二行输出section区中的键名为key的注释。同时要把此结果输出到显示器和文件result.txt中。输入示例（Sample Input）： CppFileRW Test.ini 输出示例（Sample Output）： section2区中键名为key2的值是：value2 section区中的键名为key的注释是：this is a key comment

ACM入门之新手入门

ACM入门之新手入门 1.ACM国际大学生程序设计竞赛简介 1)背景与历史 1970年在美国T exasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别：区域赛和总决赛，这便是现代ACM竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区域赛点。1995至1996年，来自世界各地的一千多支s代表队参加了ACM区域竞赛。ACM大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。 2)竞赛组织竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(Regional Contest)”。各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“总决赛(Final Contest)”，其它的高分队伍也有可能被邀请参加决赛。每个学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位的学生。每支队伍最多允许有一名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。 3)竞赛形式与评分办法竞赛进行5个小时，一般有6~8道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。程序运行不正确是指出现以下4种情况之一： (1)运行出错(run-time error)； (2)运行超时〔time-limit exceeded〕； (3)运行结果错误(wrong answer)； (4)运行结果输出格式错误(presentation error)。竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时(每次提交通不过，罚时20分钟)。没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料(包括试题)将用美国英语写出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语言包括PASCAL，C，C++及Java，也可以使用其它语言。具体的操作系统及语言版本各年有所不同。 4)竞赛奖励情况总决赛前十名的队伍将得到高额奖学金：第一名奖金为12000美元，第二名奖金为 6000美元，第三名奖金为3000美元，第四名至第十名将各得到l500美元。除此之外还将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。 2.ACM竞赛需要的知识语言是最重要的基本功无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当

第三届ACM程序设计大赛试题new

计算机工程学院第三届ACM程序设计大赛试题 Problem A Bridge Description n people wish to cross a bridge at night. A group of at most two people may cross at any time, and each group must have a flashlight. Only one flashlight is available among the n people, so some sort of shuttle arrangement must be arranged in order to return the flashlight so that more people may cross. Each person has a different crossing speed; the speed of a group is determined by the speed of the slower member. Your job is to determine a strategy that gets all n people across the bridge in the minimum time. Input The first line of input contains n, followed by n lines giving the crossing times for each of the people. There are not more than 1000 people and nobody takes more than 100 seconds to cross the bridge. Output The first line of output must contain the total number of seconds required for all n people to cross the bridge. The following lines give a strategy for achieving this time. Each line contains either one or two integers, indicating which person or people form the next group to cross. (Each person is indicated by the crossing time specified in the input. Although many people may have the same crossing time the ambiguity is of no consequence.) Note that the crossings alternate directions, as it is necessary to return the flashlight so that more may cross. If more than one strategy yields the minimal time, any one will do. Sample Input（Input file: pa.txt） 4 1 2 5 10 Sample Output 17 1 2 1 5 10 2 1 2