3

2011年までの合計が0を超える10個の整数を見つけますが、それらの逆数の合計は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

1 つの問題インスタンスに対して計算の複雑さを定義することはできないことに注意してください。答えがわかると、計算の複雑さは O(1)、つまり一定時間になるからです。計算の複雑さは、問題の無限ファミリーに対してのみ定義できます。

この種の問題を解決する 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)]) を常に確認します
    • 検索中にこれら 2 つの制約が満たされない場合、それ以上の解決策はあり得ず、アルゴリズムはすぐにバックトラックする必要があります。制約は、数値が昇順で割り当てられるという事実に基づいていることに注意してください。つまり、すべての場合でx i <= x i+1です。

注: すべての x 1 , ..., x 10が特定の数値 (たとえば 960) を均等に割ると仮定することで、検索を高速化し、検索スペースを制限して計算を高速化できます。つまり、960 となる x i のみを考慮します。 x で割ったiは整数です。これにより、1/x 1 + ... が 1 に等しいことを確認する代わりに、960/x 1 + ... が 960 に等しいことを確認できるため、小数部分の計算がはるかに簡単になります。すべての除算は偶数であり、整数を返すため、浮動小数点演算または有理演算を使用する必要はまったくありませんが、すべて整数のみで機能します。もちろん、固定係数が小さいほど、見つけられる解は少なくなりますが、これにより検索も高速になります。

于 2012-05-07T06:18:53.887 に答える
1

誰かが投稿したBillGasarchの論文に基づく動的計画法ソリューション（C＃）。ただし、これは必ずしも最適な（使用される最小数の）ソリューションを見つけるとは限りません。十分に高くなることが許された場合にのみ解決策を見つけることが保証されますが、それは目的のNである必要はありません。基本的に、それは「偶然に」機能するように感じます（10、2011）。

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)合計すると 2011 年になる 10個の数字のセットがあります10^26。したがって、ブルート フォース アプローチが機能するためには、検索ツリーを大幅にトリミングする必要があります。

幸いなことに、それを行うにはいくつかの方法があります。

最初の明らかな方法は、番号が順序付けられていることを要求することです。これにより、オプションの数が約 1 分の 1 に減ります10^7。

2 つ目は、現在の部分的な解決策が完全な解決策につながらないかどうかを早期に検出できることです。値は順序付けられているため、セット内の残りの数値は少なくとも現在の数値と同じ大きさです。数値が大きくなるにつれて数値の合計が増加し、逆数の合計が減少することに注意してください。

行き止まりになっていることを確認できる確実な方法が 2 つあります。

  1. 残りのすべての数が現在の数と同じになるようにすると、現在の場所から可能な最小の合計が得られます。この最小の合計が大きすぎると、それ以下になることはありません。

  2. 残りのすべての数が現在の数と同じになるようにすると、逆数の可能な最大の合計が得られます。この最大合計が 1 未満の場合、1 にはなりません。

これら 2 つの条件により、次の の上限が設定されxiます。

3 番目に、逆数の部分和が 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 に答える
1

このシリーズの次のブログhttp://blog.computationalcomplexity.org/2011/12/solution-to-reciprocals-problem.htmlの内容の 1 つは、この問題に関する論文であり、提案されたダイナミクスであることに注意してください。回答数をカウントするためのプログラミング アプローチ。これは動的プログラミングのアプローチであるため、それを動的プログラムに変換してそれらの答えを見つけることができるはずです。

于 2012-05-07T04:37:09.850 に答える
0

ブルート フォース アルゴリズムを使用してすべての組み合わせを繰り返すと、最終的に答えが得られます。しかし、10*2011*2011 ほど大きくはないと思います。x1 は簡単に任意に仮定できるので、

力ずくのアプローチで簡単に答えが得られると思います。ただし、インストラクターは数学的アプローチを探していると思います。「1」には、方程式を操作して答えを出す方法を見つけることに関して、何らかの意味があるに違いないと考えています。「2011」は任意のようです。

于 2012-05-07T02:29:51.860 に答える