算法练习题20---蓝桥杯2019省赛“等差数列”

2022/1/25 20:04:36

本文主要是介绍算法练习题20---蓝桥杯2019省赛“等差数列”,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、题目描述
      • 输入描述
      • 输出描述
      • 输入输出样例
        • 示例
      • 运行限制
  • 二、思路
  • 三、具体代码


前言

蓝桥杯2019省赛,编程题(C++)

一、题目描述

数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一 部分的数列,只记得其中 N 个整数。

现在给出这 N 个整数,小明想知道包含这 N 个整数的最短的等差数列有几项?

输入描述

输入的第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。(注意 A1 ∼ AN 并不一定是按等差数列中的顺序给出)

其中,2≤N≤10的5次方,0≤Ai≤10的9次方。

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

5
2 6 4 10 20

输出

10

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

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 256M

二、思路

对于无序的数据要先从小到大排序。

从已有项中找到使得项数最小的公差,这个公差必然满足最大的公差,那么就是从每项数据之间的差值中找到一个最大公约数,题目的整体做法就出来了。那么在编程时,主要考虑以下几个方面,就可以了

  • 最大公约数的函数构造
  • 在多个差值中的求出最大公约数
  • 注意公差为0的情况,直接输出n
  • 项数 n = (an-a1)/d+1 ,d为公差

三、具体代码

#include<bits/stdc++.h>
using namespace std;

long gcd(long a,long b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b,a%b);
}

int main()
{
    long n;
    cin>>n;
    long item[100005]={0};
    long dif[100005]={0};  //用来存储每一项之间的差值
    for(long i=1;i<=n;i++)
    {
        cin>>item[i];
    }
    sort(item+1,item+n+1); 
    for(long i=2;i<=n;i++)
    {
        dif[i-1]=item[i]-item[i-1];
    }
    sort(dif+1,dif+n); //1~n-1排序
    //找到一个差值序列中的最大公约数,是所有差值的因子,这个值就是最大的公差
    for(long i=2;i<n;i++)
    {
        dif[1]=gcd(dif[i],dif[1]);
    }
    if(dif[1]>0) //考虑公差为0的特殊情况
    {
        long ans=(item[n]-item[1])/dif[1]+1;
        cout<<ans<<endl;
    }
    else
    {
        cout<<n<<endl;  //公差为0,即有n项
    }
    return 0;
}


这篇关于算法练习题20---蓝桥杯2019省赛“等差数列”的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程