整数距離

As a single operation between two positive integers we
understand multiplying one of the numbers by some prime number or
dividing it by such (provided it can be divided by this prime
number without without the remainder). The distance between a and b
denoted as d(a,b) is a minimal amount of operations needed to
transform number a into number b. For example, d(69,42)=3.

Keep in mind that our function d indeed has characteristics of
the distance – for any positive ints a, b and c we
get:

a) d(a,a)==0

b) d(a,b)==d(b,a)

c) the inequality of a triangle d(a,b)+d(b,c)>=d(a,c) is
fulfilled.

You’ll be given a sequence of positive ints a_1, a_2,…,a_n.
For every a_i of them output such a_j (j!=i) that d(a_i, a_j) is as
low as possible. For example, the sequenceof length 6:
{1,2,3,4,5,6} should output {2,1,1,2,1,2}.

これは私にとって本当に難しいようです。私が有用と考えるのは、

a)a_iが素数ならば、a_iより小さい値をとることはできません(1以外の場合)。したがって、すべての操作は乗算だけです。したがって、集合の中に1があれば、すべての素数d(this_number、1)が最も小さい。

b)また、1d(1、any_prime_number)が最小である。

c)非素数の場合、我々は、その因子のセットまたは倍率にその因子のいずれかがあるかどうかをチェックする

それは私が推測することができるすべてです。最悪の部分は、そのアルゴリズムが実行され、すべての可能性をチェックすることが永遠になることを知っていることです…それを手伝ってください。これはどのように行うべきですか?

ベストアンサー

実際には、任意の数を2 ^ n1 * 3 ^ n2 * 5 ^ n3 * 7 ^ n4 *
…(nの大部分はゼロです)と表すことができます。

このようにして、 N と無限シーケンス(n1、n2、n3、…)の間の対応関係を設定します。

あなたの操作は、適切なシーケンスの場所のちょうど1つに1を加算または減算するだけです。

NとMを2つの数とし、それらのシーケンスを(n1、n2、n3、…)と(m1、m2、m3、…)とする。
2つの数の間の距離は、実際には| n1-m1 | + | n2-m2 | + …

だから、最も近い数値を見つけるためには、すべての入力数のシーケンスを計算する必要があります(これは、それらを素数に分解するだけです)。この分解を持つと、計算は簡単です。


編集:
実際には、素因数の正確な位置は必要ありません。知る必要があるのは、素因数のそれぞれの指数です。


編集:
これは、数値を連鎖表現に変換する簡単な手順です。

#include  typedef std::map ChainRepresentation; // maps prime factor -> exponent, default exponent is of course 0 void convertToListRepresentation(int n, ChainRepresentation& r) { //find a divisor int d = 2; while (n > 1) { for (; n % d; d++) { if (n/d < d)//n is prime { r[n]++; return; } } r[d]++; n /= d; } } 

編集:
…と距離のコード:

#include 

unsigned int chainDistance(ChainRepresentation& c1, ChainRepresentation& c2)
{
    if (&c1 == &c2)
        return 0;//protect from modification done by [] during self-comparison

    int result = 0;

    std::set visited;
    for (ChainRepresentation::const_iterator it = c1.begin(); it != c1.end(); ++it)
    {
        unsigned int factor = it->first;
        unsigned int exponent = it->second;
        unsigned int exponent2 = c2[factor];
        unsigned int expabsdiff = (exponent > exponent2) ?
                       exponent - exponent2 : exponent2 - exponent;
        result += expabsdiff;
        visited.insert(factor);
    }

    for (ChainRepresentation::const_iterator it = c2.begin(); it != c2.end(); ++it)
    {
        unsigned int factor = it->first;
        if (visited.find(factor) != visited.end())
            continue;
        unsigned int exponent2 = it->second;
       //unsigned int exponent = 0;
        result += exponent2;
    }

    return result;
}

コメントする

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です