求和为指定数字的连续正整数数列

寻找更高效的解决方法
服务器君一共花费了376.078 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

比如 sn = 100 时,总和为100 的连续正整数数列有

100
18 19 20 21 22
9 10 11 12 13 14 15 16

对于这种算法的设计,我们最容易想到的就是从 1 到 sn 循环遍历所有的数,对于每个数再循环计算是否以这个数为起点总和正好是sn。这种算法的时间复杂度大概是O(n*log2n), 也就是说如果这样计算,当 sn = 100万时,大概需要循环 2000万次左右。 这样做效率自然是比较低的。那么我们有没有比上述方法更高效的方法呢?答案是肯定的。

首先我们看等差数列求和的公式:Sn=n(a1+an)/2=na1+n(n-1)/2

从这个公式我们不难看出当 Sn 和 n 固定时求a1 是一个线性函数:a1 = (Sn – n(n-1)/2) / n

有了这个函数,优化这个算法就很简单了,我们只要把 n 从 1 开始遍历,一直遍历到 (Sn – n(n-1)/2) < n 为止,就可以找到所有的符合条件的连续数列了,这个算法的算法复杂度为 2N 的平方根,也就是说当 Sn = 100 万时,只需要循环1414次就可以得到所有的数列。

题目:在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

这个算法 sn = 100 万时,循环次数是 12970034 次,比之前说的算法效率上要低将近1万倍。

下面给出差点的算法代码

       static void ListSequence(int sn)
        {
            //忽略 sn 不是正整数的情况
            if (sn <= 0)
            {
                return;
            }
 
            int n = 1; //n 从1 开始遍历
 
            int m = sn - n * (n - 1) / 2; //m 为 Sn – n(n-1)/2
 
            while (m >= n) //当m < n 时即 Sn – n(n-1)/2 < n 时退出循环
            {
                if (m % n == 0) //如果m 可以被 n 整除,则存在连续n个正整数序列总和为sn。
                {
                    int a1 = m / n; //求a1
 
                    //打印符合条件的连续数列
                    for (int i = a1; i < a1 + n; i++)
                    {
                        Console.Write(string.Format("{0} ", i));
                    }
                    Console.WriteLine();
                }
 
                n++; //n 加1
                m = sn - n * (n - 1) / 2; //下一个 m
            }
 
            Console.WriteLine("循环次数:{0}", n);
        }

本文地址:http://www.nowamagic.net/librarys/veda/detail/1042,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1042

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《设计模式:可复用面向对象软件的基础》 Erich Gamma (作者), Richard Helm (作者), Ralph Johnson (作者), John Vlissides (作者), 李英军 (译者), 等 (译者)

《设计模式:可复用面向对象软件的基础》是引导读者走出软件设计迷宫的指路明灯,凝聚了软件开发界几十年设计经验的结晶。四位顶尖的面向对象领域专家精心选取了最具价值的设计实践,加以分类整理和命名,并用简洁而易于重用的形式表达出来。本书已经成为面向对象技术人员的圣经和词典,书中定义的23个模式逐渐成为开发界技术交流所必备的基础知识和语汇。

更多计算机宝库...