帮我解释一下这个程序(Pascal)的思想,谢谢(100分)

  • 主题发起人 主题发起人 QAlong
  • 开始时间 开始时间
Q

QAlong

Unregistered / Unconfirmed
GUEST, unregistred user!
帮我解释一下这个程序的思想,谢谢[:D]
请帮我解释一下如何编制的这个程序(思想)。
题目:对一个给定的自然数M,求出所有的连续的自然数段,这些连续的自然数段中的全部数只和为M。
例子:1998+1999+2000+2001+2001=10000,所以从1998到2002的一个自然数段为M=10000的一个解。
输入格式:输入一个M值(10<=M<=2,000,000)。
输出格式:每行两个自然数,给出一个满足条件的连续自然数段中的第一个数和最后一个数,两数之间用一个空格隔开,所有输出行的第一个按从小到大的升序排列,对于给定的输入数据,保证至少有一个解。
输出样例:
18 142
297 328
388 412
1998 2002
答案:
program combo;
var
m,n:integer;
i:longint;
begin
read(m);
inc(m,m);
for i:=trunc(sqrt(2*m))do
wnto 1do
begin
n:=m div (i+1)-i;
if n<0 then
continue;
if m/(i+1)-i=n then
if n mod 2 =0 then
writeln(n div 2,' ',n div 2+i);
end;
end.
 
其实我也没弄懂...
大致上代码能写成这样,其实和没说是一样,别打我(N多算法设计教程都这样写)...直接看上面代码也行。
i从根号下2*m到1 循环
n等于m整除(i+1)减i
如果n小于0,继续 否则
如果m为(i+1)的整数倍 则
如果n是2的整数倍 ->输出 n/2 和 n/2+i
先说说算法,是用搜索的方式得出结果的,从sqrt(2*m)到1一个个的试。
首先这个sqrt(2*m)是最大的自然数段间隔,10000时为200。你设多少都无所谓,比如m div 2,只不过更耗时,跟踪一下就发现,间隔不可能超过sqrt(2*m)的。
然后n,这个就是关键了,为什么是整除(i+1)-i,这个就不太明白了
而下一步的n>0,因为你要得出的序列是区段所有值的和,所以当总和大于m时,舍去(continue)。
当 m/(i+1)-i=n (即 (m/(i+1)-i) = (m div (i+1)-i)时),m是i+1的倍数,然后检查n是否为偶数。为什么?别问我....我也想知道。
大概就这样,主要就是为什么 n:=m div (i+1)-i;
 
他给的解答很简单,这应该是个数论问题
 
n:=m div (i+1)-i;
不是m整除(i+1)-i,而是m div (i+1)在减去i
 
解题思想是这样的:
对于给定的M以及指定的数段长度L,要么没有解,要么有唯一解.(证明略)
因此可以针对每一可能的数段长度来求解,题目就变成了给定M,L,求可能的连续L个数之和=M,这个解还是比较容易求的.
题目中的i循环就是所有可能数段长度,都求完了,题目也解决了.
 
后退
顶部