编写一个程序,随机产生10个1-20的整数,设计一个高效算法找其中的最大元素和最小元素,并统计元素之间的比较次数。调用该算法执行10次并求元素的平均比较次数。
时间: 2023-03-20 10:01:46 浏览: 56
以下是用Python实现的程序:
```python
import random
def find_min_max(arr):
comparisons = 0
n = len(arr)
if n % 2 == 0:
comparisons += 1
if arr[0] < arr[1]:
comparisons += 1
min_val = arr[0]
max_val = arr[1]
else:
comparisons += 1
min_val = arr[1]
max_val = arr[0]
i = 2
else:
comparisons += 1
min_val = max_val = arr[0]
i = 1
while i < n-1:
comparisons += 2
if arr[i] < arr[i+1]:
comparisons += 1
if arr[i] < min_val:
comparisons += 1
min_val = arr[i]
if arr[i+1] > max_val:
comparisons += 1
max_val = arr[i+1]
else:
comparisons += 1
if arr[i+1] < min_val:
comparisons += 1
min_val = arr[i+1]
if arr[i] > max_val:
comparisons += 1
max_val = arr[i]
i += 2
return min_val, max_val, comparisons
total_comparisons = 0
num_runs = 10
for i in range(num_runs):
arr = [random.randint(1, 20) for j in range(10)]
min_val, max_val, comparisons = find_min_max(arr)
total_comparisons += comparisons
print(f"Array: {arr}")
print(f"Min value: {min_val}")
print(f"Max value: {max_val}")
print(f"Comparisons: {comparisons}")
print()
avg_comparisons = total_comparisons / num_runs
print(f"Average comparisons: {avg_comparisons}")
```
程序使用一个叫做“比较排序”的算法来找到最大值和最小值。该算法将数组的元素分成两个组,并分别找出每个组的最大值和最小值。然后比较这两个组的最大值和最小值,就可以得到整个数组的最大值和最小值。在这个算法中,每两个元素之间最多只需要比较两次,因此算法效率较高。
程序随机生成10个1到20之间的整数,调用10次`find_min_max`函数来找到每次运行的最大值和最小值,并记录每次比较的次数。最后求出10次运行的平均比较次数,并输出结果。