f(n) = 1 n < 16 f(n) = MIN(f(n-4) + 1, f(n-8)+1, f(n-16)+1) 写出js代码，并记录map[n]详细数据

以下是使用 JavaScript 实现给定递归式的代码：

const map = { 0: 0, 1: 1, 2: 2, 3: 3, 4: 1, 5: 2, 6: 3, 7: 4, 8: 1, 9: 2, 10: 3, 11: 4, 12: 2, 13: 3, 14: 4, 15: 5 };

function f(n) {
  if (n < 16) {
    return map[n];
  }
  const a = f(n - 4) + 1;
  const b = f(n - 8) + 1;
  const c = f(n - 16) + 1;
  const res = Math.min(a, b, c);
  map[n] = res;
  return res;
}

在这个实现中，我们使用一个名为 `map` 的对象来存储已经计算过的值。如果 `n` 小于 16，那么我们可以直接查找 `map` 中对应的值并返回。否则，我们按照递归式计算 `f(n)` 并将结果存储在 `map` 中，最后返回计算结果。

相关问题

f(n) = 1 n < 16 f(n) = MIN(f(n-4) + 1, f(n-8)+1, f(n-16)+1) 写出程序

可以使用递归的方式实现这个函数：

def f(n):
    if n < 16:
        return 1
    else:
        return min(f(n-4)+1, f(n-8)+1, f(n-16)+1)

但是这个函数可能会出现大量重复计算，因此可以使用动态规划来优化。我们可以使用一个数组来记录已经计算过的 f 值，避免重复计算：

def f(n):
    if n < 16:
        return 1
    
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    dp[1:16] = [1] * 15
    
    for i in range(16, n+1):
        dp[i] = min(dp[i-4]+1, dp[i-8]+1, dp[i-16]+1)
    
    return dp[n]

这样就可以避免重复计算，提高程序效率。

#include <algorithm> #include <iostream> #include <limits> using namespace std; const int MAXN = 105; const int MAXK = 105; int h[MAXN][MAXK]; int f(int n, int m) { if (m == 1) return n; if (n == 0) return 0; int ret = numeric_limits<int>::max(); for (int i = 1; i <= n; i++) ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1); return ret; } int g(int n, int m) { for (int i = 1; i <= n; i++) h[i][1] = i; for (int j = 1; j <= m; j++) h[0][j] = 0; for (int i = 1; i <= n; i++) { for (int j = 2; j <= m; j++) { h[i][j] = numeric_limits<int>::max(); for (int k = 1; k <= i; k++) h[i][j] = min( h[i][j], max(h[i - k][j], h[k - 1][j - 1]) + 1); } } return h[n][m]; } int main() { int n, m; cin >> n >> m; cout << f(n, m) << endl << g(n, m) << endl; return 0; }

这段代码的功能是计算将 n 个元素划分成 m 个部分所需的最小代价，代价的计算方式是每个部分的代价是该部分中元素的最大值加1，且要求每个部分中至少有一个元素。

其中，函数 f(n, m) 使用递归的方式计算最小代价，函数 g(n, m) 使用动态规划的方式计算最小代价，并且使用一个二维数组 h 来存储已经计算过的值，避免重复计算。

在 main 函数中，先读入 n 和 m，然后分别调用 f(n, m) 和 g(n, m) 计算最小代价，并将结果输出。