GESP 5级客观题｜贪心算法｜课后作业

考试频率：高频。本卷共 6 题。

1. 贪心算法是一种可以应用于所有问题的通用解决方案。

   {{ select(1) }}

• 对
• 错

2. 下面C++代码用于求斐波那契数列，该数列第$1$、$2$ 项为 $1$ ，以后各项均是前两项之和。函数fibo()属于（ ）。

   int fibo(int n) {
   	if (n <= 0)
   		return 0;
   	if (n == 1 || n == 2)
   		return 1;
   	int a = 1，b = 1, next;
   	for (int i = 3; i <= n; i++) {
   		next = a + b;
   		a = b;
   		b = next;
   	}
   	return next;
   }
   
   {{ select(2) }}
   
   

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

3. 下面C++代码用于将输入金额换成最少币种组合方案，其实现算法是 （ ）。

   #include <iostream>
   using namespace std;
   #define N_COINS 7
   int coins[N_COINS] = {100, 50, 20, 10, 5, 2, 1}; //货币面值，单位相同
   int coins_used[N_COINS];
   void find_coins(int money) {
   	for (int i = 0; i < N_COINS; i++) {
   		coins_used[i] = money / coins[i];
   		money = money % coins[i];
   	}
   	return;
   }
   int main() {
   	int money;
   	cin >> money; //输入要换算的金额
   	find_coins(money);
   	for (int i = 0; i < N_COINS; i++)
   		cout << coins_used[i] << endl;
   	return 0;
   }
   
   {{ select(3) }}
   
   

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

4. 贪心算法通过每一步选择局部最优解来获得全局最优解，但并不一定能找到最优解。

   {{ select(4) }}

• 正确
• 错误

5. 假设有多个孩子，数组 g 保存所有孩子的胃口值。有多块饼干，数组 s 保存所有饼干的尺寸。小杨给孩子们发饼干，每个孩子最多只能给一块饼干。饼干的尺寸大于等于孩子的胃口时，孩子才能得到满足。小杨的目标是尽可能满足越多数量的孩子，因此打算采用贪心算法来找出能满足的孩子的数目，则横线上应填写的代码为（ ）。

int cooki4children(vector<int> &g, vector<int> &s)
{
    sort(g.begin(), g.end());
    sort(s.begin(), s.end());

    int index = s.size() - 1; // 饼干数组下标
    int result = 0;
    for (int i = g.size() - 1; i >= 0; i--)
    {
        if (index >= 0 && s[index] >= g[i])
        {
            ________________________________ // 在此处填入代码
        }
    }
    return result;
}

{{ select(5) }}

• result++; index--;
• result--; index--;
• result--; index++;
• result++; index++;

6. 贪心算法通过每一步选择当前最优解，从而一定能获得全局最优解。

   {{ select(6) }}

• 对
• 错