ruby – Prime数字和

发布时间：2020-12-17 03:50:43 所属栏目：百科来源：网络整理

导读：所以我在HackerRank上做了一个编程挑战,以帮助我建立自己的技能. (不,这不是面试！我遇到的问题是Prime数字总和.(完整描述： https://www.hackerrank.com/challenges/prime-digit-sums/problem)基本上给出一个值n,我要找到符合以下三个标准的所有n位数字的数

所以我在HackerRank上做了一个编程挑战,以帮助我建立自己的技能. (不,这不是面试！我遇到的问题是Prime数字总和.(完整描述： https://www.hackerrank.com/challenges/prime-digit-sums/problem)基本上给出一个值n,我要找到符合以下三个标准的所有n位数字的数字：

>每3个连续数字总和为素数
>每4个连续数字总和为素数
>每5个连续数字总和为素数

请参阅链接以获取详细信息……

我有一个有效的基本功能,问题是当n变得足够大时会破坏：

#!/bin/ruby
require 'prime'

def isChloePrime?(num)
    num = num.to_s
    num.chars.each_cons(5) do |set|
        return false unless Prime.prime?(set.inject(0) {|sum,i| sum + i.to_i})
    end
    num.chars.each_cons(4) do |set|
        return false unless Prime.prime?(set.inject(0) {|sum,i| sum + i.to_i})
    end
    num.chars.each_cons(3) do |set|
        return false unless Prime.prime?(set.inject(0) {|sum,i| sum + i.to_i})
    end
    return true
end

def primeDigitSums(n)
    total = 0
    (10**(n-1)..(10**n-1)).each do |i| 
       total += 1 if isChloePrime?(i)
    end
    return total
end

puts primeDigitSums(6) # prints 95 as expected
puts primeDigitSums(177779) # runtime error

如果有人能指出我正确的方向,那将是非常棒的.不一定要找“这里是答案”.理想情况下会喜欢“尝试使用此功能…”.

这里更新版本2：

#!/bin/ruby
require 'prime'

@primes = {}

def isChloePrime?(num)
  num = num.to_s
  (0..num.length-5).each do |i|
    return false unless @primes[num[i,5]]
  end
  return true
end

def primeDigitSums(n)
  total = 0
  (10**(n-1)...(10**n)).each do |i|
    total += 1 if isChloePrime?(i)
  end
  return total
end

(0..99999).each do |val|
    @primes[val.to_s.rjust(5,"0")] = true if [3,4,5].all? { |n| val.digits.each_cons(n).all? { |set| Prime.prime? set.sum } }
end

解决方法

我认为每个非负整数是有效的,如果其数字的3,4和5的每个序列的总和形成素数.

构造一组相关的素数

我们需要确定3位,4位和5位数的位数是否为素数.因此,最大数量不会大于5 * 9.构造一组素数(一组而不是一个数组来加速查找)很方便.

require 'prime'
require 'set'

primes = Prime.each(5*9).to_set
  #=> #<Set: {2,3,5,7,11,13,17,19,23,29,31,37,41,43}>

构造转换哈希

valid1是一个哈希,其密钥都是1位数字(所有这些都是有效的).键0的值是所有1位数字的数组.对于1-9,值是通过在键上附加数字而获得的2位数字的数组(所有这些数字都有效).总的来说,这些值包括所有2位数字.

valid1 = (0..9).each_with_object({}) { |v1,h|
  h[v1] = 10.times.map { |i| 10 * v1 + i } }

valid2是一个哈希,它将2位数字(全部有效)映射到有效3位数字的数组,这些数字是通过将数字附加到2位数字而获得的.总的来说,这些值包括所有有效的3位数字.所有值都是非空数组.

valid2 = (10..99).each_with_object({}) do |v2,h|
  p = 10 * v2
  b,a = v2.digits
  h[v2] = (0..9).each_with_object([]) { |c,arr|
    arr << (p+c) if primes.include?(a+b+c) }
end

请注意,Integer#digits首先返回一个数字为1的数组.

valid3是一个散列,它将有效的3位数字映射到有效的4位数字数组,这些数字是通过在数字上附加数字而获得的.总的来说,这些值包括所有有效的4位数字. 303个值中的152个是空数组.

valid3 = valid2.values.flatten.each_with_object({}) do |v3,h|
  p = 10 * v3
  c,b,a = v3.digits
  h[v3] = (0..9).each_with_object([]) do |d,arr|
    t = b+c+d
    arr << (p+d) if primes.include?(t) && primes.include?(t+a)
  end
end

valid4是一个哈希,它将有效的4位数字映射到有效4位数字的数组,这些数字是通过在键上附加一个数字并删除键的第一个数字而获得的. valid5.values.flatten.size#=> 218是有效5位数的数字. 280个值中的142个是空数组.

valid4 = valid3.values.flatten.each_with_object({}) do |v4,h|
  p = 10 * v4
  d,c,a = v4.digits
  h[v4] = (0..9).each_with_object([]) do |e,arr|
    t = c+d+e
    arr << ((p+e) % 10_000) if primes.include?(t) &&
      primes.include?(t += b) && primes.include?(t + a)
  end
end

我们将这四个哈希合并为一个哈希@transition.不再需要前哈希. @transition有294个键.

@transition = [valid1,valid2,valid3,valid4].reduce(:merge)
  #=> {0=>[0,1,2,6,8,9],#    1=>[10,12,14,15,16,18,19],#    ...
  #    9=>[90,91,92,93,94,95,96,97,98,99],#    10=>[101,102,104,106],11=>[110,111,113,115,119],#    ...
  #    97=>[971,973,977],98=>[980,982,986],99=>[991,995],#    101=>[1011],102=>[1020],104=>[],106=>[],110=>[1101],#    ...
  #    902=>[9020],904=>[],908=>[],911=>[9110],913=>[],917=>[],#    1011=>[110],1020=>[200],1101=>[],1110=>[],1200=>[],#    ...
  #    8968=>[],9020=>[200],9110=>[],9200=>[]}

过渡方法

这是每次n(位数)加1时用于更新计数的方法.

def next_counts(counts)
  counts.each_with_object({}) do |(k,v),new_valid|
    @transition[k].each do |new_v|
      (new_valid[new_v] = new_valid[new_v].to_i + v) if @transition.key?(k)
    end
  end
end

prime_digit_sum方法

def prime_digit_sum(n)
  case n
  when 1 then 10
  when 2 then 90
  when 3 then @transition.sum { |k,v| (10..99).cover?(k) ? v.size : 0 }
  else
    counts = @transition.select { |k,_| (100..999).cover?(k) }.
                         values.flatten.product([1]).to_h   
    (n - 4).times { counts = next_counts(counts) }
    counts.values.sum % (10**9 + 7)
  end
end

请注意,对于n = 4,散列计数具有有效4位数字的键和全部等于1的值：

counts = @transition.select { |k,_| (100..999).cover?(k) }.
  values.flatten.product([1]).to_h   
  #=> {1011=>1,1020=>1,1101=>1,1110=>1,1200=>1,2003=>1,2005=>1,#    ...
  #    8902=>1,8920=>1,8968=>1,9020=>1,9110=>1,9200=>1}

counts.size
  #=> 280

如图所示,对于n> = 5,每当n递增1时更新计数.值的总和等于有效的n位数的数量.

由每个有效的n位数字的后四位数组成的数字是计数键之一.每个键的值是一个数字数组,包括通过在键上附加数字而生成的所有有效(n 1)数字的最后四位数字.

例如,考虑n = 6的计数值,发现如下.

counts
  #=> {1101=>1,2003=>4,2005=>4,300=>1,302=>1,304=>1,308=>1,320=>1,#    322=>1,326=>1,328=>1,380=>1,382=>1,386=>1,388=>1,500=>1,#    502=>1,506=>1,508=>1,560=>1,562=>1,566=>1,568=>1,1200=>7,#    3002=>9,3020=>4,3200=>6,5002=>6,9200=>4,200=>9,1020=>3,20=>3,#    5200=>4,201=>2,203=>2,205=>2,209=>2,5020=>2,9020=>1}

考虑2005年的关键并注意到

@transition[2005]
  #=> [50,56]

我们看到有4个有效的6位数字,其后4位数字是2005年,对于这4个数字中的每一个,通过添加数字0和6产生有效数字,得到最后5位数为20050的数字然而,我们只需要保留最后四位数字0050和0056,它们是数字50和56.因此,当重新计算n = 7的计数时 – 称之为计数7 – 我们在两个计数中加4 [7] ]和计数7 [56].计数的其他密钥k(对于n = 6)可以使得@transition [k]具有包括50和56的值,因此它们也将对计数7 [50]和计数7 [50]有贡献.

选择性结果

让我们尝试它的各种n值

puts "digits  nbr valid*  seconds"
[1,20,50,100,1_000,10_000,40_000].each do |n|
  print "%6d" % n
  t = Time.now
  print "%11d" % prime_digit_sum(n)
  puts "%10f" % (Time.now-t).round(4)
end
puts "n* modulo (10^9+7)"

digits  nbr valid*  seconds
     1         10  0.000000
     2         90  0.000000
     3        303  0.000200
     4        280  0.002200
     5        218  0.000400
     6         95  0.000400
    20      18044  0.000800
    50  215420656  0.001400
   100  518502061  0.002700
  1000  853799949  0.046100
 10000  590948890  0.474200
 40000  776929051  2.531600

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!