不同算法的分析及出题PTA

每位同学需从循环与数组的四次实验中任选1题，通过对题目的分析，提供两种解题算法的代码和对应的流程图，且需对两种算法的思路进行简单讲解，并分析两种算法的差异或优劣。最后在此基础上，仿照所选择的题目，自己出一个新题（PTA的编程题）， 需要有题目描述、输入/输出样例、参考代码等内容。
选题范围：
实验3 循环结构I
实验4 循环结构II
实验5 一维数组
实验6 二维数组与字符数组

题目选择：实验3 循环结构I 第2题：在整数范围内求所有奇数的和

算法1：枚举法

思路：循环遍历从1到输入数字n，每次加上当前数字是否是奇数，如果是，加上该数字，最终得到所有奇数的和。
代码实现：

c

#include <iostream>
using namespace std;

int main()
{
    int n,sum=0;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        if(i%2!=0)
        {
            sum+=i;
        }
    }
    cout<<sum<<endl;
    return 0;
}

流程图：

sql

START
|
|----> INPUT n
|
|----> for i=1 to n
|       |
|       |----> if i%2 != 0
|       |      |
|       |      |----> sum+=i
|       |
|       |----> end if
|
|----> end for
|
|----> OUTPUT sum
|
END

算法2：等差数列求和公式

思路：根据等差数列求和公式，求出1到n的奇数和。该公式如下：$$S_n=\frac{n}{2}[(n-1)+1]$$
代码实现：

c

#include <iostream>
using namespace std;

int main()
{
    int n,sum=0;
    cin>>n;
    sum=(n/2)*((n-1)/2+1);
    cout<<sum<<endl;
    return 0;
}

流程图：

sql

START
|
|----> INPUT n
|
|----> sum=(n/2)*((n-1)/2+1)
|
|----> OUTPUT sum
|
END

差异或优劣分析：

枚举法算法复杂度为O(n)，等差数列求和公式的复杂

题目就叫“循环结构I”啊？

题目描述：
有一只卖萌的萌萌鸟，它会遇见多种动物，每种动物都有一个价值。卖萌鸟会给遇见的每种动物献上一个礼物，如果礼物的价值比动物的价值小，动物会把礼物收下并告诉卖萌鸟，萌萌鸟的礼物的价值不够大。请你求出卖萌鸟礼物的最小价值，使它可以使所有动物都收下礼物。

输入格式：
第一行为动物数n (1≤n≤100)；
接下来n行，每行有一个整数，为每种动物的价值a (1≤a≤100)

输出格式：
输出一行，一个整数，表示礼物的最小价值。

输入输出样例：

输入：
3
10
20
30

输出：
10

代码：
算法1：暴力枚举

n = int(input().strip())
values = [int(input().strip()) for i in range(n)]
values.sort()
for i in range(1, 101):
    flag = True
    for value in values:
        if i < value:
            flag = False
            break
    if flag:
        print(i)
        break

**流程图：

算法2：二分查找**

def check(mid, values):
    for value in values:
        mid -= (mid // value)
    return mid >= 0

n = int(input().strip())
values = [int(input().strip()) for i in range(n)]
left, right = 1, 100 * 100
while left < right:
    mid = (left + right) // 2
    if check(mid, values):