阅读程序2解析

关于limits

头文件#cinclude <limits>和第17行ret=numeric_limits<int>::max();
是为了获得整型int的最大值给到ret变量。


问题一:当输入为“7 3”时,第 19 行用来取最小值的 min 函数执行了 449 次。

下表为f(n, m)函数在不同参数下,对应min函数执行的次数。用f_m(n, m)表示。

m\n01234567
1f_m(0,1)=0f_m(1,1)=0f_m(2,1)=0f_m(3,1)=0f_m(4,1)=0f_m(5,1)=0f_m(6,1)=0f_m(7,1)=0
2f_m(0,2)=0f_m(1,2)=1f_m(2,2)=3f_m(3,2)=7f_m(4,2)=15f_m(5,2)=31f_m(6,2)=63f_m(7,2)=127
3f_m(0,3)=0f_m(1,3)=1f_m(2,3)=4f_m(3,3)=12f_m(4,3)=32f_m(5,3)=80f_m(6,3)=192f_m(7,3)=448

f_m(6,2)=6+f(5,2)+f(4,2)+f(3,2)+f(2,2)+f(1,2)=6+31+15+7+3+1=63
f_m(3,3)=3+f(2,3)+f(1,3)+f(1,2)+f(2,2)=3+4+1+1+3=12
f_m(7,3)=7+f(6,3)+f(0,2)+f(5,3)+f(1,2)+f(4,3)+f(2,2)+f(3,3)+f(3,2)+f(2,3)+f(4,2)+f(1,3)+f(5,2)+f(0,3)+f(6,2)=7+192+0+80+1+32+3+12+7+4+15+1+31+0+63=448


问题二:输出的两行整数总是相同的。

f()函数是递归函数,g()函数是递推函数,实现的功能是一样的。递归和递推可以认为是一种逆运算。


问题三:当 m 为 1 时,输出的第一行总为 n。

根据f()函数和g()函数的代码,当m=1时,输出n


问题四:g(n,m) 最为准确的时间复杂度分析结果为( )。

在g()函数里,有三个for循环,一个和m有关,一个和n有关,所以最后是O(n^2m)


问题五:当输入为“20 2”时,输出的第一行为( )。

for (int i = 1; i <= n; i++)
f(n,m)=ret = min(ret, max(f(n - i,m), f(i - 1, m - 1)) + 1);
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);
         }
m\n01234567891011121314151617181920
101234567891011121314151617181920
2012233344445555566666

f(20,2)
i=1, ret=min(ret, max(f(19,2), f(0,1))+1)=min(ret,max(6, 0)+1)=7
i=2, ret=min(ret, max(f(18,2), f(1,1))+1)=min(7, max(6, 1)+1)=7
i=3, ret=min(ret, max(f(17,2), f(2,1))+1)=min(7, max(6, 2)+1)=7
i=4, ret=min(ret, max(f(16,2), f(3,1))+1)=min(7, max(6, 3)+1)=7
i=5, ret=min(ret, max(f(15,2), f(4,1))+1)=min(7, max(5, 4)+1)=6
i=6, ret=min(ret, max(f(14,2), f(5,1))+1)=min(6, max(5, 5)+1)=6
i=7, ret=min(ret, max(f(13,2), f(6,1))+1)=min(6, max(5, 6)+1)=6
i=8, ret=min(ret, max(f(12,2), f(7,1))+1)=min(6, max(5, 7)+1)=6
i=9, ret=min(ret, max(f(18,2), f(1,1))+1)=min(6, max(6, 8)+1)=6
…………..ret都是6
i=20, ret=min(ret, max(f(0,2), f(19,1))+1)=min(6, max(0, 19)+1)=6


问题六:当输入为“100 100”时,输出的第一行为( )。

参见动态规划之扔鸡蛋问题

Scroll to Top