0%

EOJ-2017程序设计能力实训题解

EOJ-2017程序设计能力实训题解-1(1001-1005)

题目链接:https://acm.ecnu.edu.cn/contest/43/

本次更新的题目主要涉及到的知识点有语言练习、排序和表达式。难度在该题集中都为naive

由于题目难度不算太高,本期题解将会对题目进行简要讲解。

本地测试环境:Visual Studio 2019

编程语言:C++

#1001. A+B Problem

描述:最基础的语言题。

难点:可能在于如何在不知道行数的情况下输入,使用下面的语句即可实现。

1
while(cin>>a>>b)
#1002. 几位数?

描述:常规的做法应该是循环整数求位数,在本例中可以直接使用获取字符串长度的方法。
相关方法:

1
2
string str;
int length = str.size(); //获取字符串长度的方法
#1003. 计算a的n次方

描述:虽然在本题中常规方法并不会导致超时,但常规方法时间复杂度较高。因此将以快速幂方法来实现。

讲解:

在这里插入图片描述

​ 通过上述公式可知,当$n$为偶数时其规模可以降至一半。结合递归方法与位运算,可写出快速幂代码。

​ 其中,通过位与运算来实现判断奇偶,右移操作来实现除2可以提升性能。

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef long long int ll;

ll pow(ll a, ll n) {
if (n == 0) {
return 1;
}
if (n & 1) { //n为奇数时
return (a * pow(a, n - 1));
}
else {
return (pow(a, n >> 1) * pow(a, n >> 1));
}
}
#1004. 值班

描述:只需判断是否有30条记录,简单的计数题。

#1005. SQUINT

描述:求平方根,同时需要向上取整。

讲解:

​ 0.取整方法:ceil()向上取整,floor()向下取整。

​ 1.使用库函数sqrt求平方根,需要math.h头文件。

​ 2.使用二分法求平方根。

1
2
3
4
5
6
7
8
9
while(max-min>0.1){	//精度
if (mid * mid > num) {
max = mid;
}
else {
min = mid;
}
mid = (max + min) / 2;
}

​ 3.使用牛顿迭代法求平方根

在这里插入图片描述

在这里插入图片描述

img

​ 详细求解过程与代码稍后更新。(先update一个版本再说哈哈)

​ LaTex公式总是渲染失败,尝试了网上的方法也没有用(⊙﹏⊙),只好把公式截图发出来啦。