#cspjc2022y2. 2022csp-j初赛程序阅读2

2022csp-j初赛程序阅读2

2022csp-j初赛程序阅读2

判断题 1.5 分,选择题 3 分

1.第二题

#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均是不超过100 的正整数,完成下面的判断题和单选题:

判断题

1.当输入为 7 3 时,第 19 行用来取最小值的 min 函数执行了 449 次。( ) {{ select(1) }}

  • √
  • ×

2.输出的两行整数总是相同的。( ) {{ select(2) }}

  • √
  • ×

3.当 m为 1 时,输出的第一行总为 n。( ) {{ select(3) }}

  • √
  • ×

选择题

4.算法 g(n,m)最为准确的时间复杂度分析结果为。( ) {{ select(4) }}

  • O(n3/2n^{3/2}m)
  • O(nm)
  • O(n2m)O(n^2m)
  • O(nm2)O(nm^2)

5.算法 g(n,m)最为准确的时间复杂度分析结果为。( ) {{ select(5) }}

  • 4
  • 5
  • 6
  • 20

6.(4 分) 当输入 100 100 时,输出的第一行为( )。 {{ select(6) }}

  • 6
  • 7
  • 8
  • 9