千图素材网站,python做网页界面,个人做网站的必要性,自己做的网站收费这是多年以前做的一道题目#xff0c;原题来自软件报或者电脑报 #xff0c;我记不清了。解决这个题目有一个关键的步骤#xff0c;就是要求一个整数在一个整数三角阵中的坐标。这篇blog就是讨论这个求坐标的问题#xff0c;不是讨论那个报纸上的题目。现在将题目描述如下原题来自软件报或者电脑报 我记不清了。解决这个题目有一个关键的步骤就是要求一个整数在一个整数三角阵中的坐标。这篇blog就是讨论这个求坐标的问题不是讨论那个报纸上的题目。现在将题目描述如下 三角阵如下所示 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... ... ... n n1 n2 ... ... nk 三角阵中的每一个数字都有一个坐标对应其中行是X轴从右上往左下倾斜的边是Y轴。比如2的坐标是219的坐标是43应该很容易理解吧。下面还是从最简单的解法开始讨论。先看X轴坐标的求法。我们需要逐步的减去整数的个数第一次减去第一行的整数个数第二次减去第2行的整数的个数如此重复知道给定的整数不够减而成为负数为止。这时将循环中当前使用的行数就是X轴的坐标而不够减的数值就是Y轴的坐标。现在的问题就是怎么个减法效率才能尽可能的高因为给定的整数可能非常的大这里考虑理想情况不要考虑具体一个语言的对整数溢出的限制否则讨论算法的效率就没有意义了。 第一个方法是写一个第一项为1公差为1的等差数列的求和函数参数为n返回值是前n项的和。然后开始从1循环将返回值和给定整数比较从而求得坐标。这个当然是最差的做法效率几乎是最低的。如果谁在我的项目中这样写代码那么这个月的工资会打折扣的。至少我们给出的解法应该是这样的不能用一个求和函数来做而是应该利用循环从前n项的和递推出前n1项的和循环中应该有类似如下的递推求和代码 nCount nCount 1; nSum nSum nCount; 由于整个计算过程使用加减完成并且不存在回溯的情况虽然整数有可能会很大但是这个解法的效率应该是不会太差的这个非常显然。因为大O时间复杂度中最高的指数为1效率是很高的了。所以这算是一个解法如此写代码的话至少满足使用要求不扣工资了。 但是这个解法有一个问题就是太过简单。当然在很多时候简单是一个非常好的特点但是在这里不行简单的让人觉得简陋了。思考片刻后我得到了又一个更好的解法。那就是在循环递推前n项的和的时候循环递增的步长不设置为固定的1而是可变长的比如2的整数倍也就是每次循环递增一倍。这样通过若干次循环后我们可以发现给定的整数会落在前一次循环假设此时nCount等于n所求和和本次循环假设此时nCount等于2n所求和的范围之内。即便是对于一个很大的整数由于循环的步长是2的几何数量级的增长所以可以很快的找到这个范围。那么找到了这个范围之后又如何呢我们可以在脑海中假设一个数组这个数组是这个等差数列的前n项和的数组。第一个元素是前一项的和第二个元素是前两项的和如此第n个元素就是前n项的和。那么我们知道了给定整数所落在的范围于是我们就可以使用折半查找的办法来获得X轴坐标。但是需要注意的是这个前n项和的数组不是写死的需要在使用的时候动态计算出第n个元素的值。显然从算法的角度看这个解法的效率远比前面那个高。我一度为这个解法得意但是在得意的同时又感到一点遗憾就是感觉自己不是用算法解决的效率问题而是用编程技巧解决的问题。我隐隐的感觉似乎还有一个完美的解隐藏着。 于是继续思考没多久我终于找到了这个完美的解找到了一个时间复杂度与给定整数大小几乎没有关系的算法。等差数列的求和公式是这样的S n(n1)/2。以前的思路都是从n求得S然后做减法再接着判断处理在一个灵感的帮助下我发现可以把给定的整数看做S通过求和公式直接求得n。这时n的整数部分就是X坐标然后减去X坐标值所表示的前若干项的和就可以得到Y轴的坐标。 从结果看这是最好的算法它的最优几乎可以被证明。那么如此利用了求和公式而得到的解法能不能算是一个算法呢当时我认为是但是由于所用知识过于简单我不能肯定。直到2年后我自学了一本书名字叫组合数学其中有一章讲到了母函数。这时我才明白我在不自觉地情况下使用了母函数的思路解决了问题。只是这个求和公式比较简单不需要求解特征方程等等相关的东西所以我才作了出来。至此我的疑问得到了解答这是一个堂堂正正的算法。
