例题10-1 有序表的简单增删查操作
时间: 2023-04-29 17:02:52 浏览: 178
这道题目主要考察有序表的基本操作,包括增加、删除和查找。
增加操作可以通过插入元素来实现,需要保证插入后仍然保持有序性。可以使用二分查找来确定插入位置,然后将元素插入到相应位置即可。
删除操作可以通过查找元素位置来实现,然后将该位置的元素删除。同样需要保证删除后仍然保持有序性。
查找操作可以使用二分查找来实现,可以快速定位元素的位置。如果要查找多个元素,可以使用二分查找的变种,如二分查找第一个等于给定值的元素、二分查找最后一个等于给定值的元素、二分查找第一个大于等于给定值的元素、二分查找最后一个小于等于给定值的元素等。
以上就是有序表的简单增删查操作的基本思路。
相关问题
例题10-6 分治法求解金块问题
分治法是一种分而治之的思想,将问题不断分解为小问题,直到小问题可以直接求解为止。对于金块问题,可以使用分治法求解。
具体思路如下:
1. 将金块分成两份,分别称为左金块和右金块。
2. 比较左金块和右金块的重量。
3. 如果左金块的重量大于右金块,说明假金块在左金块中,递归地对左金块进行求解。
4. 如果右金块的重量大于左金块,说明假金块在右金块中,递归地对右金块进行求解。
5. 如果左金块和右金块的重量相等,说明假金块就是剩下的那个金块。
代码如下:
```python
def find_fake(gold):
# 如果金块只有一个,直接返回
if len(gold) == 1:
return gold[0]
# 将金块分成两份,分别称为左金块和右金块
mid = len(gold) // 2
left = gold[:mid]
right = gold[mid:]
# 比较左金块和右金块的重量
left_weight = sum(left)
right_weight = sum(right)
# 如果左金块的重量大于右金块,说明假金块在左金块中
if left_weight > right_weight:
return find_fake(left)
# 如果右金块的重量大于左金块,说明假金块在右金块中
elif right_weight > left_weight:
return find_fake(right)
# 如果左金块和右金块的重量相等,说明假金块就是剩下的那个金块
else:
return gold[-1]
```
测试代码如下:
```python
gold = [10, 10, 10, 10, 10, 10, 10, 10, 10, 9]
print(find_fake(gold)) # 输出 9
```
时间复杂度为 $O(n\log n)$。
例题4-1 用格里高利公式求给定精度的pi值
格里高利公式是一种计算圆周率的公式,可以用来求给定精度的pi值。具体步骤如下:
1. 设定精度要求,例如要求计算出pi值的小数点后10位。
2. 根据格里高利公式,计算出pi值的近似值。公式如下:
pi ≈ 4 × (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ...)
其中,每一项的分母为奇数,分子为1或-1,符号交替出现。
3. 计算出pi值的误差。误差可以通过比较近似值和真实值的差来计算。
4. 如果误差小于设定的精度要求,则输出近似值作为pi值;否则,继续计算下一项,直到误差满足精度要求为止。
需要注意的是,格里高利公式是一种无限级数,因此计算时需要考虑到精度和计算效率的平衡。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)