主页 / coding / 问题 / 77810560
Accepted
ABGR
Asked: 2024-01-13 14:50:02 +0800 CST

在 n 步内到达四面体的顶点 d

  • 772

我正在解决这个问题：

给定一个具有顶点 A、B、C 和 D 的四面体。一只蚂蚁站在顶点 D 处。蚂蚁不会闲着。它将沿着四面体的某些边缘不断从一个顶点移动到另一个顶点。你的任务是计算蚂蚁从初始顶点 D 到自身的路径数，正好是 n 步。

所以对于输入 2 输出：3

我能够按照以下方式使用递归轻松解决这个问题。但对于大输入（例如 15）来说，由于其时间复杂度，它似乎效率不高。

这可以通过动态编程来解决，但我在当前的方法中没有看到任何记忆范围。也许我需要改变方法。所以感谢任何帮助。

我想用递归+记忆来解决它 

var count = 0;
function recursion(n, arr=['d']){
    if(n <=1) return 0;
  
  if(arr.length === n+1 && arr[arr.length-1] ==='d'){
    console.log(arr.join(" -> "))
    count++;
    return;
  }

  if(arr.length > n+1) return;

  for(let el of ['a', 'b', 'c', 'd']){
    if(arr[arr.length-1] != el){
       recursion(n, [...arr, el]);
    }
  }
}
recursion(3)

console.log(count);

algorithm

1 个回答

  1. Best Answer

    您确实可以在这里使用记忆功能。

    首先我们来分析一下递归关系。

    定义：

    • 𝑆 𝑛是从顶点到自身的长度为 𝑛 的路径数。

    • 𝐷 𝑛是从一个顶点到选定的不同顶点的长度为 𝑛 的路径数。我们选择哪个目标顶点并不重要，因为四面体是完全对称的。

    现在的递归关系：

    要获取到原始顶点 (𝑆 𝑛 ) 的长度为 𝑛 的路径数量，您可以从三个邻居中选择一个邻居，然后计算从那里回到起始顶点的（较短）路径的数量，由 𝐷 给出。所以：

          𝑆 𝑛 = 3𝐷 𝑛−1

    要获取到不同顶点 (𝐷 𝑛 )的长度为 𝑛 的路径数，您可以选择该邻居并计算从该顶点到自身的路径数（短 1 步），或者您可以选择其他两个邻居之一并计算从那里到目标顶点的路径数（短 1 步）。所以：

          𝐷 𝑛 = 𝑆 𝑛−1 + 2𝐷 𝑛−1

    后一个方程可以通过代入此递推关系来展开：

          𝐷 𝑛 = 3𝐷 𝑛−2 + 2𝐷 𝑛−1

    当我们引用 𝑛−2 时，我们至少需要两个基本情况：

    • 𝐷 0 = 0（没有大小为 0 的路径将您带到另一个顶点）
    • 𝐷 1 = 1（从一个顶点到另一个顶点有一条大小为 1 的路径）

    执行

    由于我们对𝐷有很好的递归关系，我们可以首先实现一个函数，该函数返回从一个顶点到另一个顶点的路径数。然后使用第一个关系将原始查询（指向同一顶点的路径数）转换为该问题：

    // Memoize the number of paths from one vertex to a different one
const memo = new Map().set(0, 0).set(1, 1);

function numPathsToOther(size) {
    let result = memo.get(size);
    if (result === undefined) {
        result = 3*numPathsToOther(size-2) + 2*numPathsToOther(size-1);
        memo.set(size, result);
    }
    return result;
}

function numPathsToSelf(size) {
    return size ? 3 * numPathsToOther(size - 1) : 1;
}

// Demo runs for the first few path-sizes:
for (let i = 0; i <= 10; i++) {
    console.log(i, numPathsToSelf(i));
     console.log((3*0^i-(-4)^i)/4)
}

    例子

    假设我们像您一样将四个顶点标记为 𝑎、𝑏、𝑐 和 𝑑，并且 𝑛 为 3。我们想知道在顶点 𝑎 开始和结束的大小为 𝑛 的路径的数量。

    可以通过三种方式开始该路径：𝑎→𝑏、𝑎→𝑐 或𝑎→𝑑。让我们采取𝑎→𝑏。现在我们需要知道有多少条大小为 2 的路径从 𝑏 开始并以 𝑎 结束。

    在这里，让我们暂停一下。你会发现𝑎和𝑏没有什么特别的。它们只是邻居，但事情来了：四面体中的任何两个顶点都是邻居，并且彼此之间的关系与 𝑎 到 𝑏 相同。所以我们可以将这种情况概括为“从一个顶点到另一个顶点的路径数”！

    对于该路径的大小需要为 2 的情况，从 𝑏 出发并以 𝑎 结尾的可能路径只有两种：要么经过 𝑐，要么经过 𝑑。

    现在我们回到最初的情况。我们说过从 𝑎 返回到 𝑎 的大小为 3 的路径可以首先经过 𝑏，现在我们知道从 𝑏 有两种可能性。但我们也可以从 𝑎 到 𝑐，或者从 𝑎 到 𝑑。由于四面体是完全对称的，我们可以立即得出结论，这两个替代方案分别代表 2 条路径。所以我们总共找到了 3x2=6 条路径。

    这个小分析表明，了解从某个顶点到另一个顶点的路径数量是有用的。

    封闭式

    递推关系有解。oeis.org提供了：

    沿着基于顶点的四面体的边缘长度为 n 的闭合路径的数量。

    公式 a(n) = (3^n + (-1)^n*3)/4。

    for (let i = 0; i <= 10; i++) {
    console.log(i, (3**i + (-1)**i*3)/4)
}

    • 1

相关问题