基础知识

2、

【NOIP 2018 普及组初赛 q10】下面的故事与（ ）算法有着异曲同工之妙。

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”
A. 枚举   B. 递归   C. 贪心   D. 分治  

编程练习

阅读题

1、

【CSP 2020 入门组第一轮 q06】设A是介个实数的数组，考虑下面的递归算法：

            XYZ (A[1..n])
            1.  if n= 1 then return A[1]
            2.   else temp ← XYZ (A[l..n-1])
            3.         if temp < A[n]
            4.         then return temp
            5.         else return A[n]

请问算法XYZ的输出是什么？（）。
A. A数组的平均   B. A数组的最小值  
C. A数组的中值   D. A数组的最大值  

2、

【CSP 2020 入门组第一轮 q18】阅读程序(程序输入不超过数组或字符串定义的范围)

#include <algorithm>
#include <iostream>
using namespace std;                     
                                         
int n;                                   
int d[50][2];                            
int ans;                                 
                                        
void dfs(int n, int sum) {               
  if (n == 1) {                            
    ans = max(sum, ans);           
    return;                                   
  }                                        
  for (int i = 1; i < n; ++i) {            
    int a = d[i - 1][0], b = d[i - 1][1];  
    int x = d[i][0], y = d[i][1];            
    d[i - 1][0] = a + x;                     
    d[i - 1][1] = b + y;                     
    for (int j = i; j < n - 1; ++j)            
      d[j][0] = d[j + 1][0], d[j][1] = d[j + 1][1];
    int s = a + x + abs(b - y);              
    dfs(n - 1, sum + s);                    
    for (int j = n - 1; j > i; --j)          
      d[j][0] = d[j - 1][0], d[j][1] = d[j - 1][1];
    d[i - 1][0] = a, d[i - 1][1] = b;        
    d[i][0] = x, d[i][1] = y;                
  }                                        
}                                        
                                       
int main() {                             
  cin >> n;                                
  for (int i = 0; i < n; ++i)              
  cin >> d[i][0];
  for (int i = 0; i < n;++i)
     cin >> d[i][1];
  ans = 0;
  dfs(n, 0);
  cout << ans << endl;
  return 0;
}

假设输入的n是不超过50的正整数，d[i][0]、d[i][i]都是不超过10000的正整数，完成下面的判断题和单选题：

1）若输入 n 为 0,此程序可能会死循环或发生运行错误。（ ）
A. 正确   B. 错误  

2）若输入 n 为 20,接下来的输入全为 0，则输出为 0。（ ）
A. 正确   B. 错误  

3）输出的数一定不小于输入的 d[i][0] 和 d[i][l] 的任意一个。（ ）
A. 正确   B. 错误  

4）若输入的 n 为 20,接下来的输入是 20 个 9 和 20 个 0,则输出为（ ）。
A. 1890   B. 1881   C. 1908   D. 1917  

5）若输入的 n 为 30,接下来的输入是 30 个 0 和 30 个 5,则输出为（ ）。
A. 2000   B. 2010   C. 2030   D. 2020  

6）（4分）若输入的 n 为 15，接下来的输入是 15 到 1，以及 15到1，则输出为（ ）。
A. 2440   B. 2220   C. 2240   D. 2420  

备注：上题第6小问的计算可能用到平方和公式

3、

【NOIP 2018 普及组初赛 q20】阅读程序写结果:

#include <iostream>
using namespace std;
int n, m;

int findans(int n, int m) {
    if (n == 0) return m;
    if (m == 0) return n % 3;
    return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
}

int main(){
    cin >> n >> m;
    cout << findans(n, m) << endl;
    return 0;
}

输入：5 6

4、

【NOIP 2017 普及组初赛 q24】阅读程序写结果:

#include<iostream>
using namespace std;
int g(int m, int n, int x)
{
    int ans = 0;
    int i;
    if (n == 1)
        return 1;
    for (i = x; i <= m / n; i++)
        ans += g(m - i, n - 1, i);
    return ans;
}
int main()
{
    int t, m, n;
    cin >> m >> n;
    cout << g(m, n, 0) << endl;
    return 0;
}

输入：7 3
输出：_____