0

数字が昇順である場合、数字は「昇順」であるとしましょう。例: 1223469。「降順」の数字は降順になります。例: 9844300。「昇順」でも「降順」でもない数字は、「ジャンプ」と呼ばれます。1 から 100 までの数字は「ジャンプ」していません。101 から 10^60 までの「飛び跳ねる」数はいくつありますか?

4

4 に答える 4

3

ここにアイデアがあります: ジャンプ数を数える代わりに、昇順と降順を数えます。次に、すべての数字からそれらを引きます。

昇順/降順のカウントは簡単です。生成する残りの桁数と最後の位置に配置した桁に基づいて動的プログラミングを使用できます。

于 2012-10-12T15:48:32.123 に答える
3

昇順の数を数える方法を説明します。その方が簡単です。そこから、降順のものを数えてから、Ivan が示すように、重複を補って数字の合計量から合計量を差し引くか、ジャンプする数字のみを直接数えるためのより複雑な方法を考案することもできます。

別のアプローチ

末尾の数字でソートされた数字について考えてみてください。1 桁の数字から始めます。これがリストになります。

1 // Amount of numbers ending with 1
1 // Amount of numbers ending with 2
1 // Amount of numbers ending with 3
1 // Amount of numbers ending with 4
1 // Amount of numbers ending with 5
1 // Amount of numbers ending with 6
1 // Amount of numbers ending with 7
1 // Amount of numbers ending with 8
1 // Amount of numbers ending with 9

6 で終わる 2 桁の数を構成するには、6 以下で終わるすべての数を使用できます。

1 // Amount of numbers ending with 1 with 2 digits
2 // Amount of numbers ending with 2 with 2 digits
3 // Amount of numbers ending with 3 with 2 digits
4 // Amount of numbers ending with 4 with 2 digits
5 // Amount of numbers ending with 5 with 2 digits
6 // Amount of numbers ending with 6 with 2 digits
7 // Amount of numbers ending with 7 with 2 digits
8 // Amount of numbers ending with 8 with 2 digits
9 // Amount of numbers ending with 9 with 2 digits

これらを並べて書くと、新しい値を非常に迅速に計算する方法がわかります。

ya // y、a、および x は以前に計算されています x (a + x)

1 1  1   1 
1 2  3   4
1 3  6  10
1 4 10  20
1 5 15  35
1 6 21  56
1 7 28  84
1 8 36 120
1 9 45 165

シンプルな Python プログラム

そのような列の 1 つを反復処理すると、最後の計算を常に覚えていれば、新しい列のすべての値を直接生成できます。このscan()関数は、1 つの要素を取得する動作を正確に抽象化し、それと最終結果を使用して何らかの計算を行います。

def scan(f, state, it):
  for x in it:
    state = f(state, x)
    yield state

次の列の作成は次のように簡単になりました。

new_column = list(scan(operator.add, 0, column))

簡単にするために、開始点として 1 桁の数字を使用します。

first_row = [1]*9

常に新しい行を関数にフィードバックする必要があることを確認すると、スキャンを再度使用してそれを行うことができます。

def next_row(row):
    return list(scan(operator.add, 0, column))

def next_row_wrapper(row, _):
    return next_row(row)

>>> [list(x) for x in scan(next_row_wrapper, [1]*9, range(3))] # 3 iterations
[[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 3, 6, 10, 15, 21, 28, 36, 45], [1, 4, 10, 20, 35, 56, 84, 120, 165]]

ご覧のとおり、これにより、最初の行とは別に最初の 3 行が得られます。

すべての数値の合計を知りたいので、それを行うことができます。1 回の反復を実行すると、10^2 までのすべての昇順の数値が取得されるため、10^60 までのすべての数値に対して 59 回の反復を実行する必要があります。

>>> sum(sum(x) for x in scan(lambda x, _: next_row(x), [1]*9, range(59))) + 10
56672074888L

降順の数値については、非常に似ています。

>>> sum(sum(x) for x in scan(lambda x, _: next_row(x), [1]*10, range(59))) + 10 - 58
396704524157L<

古いアプローチ

数字がどのように終わるか考えてみてください。

10 から 99 まで、1 つの数字は 2 桁です。

がある

  • 1で終わる1
  • 2 で終わる 2
  • 3 で終わる 3
  • 4で終わる4
  • 5 で終わる 5
  • 6で終わる6
  • 7で終わる7
  • 8で終わる8
  • 9で終わる9

これらの番号はすべて、100 から 999 までの番号のプレフィックスとして機能します。

例として、 で終わる数字が 3 つあります3。

  • 13
  • 23
  • 33

これら 3 つの数字のそれぞれについて、7 つの昇順の数字を作成できます。

  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139

これにより、7 つの可能な末尾の数字のそれぞれに 3 つの数字が追加されることが簡単にわかります。

4 で終わる数字を拡張したい場合、プロセスは同様です。現在、 で終わる数字は 4 つあります4。したがって、そのような数字ごとに、6 つの新しい昇順の数字を作成できます。つまり、可能な最後の 6 桁すべてに 4 が追加されます。

ここに書いたことをすべて理解していれば、それを一般化して、それらすべての数をカウントするアルゴリズムを実装するのは簡単です。

于 2012-10-12T16:00:01.850 に答える
1

ジャンプしない数字：

  • 69 choose 9（サイズが60以下の昇順）
  • + 70 choose 10 - 60（サイズが60以下の降順）
  • - 60 * 9（ダブルカウント：すべての桁が同じ）
  • - 1（ダブルカウント：ゼロ）
  • =453376598563

（ジャンプ数を取得するには、総数から減算します：10 60）

数を計算するための単純なPythonプログラム：

# I know Python doesn't do tail call elimination, but it's a good habit.
def choose(n, k, num=1, denom=1):
  return num/denom if k == 0 else choose(n-1, k-1, num*n, denom*k)

def f(digits, base=10):
  return choose(digits+base-1, base-1) + choose(digits+base, base) - digits*base - 1

昇順の数字：9桁を選択して、。で始まる数字をインクリメントします0。

10降順の数字：数字を左に埋めるために使用される数字があるふりをします。次に、10桁を選択して、。で始まる桁をデクリメントします10。次に、選択した10個の位置が連続していて、最後ではないすべての選択肢を削除します。これは、先頭に0が付いた数字シーケンスに対応します。

桁がすべて同じであるすべての数値は、降順と昇順の両方のアルゴリズムによって生成されるため、それらを減算する必要があります。

これらのアルゴリズムはすべて、数字の0が数字なしで書き込まれると見なしていることに注意してください。また、100以下のすべての数値は昇順または降順（あるいはその両方）であるため、それらについて心配する必要はありません。

于 2012-10-12T17:19:46.187 に答える
0

321 を下降として数えますか、それとも 000000321 をジャンプとして数えますか?

答えのヒント: 59 桁の昇順の数字の数は (69 choose 10) のようになります。数字のどのポイントが異なる数字の間にあるかを選択する必要があるからです。

于 2012-10-12T16:33:55.707 に答える