在1~500这500个整数中,找出连续相加等于500的数? £神魔★判官ぃ 2022-05-15 05:08 242阅读 0赞 昨天碰到有人问起一个题目:在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共同所有,转载请注明出处。 助人等于自助! 3w@live.cn [eaglet]: http://www.cnblogs.com/eaglet/archive/2011/03/05/1971391.html
还没有评论,来说两句吧...