pascal数字游戏的简便做法
发布网友
发布时间：2024-10-01 23:23
我来回答
共1个回答
热心网友
时间：2024-11-21 01:20
对于这题给人的第一感觉就是用穷举法，把每个情况都探到即可解题。但你要仔细看一下题目要求就会发现问题所在。题目要求n（1≤n≤50）和m（1≤m≤9）粗略估计一下所可能出现的情况应为429即是4.06×1014次。这样是无法在规定的时间里完成。那么如何解决呢？答案就是用递推法。如何递推呢？我们假设有n个数分成m个部分，也可以看成切m个口。第一个切口切完后，我们就可以看成一个有n个数组成的长链。那末这第一刀就有n个切法 ,我们就先对第一种切法进行研究，也就是把从1到n个数切m-1刀分成m个部分。首先我们想象第一部分可分为1个数字、2个数字、3个数字……（n-m）个数字。我们把其求和取模的结果分别存入数组的（n-m）个单元中。接着我们可以把第一、二部分合并考虑了，我们可以认为只有（n-m+1）个数字分成两个部分和（n-m）个数字分成两个部分……和2个数字分成两个部分的（n-m）种情况。见下图所示，两个部分寻找最大值过程,我们再把每种情况中的最大值和最小值找出，分别存入d和x两个数组中。再接着我们可以把第一、二、三部分合并考虑了，我们可以认为只有（n-m+2）个数字分成三个部分和（n-m+1）个数字分成三个部分……和3个数字分成三个部分的（n-m）种情况。我们再把每种情况中的第三部分，分别于两个部分的最大值和最小值相乘就可以找到三个部分的最大值和最小值。如下图所示，三个部分寻找最大值过程。
下面就是我所编的参考程序：
Var
a,b:Array[1..100]Of integer;
d,x:Array[1..50]Of longint;
m,n,l,i,j:Integer;
mk,sk:longint;
Procedure Work;
Var
i,j,s,k,k1:Integer;
da,xiao:longint;
Begin
for i:=1 to l do
begin
s:=0;
for j:=1 to l-i+1 do
begin
s:=s+b[m+j+i-2];
end;
d[i]:=s mod 10;
if d[i]<0 then d[i]:=d[i]+10;
end;
x:=d;
for i:=m-1 downto 1 do
begin
for j:=1 to l do
begin
da:=0;xiao:=90000000;
for k:=j to l do
begin
s:=0;
for k1:=j to k do
s:=s+b[i+k1-1];
s:=s mod 10;
if s<0 then s:=s+10;
if da<s*d[k] then da:=s*d[k];
if xiao>s*x[k] then xiao:=s*x[k];
end;
d[j]:=da;x[j]:=xiao;
end;
end;
end;
begin
readln(n,m);
mk:=0;sk:=90000000;l:=n-m+1;
for i:=1 to n do
readln(a[i]);
for i:=1 to n-1 do
a[i+n]:=a[i];
for i:=1 to n do
begin
for j:=1 to n do
b[j]:=a[i+j-1];
Work;
if mk<d[1] then mk:=d[1];
if sk>x[1] then sk:=x[1];
end;
writeln(sk);writeln(mk);
end.
