算法解决问题

Question

[要求]
给定的是字母{0,1,...,k},0≤k≤9.如果单词中的任何两个相邻数字没有相差,我们说这个字母表中长度为n的单词是紧的.输入是一系列行,每行包含两个整数k和n,1≤n≤100.对于每一行输入,输出长度为n的紧字的百分比超过字母{0,1, ...,k}有5个小数位数.

[输入]

4 1
2 5
3 5
8 7

[输出]

100.00000
40.74074
17.38281
0.10130

首先,我无法理解这个测验.例如,如果输入是2, 5.我不知道为什么答案是40.74074.

在这种情况下,如果它会"紧".中间数字必须为1.

例,

00000 00001 00002
00010 00011 00012
....

所以,

这里的所有情况都是,3 ⁵ = 243

最后一位必须是1,所以3 ⁴ = 81将是"紧"的情况.

所以,输出必须是81/243 = 0.33333333333333333 = 33.333333%

我错过了什么吗？

还有什么好算法可以解决这个问题？

Answer 1

通过概括来简化这个问题

(对不起,我换了k和的顺序n.)

如果你留下一个紧密数字的最后一位数字,你得到另一个紧密的数字,它们的最后一位数最多相差1.

假设您拥有最后一位c(n, k, l)数字的所有紧密n数字l.那么长的紧号码的数量n + 1和最后一位数字l是c(n + 1, k, l) = c(n, k, l - 1) + c(n, k, l) + c(n, k, l + 1).

基本情况很简单:n=1意味着一个紧密的数字,即c(1, k, l) = 1.

测试(Python):

def c(n, k, l):
    if l > k or l < 0:
        return 0
    if n == 1:
        return 1
    return sum(c(n - 1, k, i) for i in range(l - 1, l + 2))

def f(n, k):
    tight = sum(c(n, k, l) for l in range(k + 1))
    return tight / (k + 1) ** n

例子:

>>> print(f(1,4))
1.0
>>> print(f(4, 1))
1.0
>>> print(f(5, 2))
0.4074074074074074
>>> print(f(5, 3))
0.173828125
>>> print(f(7, 8))
0.0010129691411338857

对于非常大的数字,这会变得很慢,因为相同的数字会反复计算.这些可以通过在程序开头添加以下两行来缓存("memoized")(第二行c(n, k, l)用缓存装饰以下函数):

import functools
@functools.lru_cache()

例:

>>> f(100,9)
1.0051226793648084e-53

Answer 2

下面是一些 ruby​​ 代码，其输出与示例数据匹配：

#!/usr/bin/env ruby

def isTight( x )
  for i in (1..x.length-1)
    return false if 1 < (x[i].to_i-x[i-1].to_i).abs
  end
  return true
end

def getWord( x, base, n )
  retval = []
  1.upto(n) do
    x, r = x.divmod(base)
    retval.unshift r
  end
  retval.join
end

def percent( k, n )
  nwords = (k+1) ** n
  count = 0
  for i in (0..nwords-1)
    word = getWord( i, k+1, n )
    count += 1 if isTight( word )
  end
  return 100.0 * count / nwords
end

STDIN.each_line do |line|
  line.chomp!
  puts line+' '+percent(*line.split(' ').map { |i| i.to_i }).to_s
end

这接受 4 行

4 1
2 5
3 5
8 7

作为输入和输出

4 1 100.0
2 5 40.74074074074074
3 5 17.3828125
8 7 0.10129691411338856

（抱歉没有小数点后 5 位）

编辑：在实际实践中，您肯定会希望使用 WolframH 的递归解决方案，为了完整性起见，将其包含在此处：

#!/usr/bin/env ruby

$cache = Hash.new
def count( k, n, last )
  key = "#{k}:#{n}:#{last}"
  return $cache[key] if $cache.has_key?(key)
  return 0 if !(0 <= last && last <= k) # last digit must be in range
  return 1 if n == 1 # single digit numbers are always tight
  return $cache[key] = (-1..1).inject(0) { |sum,i| sum + count(k,n-1,last+i) }
end

def percent( k, n )
  ntight = (0..k+1).inject(0) { |sum,last| sum + count(k,n,last) }
  return 100.0 * ntight / (k+1)**n
end

puts percent( 1, 4 )
puts percent( 2, 5 )
puts percent( 3, 5 )
puts percent( 8, 7 )
puts percent( 9, 100 )

使用 $cache，它在 x86_64 Intel(R) Core(TM) i3-3240 CPU @ 3.40GHz 上运行得非常快：

$ time ./tight.rb
100.0
40.74074074074074
17.3828125
0.10129691411338856
1.0051226793648083e-51

real    0m0.016s
user    0m0.010s
sys     0m0.005s