在1～500这500个整数中,找出连续相加等于500的数？

昨天碰到有人问起一个题目：在1～500这500个整数中,找出连续相加等于500的数?

其实这是一道很简单的面试题。为什么有人偏偏不喜欢自己解决呢？我想，最重要的是很多人不喜欢动脑动手。得罪很多人了啊。呵呵。

简要分析：int[] X={1,2,i,…………499}

条件是:i+(i+1)+ ……+(i+k)=500 (1式)

运用等差数列求和公式：(k+1)*i+(k+1)*k/2=500 (2式）

其中i和k还有一个隐藏关系i*k<500 (3式)

于是很自然得到如下解法：

private static void GetSomeInt(int maxInt)
      {
          for (int i = 1; i < (maxInt - 1); i++)
          {
              for (int k = 1; k < (maxInt / i); k++)
              {
                  if (((k + 1) * i + k * (k + 1) / 2) == maxInt )
                  {
                      /*******************输出结果集*********************/
                      string result = "xi=";
                      for (int s = 0; s < (k + 1); s++)
                      {
                          result += (i + s).ToString() + ";";
                      }
                      result = result.TrimEnd(';');
                      Console.WriteLine(result);
                      /************************************************/
                  }
              }
          }
      } 

得出结果：

xi=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
xi=59;60;61;62;63;64;65;66
xi=98;99;100;101;102

eaglet 提出，该算法性能不佳，参照他的算法，修改如下：

private static void GetSomeIntStep(int maxInt)
        {
            int num = 0;
            int fnum = 0;// Convert.ToInt32(System.Math.Sqrt(maxInt));
            int tmp = maxInt - fnum * (fnum + 1) / 2;
            while ((tmp > 0))
            {
                if (tmp % (fnum + 1) == 0)//源自((k+1) * i + k * (k + 1) / 2) == maxInt
                {
                    /*******************输出结果集*********************/
                    string result = "xi=";
                    int nn = tmp / (fnum + 1);
                    for (int s = nn; s < (nn + (fnum + 1)); s++)
                    {
                        result += (s).ToString() + ";";
                    }
                    result = result.TrimEnd(';');
                    Console.WriteLine(result);
                    /************************************************/
                    num++;
                }
                fnum++;
                tmp = maxInt - fnum * (fnum + 1) / 2;
            }
            Console.WriteLine("循环次数:{0}", fnum.ToString());
        }

另外根据条件，

(k+1)k<2*maxInt,可以得出(k+1)(k+1)<2*maxInt （4式）

可以提出连续的最多整数为32，故也可以得如下算法：

  private static void GetSomeIntThird(int maxInt)
        {
            int num = 0;
            int maxnum = Convert.ToInt32(System.Math.Sqrt(2 * maxInt));//(k+1)平方<maxInt的2倍
            for (int k = 1; k <= maxnum; k++)
            {
                int tmp = maxInt - k * (k + 1) / 2;
                if (tmp > 0 && tmp % (k+1) == 0)//源自((k+1) * x+ k * (k + 1) / 2) == maxInt
                {
                    /*******************输出结果集*********************/
                    string result = "xi=";
                    int x = tmp / (k+1);
                    for (int s = x; s < (x + k+1); s++)
                    {
                        result += (s).ToString() + ";";
                    }
                    result = result.TrimEnd(';');
                    Console.WriteLine(result);
                    /************************************************/
                }
                num++;
            }
            Console.WriteLine("循环次数:{0}", num.ToString());
        }

邀月注：本文版权由邀月和CSDN共同所有，转载请注明出处。
助人等于自助! [e-mail]