6

[要求]
给定一个字母表{0, 1, ... , k}, 0 ≤ k ≤ 9。我们说这个字母表上长度为 n 的单词是紧的，如果单词中的任何两个相邻数字不相差多于 1。输入是一系列行，每行包含两个整数 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 5 = 243

最后一位数字必须是 1，所以 3 4 = 81 将是“紧”的情况。

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

我错过了什么吗？

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

4

5 回答 5

7

通过概括这个问题来简化它

（对不起，我交换了k和的顺序n。）

如果你去掉一个紧数的最后一位，你会得到另一个紧数，它们的最后一位最多相差1.

假设您拥有最后一位c(n, k, l)的所有长度紧数字。那么长度和最后一位的紧数是。nln + 1lc(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
于 2013-09-04T00:14:02.497 回答
4

我的阅读与您的略有不同：据我了解，第一个数字是字母表的大小，第二个数字是必须考虑的字母表中单词的长度，所以：

4 1 => 100%

似乎是一个定义问题；可能的理由是，由于长度为 1 的单词中的数字没有任何邻居，因此它们与它们的差异不能超过 1，与字母表的大小无关，因此长度为 1 的单词根据定义被认为是“紧”的。

2 5 => 40.74074%

所以这是长度为 5 的单词，在三元（3 位）字母表 {0,1,2} 上。如您所见，有 3^5 个可能的此类词。不紧的词是那些（其中x表示“不关心”），如“xxx02”、“xxx20”、“xx02x”、“xx20x”、“x02xx”、“x20xx”、“02xxx”和“20xxx”其中有一个 2 与一个 0 相邻。这 8 种模式中的每一种都有 27 种变化（每种情况下有 3 个 x，每个可以有 3 个值中的任何一个），但当然有很多重叠：“02020”最终出现在其中的 3 个中。

所以，如果我理解正确，在没有任何捷径的情况下，解决方案必须是生成所有组合，检查每个组合中的相邻数字对（一旦你知道一个词不紧，你就可以尽早出错） ，然后计算紧词或非紧词的数量（要么给你另一个，因为你知道集合的总大小。

于 2013-09-03T23:59:58.823 回答
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
于 2013-09-04T00:15:00.183 回答
2

我们的问题是找到长度为 n 的紧单词的数量，即a[1 .. n]。下面是一个基于动态规划的解决方案。这个想法是假设我们有长度的答案i - 1，我们构造一个方程来计算长度的答案i。

LetC(i, d)是长度为 i 的紧单词的总数，即a[1 .. i]，最后一个数字a[i] = d，0 <= d <= k。观察到a[i - 1] - 1 <= a[i] <= a[i - 1] - 1（紧字的定义），我们有以下递归关系：

For i = 1: 
  C(1, d) = 1

For i > 1: 
  C(i, d) = 
    C(i - 1, 0) + C(i - 1, 1) -- if d == 0
    C(i - 1, k - 1) + C(i - 1, k) -- if d == k
    C(i - 1, d - 1) + C(i - 1, d) + C(i - 1, d + 1) -- otherwise

那么我们所追求的只是：

N(n) = C(n, 0) + C(n, 1) + ... C(n, k)

代码：

这是一个 nodejs 程序，经过测试可以在您的示例输入中生成相同的答案（它还不是动态编程，因为我没有缓存C(i, p)——有很多重复计算，但应该很容易做到）

// tight_words.js

var k = 2;
var n = 5;

function N(i) {
    var n = 0;

    for (d = 0; d <= k; ++d)
        n += C(i, d);

    return n;
}

function C(i, d) {
    if (i == 1)
        return 1;

    if (d == 0)
        return C(i - 1, 0) + C(i - 1, 1);

    if (d == k)
        return C(i - 1, k - 1) + C(i - 1, k);

    return C(i - 1, d - 1) + C(i - 1, d) + C(i - 1, d + 1);
}

var total = Math.pow(k + 1, n);
var c = N(n);
console.log('k = ' + k + ', n = ' + n);
console.log('==> percentage = ' + c / total);
于 2013-09-04T00:57:28.973 回答
0

根据WolframH的回答，我尝试了C++中示例输入的问题，它似乎有效。我还尝试了phython解决方案，该解决方案与示例输入配合良好。有趣的是，当我将输入增加到更大的数字（即 3 和 18）时，我在C++和phython中的两种解决方案都会挂起不确定的时间。

出了什么问题？

非常巧合的是，我昨天晚上恰好浏览了我的动态规划笔记，并阅读了有关加权独立集问题的内容。啊哈！我们做的工作比我们应该做的要多得多！在：

#include <math.h>
#include <iomanip>
#include <iostream>
using namespace std;

void get_tight_number(int base_max, int length)
{
  double result = 0;
  int _tight_numbers = 0;
  double total = pow(base_max + 1, length);
  for (int i = 0; i <= base_max; ++i)
  {
    _tight_numbers += get_tight_number_help(base_max, length, i);
  }
  result = 100 * _tight_numbers / total;
  cout << fixed << setprecision(5) << result << "\n";
}

int get_tight_number_help(int base_max, int length, int endwith)
{
  cout << "Length: " << length << "endwith: " << endwith << endl;
  if (length < 1 || endwith < 0 || endwith > base_max)
    return 0;
  if (length == 1)
  {
    return 1;
  } else 
  {
    return get_tight_number_help(base_max, length - 1, endwith)
         + get_tight_number_help(base_max, length - 1, endwith + 1)
         + get_tight_number_help(base_max, length - 1, endwith - 1);
  }
}

int main()
{
  get_tight_number(8, 7);
  return 0;
}

有了一堆prints正确的结果0.10130。如果我这样做，grep "endwith:" | wc -l我会得到7719，这意味着对于这个输入，辅助函数被调用了 7000 多次！为了知道它在其他输入上被调用了多少次，我得到了：

Input    #
8, 8     22254
8, 6     2682
8, 5     933

不是很好...我们正在做太多的重新计算。相反，我将bottom up参考数组的解决方案放在一起：

int** tight_number_bottom_up(int base_max, int length)
{
  int** result = new int*[base_max + 1];
  for (int i = 0; i < base_max + 1; ++i)
  {
    result[i] = new int[length];
  }
  //Ends with i, i.e., looping over them
  for (int j = 0; j < length + 1; ++j)
  {
    for (int i = 0; i < base_max + 1; ++i)
    {
      if (j == 0)
      {
        result[i][j] = 0;
      } else if (j == 1)
      {
        result[i][j] = 1;
      } else
      {
        int bigger = i == base_max ? 0 : result[i + 1][j - 1];
        cout << "bigger: " << bigger << endl;
        int smaller = i == 0 ? 0 : result[i - 1][j - 1];
        cout << "smaller: " << smaller << endl;
        result[i][j] = result[i][j - 1] + bigger + smaller;
      }
    }
  }
  return result;
}

我确信形成自下而上表的迭代次数是最大的(base_max + 1) * (length + 1)，很高兴我完成了写作，很高兴它给出了正确的结果。

后续问题（如果你还在我身边）

double9, 100对于像甚至这样的输入似乎还不够，9, 50我该怎么做才能使“更长”的双倍？

于 2013-09-04T14:33:51.820 回答