开发者

What would be a good general algorithm for approaching integer sequence problems?

开发者 https://www.devze.com 2023-01-02 08:31 出处:网络
Say the input will always be the same number N of numbers (e.g., 5) and assume the integers actually have a mathematical relation (no lengths of the numbers \'one\', \'two\', days in the nth month, et

Say the input will always be the same number N of numbers (e.g., 5) and assume the integers actually have a mathematical relation (no lengths of the numbers 'one', 'two', days in the nth month, etc.). The output would be either the next integer and the rule discovered or a message that no rule could be detected. I was thinking to have in one-two-three order, a module that tries to find arithmetic sequence rules by doing sums and/or differences between numbers adjacent, one away, two away, etc. looking for patterns, then having a module focused on geometric seq开发者_如何学Cuences by multiplying and/or dividing in the same way, and then, if there is a general approach, a module for detecting recursive sequences.

Thanks!


The On-Line Encyclopedia of Integer Sequences solves precisely this problem :-)


Given any sequence of numbers, we can come up with a formula which 'fits'!

Given a1, a2, ..., an

All you need to do is find an n-1 degree polynomial (using Polynomial interpolation) so that

P(i) = ai

and that's it, you have a formula. Polynomial interpolation can be as easy as solving a matrix equation Ax = b (with A being a Vandermonde matrix).

Check out: http://en.wikipedia.org/wiki/Polynomial_interpolation

That is one of the reasons I find these 'guess the next number' problems a bit silly (read: pathetic IQ tests). Not everyone thinks the same way.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号