31

タクシー番号は、整数の 2 つの立方体の合計として 2 つの異なる方法で表すことができる整数ですa^3+b^3 = c^3+d^3。a、b、c、d が N より小さいすべてのタクシー番号を見つけるアルゴリズムを設計します。

空間と時間の両方の計算量を N で表してください。空間に合わせて計算できo(N^2.logN)ますO(N^2)。

これまでに見つけた最高のアルゴリズム:

すべてのペアを形成する:N^2
合計を並べ替える: N^2 logN
N 未満の重複を見つける

しかし、これにはN^2スペースが必要です。もっとうまくやれるでしょうか？

4

9 に答える 9

27

しかし、これには N^2 のスペースが必要です。もっとうまくやれるでしょうか？

プライオリティ キューに基づくO(N) スペース ソリューションが存在します。時間計算量はO(N^2 logN)です。アルゴリズムのアイデアをスケッチするために、M[i][j] = i^3 + j^3 となる行列 M を次に示します (もちろん、行列はメモリ内に作成されません)。

0    1    8    27    64    125
1    2    9    28    65    126
8    9    16   35    72    133
27   28   35   54    91    152
64   65   72   91    128   189
125  126  133  152   189   250

すべての行とすべての行が昇順で並べ替えられていることを確認します。PQ をプライオリティ キューとします。まず、最大の要素を優先キューに入れます。次に、PQ が空でない限り、以下を実行します。
  1. PQ から最大の要素を取り出す
  2. PQ にその行の要素がない場合は、上に隣接する要素を追加します
  3. PQ にその列の要素がなく、行列の対角線の下にない場合 (冗長な要素を避けるため)、左側に隣接する要素を追加します。

ご了承ください

  1. アルゴリズムを実装するためにメモリ内に行列を作成する必要はありません
  2. 要素は、行列の最大の要素から最小の要素まで (行列の冗長な半分の要素を避けて) 降順で PQ からポップされます。

PQ が同じ値を 2 回発行するたびに、タクシー番号が見つかりました。

例として、C++ での実装を次に示します。時間の計算量は O(N^2 logN)で、空間の計算量は O(N)です。

#include <iostream>
#include <cassert>
#include <queue>

using namespace std;

typedef unsigned int value_type;

struct Square
{
    value_type i;
    value_type j;
    value_type sum_of_cubes;
    Square(value_type i, value_type j) : i(i), j(j), sum_of_cubes(i*i*i+j*j*j) {}
    friend class SquareCompare;
    bool taxicab(const Square& sq) const
    {
        return sum_of_cubes == sq.sum_of_cubes && i != sq.i && i != sq.j;
    }
    friend ostream& operator<<(ostream& os, const Square& sq);
};

class SquareCompare
{
public:
    bool operator()(const Square& a, const Square& b)
    {
    return a.sum_of_cubes < b.sum_of_cubes;
    }
};

ostream& operator<<(ostream& os, const Square& sq)
{
    return os << sq.i << "^3 + " << sq.j << "^3 = " << sq.sum_of_cubes;
}

int main()
{
    const value_type N=2001;
    value_type count = 0;
    bool in_i [N];
    bool in_j [N];

    for (value_type i=0; i<N; i++) {
    in_i[i] = false;
    in_j[i] = false;
    }

    priority_queue<Square, vector<Square>, SquareCompare> p_queue;

    p_queue.push(Square(N-1, N-1));
    in_i[N-1] = true;
    in_j[N-1] = true;

    while(!p_queue.empty()) {
    Square sq = p_queue.top();

    p_queue.pop();
    in_i[sq.i] = false;
    in_j[sq.j] = false;

    // cout << "pop " << sq.i << " " << sq.j << endl;

    if (sq.i > 0 && !in_i[sq.i - 1] && sq.i-1 >= sq.j) {
        p_queue.push(Square(sq.i-1, sq.j));
        in_i[sq.i-1] = true;
        in_j[sq.j] = true;
        // cout << "push " << sq.i-1 << " " << sq.j << endl;
    }
    if (sq.j > 0 && !in_j[sq.j-1] && sq.i >= sq.j - 1) {
        p_queue.push(Square(sq.i, sq.j-1));
        in_i[sq.i] = true;
        in_j[sq.j - 1] = true;
        // cout << "push " << sq.i << " " << sq.j-1 << endl;
    }

    if (sq.taxicab(p_queue.top())) {
        /* taxicab number */
        cout << sq << " " << p_queue.top() << endl;
        count++;
    }
    }
    cout << endl;

    cout << "there are " << count << " taxicab numbers with a, b, c, d < " << N << endl;

    return 0;
}
于 2014-05-14T15:03:14.740 に答える
10

私はここで解決策/コードを見つけました：時間の複雑さO（N ^ 2 logN）、空間の複雑さO（N） 解決策は、優先キューの助けによって実装されます。

逆の考え方は、コードを見て簡単に行うことができます。次の最小値と比較した後に最小合計が配列から削除され、新しい合計 - (i^3 + (j+1) ^3)。

直感的な証明は次のとおりです。

最初に、最小優先度キューに (1,1),(2,2),(3,3),...,(N,N) を追加しました。

a^+b^3=c^3+d^3 で、(a,b) が次に優先キューから取り出される最小値であるとします。このタクシー番号を検出できるようにするには、(c,d) も (a,b) の後に取り出される優先キューにある必要があります。

注: (a,b) を抽出した後に (a,b+1) を追加するため、(a,b) を抽出しても (c,d) が優先キューに追加されることはありません。プライオリティ キューにすでに存在している必要があります。

ここで、(c,d) がまだ優先キューに入っていないため、優先キューにないと仮定しましょう。代わりに、k>0 のプライオリティ キューに (c,d-k) がいくつかあります。

(a,b)を取り出しているので a^3+b^3≤c^3+(d−k)^3

ただし、a^3+b^3=c^3+d^3

したがって、

c^3+d^3≤c^3+(d−k)^3 d≤d−k k≤0

k > 0 なので、これは不可能です。したがって、私たちの仮定は決して実現することはできません。したがって、a^3+b^3=c^3+d の場合、最小 PQ から削除されるすべての (a,b) について、(c,d) は既に最小 PQ に含まれています (または削除されたばかりです)。 ^3

于 2014-07-23T21:12:05.200 に答える
8

アルゴリズムの時間計算量は、O(N 2 )までのタクシー番号を出力する可能性があるため、いずれの場合もO(N 2 )より小さくすることはできません。

スペースの使用量を減らすには、理論的には、ここに記載されている提案を使用できます: little link。基本的には、最初にすべての可能なペアa、bを試して、これに対する解決策を見つけるという考え方です。

a = 1 − (p − 3 * q)(p 2 + 3 * q 2 )

b = −1 + (p + 3 * q)(p 2 + 3q 2 )

次に、次を使用して適切なc、dペアを見つけることができます。

c = (p + 3 * q) - (p 2 + 3 * q 2 )

d = -(p - 3 * q) + (p 2 + 3 * q 2 )

両方とも N より小さいかどうかを確認します。ここでの問題は、その連立方程式を解くのが少し面倒になる可能性があることです (「少し」とは、非常に面倒なことを意味します)。

O ( N 2 )空間ソリューションははるかに単純であり、合理的な時間制限内で実行できる二次時間の複雑さはおそらく二次空間の使用で問題ないため、おそらく十分に効率的です。

それが役に立ったことを願っています！

于 2012-09-03T08:46:57.617 に答える
1

時間の複雑さ O(N^2 logN)、空間の複雑さ O(N)を理解する簡単な方法は、N並べ替えられた配列のマージに加えて、以前にマージされた要素の簿記と考えることです。

于 2016-02-21T06:11:10.383 に答える
0

まず、タクシー番号を検索する代わりに、タクシー番号を作成します。タクシー番号を作成するために使用する範囲、つまりnotTa(2)まで上がります。それよりも大きい数値を 3 乗すると、それよりも大きくなり、負の数を 3 乗してそのケースを防ぐことはできません。HashSet を使用して、アルゴリズムで 2 つの立方数の合計を記憶します。これは、前に述べた範囲内のすべての可能な数値ペアを反復処理している間に、以前の 3 乗合計を時間内に検索するのに役立ちます。n^1/3nn^1/3nO(1)

時間の複雑さ:O(n^2/3)

スペースの複雑さ:O(n^1/3)

def taxicab_numbers(n: int) -> list[int]:
    taxicab_numbers = []
    max_num = math.floor(n ** (1. / 3.))
    seen_sums = set()
    for i in range(1, max_num + 1):
        for j in range(i, max_num + 1):
            cube_sum = i ** 3 + j ** 3
            if cube_sum in seen_sums:
                taxicab_numbers.append(cube_sum)
            else:
                seen_sums.add(cube_sum)
    return taxicab_numbers
于 2021-05-23T19:17:38.500 に答える