让我们说号码升如果它的数字会按升序排列。示例：1223469.位数降号去降序排列。示例：9844300.数字不是升序或降序，被称为跳跃。号码1至100不是跳跃。有多少跳的数字有没有从101到10 ^ 60？

Let's say number is "ascending" if its digits are going in ascending order. Example: 1223469. Digits of "descending" number go in descending order. Example: 9844300. Numbers that are not "ascending" or "descending", are called "jumping". Numbers from 1 to 100 are not "jumping". How many "jumping" numbers are there from 101 to 10^60?

推荐答案

我将介绍如何计算上升的数字，因为这是更容易。从去，还可以指望降那些，然后从数字的合计量中减去结合量，以补偿重复，由Ivan所示，或设计更复杂的方式来只计数直接跳号。

I'll describe how to count the ascending numbers, because that's easier. Going from that, you could also count the descending ones and then subtract the combined amount from the total amount of numbers, compensating for duplicates, as indicated by Ivan, or devise a more complex way to only count jumping numbers directly.

想想排序结束位数的数字。我们开始是1位长，这将是我们的列表编号

Think about the numbers sorted by ending digit. We start with numbers that are 1 digit long, this will be our list

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中，我们可以使用具有6个或更少的结尾的所有数字

To construct numbers with two digits ending with 6, we can use all numbers ending with 6 or less

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

写这些并排，可以看到如何很快计算出新值：

Writing these side by side, can see how to calculate the new values very quickly:

亚// Y，A和x已经计算previously X（A + X）

y a // y, a, and x have been computed previously 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程序

遍历一个这样的专栏中，我们可以直接产生新列的所有值，如果我们永远记住最后的计算。该扫描（）功能抽象了取一个元素正是这样的行为，并做一些计算与它最后的结果。

A simple Python program

Iterating over one such column, we can directly produce all values of the new column, if we always remember the last computation. The scan() function abstracts away exactly that behavior of taking one element, and do some computation with it and the last result.

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

产下一列，现在就这么简单：

Producing the next column is now as simple as:

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

为简单起见，我们用个位数的为出发点：

To make it simple, we use single digit numbers as starting point:

first_row = [1]*9

眼看我们总是需要反馈的新行的功能，可以再次使用扫描来做到这一点：

Seeing that we always need to feed back the new row to the function, can use scan again to do just that:

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]]

正如你所看到的，这给人的第一三排除了第一个。

As you can see, this gives the first three row apart from the first one.

因为我们想知道的所有号码的总和，我们可以做到这一点。当我们做1次迭代，我们得到了所有的数字上升到10 ^ 2，所以我们需要做59次迭代的所有数字，直到10 ^ 60：

Since we want to know the sum, of all numbers, we can do just that. When we do 1 iteration, we get all ascending numbers until 10^2, so we need to do 59 iterations for all numbers until 10^60:

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

有关的下降的数字，这是相当类似的：

For the descending numbers, it's quite similar:

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

老办法

想想这些数字是如何结束：

Old approach

Think about how the numbers end:

从10到99，我们有两个每个号码数字。

From 10 to 99, we have two digits per number.

有

1，在1 结束 2的结尾在2 3的结束3 4为此在4 5为此在5 6的结束6 在7为此在7 在8结尾的8 9结尾是9 1 that ends in 1 2 that end in 2 3 that end in 3 4 that end in 4 5 that end in 5 6 that end in 6 7 that end in 7 8 that end in 8 9 that end in 9

所有这些号码100到999充当prefixes为数字

All of these numbers act as prefixes for numbers from 100 to 999.

这是例子，也有结尾 3 三个数字：

An example, there are three numbers that end in 3:

13 23 33

有关这三个数字中，我们可以创建7升序编号：

For each of these three numbers, we can create seven ascending numbers:

133 134 135 136 137 138 139

这是很容易看到，这增加了三个数字为每个七个可能的结局位数。

It is easy to see, that this adds three numbers for each of the seven possible ending digits.

如果我们想延长4号结束，这个过程有异曲同工之处：目前，有4个数字的 4 结束。因此，对于每个这样的数字，我们可以创建6个新的升序编号。这意味着，将有一个附加的4对所有的六个可能的结局位数

If we wanted to extend numbers ending on 4, the process would be similar: Currently, there are 4 numbers ending on 4. Thus, for each such number, we can create 6 new ascending numbers. That means, that there will be an additional 4 for all of the six possible ending digits.

如果你已经明白了一切我已经写在这里，它应该很容易笼统地说，实施一种算法来计算所有这些数字。

If you have understood everything I've written here, it should be easy to generalize that and implement an algorithm to count all those numbers.