c# - 构造一个整数数组来实现特定的序列

Question

construct the shortest possible sequence of integers ending with A, using the following rules:

the first element of the sequence is 1, each of the successive elements is the sum of any two preceding elements (adding a single element to itself is also permissible), each element is larger than all the preceding elements; that is, the sequence is increasing.

For example, for A = 42, a possible solutions is [1, 2, 3, 6, 12, 24, 30, 42]. Another possible solution is [1, 2, 4, 5, 8, 16, 21, 42].

我编写了以下内容，但在输入 456 时失败，通过返回 [1,2,4,8,16,32,64,128,200,256,456] ，序列中没有可以加在一起得到 200 的数字。

如何修复以下代码？我做错了什么？

  public static int[] hit(int n)
    {
        List<int> nums = new List<int>();

        int x = 1;

        while (x < n)
        {
            nums.Add(x);
            x = x * 2;

            if (x > n)
            {

                    nums.Add(n - (x / 2));

                nums.Add(n);
            }
        }

        nums.Sort();
        int[] arr =  nums.ToArray();
        return arr;
    }

Answer 1

我知道这背后会有一个数学证明，但我的猜测是将数字除以 2，如果它相等，则重复该过程。如果有余数，则为 1。因此您将得到整数商和商加一。由于保证其中有一个数字存在，因此 2 个数字中较大的一个已被处理。因此，只需对较小的重复该过程即可。这个问题肯定意味着一个相对简单的递归解决方案，所以我将把它留给发布者来实现。