加法序列 [英] Additive Sequence

问题描述

加法序列. 3,3,6,9,15 ....被称为加法序列，其中前两个数字必须相同..3+ 3 = 6,3 + 6 = 9，依此类推. 同样，可以从加法序列中将一个数字分解为多个数字之一. 例如:12,122,436 ...按该顺序，12 + 12 = 24 .... 12 + 24 = 36. 给问题一个开始和结束的数字，在加法顺序中查找所有可能的项. 我知道可以很容易地找到一个序列.但是我不知道如何考虑更大的数字，例如122,436等.

additive sequence. 3,3,6,9,15.... is called an additive sequence where the first two numbers must be the same..3+3=6,3+6=9 and so on. Also a number can be split into one of more digits to from the additive sequence. For eg: 12,122,436... In that sequence,12+12=24....12+24=36. The question is given the starting and ending numbers,find all the possible terms in the additive sequence. I get it that one sequence can be found pretty easily.But I have no clue how to take the bigger numbers like 122,436 etc into consideration.

推荐答案

为简单起见，我将说，如果不拆分数字，则加法序列是严格的.严格的加法序列具有以下形式:n * 1，n * 1，n * 2，n * 3，n * 5，...，n * Fk，其中Fk是第k个斐波那契数.因此，对于严格的序列，您需要将最后一个元素除以第一个元素，并检查结果是否为斐波那契数.如果是，则可以容易地重建序列.如果否，则不存在这样的顺序.

For the sake of simplicity I'll say that an additive sequence is strict if no numbers are split. Strict additive sequences have the following form: n*1, n*1, n*2, n*3, n*5, ..., n*Fk, where Fk is the k-th Fibonacci number. Hence, for strict sequences you need to divide the last element by the first one and check whether the result is a Fibonacci number. If yes, the sequence can be easily reconstructed. If no, no such sequence exists.

让我们现在考虑非严格加法序列，并让A1 ... An为第一个数字.首先，我们尝试找到如上所述的严格加法顺序.如果此尝试失败并且存在加法序列，则A1 ... An或最后一个数字应代表更多，然后是一个实际"数字.

Let us now consider non-strict additive sequences and let A1...An be the first number. First of all, we try to find a strict additive sequence as explained above. If this attempt fails and an additive sequence exists, either A1...An or the last number should represent MORE then one "actual" number.

如果A1 ... An代表多个实际"数字，则存在k< = n，使得A_1 + p = A_k + p对于所有0< = p< = min(nk，k )(因为第二个数字应等于第一个数字).如果找不到这样的k，则没有加法序列.如果可以找到这样的k，则尝试使用所有形式为A1 ... A_k-1 * F(m)的数字，其中F(m)是第m个斐波那契数，只要此乘积小于或等于最后一个乘积即可.编号，并尝试拟合顺序.如果有多个这样的k(111)，请尝试所有可能性.

If A1...An represents more than one "actual" number, then there exists k <= n such that A_1+p = A_k+p for all 0 <= p <= min(n-k,k) (since the second number should be equal to the first one). If no such k can be found, there is no additive sequence. If such k can be found, try all numbers of the form A1...A_k-1 * F(m), where F(m) is the m'th Fibonacci number as long as this product is less or equal than the last number, and try to fit the sequence. If there is more than one such k (111) try all possibilities.

如果最后一个数字表示多个数字，而A1 ... An不表示多个数字，则按与上述相同的方式尝试A1 ... A_n * F(m)形式的所有数字.

If the last number represents multiple numbers and A1...An does not, try all numbers of the form A1...A_n * F(m) in the same way as above.

这篇关于加法序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！