在 ruby 中从没有循环的范围编号中计算相同的包含编号

Question

示例：如果我有 1..100 范围内的数字并且我想计算所有包含 14 的数字，我会使用：

total = 0

(1..100).each do |x|
 if x.to_s.include?("14")
   total += 1
 end
end

puts "total : #{total}"

此代码有效，但如果数字范围太长，如 (1..1000000000) 或更长，如何执行此操作。当然这需要很长时间来计算总数。我的问题是如何在没有循环的情况下计算相同包含的数字？因为在我的情况下，我需要更快的方式来获得总数。

Answer 1

考虑范围：

def str_range(n)
  "1"..(10**n).to_s
end

我将解决查找范围内包含字符串 "14"（一次或多次）的字符串数的问题。¹ 一种直接的方法是:

def nbr_14s_brute_force(n)
  str_range(n).count { |s| s[/14/] }
end

nbr_14s_brute_force(2) #=>     1
nbr_14s_brute_force(3) #=>    20
nbr_14s_brute_force(4) #=>   299
nbr_14s_brute_force(5) #=>  3970 
nbr_14s_brute_force(6) #=> 49401

现在让我们寻找一种更有效的方法，借鉴离散概率论。

假设n = 2。那么：

str_range(2) #=> "1".."100"

由于 "14" 在范围 "1".."100" 中只出现一次，因此范围中只有一个（字符串）元素包含 "14".

现在让 cnt_first(n,i) 等于 str_range(2) 的元素数不包含 "14" 当十位等于 "i":

cnt_first(2,1) # => 9
cnt_first(2,i) # => 10

对于 0 <= i <= 9, i != 4。

此外，让 cnt(2) 表示范围 str_range(2) 中不包含 "14" 的字符串数。我们有：

cnt(2) = (0..9).reduce { |i| cnt_first(2,i) }
  #=> 99

由此可见，包含"14"的字符串的个数等于100 - cnt(2) #=> 1。

现在考虑 n #=> 3，其中：

str_range(3)
  #=> "1".."1000"

在此范围内的 1,000 个元素中，有多少元素不包含字符串 "14"?

我们可以直接剔除"1000"，因为"14"的单位位置没有零，所以我们只需要考虑范围"1".."999".

假设第一位（百位）的数字是1。那么不包含 "14" 的字符串必须在十列中包含 "4" 以外的字符。因此，以"1"开头且不包含"14"的两位数字符串的个数等于：

cnt_first(3,1) = cnt_first(2,0) + cnt_first(2,1) + cnt_first(2,2) +
                 cnt_first(2,3) + cnt_first(2,5) + cnt_first(2,6) +
                 cnt_first(2,7) + cnt_first(2,8) + cnt_first(2,9)  

               = (0..9).reduce { |i| cnt_first(2,i) } - cnt_first(2,4)
  #=> cnt(2) - cnt_first(2,4)
  # => 99 - 10 => 89

现在假设百位数字 (i) 不等于 1。那么：

cnt_first(3,i) = (0..9).reduce { |i| cnt_first(2,i) }
  # => cnt(2) => 99

所以

cnt(3) = 10 * cnt(2) - cnt_first(2,4)
  #=> 10 * 99 - 10 => 980

表示 "1"-"1000" 范围内有 1000 - 980 #=> 20 个数字不包含 "14"。早先的 "brute force" 计算证实了这一点。

可见计算cnt(4)的步骤与计算cnt(3)的步骤相同。

对于i = 1：

cnt_first(4,1) = cnt(3) - cnt_first(3,4)

对于i != 1：

cnt_first(4,i) = cnt(3) => 980

所以

cnt(4) = 10 * cnt(3) - cnt_first(3,4)
  #=> 10 * 980 - 99 => 9800 - 9701

所以对于 n => 4 有 10000 - 9701 #=> 299 个不包含 "14" 的字符串，这再次被前面的计算所证实。

如果reader不服气，这个可以很容易的用归纳法证明。

可以使用简单的递归方法来计算所需的结果：

def nbr_14s_smart(n)
  10**n - recurse(n).first
end

def recurse(n)
  if n == 2
    puts "2: 1"
    [99, 10]
  else 
    cnt, cnt4 = recurse(n-1)
    new_cnt, new_cnt4 = 10 * cnt - cnt4, cnt
    puts "#{ n }: #{ 10**n - new_cnt }"
    [new_cnt, new_cnt4]
  end
end

nbr_14s_smart(10)
  #  2: 1
  #  3: 20
  #  4: 299
  #  5: 3970
  #  6: 49401
  #  7: 590040
  #  8: 6850999
  #  9: 77919950
  # 10: 872348501
  #=> 872348501

^{¹Only minor modifications are required to replace "14" with the string representation of an
arbitrary two-digit number, but the exposition is easier to follow by hardwiring the string.}

在 ruby 中从没有循环的范围编号中计算相同的包含编号

Counting same containt number from range number without loop in ruby

ruby

algorithm

numbers

range