一段时间在编程比赛中我遇到了一个令人费解的问题,从那以后它一直困扰着我.虽然我不记得它,但我会尽力重现它:
杰克从数字线上的0开始,向任一方向跳跃一个单位.他所做的每次连续跳跃都比之前的1个单位长,并且可以在任一方向上进行.编写一个带有数字的程序,并返回Jack为达到该数字而进行的最小跳跃次数.
如果这不是一个好问题,或者如果标题被认为具有误导性,我会提前道歉.
对于任意数量的跳跃,人们可以轻松计算出千斤顶可以行进的最大正距离.翻转正跳跃的极性总计任何特定值k将导致千斤顶结束2k计数低于其他情况.对于任何最大距离t,以及相同奇偶校验的任何非负n(即使t是偶数;奇数,如果t是奇数)小于或等于该距离,将有可能找到总数为n的跳跃组合.因此,人们不必担心树木,背包或任何其他类似的东西 - 只是一些跳跃是否足够,以及它是否会产生正确的"奇偶校验".
我想详细说明@ supercat的正确和快速的解决方案,并描述一种算法,除了计算这样一个总和的长度外,还计算最小长度和.
找到最小整数k,使得t_k:= 1 + 2 + 3 + ... + k> = | n | 和t_k具有与| n |相同的奇偶校验.然后以系统的方式将t_k的加号的符号翻转为总n.
这是详细信息.注意t_k = k(k + 1)/ 2,三角形数.设置t_k = | n | 并且求解k给出(-1 + sqrt(1 + 8 | n |))/ 2的上限.因此k等于上限或1或2加上它,这三个数字中的哪一个具有与n相同的奇偶性且最小.这里我们使用的事实是,对于任何正整数t,s,三个连续三角数的集合{t,t + s,t + s +(s + 1)}包含偶数和奇数.(只需检查t和s的所有四种奇偶校验可能性.)
要找到n的最小长度和,首先计算d:=(t_k - n)/ 2.因为t_k> = | n | 并且t_k和n具有相同的奇偶校验,d位于集合{0,1,2,...,t_k}中.现在重复减去:d = a_k(k)+ r_k,r_k = a_ {k-1}(k-1)+ r_ {k-1},...,r_2 = a_1(1)+ r_1,选择每个a_i最大值为{0,1}.通过下面的引理,r_1 = 0.所以d = sum_ {i = 1} ^ k a_i i.因此,n = t_k-2d = sum_ {i = 1} ^ ki - sum_ {i = 1} ^ k 2a_i i = sum_ {i = 1} ^ k(1 - 2a_i)i和1 - 2a_i位于{-1 ,1}.因此序列b_i:= 1 - 2a_i是路径,并且通过k的最小值,b_i是最小路径.
考虑目标数n = 12.根据算法3,k的可能性是5,6或7.对应的t_k值是15,21和28.由于28是具有与n相同奇偶性的最小值,我们看到k = 7 .所以d =(t_k - n)/ 2 = 8,我们根据算法写成1 + 7.因此,到12的最短路径是-1 + 2 + 3 + 4 + 5 + 6-7.
我说一个最短路径,因为最短路径不是一般的独特.例如,1 + 2 -3 + 4 - 5 + 6 + 7也有效.
引理:让A_k = {0,1,2,...,t_k}.然后,当且仅当它可以表示为{0,1}中的某个序列a_i的和sum_ {i = 1} ^ k a_i i时,数字位于A_k中.
证明:通过感应k.首先,0 = sum_ {i = 1} ^ 0 1,空和.现在假设结果适用于所有k - 1> = 0并假设数字d位于A_k中.重复减去:d = a_k(k)+ r_k,r_k = a_ {k-1}(k-1)+ r_ {k-1},...,在{0,1中最大选择每个a_i = 0或1并且当第一个r_j位于A_j中时停止某些j <k.然后通过归纳假设,对于{0,1}中的一些b_i,r_j = sum_ {i = 0} ^ j b_i i.然后根据需要d = r_j + sum_ {i = j + 1} ^ k a_k i.相反,对于{0,1}中的a_i,和s s = = sum_ {i = 1} ^ k a_i i满足0 <= s <= sum_ {i} ^ ki = t_k,因此s位于A_k中.
假设算术运算是恒定时间,从n计算k需要O(1)时间,因此从n计算最小路径的长度.然后花费O(k)时间来找到d的最小长度和,然后花费O(k)时间来使用该和来产生n的最小长度和.所以O(k)= O(sqrt(n))时间全部.