動的プログラミング：間に数を数えよう

Question

XとYの2つの数字が与えられている場合、それらの数字の半分以上が同じである数字はいくつありますか？たとえば、1122および4444が機能し、11234および112233は機能しません。

明らかに、最も簡単な方法は、Yに1 Xと増分ですべての方法を起動し、各番号を確認することですが、それはXのための境界として、あまりにも遅く、Yは100と10^18の間にあります。私はそれが動的プログラミングの何らかの形であり、数字を表すために文字列を使うべきだと知っていますが、それ以上は得られません。

ヘルプが受け付けられます。ありがとう！

Answer 1

明らかに、範囲内のすべての数値を考慮してこれを行うことはありません。代わりに、という数字でを生成すると考えてください。例えば、数字の長さを超えて与えられていないすべての適格な数字を生成する関数を設計します。

たとえば、1桁または3桁の数字を含むすべての数字を1桁で入力するか、で3桁で区切る必要がありますか？ 3桁1つはより多くのものか​​らですか？

今、あなたはそのことについて考えたことを、このことについて考える：代わりにのすべてのこれらの数字だけ数それらを生成します。たとえば、3つの1と2つのの他の桁の場合、9 * 9の他の桁があります（11122のようなものを二重にしないでください）。あなたは10の方法で1を手配することができ、他の2桁の交換が可能です。問題は、偶数桁の量と少し異なっている

注：ダブルカウント半分ずつ番号を避けるために必要があり、そのよう111222.

ないとしてあなたが移動を取得？

---

コメント03に対する応答12月

bobjoe628 @：これは完全なアルゴリズムであることを意図したものではありません。むしろ、あなたを始めるための提案です。はい、処理すべきいくつかの組み合わせ問題があります。 11122233に​​ついては、私はあなたの懸念を理解しているかどうかはわかりません。そのような順列問題の場合と同様に、各桁を兄弟と交換可能に扱わなければなりません。 1を配布する方法は10C5通りあります。残りのスポットには、2Cを配布する5C3の方法があります。他の2つのスロットは3'3です。容易に利用可能なアルゴリズム（すなわち、ブラウザ検索）は、それらのマッチングをカバーする。

数字を生成するアルゴリズムを書くことができると信じています.1つの数字の組み合わせしか必要ではないことに注意してください。例：1111122233のように、数字を昇順で生成するのが安全です。あなたのコンビナトリアルコードはそれらの数字のすべてのユニークな順列をカバーすべきです。

最後に、ほとんどの言語では、順列と組み合わせを実行するパッケージがサポートされていることに注意してください。

Answer 2

私はいくつかのステップであなたを説明します：

まずステップ：常に0 to Xと0 to Y-1の間でカウントすることで、それを簡単にXとYとの間の範囲のこの種の問題を解決するため

をし、引きます結果。あなたは0とNの間に同じ少なくとも半分自分の数字を持っている数字を計算f(N)のような機能を持っている場合つまりは、その後、最終的な結果は次のとおりです。

f(X) - f(Y-1) 

第二ステップ：

次我々 f（N）を計算しなければならない。この関数を2つのサブ関数に分割します.1つはNと同じ桁数（f_equalと呼ぶ）の結果を計算するためのもの、もう1つはNより小さな数字を持つ修飾された数値を数える（f_lessと呼ぶ） 。例えば。 Nが19354であれば、0から9999までの適格な数を数え、次に別の方法で10000から19354の間の好きな数を数え、その結果を合計します。次に、これらの2つの方法を実装する方法について説明します。

第三ステップ：ここで

、我々はf_less方法を計算したいです。いくつかの数学によってそれを行うことができますが、私はいつもこれらの課題を解決するための簡単なDPを書くことを好みます。私はmemoizationを使うことができるかどうかにかかわらず、いくつかのループでボトムアップにすることができるかどうかにかかわらず、再帰関数を記述します（私はあなたのために練習として残します）。

long long f_less(int curDigit, int favNum, int favNumCountSoFar, int nonFavNum, int nonFavNumCountSoFar, int maxDigit){ 
    if(curDigit == maxDigit){ 
     //for numbers with even maxDigit there may be a case when we have 2 favorite numbers 
     //and we should count them only once. like 522552 
     if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1; 
     if(2*favNumCountSoFar >= maxDigit) return 2; 
     return 0; 
    } 
    long long res = 0; 
    for(int i=(curDigit==0?1:0);i<=9;++i) //skip the leading zero 
     if(i==favNum) 
      res += f_less(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar,maxDigit); 
     else 
      res += f_less(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1),maxDigit); 
    return res; 
} 

そして、0〜9を介してすべての数字のためにそれを呼び出す：

long long res = 0; 
for(int maxDigit = 1; maxDigit < NUMBER_OF_DIGITS(N); ++maxDigit) 
    for(int favNumber = 0; favNumber < 10; ++favNumber) 
     res += f_less(0, favNumber, 0, -1, 0, maxDigit); 

第四ステップ：

最後に、我々はf_equalを計算する必要があります。ここでは、再帰関数でN以下の範囲にあるかどうかを常にチェックするために、数値を文字列に保持する必要があります。ここf_equalの実装は、（再びメモ化を使用するか、それボトムアップします）です。

string s = NUM_TO_STRING(N); 
int maxDigit = s.size(); 
long long f_equal(int curDigit, int favNum, int favNumCountSoFar,int nonFavNum, int nonFavNumCountSoFar, bool isEqual){ //isEqual checks that whether our number is equal to N or it's lesser than it 
    if(curDigit == maxDigit){ 
     //for numbers with even maxDigit there may be a case when we have 2 favorite numbers 
     //and we should count them only once. like 522552 
     if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1; 
     if(2*favNumCountSoFar >= maxDigit) return 2; 
     return 0; 
    } 
    long long res = 0; 
    for(int i=(curDigit==0?1:0);i<=9;++i){ //skip the leading zero 
     if(isEqual && i>(s[curDigit]-'0')) break; 
     if(i==favNum) 
      res += f_equal(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar, isEqual && (i==(s[curDigit]-'0'))); 
     else 
      res += f_equal(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1), isEqual && (i==(s[curDigit]-'0'))); 
    } 
    return res; 
} 

そして、それを呼び出す：

long long res = 0; 
for(int favNumber = 0; favNumber < 10; ++favNumber) 
    res += f_equal(0, favNumber,0, -1, 0, true); 

最終結果がres/2です。コードはテストされ、うまく動作します。

Answer 3

ここに部分的な組み合わせの答えがあります。私は完全な答えを構築するために関数を使用する方法を除外します。

（より精巧なコメントと同じコードについてはこちらをご覧ください： https://repl.it/@gl_dbrqn/AllSteelblueJuliabutterfly）、左端の桁（s）は、 Lを修正

Lの右側にR桁の番号で、私たちはどのように多くの計算することができます番号0がちょうど翔です

Pythonのコード

import math, operator, collections 

# Assumes L has at least one digit set 
# f({'string':'12', 'digit_frequencies':[0,1,1,0,0,0,0,0,0,0], 'num_digit_frequencies': 2}, 6) 
def f(L, N): 
    R = N - len(L['string']) 

    count = 0 
    counted = False 

    for digit_frequency in L['digit_frequencies']:  
    start = int(math.ceil(N/2.0)) - digit_frequency 
    if start > R: 
     continue 

    for i in xrange(start, R + 1): 
     if not (N & 1) and not counted: 
     if L['num_digit_frequencies'] == 1 and not digit_frequency and i == N/2: 
      count = count - choose(R, i) 

     if L['num_digit_frequencies'] == 2 and digit_frequency and not any([x > N/2 for x in L['digit_frequencies']]) and i + digit_frequency == N/2: 
      count = count - choose(R, i) 
      counted = True 

     m = 9**(R - i) 
     n = R - i + 1 
     k = i 

     count = count + m * choose(n + k - 1, k) 

    return count 


# A brute-force function to confirm results 
# check('12', 6) 
def check(prefix, length): 
    result = [x for x in xrange(10**(length - 1), 10**length) if len(str(x)) == length and str(x).startswith(prefix) and isValid(str(x))] 

    print result 
    return len(result) 

def isValid(str): 
    letters = collections.Counter(str) 
    return any([x >= math.ceil(len(str)/2.0) for x in letters.values()]) 


# https://stackoverflow.com/questions/4941753/is-there-a-math-ncr-function-in-python 
def choose(n, r): 
    r = min(r, n-r) 
    if r == 0: return 1 
    numer = reduce(operator.mul, xrange(n, n-r, -1)) 
    denom = reduce(operator.mul, xrange(1, r+1)) 
    return numer//denom 

Answer 4

：我々はによって桁dの(N/2)以上を配布することができる方法rthand。実際には、無限の先行ゼロと無限の末尾のゼロ（小数点以下）があります（...000000.000000...など）。

すべての整数については、少なくとも小数点の前にゼロ以外の桁があるので、小数点の後には少なくとも0があることは明らかです。すべての整数を数えることができます。

0と1の間に無限の数があります。小数点の後に0以外の数字があるため、これらのすべてに小数点の左側に少なくとも0があります。同じことが0と-1の間の数字にも当てはまります。

コンピュータが保存できるほとんどすべての浮動小数点数に対して、先頭と末尾のゼロをすべて取り消すビットが不足しているだけです。

カウントできない唯一の数値は、正と負の無限大と、一部ではありませんが、< = 1または> = -1のすべての非合理的な数値です。

コード：

float getCount(int x, int y) { 
    if(x == y) return 0.0; // Special case (no numbers are between x and y) 
    return INFINITY;  // The closest value to the correct answer that a computer can use 
}