题目描述 Description对于一个自然数M,求出所有的连续.pptVIP

题目描述?Description 对于一个自然数M,求出所有的连续的自然数段,使得这些连续自然数段的全部数字和为M.eg:1998+1999+2000+2001+2002=10000,所以从1998到2002的一个自然数段为M=10000的一个解。? 输入描述?Input Description 一个数M 输出描述?Output Description 每行两个数，为连续自然数段的一头一尾，所有输出行的第一个数按照升序排列 样例输入?Sample Input 10000 样例输出?Sample Output 18 142 297 328 388 412 1998 2002 算法一：用i枚举起点，用j枚举落点，用k来枚举起点到落点，ans求和，很容易得到 for i:=1 to m-1 do for j:=i to m-1 do begin for k:=i to j do inc(ans,k); if ans=m then writeln(i, ,j); ans:=0; end； 算法二：类似于算法一，只不过生略掉k，直接用求和等差数列公式（首项+末项）*项数/2，得到： for i:=1 to m-1 do for j:=i to m-1 do if (i+j)*(j-i+1)/2=m then writeln(i,‘ ’,j)； 算法三：建立在算法二的基础上，用i枚举起点，进行二分查找结束点j，得到 function find(l,r:longint):longint; var x:longint; begin if lr then exit; x:=(l+r)div 2; if (i+x)*(x-i+1)/2=m then writeln(i, ,x) else if (i+x)*(x-i+1)/2m then find(l,x-1) else find(x+1,r); end; 算法四：对于算法二的优化，如果和大于m，j的扩大只会使和也扩大，所以就直接退出循环 for i:=1 to m-1 do for j:=i to m-1 do if (i+j)*(j-i+1)/2=m then writeln(i, ,j) else if (i+j)*(j-i+1)/2m then break; 八年级下学期时，将会学习一元二次方程的解法： 首先明确形如一元二次方程 ax^2+bx+c(a0)的求根公式 ? x=(-b+sqrt(b^2-4*a*c))/2 或 (-b-sqrt(b^2-4*a*c))/2 推导方法可以用配方法，左边配成一个完全平方式，右边只含有常数项，就可以求出x 算法五：设起点为i，共有n个数 则结束的数为(i+n-1)所以得 (i+i+n-1)*n/2=m ? n^2-(2*i-1)-2*m=0 ? 所以n=(1-2*i+sqrt((2*i-1)^2-4*1*(-2*m)))/2 ? ?（大家自行思考为什么忽略另一个解） ? ? ? ?n=(1-2*i+sqrt(4*i*i-4*i+1+8*m))/2 ? ? ? 所以只要用i枚举起点，在判断n是否为自然数然后输出 ? 就可以得到 ? for i:=1 to m-1 do ?if trunc((1-2*i+sqrt(4*i*i-4*i+1+8*m))/2) =(1-2*i+sqrt(4*i*i-4*i+1+8*m))/2 then writeln(i,‘ ’,i+((1-2*i+sqrt(4*i*i-4*i+1+8*m))/2-1):0:0); 算法六：以上五种算法都是枚举起点i，不妨换个角度，枚举长度i，设起点为x，则结束点为x+i-1，所以，(x+x+i-1)*i/2=m (2*x+i-1)*i=2*m 2*i*x+i*i-i=2*m 2*i*x=2*m-i*i+i x=(2*m-i*i+i)/(2*i) 只要判断x是否为自然数，然后输出。 注意：1.x为自然数 2.题目要求是升序输出，所以枚举长度是要倒序 for i:=trunc(sqrt(4*m+0.25)-0.5) downto 2 do if (trunc((-i*i+i+2*m)/(2*i))= (-i*i+i+2*m)/(2*i))and ((-i*i+i+2*m)/(2*i)0) then writeln((-i*i+i+2*m)/(