3

找到十个整数>0,总和为 2011,但它们的倒数总和为 1

例如

x1+x2+..+x10 = 2011

1/x1+1/x2+..+1/x10 = 1

我在这里发现了这个问题http://blog.computationalcomplexity.org/2011/12/is-this-problem-too-hard-for-hs-math.html

我想知道计算复杂度是多少,什么类型的算法可以解决它。

EDIT2:我编写了以下足够快的蛮力代码。我没有找到任何解决方案,所以我需要稍微调整一下我的假设。我现在有信心找到解决办法。

 from fractions import Fraction

pairs = [(i,j) for i in range(2,30) for j in range(2,30)]

x1x2 = set((i+j, Fraction(1,i)+Fraction(1,j)) for i,j in pairs)

print('x1x2',len(x1x2))

x1x2x3x4 = set((s1+s2,f1+f2) for s1,f1 in x1x2 for s2,f2 in x1x2 if f1+f2<1)

print('x1x2x3x4',len(x1x2x3x4))

count = 0
for s,f in x1x2x3x4:
    count+=1
    if count%1000==0:
        print('count',count)
    s2 = 2011 - s
    f2 = 1 - f
    for s3,f3 in x1x2:
        s4 = s2-s3
        if s4>0:
            f4 = f2-f3
            if f4>0:
                if (s4,f4) in x1x2x3x4:
                    print('s3f3',s3,f3)
                    print('sf',s,f)
4

5 回答 5

2

请注意,您不能为单个问题实例定义计算复杂度,因为一旦您知道答案,计算复杂度就是 O(1),即常数时间。计算复杂度只能针对无限的问题族来定义。

解决此类问题的一种方法是使用回溯搜索。您的算法花费了太多时间来搜索 10 维空间中不能包含解的部分。一个有效的回溯算法将

  • 按 x 1 , x 2 , ..., x 10的顺序分配变量
  • 保持约束 x 1 <= x 2 <= ... <= x 10
  • 在搜索期间,总是在分配了编号 xi 时
    • 让 S = x 1 + ... + x i
    • 让 R = 1/x 1 + ... + 1/x i
    • 始终检查 S <= 2011 - (10 - i) * x i
    • 始终检查 R <= 1 - (1 / [(2011 - S) / (10 - i)])
    • 如果在搜索过程中没有满足这两个约束条件,则不再有解决方案,算法应立即回溯。请注意,约束是基于数字按升序分配的事实,即在所有情况下x i <= x i+1

注意:您可以加快搜索速度,限制搜索空间并加快计算速度,假设所有 x 1,...,x 10均分给定数字,例如 960。也就是说,您只考虑 x i即 960除以 x i是一个整数。这使得计算小数部分变得更加容易,因为您可以检查 960/x 1 + ... 是否等于 960 ,而不是检查 1/x 1 + ... 是否等于 960。因为所有除法都是偶数并返回整数,所以根本不需要使用浮点或有理算术,但一切都只适用于整数。当然,固定模数越小,你能找到的解就越少,但这也使得搜索速度更快。

于 2012-05-07T06:18:53.887 回答
1

我注意到该系列的下一篇博客http://blog.computationalcomplexity.org/2011/12/solution-to-reciprocals-problem.html中的一件事是关于该问题的论文,以及建议的动态计算答案数量的编程方法。由于它是一种动态编程方法,因此您应该能够将其转换为动态程序以找到这些答案。

于 2012-05-07T04:37:09.850 回答
1

基于某人发布的 Bill Gasarch 论文的动态编程解决方案 (C#)。但这并不一定能找到最佳(使用的最少数字)解决方案。只有在允许足够高的情况下才能保证找到解决方案,但它不必与所需的 N 一致。基本上,我觉得它“意外地”适用于(2011 年 10 月)。

2011 年的一些示例解决方案:

  • 10 个数字:2、4、5、80、80、80、160、320、640、640
  • 11 个数字:3、6、4、12、12、24、30、480、480、480、480
  • 13 个数字:2、4、5、200、200、200、200、200、200、200、200、200、200
  • 15 个数字:3、6、6、12、16、16、32、32、32、64、256、256、256、512、512

任何人都知道如何修复它以使其正常工作?

using System;
using System.Collections.Generic;

namespace Recip
{
    class Program
    {
        static void Main(string[] args)
        {
            int year = 2011;
            int numbers = 20;

            int[,,] c = new int[year+1, numbers+1, numbers];

            List<int> queue = new List<int>();

            // need some initial guesses to expand on - use squares because 1/y * y = 1
            int num = 1;
            do
            {
                for (int i = 0; i < num; i++)
                    c[num * num, num, i] = num;
                queue.Add(num * num);
                num++;
            } while (num <= numbers && num * num <= year);

            // expand
            while (queue.Count > 0)
            {
                int x0 = queue[0];
                queue.RemoveAt(0);
                for (int i = 0; i <= numbers; i++)
                {
                    if (c[x0, i, 0] > 0)
                    {
                        int[] coefs ={ 20, 4, 2, 2, 3, 3};
                        int[] cons = { 11, 6, 8, 9, 6, 8};
                        int[] cool = {  3, 2, 2, 2, 2, 2};
                        int[] k1   = {  2, 2, 4, 3, 3, 2};
                        int[] k2 =   {  4, 4, 4, 6, 3, 6};
                        int[] k3 =   {  5, 0, 0, 0, 0, 0};
                        int[] mul =  { 20, 4, 2, 2, 3, 3};

                        for (int k = 0; k < 6; k++)
                        {
                            int x1 = x0 * coefs[k] + cons[k];
                            int c1 = i + cool[k];
                            if (x1 <= year && c1 <= numbers && c[x1, c1, 0] == 0)
                            {
                                queue.Add(x1);
                                c[x1, c1, 0] = k1[k];
                                c[x1, c1, 1] = k2[k];
                                int index = 2;
                                if (k == 0)
                                {
                                    c[x1, c1, index] = k3[k];
                                    index++;
                                }
                                int diff = index;
                                while (c[x0, i, index - diff] > 0)
                                {
                                    c[x1, c1, index] = c[x0, i, index - diff] * mul[k];
                                    index++;
                                }
                            }
                        }
                    }
                }
            }

            for (int n = 1; n < numbers; n++)
            {
                if (c[year, n, 0] == 0) continue;
                int ind = 0;
                while (ind < n && c[year, n, ind] > 0)
                {
                    Console.Write(c[year, n, ind] + ", ");
                    ind++;
                }
                Console.WriteLine();
            }
            Console.ReadLine();
        }
    }
}
于 2012-05-07T13:10:24.373 回答
1

Choose(2011,10)或大约10^2610 个数字加起来等于 2011。因此,为了使蛮力方法起作用,必须显着修剪搜索树。

幸运的是,有几种方法可以做到这一点。

第一个明显的方法是要求数字是有序的。这将选项的数量减少了大约10^7.

第二个是我们可以及早发现我们当前的部分解决方案是否永远无法得出完整的解决方案。由于我们的值是有序的,因此集合中的剩余数字至少与当前数字一样大。请注意,数字之和随着数字变大而增加,而倒数之和则减少。

有两种确定的方法可以告诉我们我们处于死胡同:

  1. 当我们将所有剩余数字与当前数字相同时,我们会从我们所在的位置得到最小的总数。如果这个最小的数目太大,我们永远不会得到更少。

  2. 当我们取所有剩余数字与当前数字相同时,我们得到最大可能的倒数和。如果这个最大的和小于 1,我们永远不会达到 1。

这两个条件设置了 next 的上限xi

第三,如果我们的部分倒数和大于或等于 1,我们可以停止查看。

将所有这些放在一起,这是 C# 中的一个解决方案:

static int[] x = new int[10];
static void Search(int depth, int xi, int sum, double rsum) {
    if (depth == 9) {
        // We know exactly what the last number should be
        // to make the sum 2011:
        xi = 2011 - sum;
        // Now check if the sum of reciprocals adds up as well
        if (Math.Abs(rsum + 1.0 / xi - 1.0) < 1e-12) {
            // We have a winner!
            x[depth] = xi;
            var s = string.Join(" ", Array.ConvertAll(x, n => n.ToString()));
            Console.WriteLine(s);
        }
    } else {
        int lastxi = xi;
        // There are 2 ways xi can be too large:
        xi = Math.Min(
            // 1. If adding it (10 - depth) times to the sum
            // is greater than our total:
            (2011 - sum) / (10 - depth),
            // 2. If adding (10 - depth) times its reciprocal
            // is less than 1.
            (int)((10 - depth) * remainder));
        // We iterate towards smaller xi so we can stop 
        // when the reciprocal sum is too large:
        while (xi >= lastxi) {
            double newRSum = rsum + 1.0 / xi;
            if (newRSum >= 1.0)
                break;
            x[depth] = xi;
            Search(depth + 1, xi, sum + xi, newRSum);
            xi--;
        }
    }
}
Search(0, 1, 0, 0)
于 2012-05-07T15:30:43.383 回答
0

如果您使用蛮力算法遍历所有组合,您最终会得到答案。但我认为它没有 10*2011*2011 这么大。因为你可以很容易地任意假设 x1

我认为蛮力方法很容易得到答案。但是,我想教练正在寻找一种数学方法。我认为“1”对于寻找如何操纵方程式来获得答案必须具有一定的意义。“2011”似乎是任意的。

于 2012-05-07T02:29:51.860 回答