欧拉计划 发表于 2016-8-21 01:04:18

题目113：一个googol（10^100）以下有多少数字不是跳跃数？

Non-bouncy numbers

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

As n increases, the proportion of bouncy numbers below n increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below .

How many numbers below a googolare not bouncy?

题目：

如果一个数的每一位都大于等于前一位，则称其为递增数，例如 134468。

类似的，如果一个数的每一位都小于等于前一位，则称其为递减数，例如 66420。

如果一个正整数既不是递增数也不是递减数，则称其为一个“跳跃数”，例如 155349。

随着 n 的增加，小于 n 的跳跃数的比例不断增加，以至于到了一百万以下的数中只有 12951 个不是跳跃数， 以下只有 277032 个数不是跳跃数。

一个googol以下的数中有多少个不是跳跃数？

迷雾少年 发表于 2016-8-31 17:34:49

googol是啥意思

jerryxjr1220 发表于 2017-6-6 21:28:03

from math import factorial as f
print(sum() + sum() - 10*100)
51161058134250

永恒的蓝色梦想 发表于 2019-9-8 09:52:58

本帖最后由 永恒的蓝色梦想 于 2021-7-8 19:13 编辑

C++ 2ms#include<iostream>
using ulong = unsigned long long;


template<size_t size>
constexpr ulong sum(ulong(&array))noexcept {
    ulong result = 0;

    for (ulong i : array) {
      result += i;
    }

    return result;
}


template<size_t size>
constexpr void accumulate(ulong(&array)) noexcept { //累加函数，参考 Python 的 itertools.accumulate
    for (size_t index = 1; index < size; index++) {
      array += array;
    }
}


constexpr ulong non_bouncy(size_t digits)noexcept {
    switch (digits) {
    case 0:
    case 1:
      return 0;
    }

    ulong array[]{ 1,2,3,4,5,6,7,8,9,9 };
    ulong result =
      9 //1位数既不是递增数也不是递减数
      + sum(array) * 2 - array //递增数和递减数的和
      - --digits * 9 //每位都相同的数字，既属于递增数又属于递减数
      ;

    while (--digits) {
      accumulate(array);
      result += sum(array) * 2 - array;//递增数和递减数的和
    }

    return result;
}


int main() {
    using namespace std;
    ios::sync_with_stdio(false);
    cout << non_bouncy(100) << endl;
    return 0;
}

guosl 发表于 2022-2-10 11:45:20

本帖最后由 guosl 于 2022-2-10 11:48 编辑

本题所涉及的数比较大故在程序中用了大数库mpir。
/*
答案：51161058134250
耗时：0.000191秒
*/
#include <iostream>
#include <mpir.h>
#include <omp.h>
using namespace std;

int f;//f为长度是i且最后一个数的值是j的严格递增序列的个数
int g;//g为长度是i且最后一个数的值是j的严格递减序列的个数

int main(void)
{
double d = omp_get_wtime();
for (int i = 1; i < 10; ++i)
{
    f = 1;//长度为1的序列只有一个
    g = 1;//长度为1的序列只有一个
}
for (int i = 2; i < 10; ++i)
{
    for (int j = 1; j < 10; ++j)
    {
      for (int k = 1; k < j; ++k)
      f += f;
    }
}
for (int i = 2; i <= 10; ++i)
{
    for (int j = 1; j < 10; ++j)
    {
      for (int k = 1; k <= j; ++k)
      g += g;
    }
}
mpz_t zSum, t;
mpz_inits(zSum, t, 0);
mpz_set_ui(zSum, 99);
for (int w = 3; w <= 100; ++w)//对数字位数进行枚举
{
    //计算递增数的个数
    for (int k = 1; k < 9; ++k)//枚举跳跃点的个数
    {
      if (k > w - 1)
      break;
      mpz_bin_uiui(t, w - 1, k);//跳跃点的选取方式数
      int s = 0;
      //此时跳跃数组的长度为k+1
      for (int a = 1; a < 10; ++a)//计算具体的递增数组的选取方式数
      s += f;
      mpz_mul_si(t, t, s);
      mpz_add(zSum, zSum, t);
    }
    //计算递减数的个数
    for (int k = 1; k <= 9; ++k)//枚举跳跃点的个数
    {
      if (k > w - 1)
      break;
      mpz_bin_uiui(t, w - 1, k);//跳跃点的选取方式数
      int s = 0;
      //此时跳跃数组的长度为k+1
      for (int a = 0; a < 10; ++a)//计算具体的递减数组的选取方式数
      s += g;
      mpz_mul_si(t, t, s);
      mpz_add(zSum, zSum, t);
    }
    mpz_add_ui(zSum, zSum, 9);//加上跳跃数为0的数的个数
}
d = omp_get_wtime() - d;
gmp_printf("%Zd\n%lf\n", zSum, d);
mpz_clears(zSum, t, 0);
return 0;
}
页: [1]
查看完整版本: 题目113：一个googol（10^100）以下有多少数字不是跳跃数？