构造一个整数数组以实现特定的序列

本文关键字：实现数组整数一个 | 更新日期: 2023-09-27 18:32:46

构造以 A 结尾的尽可能短的整数序列，使用以下规则：

序列的第一个元素是 1，每个连续的元素是前面任意两个元素的总和（添加一个元素本身也是允许的），每个元素都大于上述所有要素;也就是说，序列正在增加。

例如，对于 A = 42，可能的解为 [1， 2， 3， 6， 12， 24， 30, 42].另一种可能的解决方案是 [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;
    }

构造一个整数数组以实现特定的序列

我知道

这背后会有一个数学证明，但我的猜测是将数字除以 2，如果它平均除以，则重复该过程。如果有余数，则为 1。所以你会有整数商和商加一。由于保证一个在集合中，因此已经处理了 2 个数字中较大的一个。因此，只需对较小的重复该过程即可。这个问题当然意味着一个相对微不足道的递归解决方案，所以我将把它留给海报来实现。

我想我明白了：

public Set<Integer> shortList(int n){
    Set<Integer> result = new HashSet<Integer>();
    Stack<Integer> stack = new Stack<Integer>();
    result.add(n);
    int num=n, den=0;
    while(num>1){
        while(num > den){
            num--; den++;
            if(num%den==0)
                stack.push(num);
        }//num>den
        if(!stack.isEmpty()){
            num = stack.pop();
            result.add(num);
            stack.clear();
        }else{
            result.add(num);
            result.add(den);
        }
        den=0;
    }
    return result;
}//

结果（未排序）

for 42: [1, 2, 3, 21, 6, 7, 42, 14]
for 15: [1, 2, 4, 5, 10, 15]
for 310: [1, 2, 155, 4, 5, 310, 10, 124, 62, 31, 15, 30]

这是我

在C++中的解决方案（可以简单地更改为 C#）：

void printSequenceTo(unsigned n)
{
    if (n == 1) { printf("1"); return; }
    if (n & 1) {
        int factor = 3;
        do {
            if (n % factor == 0) {
                printSequenceTo(n / factor * (factor-1));
                factor = 0;
                break;
            }
            factor += 2;
        } while (factor * factor <= n);
        if (factor) printSequenceTo(n-1);
    }
    else
        printSequenceTo(n/2);
    printf(",%u", n);
}

演示：http://ideone.com/8lXxc

当然，可以使用筛子进行分解来加速。

请注意，这是对已接受答案的显着改进，但仍然不是最佳的。

这是我

的尝试。它可能会被优化，但它显示了我的想法：

private static IEnumerable<int> OptimalSequence(int lastElement)
{
    var result = new List<int>();
    int currentElement = 1;
    do
    {
        result.Add(currentElement);
        currentElement = currentElement * 2;
    } while (currentElement <= lastElement);
    var realLastElement = result.Last();
    if (lastElement != realLastElement)
    {
        result.Add(lastElement);                
        FixCollection(result, lastElement - realLastElement);
    }
    return result;
}
private static void FixCollection(List<int> result, int difference)
{
    for (int i = 0; i < result.Count; i++)
    {
        if (result[i] == difference) break;
        if (result[i] > difference)
        {
            result.Insert(i, difference);
            FixCollection(result, difference - result[i-1]);
            break;
        }
    }
}

编辑我无法正式证明这一点，但我的答案和克里斯·盖斯勒的答案给出了相同大小的序列（至少我检查了 1 到 10000 之间的数字），因为两种算法都补偿奇数。一些例子：

Number 1535
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1024,1535
Number 2047
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047
Number 3071
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2048,3071
Number 4095
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047,2048,4095
Number 6143
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047,2048,4096,6143
Number 8191
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047,2048,4095,4096,8191
==============
Number 1535
1,2,4,5,10,11,22,23,46,47,94,95,190,191,382,383,766,767,1534,1535
Number 2047
1,2,3,6,7,14,15,30,31,62,63,126,127,254,255,510,511,1022,1023,2046,2047
Number 3071
1,2,4,5,10,11,22,23,46,47,94,95,190,191,382,383,766,767,1534,1535,3070,3071
Number 4095
1,2,3,6,7,14,15,30,31,62,63,126,127,254,255,510,511,1022,1023,2046,2047,4094,4095
Number 6143
1,2,4,5,10,11,22,23,46,47,94,95,190,191,382,383,766,767,1534,1535,3070,3071,6142,6143
Number 8191
1,2,3,6,7,14,15,30,31,62,63,126,127,254,255,510,511,1022,1023,2046,2047,4094,4095,8190,8191

public static int[] hit(int n)
    {
        List<int> nums = new List<int>();
        nums.Add(n);
        int x = 0;
        int Right = 0;
        int Left = 0;
        do
        {
            //even num
            if (n % 2 == 0)
            {
                x = n / 2;
                //result of division is also even 20/2 = 10 
                if (x % 2 == 0 || n>10 )
                {
                    nums.Add(x);
                    n = x;
                }
                else
                {
                    nums.Add(x + 1);
                    nums.Add(x - 1);
                    n = x - 1;
                }
            }
                //numbers that can only be divided by 3
            else if (n % 3 == 0)
            {
                x = n / 3;//46/3 =155
                 Right = x * 2;//155*2 = 310
                 Left = x;//155
                nums.Add(Right);
                nums.Add(Left);
                n = x;
            }
                //numbers that can only be divided by 5
            else
            {
                x = n / 2;
                Right = x + 1;
                Left = x;
                nums.Add(Right);
                nums.Add(Left);
                n = Left;
            }
        } while (n > 2);
        nums.Add(1);
        nums.Reverse();
        int[] arr = nums.ToArray();

        return arr;
    }