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 结尾的两位数字，我们可以使用所有以 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 程序

迭代一个这样的列，如果我们总是记住最后一次计算，我们可以直接产生新列的所有值。该scan()函数准确地抽象出获取一个元素的行为，并用它和最后一个结果进行一些计算。

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

生成下一列现在很简单：

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

为简单起见，我们使用单个数字作为起点：

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

如您所见，这给出了前三行与第一行不同。

由于我们想知道所有数字的总和，我们可以做到这一点。当我们进行 1 次迭代时，我们会得到所有升序的数字，直到 10^2，因此我们需要对所有数字进行 59 次迭代，直到 10^60：

>>> 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 结尾的 1
  • 2 以 2 结尾
  • 以 3 结尾的 3
  • 4 以 4 结尾
  • 5 以 5 结尾
  • 6 以 6 结尾
  • 以 7 结尾的 7
  • 8 以 8 结尾
  • 以 9 结尾的 9

所有这些数字都充当从 100 到 999 的数字的前缀。

例如，有三个以 结尾的数字3：

  • 13
  • 23
  • 33

对于这三个数字中的每一个，我们可以创建七个升序数字：

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

很容易看出，这为七个可能的结束数字中的每一个添加了三个数字。

如果我们想扩展以 4 结尾的数字，过程将类似：目前，有 4 个以 . 结尾的数字4。因此，对于每个这样的数字，我们可以创建 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 选择 10），因为您必须选择数字中的哪些点位于不同数字之间。

于 2012-10-12T16:33:55.707 回答