当前位置：首页 > news >正文

每日一练-等差数列

news 2025/6/26 4:27:01

等差数列

- - - 🍀题目描述
    - 🌿解题思路
    - 🌸Python源码
    - 📧Summary

📆Date: 2023年2月10日
🎬Author: 小 y 同学
📃Classify: 蓝桥杯每日一练
🔖Language: Python

🍀题目描述

题意
数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列，只记得其中 N 个整数。
现在给出这 N 个整数，小明想知道包含这 N 个整数的最短的等差数列有几项？

输入格式
输入的第一行包含一个整数 N。
第二行包含 N 个整数 A₁, A₂, · · · , A_N。(注意 A₁ ∼ A_N 并不一定是按等差数列中的顺序给出)

输出格式
输出一个整数表示答案。

样例输入
5
2 6 4 10 20
样例输出
10
样例说明
包含 2、6、4、10、20 的最短的等差数列是 2、4、6、8、10、12、14、16、18、20。

评测用例规模与约定
对于所有评测用例，2 ≤ N ≤ 100000，0 ≤ A_i ≤ 109。

🌿解题思路

题目梳理
题目会给出一串数字，我们需要做的就是找出包含这些数字的等差数列，且这个等差数列的项数最小，注意我们要输出的是等差数列的项数，不是等差数列的元素或者其求和。
核心处理
首先给出的数字串是没有顺序的，我们首先肯定是想到将给出的数字排序。然后我们要做的就是寻找公差：起初小y想的是排序完的数组每相邻两项做差，然后最小的就是公差，但是仔细一想：如果排序完的数组中的相邻两项差一个是2，一个是3：例如数组：1、3、6；要想组成等差数列，必须以1为公差；随后就想到了取2和3的最大公因数也就是1来作为公差；同样的思路，就可以类比出给出的任意数列对应的公差。随后就是求项数，给出的数列最小的和最大的一定是等差数列的首尾项，我们可以由 $an=a1+(n−1)×da_n=a_1+(n-1)\times d$ 推导出 $n=an−a1d+1n=\frac{a_n - a_1}{d}+1$ ，但是我们要注意d为0的情况分开讨论！

🌸Python源码

# _*_coding:utf-8_*_
# created by cy on 2023/2/10
import math# 求最大公因数
def gcd_many(li, n):
g = 0
for i in range(n):if i == 0:g = li[i]else:g = math.gcd(g, li[i])
return gn = int(input())
A = list(map(int, input().split()))
A.sort()
d_li = []
for i in range(n - 1):
d_li.append(A[i + 1] - A[i])
if min(d_li) == 0:  # 公差为0的情况
print(n)
else:
d = gcd_many(A, n)
print(int((A[-1] - A[0]) / d + 1))