一個公司得面試題

Question

编程实现求出若干个整数之和为500的连续整数（如98，99，100，101，102），所有组合。

Answer 1

using System;namespace MySpace
{

class Test
{

static void Main()
{
int sum=0;
for (int i=1;i<500;i++)
{
for (int j=i;j<500;j++)
{
sum=(j-i+1)*(i+j)/2;
if (sum==500)
{
Console.WriteLine("第一个数是{0}  最后一个数{1}",i,j);
}
}
}
Console.ReadLine(); }
}
}

Answer 2

string str = "";
bool vb;
for(int i=1; i<250; i++)
{
vb = true;
for(int j=i; j<250 && vb; j++)
{
if(((i+j)*(j-i+1)/2) == 500)
{
str = str + i+"abc   ";
vb = false;
}
if(((i+j)*(j-i+1)/2) > 500)
{
vb = false;
}
}
}

Answer 3

恩  感觉小伤的思路已经不错了……～……～
如果是我肯定想不到
sum=(j-i+1)*(i+j)/2;    
呵呵  忽然就想起来小时候说的 1＋………………＋100 ＝ ？？？
 
这个用起来应该已经是比较快的了吧
没有想到更好的算法了！！～～

Answer 4

不好意思
//shy
多了个-

Answer 5

float fx=(1000.0f/(n+1)-n)/2;      //看fx是不是整数int x=(int)Math.Floor(fx);         //取fx的整数if((fx-x)<0.000001)                //比较fx和x是否一样大小
{
   Console.WriteLine("从{0}开始，{1}结束",x,n+x);
}==================
输出结果：
从98开始，102结束
从59开始，66结束
从8开始，32结束
从-7开始，32结束
从-58开始，66结束
从-97开始，102结束

Answer 6

sorry，少了一个循环
for(int n=2;n<500;n++)
{
   float fx=(1000.0f/(n+1)-n)/2;      //看fx是不是整数
   
   int x=(int)Math.Floor(fx);         //取fx的整数   if((fx-x)<0.000001)                //比较fx和x是否一样大小
   {
Console.WriteLine("从{0}开始，{1}结束",x,n+x);
   }
}
==================
输出结果：
从98开始，102结束
从59开始，66结束
从8开始，32结束
从-7开始，32结束
从-58开始，66结束
从-97开始，102结束

Answer 7

(a + b)*(b - a + 1)/2 = 500
就是求 (2 * a + delta) * (delta + 1)  = 1000 的所有整数解啊这个根本不需要写什么代码吧1000 = 10^3 = 2^3 * 5^3要分解成两数之积, 只可能以下几种情况
(2*a+delta) * (delta + 1)
-------------------------
(2^0 * 5^0) * (2^3 * 5^3)
(2^0 * 5^1) * (2^3 * 5^2)
(2^0 * 5^2) * (2^3 * 5^1)
(2^0 * 5^3) * (2^3 * 5^0)(2^1 * 5^0) * (2^2 * 5^3)
(2^1 * 5^1) * (2^2 * 5^2)
(2^1 * 5^2) * (2^2 * 5^1)
(2^1 * 5^3) * (2^2 * 5^0)(2^2 * 5^0) * (2^1 * 5^3)
(2^2 * 5^1) * (2^1 * 5^2)
(2^2 * 5^2) * (2^1 * 5^1)
(2^2 * 5^3) * (2^1 * 5^0)(2^3 * 5^0) * (2^0 * 5^3)
(2^3 * 5^1) * (2^0 * 5^2)
(2^3 * 5^2) * (2^0 * 5^1)
(2^3 * 5^3) * (2^0 * 5^0)剩下的就简单得很了，比方(2^3 * 5^2) * (2^0 * 5^1) = (2 * a + delta) * (delta + 1)
2^0 * 5^1 = delta + 1 ，所以  delta = 4
2^3 * 5^2 = 2 * a + delta , 所以 a = 98, 即 (98, 102)过滤其中的小数解，就可以了，这个要比上面完全搜索要快得多吧

Answer 8

for( int n = 5; n < 33 ; n ++ )
{
int sum = 0;
for( int X = 1 ; X < 500 ; X ++ )
{
for( int step = 0 ; step < n ; step ++ )
{
sum += X + step;
}
if( sum == 500 )
{
Console.WriteLine( n.ToString() + " 个数:  " );
for( int step = 0 ; step < n ; step ++ )
{
Console.WriteLine( Convert.ToString( X + step ) + ";" );
}
break;
}
sum = 0;
}
}/// 测试过 : 得到的结果是 :5 个数:  
98;
99;
100;
101;
102;8 个数:  
59;
60;
61;
62;
63;
64;
65;
66;25 个数:  
8;
9;
10;
11;
12;
13;
14;
15;
16;
17;
18;
19;
20;
21;
22;
23;
24;
25;
26;
27;
28;
29;
30;
31;
32;

Answer 9

for( int n = 5; n < 33 ; n ++ )
{
int sum = 0;
for( int X = 1 ; X < 500 ; X ++ )
{
for( int step = 0 ; step < n ; step ++ )
{
sum += X + step;
}
if( sum == 500 )
{
Console.WriteLine( n.ToString() + " 个数:  " );
for( int step = 0 ; step < n ; step ++ )
{
Console.WriteLine( Convert.ToString( X + step ) + ";" );
}
break;
}
sum = 0;
}
}测试结果如下:
5 个数:  
98;
99;
100;
101;
102;8 个数:  
59;
60;
61;
62;
63;
64;
65;
66;
25 个数:  
8;
9;
10;
11;
12;
13;
14;
15;
16;
17;
18;
19;
20;
21;
22;
23;
24;
25;
26;
27;
28;
29;
30;
31;
32;

Answer 10

{-499，500}不也是吗？
用我的方法，如果扩大外面的循环到5000，就能得到这一组数据for(int n=2;n<5000;n++)
{
   float fx=(1000.0f/(n+1)-n)/2;      //看fx是不是整数
   
   int x=(int)Math.Floor(fx);         //取fx的整数   if((fx-x)<0.000001)                //比较fx和x是否一样大小
   {
Console.WriteLine("从{0}开始，{1}结束",x,n+x);
   }
}

Answer 11

再次对上面结果过滤，如果delta 是偶数，则 delta +1 是奇数, 2 * a + delta 是偶数
如果delta 是奇数，则 delta +1 是偶数, 2 * a + delta 是奇数所以必须一项偶数,一项奇数分解,过滤后得到
(2*a+delta) * (delta + 1)
-------------------------
(2^0 * 5^0) * (2^3 * 5^3) -> -499到 500
(2^0 * 5^1) * (2^3 * 5^2) -> -97 到 102
(2^0 * 5^2) * (2^3 * 5^1) ->  -7 到  32
(2^0 * 5^3) * (2^3 * 5^0) ->  59 到  66(2^3 * 5^0) * (2^0 * 5^3) -> -58 到  66
(2^3 * 5^1) * (2^0 * 5^2) ->   8 到  32
(2^3 * 5^2) * (2^0 * 5^1) ->  98 到 102
(2^3 * 5^3) * (2^0 * 5^0) -> 500 到 500所以一共有 8 组解

Answer 12

to longqiaoman(龙桥人) 看前面的分析

Answer 13

tiaoci(我挑刺，我快乐):
我们也用数学推导出来的呀，要是题名改了，求连续整数和等于499的所有连续整数，你的方法还行吗？

Answer 14

tiaoci(我挑刺，我快乐):
我们也用数学推导出来的呀，要是题名改了，求连续整数和等于499的所有连续整数，你的方法还行吗？=============================================================你那只是简化了算法，算不上推导。如果没有计算机/计算器，那你的方法会比挑刺的快吗？数学不是靠蛮力的。

Answer 15

(a+b)(a-b+1)/2=500
(a+b)(a-b+1)=1000
假设a-b=D
则有:
(2a+D)(D+1)=1000
如果:D为奇数-->2a+D为奇数 且D+1为偶数;
如果:D为偶数-->2a+D为偶数 且D+1为奇数;
也就是说只可能出现一个奇数和一个偶数相乘的情况;
又:
1000=10*10*10=2*5*2*5*2*5=2*2*2*5*5*5
只有以下情况:
5*200
25*40
125*8
接下来可以得到:
a=98 D=4
a=8 D=24
a=59 D=7
当然求为负数的也可以这样做的.

Answer 16

to longqiaoman(龙桥人) 而且“如果扩大外面的循环到5000”你通过什么来保证上面的5000就是正确呢？为什么不是5001?是不是还存在5000以外的解？这些都是需要通过数学公式来保证的，嘿嘿

Answer 17

因子分解的确不好做，但是总比使用硬搜索要强当数据大时 "if((fx-x)<0.000001)" 是无法保证的

Answer 18

但是就算我使用最简单的因子分解，那也只需要计算差不多 sqrt(1000) =30 次左右吧更何况因子分解存在很好的算法

Answer 19

tiaoci(我挑刺，我快乐) :
其实扩大到1000(500*2)就够了，1000之外不可能有了，1000之外，两头至少有一头肯定有绝对值大于500的数,也就是数其他绝对值小于500的连续数必须用相反数抵消

Answer 20

谁能解释一下为什么(j-i+1)*(i+j)=1000那么I 和J之间连续的那几个数字之和就是500啊

Answer 21

哦，我说的是ivony, 消消气哦 :)to longqiaoman(龙桥人)， "其实扩大到1000(500*2)就够了" ,这个对于500这个数的确如此但是你的理由是不正确的，如果要求的数是0, 那么是不是只要搜索2*0范围的数呢？显然不对当然 按照公式  (2*a+delta) * (delta + 1) = 2 * S我们是可以知道,除零外,只需要搜索 2 * S 的数就够了,但是决不是你给出的理由

Answer 22

using System;namespace  Lzjsoft_Test.DataTest
{

class mianshi
{

public mianshi()
{
string str = "";
int sum=0;
for (int i=-500;i<=500;i++)
{
for (int j=i;j<=500;j++)
{
sum=(j-i+1)*(i+j)/2;
if (sum==500)
{
str += "第一个数是：" + Convert.ToString(i) + "最后一个数是：" + Convert.ToString(j) + "\n";
}
}
}
System.Windows.Forms.MessageBox.Show(str);
}
}
}

Answer 23

算法还可以深入点简单分析一下
f为起始数字，n为数字个数
则(f+f+n-1)*n/2=500   f=(1000/n+1-n)/2 只考虑f>0,因为f<0的结果可以由f>0的结果一一对应出来，所以n(n-1)<1000所以n<33
不管n为奇数或者偶数，1000应该可以被n整除，即n应该是1000的约数
假如n为偶数，那么n应该是4的倍数（因为500为偶数，不可能有两个奇数的乘积等于偶数
假如n为奇数那么n应该是5(最小奇数约数)的倍数，且f为偶数假如结果和不是偶数，而是奇数R，那么根据(f+f+n-1)*n/2=R，2f+n-1和n/2都应该是奇数，所以n应该是2的倍数，但不应该是4的倍数，所以n应该是2，然后是R的最小奇数公约数，这样算法还可以继续推理...有谁写进一步的算法？

Answer 24

int j;
for (int i=0; i<500;i++)
{
int tmp ;
tmp = i;
j = i;
while ( ++j<500)
{
  tmp += j;
if (tmp== 500) 
{
  for (;i<=j;i++)
System.Console.Write("{0},",i);
  System.Console.Write("\n");
}
 if (tmp >500) break;
}
}
}

Answer 25

wxwx110(无敌大馒头) 谁能解释一下为什么(j-i+1)*(i+j)=1000那么I 和J之间连续的那几个数字之和就是500啊
=================================================================================
我也不懂。谁可以解释下。

Answer 26

i+(i+1)+(i+2)+..+(i+n)的和为：(首数+末数)*数的个数/2——(i+(i+n))*n/2
正如1+2++100为(1+100)*100/2一样此处将i+n替换为j，即(i+j)*(j-i+1)/2

Answer 27

(j-i+1)*(i+j)=1000是由(i+j)(j-i+1)/2=500推出来的.等差数列的求和公式.

Answer 28

string str = "";
int sum=0;
for (int i=-250;i<=250;i++)
{
for (int j=i;j<=250;j++)
{
sum=(j-i+1)*(i+j)/2;
if (sum==500)
{
str = "第一个数是：" + Convert.ToString(i) + "最后一个数是：" + Convert.ToString(j) + "\n";
RT_Sum.AppendText(str);//RT_Sum为RichTextBox
}
}
}

Answer 29

如果delta 是偶数，则 delta +1 是奇数, 2 * a + delta 是偶数----〉怎么确定2*a + delta为偶数？delta = a - b, 则a=delta+b， delta是偶数， b未知是奇是偶， 那任何确认a是偶数？ 
  

Answer 30

1、2*a为偶数，delta为偶数，偶数相加必为偶数
2、b未知是奇是偶的情况下，delta为偶数，无法确认a是否是偶数，但是如果b为奇数，则a一定为奇数，而b为偶数，则a一定为偶数：
原因：
如果（奇数b-奇数c）>0，如果奇数b=2X+1；奇数c=2Y+1，则（奇数b-奇数c）=(2X+1)-(2Y+1)=2(X-Y)——一定为偶数
c、如果（偶数b-偶数c）>0，如果偶数b=2X；偶数c=2Y，则（偶数b-偶数c）=(2X)-(2Y)=2(X-Y)——一定为偶数

Answer 31

我写了个算法,请大家指教:
for(int i=2;i<=10000;i++)
{
int []Res=new int[i];
int Middle=0;
if(i%2==0)
{
if(500%(i/2)>0||500%i==0) continue;
}
else
{
if(500%i>0) continue;
}
Middle=(int)(500/i);
for(int j=0;j<i;j++)
{
Res[j]=Middle-(int)(i/2)-(i%2)+1+j;
}
}

Answer 32

小弟在13亿（基本上每个中国人都有份）的范围内用以下基于高斯求和公式的算法计算了一下，在13亿范围内确实只有8组（包括500-500）解，但是电脑（Ｐ4 2.8G）用了4分钟，使用这种解法的话如果是把范围确定在＋1000－－1000还好，关键是获得边界条件!#include "stdafx.h"int main(int argc, char* argv[])
{
long nNum=0;
for(unsigned long nB=0;nB<1300000000;nB++)
{
double x0=(500-(double(nB)+1)*double(nB)/2)/(double(nB)+1);
if (x0==long(x0))
{
nNum++;
printf("第%d个解答：",nNum);
printf("%d  ",long(x0));
printf("%d  ",long(x0+nB));
printf("\n\n");
}
}
printf("在%d范围内，解得情况：共有%d组解。\n",nB,nNum);
return 0;
}

Answer 33

费了好大劲，终于证得出了n>0情况下的边界。
这道题目如果用穷举一定是错的！！因为证明边界的过程中顺便就能把结果一起给证了。