第11课 基础程序.docx

第11课 基础程序.docx

《第11课 基础程序.docx》由会员分享，可在线阅读，更多相关《第11课 基础程序.docx（36页珍藏版）》请在冰点文库上搜索。

第11课基础程序

最大公约数

描述：

计算出m与n的最大公约数。

要求：

用两种方法实现

方法一：

递归实现

方法二：

非递归实现

输入格式：

就一行，用空格隔开的两个整数

输出格式：

直接输出最大公约数

样例输入：

1624

样例输出：

8

分析：

从数学上可以知道求m和n的最大公约数等价于求n与（mmodn）的最大公约数，这时可以将n当作新的m，（mmodn）当作新的n，问题又变成了求新的m和n的最大公约数，如此继续，直到新的n等于0时，其最大公约数就是m。

递归实现：

programss;

var

m,n,g:

integer;

functiongcd（m,n:

integer）:

integer;

begin

ifn=0

thengcd:

=m

elsegcd:

=gcd（n,mmodn）;

end;

begin

read（m,n）;

g:

=gcd（m,n）;

write（g）;

end.

非递归实现：

将n当作新的m，（mmodn）当作新的n，也就是在实现m和n交换的时候，将（mmodn）的值保存在中间变量中，最后赋给n。

参考程序：

programss;

var

m,n,t:

integer;

begin

read（m,n）;

repeat

t:

=mmodn;

m:

=n;

n:

=t;

untiln=0;

write（m）;

end.

最小公倍数

描述：

计算出m与n的最小公倍数。

要求：

用两种方法实现

方法一：

非递归实现

方法二：

递归实现

输入格式：

就一行，用空格隔开的两个整数

输出格式：

直接输出最小公倍数

样例输入：

1624

样例输出：

48

分析：

从数学上可以知道求m和n的最小公倍数，应找到两个数中最大的一个，然后对其依次加倍，直到得到的数g也能被两个数中比较小的那个数整除为止，这个数g就是两个数的最小公倍数。

非递归实现：

programss;

var

m,n,g:

integer;

begin

read（m,n）;

ifm

thenbegin

t:

=m;

m:

=n;

n:

=t;

end;

g:

=m;

whilegmodn<>0do

g:

=g+m;

write（g）;

end.

递归实现：

programss;

var

m,n,t:

integer;

functionlcm（a,b:

integer）:

integer;

begin

ifamodb=0

thenlcm:

=a

elselcm:

=lcm（a+m,b）;

end;

begin

read（m,n）;

ifm

thenbegin

t:

=m;m:

=n;n:

=t;

end;

t:

=lcm（m,n）;

write（t）;

end.

求素数

描述：

找出一个给定区域之间的所有素数。

（5000以内）

输入格式：

两个整数，用空格隔开，表示闭区间的开始和结束

输出格式：

第一行输出素数的个数，从第二行开始从小到大输出所有的素数，中间用一个空格隔开。

样例输入：

2100

样例输出：

25

2357111317192329313741434753596167717379838997

分析：

素数是指除1及本身以外不能被其他数整除的自然数。

为了判断某个数m是不是素数，最简单的办法是用2，3，4，……m-1逐个去除m，看能否除尽。

若被其中一个数除尽了，则m不是素数，否则m就是素数。

当m较大时，用这种办法除的次数太多，可以有多种方法改进，以减少除的次数。

其中一种方法：

用2，3，4，……√m去除，如果除不尽，则m为素数。

可以用反证法证明：

假设有大于√m的数j能除尽m，则它的商k必定小于√m，说明k能除尽√m，这与小于等于√m的数都除不尽m相矛盾，假设不成立。

参考程序如下：

programexample4（input,output）;

var

i,j,n:

integer;

flag:

boolean;

begin

read（n）;

Fori:

=2tondo

Begin

Flag:

=true;

Forj:

=2toround（sqrt（i））do

Ifimodj=0

Thenbegin

flag:

=false;

break;

end;

Ifflag

Thenwrite（i,''）;

End;

End.

筛选法求素数：

programexample4（input,output）;

var

i,j,n,k:

integer;

flag:

boolean;

a:

array[1..1000000000]oflongint;

f:

array[1..1000000000]ofboolean;

begin

read（n）;

k:

=0;

f[1]:

=false;

fori:

=2tondof[i]:

=ture;

fori:

=2tondo

iff[i]

thenbegin

inc（k）;

p[k]:

=i;

j:

=2*i;

whilej<=ndo

begin

f[j]:

=0;

inc（j,i）

end;

end

fori:

=2tokdowrite（i,''）;

End.

超级素数（USACO1994决赛）

描述：

一个n位超级素数是指一个n位正整数，它的前1位，前2位,...,前n位均为素数，例如，7331是个4位超级素数，因为7，73，733，7331均为素数。

由键盘输入n（n<9）,然后输出全部的n位超级素数。

输入格式：

一个整数n

输出格式：

第一行输出超级素数的个数，从第二行开始从小到大输出所有的超级素数，中间用一个空格隔开。

样例输入：

2

样例输出：

9

232931375359717379

分析：

素数是指除1及本身以外不能被其他数整除的自然数，1不是素数。

一、为了判断某个n位数m是不是超级素数，最简单的办法是从2到n个9组成的数逐个验证，并应按照超级素数的定义完整验证，注意高位出现0和1的情况。

二、当m较大时，用上面这种办法计算的次数太多，其中一种改进方法是先筛选后判断，筛选的结果是：

（1）高位可能为2,3,5,7，而绝对不能是0,1,4,6,8,9；

（2）除高位外的其它各位数字可能是1,3,7,9，而绝对不能是0,2,4,5,6,8。

参考程序如下：

programss;

type

ar=array[1..4]ofinteger;

var

n,i:

integer;

s:

longint;

a,b:

ar;

functionsushu（x:

longint）:

boolean;

var

i:

integer;

begin

sushu:

=true;

fori:

=2totrunc（sqrt（x））do

ifxmodi=0

thenbegin

sushu:

=false;

break;

end;

end;

procedurezushu（y:

longint;m:

integer）;

var

i:

integer;

z:

longint;

begin

ifm<=n-1

thenfori:

=1to4do

begin

z:

=y*10+b[i];

ifsushu（z）

thenzushu（z,m+1）

end

elsewrite（y,''）;

end;

begin

read（n）;

a[1]:

=2;a[2]:

=3;a[3]:

=5;a[4]:

=7;

b[1]:

=1;b[2]:

=3;b[3]:

=7;b[4]:

=9;

fori:

=1to4do

begin

s:

=a[i];

zushu（s,1）;

end;

end.

回文数

描述：

一个从左到右看和从右到左看是一样的字符串就称为回文。

一个从左到右看和从右到左看是一样的数就是一个回文数，比如数151就是一个回文数。

写一个程序来判断给定的一个数x是否为回文数;（x<109）

输入格式：

一个整数

输出格式：

是回文数输出“Yes”，不是输出“No”。

样例输入：

284542

样例输出：

No

参考：

str（x[:

w:

d],s）——将整数或实数（[:

w:

d]为场宽的用法）转换为字符串的函数。

val（s,x,code）——将字符串转换为整数或实数的函数。

若s中有非法字符，则code存放非法字符在s中的下标；否则，code为零。

code为整型数。

参考程序如下：

programhuiwenshu;

var

i,j,lc:

integer;

n:

longint;

s:

string;

flag:

boolean;

begin

read（n）;

str（n,s）;

lc:

=length（s）;

i:

=1;

j:

=lc;

flag:

=true;

repeat

ifs[i]=s[j]

thenbegin

inc（i）;

dec（j）;

end

elsebegin

flag:

=false;

break;

end;

untili>=j;

ifflag

thenwrite（'Yes'）

elsewrite（'No'）;

end.

回文素数（PrimePalindromes）（USACO）

描述：

因为151即是一个素数又是一个回文数（从左到右和从右到左是看一样的），所以151号是回文素数。

写一个程序来找出范围[a,b]（5<=a

程序名称:

pprime

输入格式：

就1行:

二个整数a和b。

输出格式：

输出一个回文素数的列表，一行一个。

样例输入：

（filepprime.in）

5500

样例输出：

（filepprime.out）

5

7

11

101

131

151

181

191

313

353

373

383

5位数以内的参考程序：

programhuiwensushucx;

var

m,n,i:

longint;

functionsushu（x:

longint）:

boolean;

var

i:

integer;

begin

sushu:

=true;

fori:

=2totrunc（sqrt（x））do

ifxmodi=0

thenbegin

sushu:

=false;

exit;

end;

end;

functionhuiwenshu（y:

longint）:

boolean;

var

lc,i,j:

integer;

s:

string;

begin

str（y,s）;

lc:

=length（s）;

i:

=1;

j:

=lc;

huiwenshu:

=true;

repeat

ifs[i]=s[j]

thenbegin

inc（i）;

dec（j）;

end

elsebegin

huiwenshu:

=false;

exit;

end;

untili>=j;

end;

begin

read（m,n）;

fori:

=mtondo

ifsushu（i）

thenifhuiwenshu（i）

thenwrite（i,''）;

end.

5位数以上的参考程序：

programhuiwensushucx;

var

m,n,i:

longint;

f:

array[1..100000000]ofboolean;

proceduresushu;

var

i,j:

longint;

begin

f[1]:

=false;

fori:

=2tondo

f[i]:

=true;

j:

=1;

repeat

while（j<=n）and（f[j]<>true）do

j:

=j+1;

i:

=j+j;

whilei<=ndo

begin

f[i]:

=false;

i:

=i+j;

end;

j:

=j+1;

untilj>n;

end;

functionhuiwenshu（y:

longint）:

boolean;

var

lc,i,j:

integer;

s:

string;

begin

str（y,s）;

lc:

=length（s）;

i:

=1;

j:

=lc;

huiwenshu:

=true;

repeat

ifs[i]=s[j]

thenbegin

inc（i）;

dec（j）;

end

elsebegin

huiwenshu:

=false;

exit;

end;

untili>=j;

end;

begin

read（m,n）;

sushu;

fori:

=mtondo

iff[i]

thenifhuiwenshu（i）

thenwrite（i,''）;

end.

又是一题枚举搜索的题目，先生成sqrt（100,000,000）也就是10000以内的质数，这样判断是否质数时只需要拿这些数来除就行了,小剪一下,开头一个数是偶数的不考虑,除11以外回文质数都是奇数位的,因为奇数位之和与偶数位之和的差为11的倍数的数能整除11,而偶数位的回文数,满足之前条件（=0）.然后枚举10^[（wadiv2）]到10^index[（wbdiv2）+2]-1中的数x作为类似于xyx这样的数来判断是否质数.

{

TASK:

pprime

LANG:

PASCAL

}

programpprime;

const

maxn=10000;

index:

array[0..9]ofqword=（1,1,10,100,1000,10000,100000,1000000,10000000,100000000）;

var

isprime:

array[2..maxn]ofboolean;

prime:

array[0..1500]ofinteger;

a,b,sqrtb,i:

longint;

procedureinit;

var

c:

longint;

begin

assign（input,'pprime.in'）;reset（input）;

readln（a,b）;

ifa>bthen

begin

c:

=a;

a:

=b;

b:

=c;

end;

sqrtb:

=trunc（sqrt（b））;

close（input）;

end;

procedureinitprime;{生成<10000的质数}

var

i,j:

integer;

begin

fillchar（isprime,sizeof（isprime）,true）;

fori:

=2to100do

ifisprime[i]then

forj:

=2to（maxndivi）do

isprime[j*i]:

=false;

fillchar（prime,sizeof（prime）,0）;

fori:

=2tomaxndo

ifisprime[i]then

begin

inc（prime[0]）;

prime[prime[0]]:

=i;

end;

end;

procedurecheck（x:

longint）;{检查是否素数}

var

i:

integer;

isprime:

boolean;

begin

isprime:

=true;

fori:

=1toprime[0]do

begin

ifprime[i]>trunc（sqrt（x））+1thenbreak;

ifxmodprime[i]=0then

begin

isprime:

=false;

break;

end;

end;

ifisprimethenwriteln（x）;

end;

proceduremake;

var

i,num:

longint;

j,wa,wb,k,len,code:

integer;

st,stt:

string;

begin

assign（output,'pprime.out'）;rewrite（output）;

fori:

=ato11do

ifisprime[i]and（i

wa:

=trunc（ln（a）/ln（10））+1;{a的位数}

wb:

=trunc（ln（b）/ln（10））+1;{b的位数}

fori:

=index[（wadiv2）]toindex[（wbdiv2）+2]-1do

begin

str（i,st）;

len:

=length（st）;

ifnotodd（ord（st[1]）-48）thencontinue;{剪枝一，另外奇数数位那个剪枝直接+了中间数剪了}

forj:

=0to9do

begin

stt:

=st+chr（j+48）;

fork:

=lendownto1do

stt:

=stt+st[k];

val（stt,num,code）;

if（num>=a）and（num<=b）then

check（num）;

end;

end;

close（output）;

end;

begin

init;

initprime;

make;

end.

亲和数（）

背景Background

某一天，CCC老师买了一本趣味数学书，上面提到了一种数……

描述Description

这种数是——亲和数，所谓亲和数就是：

定义数对（x,y）为亲和数对当且仅仅当x、y为不同正整数，且x、y各自的所有非自身正因子之和等于另一个数。

例如（220,284）和（280,224）都是亲和数对，因为：

220的所有非自身正因子之和为：

1+2+4+5+10+11+20+22+44+55+110=284

284的所有非自身正因子之和为：

1+2+4+71+142=220

数对（x,y）跟（y,x）被认为是同一数对，所以我们只考虑x

任务　：

tenshi对某个范围内的亲和数对的数量非常感兴趣，所以希望你能帮她编写一个程序计算给定范围内的亲和数对的数量。

给定一个范围A到B，如果A≤x≤B，则我们称（x,y）在范围[A,B]内。

输入格式InputFormat

从文件的第一行分别读入正整数A和B，其中A、B满足

　　　　　1≤A≤B≤10^8且B-A≤10^5

输出格式OutputFormat

输出文件只有一行，就是[A,B]内亲和数对的数量

样例输入SampleInput

2002000

样例输出SampleOutput

2

注释Hint

[200,1200]内的数对只有两个，分别是（220,284）和（11841210）

参考程序：

programgxy;

var

a,b,i,j,k,s:

longint;

proceduretry（x:

longint）;

　varii:

longint;

　begin

　　s:

=1;

　　forii:

=2totrunc（sqrt（x））do

　　begin

　　　　ifxmodii=0

thenbegin

　　　　ifii*ii<>x

thens:

=s+ii+（xdivii）

　　　　else　s:

=s+ii;

　　　　end;

　　end;

　end;

begin

　read（a,b）;

　fori:

=atobdo

　　begin

　　try（i）;

j:

=s;

　　if（j>i）and（j<=i+100000）

thenbegin

　　　　try（j）;

　　　　ifs=itheninc（k）;

　　end;

　　end;

　writeln（k）;

end.

全排列

描述：

求N个数的全排列。

（1~N）

输入格式：

一个整数N

输出格式：

输出所有的全排列，每输出一个全排列，然后换行输出下一个全排列，最后一行输出全排列的数目。

样例输入：

3

样例输出：

123

132

213

231

312

321

6

参考程序：

programquanpailie;

var

total:

longint;

i,n:

integer;

x:

array[1..10]ofinteger;

a:

array[1..10]ofboolean;

procedureprint;

var

i:

integer;

begin

fori:

=1tondo

write（x[i],''）;

writeln;

total:

=total+1;

end;

proceduretry（i:

integer）;

var

j:

integer;

begin

forj:

=1tondo

ifa[j]

thenbegin

x[i]:

=j;

a[j]:

=false;

ifi

thentry（i+1）

elseprint;

a[j]:

=true;

end;

end;

begin

total:

=0;

writeln（'Pleaseinputn'）;

readln（n）;

fori:

=1tondo

a[i]:

=true;

try

（1）;

writeln（'total=',total）;

readln;

end.

组合数

描述：

求出从N个自然数（1,2,…,n）中选出r个数的所有组合。

输入格式：

两个整数n和r，用空格隔开

输出格式：

输出r个数的所有组合，每输出一个组合，然后换行输出下一个组合，最后一行输出组合的数目。

样例输入：

53

样例输出：

123

124

125

134

135

145

234

235

245

345