算法习题及解答.doc

一个自然数可以写成若干个小于等于自己的自然之和，这叫该自然数的一个分解。不同的分解是表示这个自然数分解成的所有自然数不完全相同。例如：3=2+1和3=1+1+1表示不同的分解。而3=2+1和3=1+2为相同的分解。现在的任务是，给出一个自然数，要求所有不同的分解方案数。输入：输入文件的只有一个自然数N，N=10000。(input.txt)输出：输出文件只有一个数，为N的分解方案数。(output.txt)var n:integer; x:integer; a:array 0.10000 of integer;procedure writestr();var i:integer;begin write(n,=,a1); for i:=2 to x do begin write(+,ai); end; writeln;end;function adda():integer;var s:integer; i:integer;begin s:=0; for i:=1 to x do s:=s+ai; adda:=s;end;function test(m:integer):boolean;var i:integer;begin if m0 do begin ai:=m mod 10; m:=m div 10; i:=i+1; end; for i:=3 downto 1 do begin for j:=1 to i do begin if ajaj+1 then begin tmp:=aj; aj:=aj+1; aj+1:=tmp; end; end; end; max:=1000*a4+100*a3+10*a2+a1; min:=1000*a1+100*a2+10*a3+a4;end;procedure test(m:integer);var i:integer;begin if m=6174 then begin write(SETP=,x); halt; end; getmaxmin(m); writeln(max,-,min,=,max-min); x:=x+1; test(max-min);end;beginassign(input,input.txt); assign(output,output.txt); reset(input); rewrite(output); read(n); writeln(n=,n); x:=0; test(n); close(input); close(output);end.253、溢出 over.pas问题描述 写一个程序，读入两个非负整数及一个运算符号判断两整数及运算结果是否超出了PASCAL语言中关于长整数类型的定义。（长整数范围为-2147483648到2147483647）输入文件一行包含整数和运算符，运算符（，*，div）输出文件先输出一遍原输入，并在后面输出0到3行适当内容，如：first number is too big second number is too bigresult number is too big例如： 输入 输出300+3 300+3300000*300000 300000*300000 result is too big9999999999999999999+1 9999999999999999999+1 first number is too big result number is too big建议用int64来处理，范围大小是（-9223372036854775808 . 9223372036854775807）259、最大最小差(MaxMin) 问题描述： 现在有N个正整数，每一次去掉其中2个数a和b，然后加入一个数a*b+1，这样最后只剩下一个数P。要求求出最大的P记为MaxP，最小的p记MinP，和他们的差K=MaxP-MinP。 对于给定的数列，编程计算出它的Max,Min和K。 输入文件（MAXMIN.IN）： 第一行是数列的长度N（不超过50），以下N行，每行一个正整数（不超过2位）。 输出文件（MAXMIN.OUT）： 输出一共三行，每行一个整数，依次为max,min,K。 输入输出样例： MAXMIN.IN MAXMIN.OUT 2 1 1 2 2 0 var arr:array 0.49 ofinteger; excepti:array 0.49 of integer; test:array 0.49 of integer; max,min,n:integer;procedure InitExcept();var i:integer;begin for i:=0 to n-1 do exceptii := -1;end;function IsIn(i:integer):boolean;var j:integer;begin for j:=0 to n-1 do begin if exceptij=i then exit(true); end; IsIn:=false;end;procedure writestr();var i,r:integer;begin for i:=0 to n-2 do begin r:=testi*testi+1+1; testi+1:=r; end; if maxr then min:=r;end;procedure PaiLie(num:integer);var i:integer;begin if num = 0 then begin writestr(); exit; end; for i:=0 to n-1 do begin if not IsIn(i) then begin exceptin-num:=i; testn-num:=arri; PaiLie(num-1); end; end; exceptin-num:=-1;end;procedure ReadArray();var i:integer;begin for i:=0 to n-1 do read(arri);end;begin assign(input,MAXMIN.IN); assign(output,MAXMIN.OUT); reset(input); rewrite(output); read(n); max:=0; min:=10000; ReadArray(); InitExcept(); PaiLie(n); writeln(max=,max); writeln(min=,min); write(k=,max-min); close(input); close(output);end.260、输入一个英文句子，例如：“This is a Book.，可以看到句子是以“.”来作为结束符号的，并且单词之间以一个空格来分隔。接着再输入一个单词A，请找出首次在句子中出现的与A$相同的单词，是句子中的第几个单词，若不存在，则输出该句子中单词字符的总个数。 例如对上句子而言，若输入单词“is”，则应输出： 2 若输入单词“isa”，则应输出：11var n,ls,la,i:integer; a,s,sf:string;begin readln(s); readln(a); s:=copy(s,1,length(s)-1); n:=1; la:=length(a); ls:=length(s); sf:=s; while pos( ,sf)0 do begin delete(sf, pos( ,sf),1); n:=n+1; end; sf:=; for i:=1 to ls-la+1 do begin if (copy(s,i,la)=a)and(copy(s,i-1,1)= )and(copy(s,i+la,1)= ) then begin sf:=copy(s,1,i+la-1); break; end; end; if sf then begin i:=1; while pos( ,sf)0 do begin i:=i+1; delete(sf,pos( ,sf),1); end; end else begin while pos( ,s)0 do begin delete(s,pos( ,s),1); end; i:=length(s) end; write(i);end.263、给出二个任意的正整数N，K（1=N=10000，0=K 0 do begin i:=i+1; temp:=temp-mexp(2,i); if temp=0 then begin write(ERROR!); halt; end; end; i:=0; s:=0; while n0 do begin s:=s+1; n:=n-mexp(2,i); i:=i+1; if n0 then begin i:=0; while n0 do begin n:=n+k; end; end; end; write(STEP=,s);end.264、生日日期 ( Birthday ) 问题描述：小甜甜的生日是YY年MM月DD日，他想知道自己出生后第一万天纪念日的日期（出生日算第0天）。输入格式：从文件的第一行分别读入YY，MM，DD其中1949=YYflag then begin d:=1; m:=m+1; if m=13 then begin m:=1; y:=y+1; end; end; exit; end; if (y mod 4=0)and(m=2) then begin flag:=29; end else begin case m of 1,3,5,7,8,10,12:flag:=31; 4,6,9,11:flag:=30; 2:flag:=28; end; end; if dflag then begin d:=1; m:=m+1; if m=13 then begin m:=1; y:=y+1; end; end;end;begin assign(input,BIRTHDAY.DAT); assign(output,BIRTHDAY.OUT); reset(input); rewrite(output); read(y); read(m); read(d); for i:=1 to 10000 do begin incdate(); end; write(y,-,m,-,d); close(input); close(output);end.265、分解因式 ( Factor )问题描述：一个自然数N的正因子个数记为F(N)，例如18的所有正因子为1、2、3、6、9、18，所以F(18)=6。现在给出K，求所有满足F(N)=K的N中最小的数。输入格式：从文件读入数据，第一行为K，其中0K=80。输出格式：输出到文件第一行，如果存在不大于20000的解，则输出这个N，否则输出“NO SOLUTION”。样例1：FACTOR.DATFACTOR.OUT9样例2：FACTOR.DATFACTOR.var i:longint; n:integer;function getfactor(x:longint):integer;var m:longint; r:integer;begin r:=0; for m:=1 to x do begin if x mod m=0 then r:=r+1; end; getfactor:=r;end;begin assign(input,FACTOR.DAT); assign(output,FACTOR.OUT); reset(input); rewrite(output); read(n); for i:=1 to 20000 do begin writeln(i); if getfactor(i)=n then begin write(i); close(input); close(output); halt; end; end; write(NO SOLUTION); close(input); close(output);end.266、K好数（K-Good Number）问题描述：如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。给定K、L，求L位K好数的数目。输入格式：从文件读入数据，第一行为K、，其中K=16，L=10。输出格式：将结果输出到 KGOOD.OUT样例KGOOD.DATKGOOD.OUT4 27var k,l,n:integer; a:array 1.16 of integer; test:boolean;procedure getnum(i:integer);var m,j,s:integer;begin if i=1 then s:=1 else s:=0; for m:=s to k-1 do begin ai:=m; if i=l then begin test:=true; for j:=1 to l-1 do begin if (aj-aj+1)*(aj-aj+1)=1 then begin test:=false; end; end; if test then begin n:=n+1; end; end else begin getnum(i+1); end; end;end;begin assign(input,KGOOD.DAT); assign(output,KGOOD.OUT); reset(input); rewrite(output); read(k); read(l); for n:=1 to l do begin an:=0; end; n:=0; getnum(1); write(n); close(input); close(output);end.267、Sramoc问题 ( Sramoc Problem )问题描述：Sramoc ( K , M ) 表示用数字0、1、K-1组成的自然数中能被M整除的最小数。给定 K、M，求Sramoc ( K,M )。例如 K=2，M=7的时候，Sramoc( 2 , 7 ) = 1001。输入格式：从文件SRAMOC.DAT读入数据。第一行为两个整数K、M满足2=K=10、1=M=1000。输出格式：输出Sramoc(K,M) 到 SRAMOC.OUT。样例SRAMOC.DATSRAMOC.OUT2 71001var k,m,n,l:integer; a1,a2:longint; a:array 1.100 of integer; test:boolean;procedure getnum(i:integer);var j,x:integer; s:longint;begin if test then exit; for x:=0 to k-1 do begin ai:=x; if i=l then begin s:=0; for j:=1 to l do s:=s*10+aj; if s=0 then continue; if s mod m=0 then begin test:=true; n:=s; break; end; end else begin getnum(i+1); end; end;end;begin assign(input,SRAMOC.DAT); assign(output,SRAMOC.OUT); reset(input); rewrite(output); read(k); read(m); test:=false; l:=1; if mk then begin n:=m; end else begin l:=0; while not test do begin l:=l+1; getnum(1); end; end; write(n); close(input); close(output);end.269、顺序数串无穷小数小明构造了一个无穷小数x=0.12345678910119899100101，其中的数字是依次写下各自然数而得到的。试求出小数点后第m位数字。 输入：文件中每行有一个整数m( m0 do begin i:=i+1; n:=n-9*mexp(i); end; n:=n+9*mexp(i); if n mod (i+1)=0 then r:=i+1 else r:=n mod (i+1); x:=(n-r) div (i+1); s:=mstr(x+mexp(i); s:=copy(s,r,1); writeln(s);end;begin assign(input,c:input.txt); assign(output,c:output.txt); reset(input); rewrite(output); while not eof do begin readln(m); writeret(m); end; close(input); close(output);end.270、NCL是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手ZL先生。为了很好的完成这个任务，ZL先生首先研究了一些一元一次方程的实例： 43x8 6a5122a 512y0ZL先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母及、这三个数学符号（当然，符号“”既可作减号，也可作负号）。方程中并没有括号，也没有除号，方程中的字母表示未知数。 问题求解 编写程序，解输入的一元一次方程, 将解方程的结果(精确至小数点后三位)输出至屏幕。 你可假设对键入的方程的正确性的判断是由另一个程序员在做，或者说可认为键入的一元一次方程均为合法的，且有唯一实数解。 样 例 输入： 6a5122a输出： a0.750 275、问题描述：给出n个整数x1,x2,x3,x4.xn,将这n个数从小到大排序为：A1,A2,A3,A4.AN，记数列A1,A2,A3,A4.AN的奇数项之和为P，偶数项之和为Q，令T=|P-Q|求出T的值。输入格式：输入文件的第一行为整数N（1=n=50000）。接下来的N行每行有一个整数，按顺