c++ - 分数の構成 インタビューの課題

Question

私は最近、次のインタビューの質問に出くわしました.動的プログラミングアプローチが機能するかどうか、または/およびソリューションを簡単にする数学的な洞察があるかどうか疑問に思っていました.ieee754 double が構築される方法と非常に似ています.

質問: N 個の double 値のベクトル V があります。ベクトルの i 番目のインデックスの値は 1/2^(i+1) に等しくなります。例: 1/2、1/4、1/8、1/16 など...

0 < r < 1 の場合、1 つの double 'r' を入力として受け取る関数を作成し、V のインデックスを標準出力に出力します。これを合計すると、他のどの組み合わせよりも値 'r' に最も近い値が得られます。ベクトル V からのインデックスの

さらに、インデックスの数は最小限にする必要があり、2 つのソリューションがある場合は、ゼロに最も近いソリューションを優先する必要があります。

void getIndexes(std::vector<double>& V, double r)
{
 .... 
}

int main()
{
   std::vector<double> V;
   // populate V...
   double r = 0.3;
   getIndexes(V,r);
   return 0;
}

注:質問を完全に読む気がない SO'ers が何人かいるようです。したがって、次の点に注意してください。

1. 解、つまり合計は r よりも大きい可能性があります。したがって、ゼロまたはゼロに近づくまで、r から分数を段階的に減算する戦略は間違っています。

2. |r-s0| である 2 つの解がある r の例があります。== |r-s1| および s0 < s1 - この場合、s0 を選択する必要があります。ナップザック スタイルのソリューションは最初に貪欲に過大評価する傾向があるため、問題が少し難しくなります。

3. この問題が些細なことであると信じているなら、おそらくそれを理解していないでしょう。したがって、質問をもう一度読むことをお勧めします。

EDIT（Matthieu M.）： 2つの例V = {1/2, 1/4, 1/8, 1/16, 1/32}

• r = 0.3、S = {1, 3}
• r = 0.256652、S = {1}

Answer 1

アルゴリズム

目標数と分数rのセットを考えてみましょう。最小の分数 をとします。F{1/2, 1/4, ... 1/(2^N)}1/(2^N)P

次に、最適な合計は次のようになります。

S = P * round(r/P)

つまり、最適な合計Sは、利用可能な最小の分数 の整数P倍になります。最大誤差err = r - Sは です± 1/2 * 1/(2^N)。1/(2^N)セット内の最小数であるよりも小さい数を使用する必要があるため、これ以上の解決策はありませんF。

分数Fはすべて の 2 乗の倍数であるP = 1/(2^N)ため、 の任意の整数倍はPの分数の和として表すことができますF。使用する必要がある分数のリストを取得するには、整数を 2 進数でエンコードし、2 進数の場所で "分数をソリューションに含める" としてround(r/P)読み取ります。1kthkth

例：

r = 0.3とFをとり{1/2, 1/4, 1/8, 1/16, 1/32}ます。

1. 問題全体に 32 を掛けます。

   r = 9.6、およびFとして{16, 8, 4, 2, 1}。

2. r最も近い整数に丸めます。

   取るr = 10。

3. 102 進整数 (5 桁) としてエンコードします

   10 = 0b 0 1 0 1 0    ( 8 + 2 )
           ^ ^ ^ ^ ^
           | | | | |
           | | | | 1
           | | | 2
           | | 4
           | 8
           16
   

4. 各バイナリ ビットを分数に関連付けます。

      = 0b 0 1 0 1 0    ( 1/4 + 1/16 = 0.3125 )
           ^ ^ ^ ^ ^
           | | | | |
           | | | | 1/32
           | | | 1/16
           | | 1/8
           | 1/4
           1/2
   

証拠

2**Nすべての分数が整数になるように、関係するすべての数値を掛けて問題を変換することを検討してください。

元の問題:

r範囲内のターゲット数0 < r < 1と分数のリストを考えてみましょう{1/2, 1/4, .... 1/(2**N)。S合計するerror = r - Sと最小化される分数のリストのサブセットを見つけます。

次の同等の問題になります ( を掛けた後2**N)。

r範囲内のターゲット数と整数0 < r < 2**Nのリストを考えてみましょう。合計すると最小化される整数のリストのサブセットを見つけます。 {2**(N-1), 2**(N-2), ... , 4, 2, 1}Serror = r - S

合計が特定の数になる 2 の累乗を選択する (可能な限りエラーが少ない) のは、単純に整数のバイナリ エンコードです。したがって、この問題は整数のバイナリ エンコーディングに帰着します。

• 解の存在: 任意の正の浮動小数点数r、0 < r < 2**Nは、整数にキャストしてバイナリ形式で表すことができます。
• 最適性: 解の整数バージョンの最大誤差は、の丸め誤差です±0.5。(元の問題では、最大誤差は±0.5 * 1/2**Nです。)
• 一意性: 任意の正の (浮動小数点) 数値には、一意の整数表現があり、したがって一意のバイナリ表現があります。( 0.5= の例外の可能性があります。以下を参照してください。)

実装 (Python)

この関数は、問題を等価の整数に変換し、整数に丸めr、次に のバイナリ表現をr整数として読み取り、必要な分数を取得します。

def conv_frac (r,N):
    # Convert to equivalent integer problem.
    R = r * 2**N
    S = int(round(R))

    # Convert integer S to N-bit binary representation (i.e. a character string
    # of 1's and 0's.) Note use of [2:] to trim leading '0b' and zfill() to
    # zero-pad to required length.
    bin_S = bin(S)[2:].zfill(N)

    nums = list()
    for index, bit in enumerate(bin_S):
        k = index + 1
        if bit == '1':
            print "%i : 1/%i or %f" % (index, 2**k, 1.0/(2**k))
            nums.append(1.0/(2**k))
    S = sum(nums)
    e = r - S

    print """
    Original number        `r` : %f
    Number of fractions    `N` : %i (smallest fraction 1/%i)
    Sum of fractions       `S` : %f
    Error                  `e` : %f
    """ % (r,N,2**N,S,e)

出力例:

>>> conv_frac(0.3141,10)
1 : 1/4 or 0.250000
3 : 1/16 or 0.062500
8 : 1/512 or 0.001953

    Original number        `r` : 0.314100
    Number of fractions    `N` : 10 (smallest fraction 1/1024)
    Sum of fractions       `S` : 0.314453
    Error                  `e` : -0.000353

>>> conv_frac(0.30,5)
1 : 1/4 or 0.250000
3 : 1/16 or 0.062500

    Original number        `r` : 0.300000
    Number of fractions    `N` : 5 (smallest fraction 1/32)
    Sum of fractions       `S` : 0.312500
    Error                  `e` : -0.012500

補遺:0.5問題

r * 2**Nで終わる場合は0.5、切り上げまたは切り捨てが可能です。つまり、分数の合計として 2 つの可能な表現があります。

元の問題ステートメントのように、小数を使用する表現 (つまり、2 進表現の最小1ビット数) が必要な場合は、両方の丸めオプションを試して、より経済的な方を選択してください。

Answer 2

たぶん私はばかです...

ここでわかる唯一の秘訣は、(1/2)^(i+1)for iin [0..n)whereの合計がn無限大になる傾向があるということ1です。この単純な事実は、 forが何であれ、for(1/2)^iよりも常に優れていることを証明しています。sum (1/2)^jj[i+1, n)n

したがって、インデックスを探す場合、選択肢はあまりないようです。から始めましょうi = 0

• どちらかrが優れているため2^-(i+1)、必要です
• または劣っており、in の OR が最も近いかどうかを選択する必要があります(等しい2^-(i+1)場合は後者に従います)。sum 2^-jj[i+2, N]

コストがかかる可能性のある唯一のステップは合計を取得することですが、一度だけ事前計算することができます (遅延して事前計算することもできます)。

// The resulting vector contains at index i the sum of 2^-j for j in [i+1, N]
// and is padded with one 0 to get the same length as `v`
static std::vector<double> partialSums(std::vector<double> const& v) {
    std::vector<double> result;

    // When summing doubles, we need to start with the smaller ones
    // because of the precision of representations...

    double sum = 0;
    BOOST_REVERSE_FOREACH(double d, v) {
        sum += d;
        result.push_back(sum);
    }

    result.pop_back(); // there is a +1 offset in the indexes of the result

    std::reverse(result.begin(), result.end());

    result.push_back(0); // pad the vector to have the same length as `v`

    return result;   
}

// The resulting vector contains the indexes elected
static std::vector<size_t> getIndexesImpl(std::vector<double> const& v,
                                          std::vector<double> const& ps,
                                          double r)
{
  std::vector<size_t> indexes;

  for (size_t i = 0, max = v.size(); i != max; ++i) {
      if (r >= v[i]) {
          r -= v[i];
          indexes.push_back(i);
          continue;
      }

      // We favor the closest to 0 in case of equality
      // which is the sum of the tail as per the theorem above.
      if (std::fabs(r - v[i]) < std::fabs(r - ps[i])) {
          indexes.push_back(i);
          return indexes;
      }
  }

  return indexes;
}

std::vector<size_t> getIndexes(std::vector<double>& v, double r) {
    std::vector<double> const ps = partialSums(v);
    return getIndexesImpl(v, ps, r);
}

コードはideoneで実行されます (デバッグ出力がいくつかあります) 。0.3それが与えることに注意してください：

0.3:
   1: 0.25
   3: 0.0625
=> 0.3125

これは他の回答とは少し異なります。

Answer 3

反対票を投じるリスクはありますが、この問題はかなり単純なようです。から生成できる最大値と最小値から始めて、V最も近い 2 つの可能な答えが得られるまで、各インデックスを順番に調整します。次に、どちらがより良い答えであるかを評価します。

これはテストされていないコードです（私が書いていない言語で）：

void getIndexes(std::vector<double>& V, double r)
{
  double v_lower = 0;
  double v_upper = 1.0 - 0.5**V.size();
  std::vector<int> index_lower;
  std::vector<int> index_upper;

  if (v_upper <= r)
  {
    // The answer is trivial.
    for (int i = 0; i < V.size(); i++)
      cout << i;
    return;
  }

  for (int i = 0; i < N; i++)
  {
    if (v_lower + V[i] <= r)
    {
      v_lower += V[i];
      index_lower.push_back(i);
    }

    if (r <= v_upper - V[i])
      v_upper -= V[i];
    else
      index_upper.push_back(i);
  }

  if (r - v_lower < v_upper - r)
    printIndexes(index_lower);
  else if (v_upper - r < r - v_lower)
    printIndexes(index_upper);
  else if (v_upper.size() < v_lower.size())
    printIndexes(index_upper);
  else
    printIndexes(index_lower);
}

void printIndexes(std::vector<int>& ind)
{
  for (int i = 0; i < ind.size(); i++)
  {
    cout << ind[i];
  }
}

就職したか！:D

(注意してください、これはV が何を持っているかを正確に知ることに依存する恐ろしいコードです...)

Answer 4

テストケースがあるかどうかわかりません。以下のコードを試してください。これは動的計画法のアプローチです。

1] exp: given 1/2^i, find the largest i as exp. Eg. 1/32 returns 5.
2] max: 10^exp where exp=i.
3] create an array of size max+1 to hold all possible sums of the elements of V.
   Actually the array holds the indexes, since that's what you want.
4] dynamically compute the sums (all invalids remain null)
5] the last while loop finds the nearest correct answer.

コードは次のとおりです。

public class Subset {

public static List<Integer> subsetSum(double[] V, double r) {
    int exp = exponent(V);
    int max = (int) Math.pow(10, exp);
    //list to hold all possible sums of the elements in V
    List<Integer> indexes[] = new ArrayList[max + 1];
    indexes[0] = new ArrayList();//base case
    //dynamically compute the sums
    for (int x=0; x<V.length; x++) {
        int u = (int) (max*V[x]);
        for(int i=max; i>=u; i--) if(null != indexes[i-u]) {
            List<Integer> tmp = new ArrayList<Integer>(indexes[i - u]);
            tmp.add(x);
            indexes[i] = tmp;
        }
    }
   //find the best answer
    int i = (int)(max*r);
    int j=i;
    while(null == indexes[i] && null == indexes[j]) {
        i--;j++;
    }
      return indexes[i]==null || indexes[i].isEmpty()?indexes[j]:indexes[i];
}// subsetSum

private static int exponent(double[] V) {
    double d = V[V.length-1];
    int i = (int) (1/d);
    String s = Integer.toString(i,2);
    return s.length()-1;
}// summation

public static void main(String[] args) {
    double[] V = {1/2.,1/4.,1/8.,1/16.,1/32.};
    double r = 0.6, s=0.3,t=0.256652;
    System.out.println(subsetSum(V,r));//[0, 3, 4]
    System.out.println(subsetSum(V,s));//[1, 3]
    System.out.println(subsetSum(V,t));//[1]
}
}// class

コードを実行した結果は次のとおりです。

For 0.600000  get 0.593750 => [0, 3, 4]
For 0.300000  get 0.312500 => [1, 3]
For 0.256652  get 0.250000 => [1]
For 0.700000  get 0.687500 => [0, 2, 3]
For 0.710000  get 0.718750 => [0, 2, 3, 4]

Answer 5

このソリューションは、多項式時間近似アルゴリズムを実装しています。プログラムの出力は、別のソリューションの出力と同じです。

#include <math.h>                                                                                                                                             
#include <stdio.h>                                                                                                                                            
#include <vector>                                                                                                                                             
#include <algorithm>                                                                                                                                          
#include <functional>                                                                                                                                         

void populate(std::vector<double> &vec, int count)                                                                                                            
{                                                                                                                                                             
    double val = .5;                                                                                                                                          
    vec.clear();                                                                                                                                              
    for (int i = 0; i < count; i++) {                                                                                                                         
        vec.push_back(val);                                                                                                                                   
        val *= .5;                                                                                                                                            
    }                                                                                                                                                         
}                                                                                                                                                             

void remove_values_with_large_error(const std::vector<double> &vec, std::vector<double> &res, double r, double max_error)                                     
{                                                                                                                                                             
    std::vector<double>::const_iterator iter;                                                                                                                 
    double min_err, err;                                                                                                                                      

    min_err = 1.0;                                                                                                                                            
    for (iter = vec.begin(); iter != vec.end(); ++iter) {                                                                                                     
        err = fabs(*iter - r);                                                                                                                                
        if (err < max_error) {                                                                                                                                
            res.push_back(*iter);                                                                                                                             
        }                                                                                                                                                     
        min_err = std::min(err, min_err);                                                                                                                     
    }                                                                                                                                                         
}

void find_partial_sums(const std::vector<double> &vec, std::vector<double> &res, double r)                                                                    
{                                                                                                                                                             
    std::vector<double> svec, tvec, uvec;                                                                                                                     
    std::vector<double>::const_iterator iter;                                                                                                                 
    int step = 0;                                                                                                                                             

    svec.push_back(0.);                                                                                                                                       
    for (iter = vec.begin(); iter != vec.end(); ++iter) {                                                                                                     
        step++;                                                                                                                                               
        printf("step %d, svec.size() %d\n", step, svec.size());                                                                                               
        tvec.clear();                                                                                                                                         
        std::transform(svec.begin(), svec.end(), back_inserter(tvec),                                                                                         
                       std::bind2nd(std::plus<double>(), *iter));                                                                                             
        uvec.clear();                                                                                                                                         
        uvec.insert(uvec.end(), svec.begin(), svec.end());                                                                                                    
        uvec.insert(uvec.end(), tvec.begin(), tvec.end());                                                                                                    
        sort(uvec.begin(), uvec.end());                                                                                                                       
        uvec.erase(unique(uvec.begin(), uvec.end()), uvec.end());                                                                                             

        svec.clear();                                                                                                                                         
        remove_values_with_large_error(uvec, svec, r, *iter * 4);                                                                                             
    }                                                                                                                                                         

    sort(svec.begin(), svec.end());                                                                                                                           
    svec.erase(unique(svec.begin(), svec.end()), svec.end());                                                                                                 

    res.clear();                                                                                                                                              
    res.insert(res.end(), svec.begin(), svec.end());                                                                                                          
} 

double find_closest_value(const std::vector<double> &sums, double r)                                                                                          
{                                                                                                                                                             
    std::vector<double>::const_iterator iter;                                                                                                                 
    double min_err, res, err;                                                                                                                                 

    min_err = fabs(sums.front() - r);                                                                                                                         
    res = sums.front();                                                                                                                                       

    for (iter = sums.begin(); iter != sums.end(); ++iter) {                                                                                                   
        err = fabs(*iter - r);                                                                                                                                
        if (err < min_err) {                                                                                                                                  
            min_err = err;                                                                                                                                    
            res = *iter;                                                                                                                                      
        }                                                                                                                                                     
    }                                                                                                                                                         
    printf("found value %lf with err %lf\n", res, min_err);                                                                                                   
    return res;                                                                                                                                               
}                                                                                                                                                             

void print_indexes(const std::vector<double> &vec, double value)                                                                                              
{                                                                                                                                                             
    std::vector<double>::const_iterator iter;                                                                                                                 
    int index = 0;                                                                                                                                            

    printf("indexes: [");                                                                                                                                     
    for (iter = vec.begin(); iter != vec.end(); ++iter, ++index) {                                                                                            
        if (value >= *iter) {                                                                                                                                  
            printf("%d, ", index);                                                                                                                            
            value -= *iter;                                                                                                                                   
        }                                                                                                                                                     
    }                                                                                                                                                         
    printf("]\n");                                                                                                                                            
}                                                                                                                                                             

int main(int argc, char **argv)                                                                                                                               
{                                                                                                                                                             
    std::vector<double> vec, sums;                                                                                                                            
    double r = .7;                                                                                                                                            
    int n = 5;                                                                                                                                                
    double value;                                                                                                                                             
    populate(vec, n);                                                                                                                                         
    find_partial_sums(vec, sums, r);                                                                                                                          
    value = find_closest_value(sums, r);                                                                                                                      
    print_indexes(vec, value);                                                                                                                                
    return 0;                                                                                                                                                 
}

Answer 6

質問を言い換えると、r の 2 進数表現 (2 進小数点の後の) の 1 ビットは何ですか? 必要に応じて、N は「精度」です。

Cish 疑似コードで

for (int i=0; i<N; i++) {
  if (r>V[i]) {
    print(i);
    r -= V[i];
  }
}

r == 0 の追加テストを追加して、ループを早期に終了できます。

これは、'r' に最も近い最小の 2 進数を与えることに注意してください。つまり、2 つの等しく「正しい」答えがある場合、0 に近い 1 つです。

N 桁目が 1 の場合は、取得した「2 進数」に「1」を追加し、両方を元の「r」と照合する必要があります。(ヒント: 「ビット」のベクトル a[N]、b[N] を構築し、上記の「印刷」の代わりに「1」ビットを設定します。b = a を設定し、手動で追加を行い、「 b' 運ぶのをやめるまで. double に変換し、どちらか近い方を選択します。

a[] <= r <= a[] + 1/2^N および b[] = a[] + 1/2^N であることに注意してください。

「インデックスの最小数[原文のまま]」は、ニシンです。

Answer 7

ベクトルを並べ替えて、r に使用できる最も近い分数を検索します。そのインデックスを保存し、r から値を減算し、r の残りで繰り返します。r に到達するか、そのようなインデックスが見つからなくなるまで繰り返します。

例 ：

0.3 - 利用可能な最大値は 0.25 です。(インデックス 2)。残りは現在0.05です

0.05 - 利用可能な最大値は 0.03125 です - 残りは 0.01875 です

等

など。すべてのステップは、ソートされた配列での O(logN) 検索になります。ステップ数も O(logN) になり、合計の複雑さは O(logN^2) よりも大きくなります。

Answer 8

これは動的プログラミングの質問ではありません

出力は、double のベクトルではなく、int (インデックス) のベクトルであるべきです

これは、正確な値で 0 ～ 2 ずれている可能性があります。これは単なる概念です。

A) r0 (r - 既に出力されたインデックス値) が 1/2 より大きくなるまでゼロインデックスを出力する

B) r0 double の内部表現を検査し、次のことを行います。

x (最初のビット シフト) = -指数; // 大きい方の指数、最小の数 (開始時の 1/2^(x) で大きい方の x)

float の小数部分のビット表現を body で検査します: (方向はリトルエンディアン/ビッグ エンディアンによって異なります)

{
  if (bit is 1)
    output index x;
  x++;

}

各ステップの複雑さは一定であるため、全体として O(n) であり、n は出力のサイズです。