通过删除总和不为 17 的连续数字对来计算删除的数字

Question

以下是我的问题陈述：

你得到一个以 10 为基数的数字，你必须通过选择两个连续的数字并删除它们来完全删除它。但是这2个数字的和不应该是17。我们把重复上述操作完全删除的数字称为"Good".

示例：

9889 => 删除 88 得到 99
99 => 删除 99 以完全删除号码。结论：9889 好。注意：我们不能删除 98 或 89，因为这两个数字的总和是 17.

给定一个数 N(even)，你想找到 good N 位数模数 10^9 + 7 的数。也将包含前导零的 N 位数字也计入计数。

测试用例：

案例一：

Input: 2
Output: 98

案例二：

Input: 4
Output: 9926

案例三：

Input: 442
Output: 417551213

我试过使用各种代码解决这个问题，但无法得到结果。

Answer 1

尝试使用树来尝试所有可能的解决方案。真正的问题是，你必须预测哪些数字会保留下来，以及是否可以在总和为 17 的情况下删除它们。例如，如果您有 9823，您可以删除 23，但最后会被 98 阻止。

你可以试着建一棵树，每个分支都有可能被删除。如果所有分支都被阻止，您将返回到前一个节点

Answer 2

对于最后一个可能的坏状态的每个序列，必须有一个强制序列产生它。查看可能的位置 wild-cards（提供选择的数字当然是感兴趣的数字），并尝试找到一种模式。

在下面的例子中，为了对称，把9换成8； xs 是通配符：

输入长度 4，错误结果 9898：

输入长度 4，错误结果 98：

989x
98x8
9x98
x898

从上面两个我们可以清楚的看出为什么会得到输出，9926个好的4位数字。

输入长度 6，错误结果 9898:

输入长度 6，错误结果 9898 或 98:

9898xx
989xx8
98xx98
9xx898
xx9898

输入长度 6，错误结果 98：

989x9x
98x8x8
...
9x989x
...

等等

Python代码：

# https://gist.github.com/rougier/ebe734dcc6f4ff450abf
def binom(n,k):
  if not 0<=k<=n: return 0
  b=1
  for t in range(min(k,n-k)):
    b*=n; b//=t+1; n-=1
  return b

def f(n):
  bads = 0
  
  for k in range((n - 2) // 2 + 1):
    bads += 9**k * binom(n, k)
  
  return (10**n - 2 * bads) % (10**9 + 7) 
  
print(f(442)) # 417551213

Answer 3

不想破坏编码，但数字是否正确，可以通过回溯来完成。

    solve(9889);

public static void solve(int num) {
    try {
        solve(num, new LinkedList<>());
        System.out.println("Not found");
    } catch (FoundException fe) {
        System.out.printf("%d%n", num);
        fe.result.forEach(pair -> System.out.printf("-> %d, having deleted %d%n",
            pair.getKey(), pair.getValue()));
    }
}

private static class FoundException extends RuntimeException {
    public final List<Pair<Integer, Integer>> result;

    public FoundException(List<Pair<Integer, Integer>> result) {
        this.result = result;
    }
}

private static void solve(int num, LinkedList<Pair<Integer, Integer>> partialResult) {
    if (num == 0) {
        throw new FoundException(partialResult);
    }
    int tenPower = 1;
    while (num >= tenPower) {
        int n = num / tenPower;
        int del = n % 100;
        if (del % 10 + del / 10 != 17) {
            int n2 = (n / 100) * tenPower + (num % tenPower);
            partialResult.addLast(new Pair<>(n2, del));
            solve(n2, partialResult);
            partialResult.removeLast();
        }
        tenPower *= 10;
    }
}

问题的表述似乎是 int（31 位 unsigned int）就足够了。因此，我尝试使用 int 而不是数字列表。

另一个功能：使用 return 的异常从深层内部递归到顶层并得到肯定的结果。传统的方法是检查递归调用的结果。

注意：实际问题是数学题。

通过删除总和不为 17 的连续数字对来计算删除的数字

Count numbers deleted by removing consecutive digit pairs that don't sum to 17

java

algorithm

dynamic-programming