algorithm - アルゴリズム解決の問題

Question

[要件]
与えられたアルファベット {0, 1, ... , k}, 0 ≤ k ≤ 9. このアルファベットの長さ nの単語は、単語内の隣接する 2 つの数字が入力は一連の行で、各行には 2 つの整数 k と n、1 ≤ n ≤ 100 が含まれます。入力の各行について、アルファベット {0, 1, ... , k} 小数部 5 桁。

[入力]

4 1
2 5
3 5
8 7

[出力]

100.00000
40.74074
17.38281
0.10130

まず、このクイズがわかりません。例、入力が の場合2, 5。なぜ答えが 40.74074 なのかわかりません。

この場合、「きつい」となります。真ん中の数は 1 でなければなりません。

例、

00000 00001 00002
00010 00011 00012
....

そう、

ここにあるすべてのケースは、3 ⁵ = 243です。

最後の桁は 1 でなければならないので、3 ⁴ = 81 が「タイト」なケースになります。

したがって、出力は 81/243 = 0.3333333333333333 = 33.333333% になります。

私は何かを逃しましたか？

そして、これを解決するための良いアルゴリズムはありますか?

Answer 1

この問題を一般化して単純化する

k(すみません、との順番を入れ替えましたn。)

タイトな数値の最後の桁を省略すると、別のタイトな数値が得られ、それらの最後の桁の差は最大で1.

最後の桁c(n, k, l)の長さのタイトな数のすべての数があると仮定します。次に、長さと最後の桁のタイトな数の数は です。nln + 1lc(n + 1, k, l) = c(n, k, l - 1) + c(n, k, l) + c(n, k, l + 1)

基本ケースは単純です: 1 つのタイトな数値、つまりn=1を意味します。c(1, k, l) = 1

テスト (Python):

def c(n, k, l):
    if l > k or l < 0:
        return 0
    if n == 1:
        return 1
    return sum(c(n - 1, k, i) for i in range(l - 1, l + 2))

def f(n, k):
    tight = sum(c(n, k, l) for l in range(k + 1))
    return tight / (k + 1) ** n

例:

>>> print(f(1,4))
1.0
>>> print(f(4, 1))
1.0
>>> print(f(5, 2))
0.4074074074074074
>>> print(f(5, 3))
0.173828125
>>> print(f(7, 8))
0.0010129691411338857

非常に大きな数の場合、同じ数が何度も計算されるため、これは遅くなります。これらは、プログラムの開始時に次の 2 行を追加することにより、キャッシュ (「メモ化」) できます (2 行目は、次の関数c(n, k, l)をキャッシュで装飾します)。

import functools
@functools.lru_cache()

例：

>>> f(100,9)
1.0051226793648084e-53

Answer 2

私たちの問題は、長さ n のタイトな単語の数、つまり を見つけることa[1 .. n]です。以下は、動的計画法に基づくソリューションです。アイデアは、長さまでの答えがあると仮定することです。i - 1長さの答えを計算する方程式を作成しますi。

LetC(i, d)は、長さが i のタイトな単語の総数です。つまりa[1 .. i]、最後の桁a[i] = dが0 <= d <= kです。（タイトワードの定義）を観察するとa[i - 1] - 1 <= a[i] <= a[i - 1] - 1、次の再帰関係があります。

For i = 1: 
  C(1, d) = 1

For i > 1: 
  C(i, d) = 
    C(i - 1, 0) + C(i - 1, 1) -- if d == 0
    C(i - 1, k - 1) + C(i - 1, k) -- if d == k
    C(i - 1, d - 1) + C(i - 1, d) + C(i - 1, d + 1) -- otherwise

次に、私たちが求めているのは単純です:

N(n) = C(n, 0) + C(n, 1) + ... C(n, k)

コード：

これは、サンプル入力で同じ回答を生成するようにテストされた nodejs プログラムです (キャッシュしていないため、まだ動的プログラミングではありませんC(i, p)。繰り返し計算がたくさんありますが、簡単に実行できるはずです)。

// tight_words.js

var k = 2;
var n = 5;

function N(i) {
    var n = 0;

    for (d = 0; d <= k; ++d)
        n += C(i, d);

    return n;
}

function C(i, d) {
    if (i == 1)
        return 1;

    if (d == 0)
        return C(i - 1, 0) + C(i - 1, 1);

    if (d == k)
        return C(i - 1, k - 1) + C(i - 1, k);

    return C(i - 1, d - 1) + C(i - 1, d) + C(i - 1, d + 1);
}

var total = Math.pow(k + 1, n);
var c = N(n);
console.log('k = ' + k + ', n = ' + n);
console.log('==> percentage = ' + c / total);

Answer 3

出力がサンプル データと一致する ruby​​ コードを次に示します。

#!/usr/bin/env ruby

def isTight( x )
  for i in (1..x.length-1)
    return false if 1 < (x[i].to_i-x[i-1].to_i).abs
  end
  return true
end

def getWord( x, base, n )
  retval = []
  1.upto(n) do
    x, r = x.divmod(base)
    retval.unshift r
  end
  retval.join
end

def percent( k, n )
  nwords = (k+1) ** n
  count = 0
  for i in (0..nwords-1)
    word = getWord( i, k+1, n )
    count += 1 if isTight( word )
  end
  return 100.0 * count / nwords
end

STDIN.each_line do |line|
  line.chomp!
  puts line+' '+percent(*line.split(' ').map { |i| i.to_i }).to_s
end

これは4行を受け入れます

4 1
2 5
3 5
8 7

入力として、出力として

4 1 100.0
2 5 40.74074074074074
3 5 17.3828125
8 7 0.10129691411338856

（小数点以下5桁でなくてすみません）

---

編集:実際には、完全を期すためにここに含まれているWolframHの再帰ソリューションを使用することをお勧めします:

#!/usr/bin/env ruby

$cache = Hash.new
def count( k, n, last )
  key = "#{k}:#{n}:#{last}"
  return $cache[key] if $cache.has_key?(key)
  return 0 if !(0 <= last && last <= k) # last digit must be in range
  return 1 if n == 1 # single digit numbers are always tight
  return $cache[key] = (-1..1).inject(0) { |sum,i| sum + count(k,n-1,last+i) }
end

def percent( k, n )
  ntight = (0..k+1).inject(0) { |sum,last| sum + count(k,n,last) }
  return 100.0 * ntight / (k+1)**n
end

puts percent( 1, 4 )
puts percent( 2, 5 )
puts percent( 3, 5 )
puts percent( 8, 7 )
puts percent( 9, 100 )

$cache を使用すると、これは x86_64 Intel(R) Core(TM) i3-3240 CPU @ 3.40GHz で非常に高速に実行されます。

$ time ./tight.rb
100.0
40.74074074074074
17.3828125
0.10129691411338856
1.0051226793648083e-51

real    0m0.016s
user    0m0.010s
sys     0m0.005s

Answer 4

WolframHの回答に基づいて、サンプル入力の問題をC++で試してみましたが、うまくいくようです。また、サンプル入力で問題なく動作するphythonソリューションも試しました。興味深いのは、入力を少し大きな数 (つまり、3 と 18) に増やすと、C++とphythonの両方のソリューションが不確定な時間ハングすることです。

何がうまくいかなかったのですか？

偶然にも、昨日の夜、たまたま動的計画法のノートを読んでいて、加重独立集合問題について読んだところです。あはは！私たちは想定よりもはるかに多くの仕事をしています! の：

#include <math.h>
#include <iomanip>
#include <iostream>
using namespace std;

void get_tight_number(int base_max, int length)
{
  double result = 0;
  int _tight_numbers = 0;
  double total = pow(base_max + 1, length);
  for (int i = 0; i <= base_max; ++i)
  {
    _tight_numbers += get_tight_number_help(base_max, length, i);
  }
  result = 100 * _tight_numbers / total;
  cout << fixed << setprecision(5) << result << "\n";
}

int get_tight_number_help(int base_max, int length, int endwith)
{
  cout << "Length: " << length << "endwith: " << endwith << endl;
  if (length < 1 || endwith < 0 || endwith > base_max)
    return 0;
  if (length == 1)
  {
    return 1;
  } else 
  {
    return get_tight_number_help(base_max, length - 1, endwith)
         + get_tight_number_help(base_max, length - 1, endwith + 1)
         + get_tight_number_help(base_max, length - 1, endwith - 1);
  }
}

int main()
{
  get_tight_number(8, 7);
  return 0;
}

たくさんのprints正しい結果があります0.10130。これは、この入力に対して、ヘルパー関数が 7000 回以上呼び出されたことを意味しますgrep "endwith:" | wc -l。7719他の入力で何回呼び出されたかを把握するために、次のようにしました。

Input    #
8, 8     22254
8, 6     2682
8, 5     933

あまり良くありません...再計算が多すぎます。bottom up代わりに、参照配列のソリューションをまとめました。

int** tight_number_bottom_up(int base_max, int length)
{
  int** result = new int*[base_max + 1];
  for (int i = 0; i < base_max + 1; ++i)
  {
    result[i] = new int[length];
  }
  //Ends with i, i.e., looping over them
  for (int j = 0; j < length + 1; ++j)
  {
    for (int i = 0; i < base_max + 1; ++i)
    {
      if (j == 0)
      {
        result[i][j] = 0;
      } else if (j == 1)
      {
        result[i][j] = 1;
      } else
      {
        int bigger = i == base_max ? 0 : result[i + 1][j - 1];
        cout << "bigger: " << bigger << endl;
        int smaller = i == 0 ? 0 : result[i - 1][j - 1];
        cout << "smaller: " << smaller << endl;
        result[i][j] = result[i][j - 1] + bigger + smaller;
      }
    }
  }
  return result;
}

ボトムアップ表を作成する際の反復回数は最大であると確信しており、(base_max + 1) * (length + 1)書き終えたことに満足し、正しい結果が得られたことに満足しています。

フォローアップの質問(あなたがまだ私と一緒にいる場合)

double9, 100またはのような入力には十分ではないよう9, 50ですが、「長い」ダブルを作成するにはどうすればよいですか?