建模-判断一列数是不是等差数列

题目: 如果一个数列S满足对于所有的合法的i,都有S[i + 1] = S[i] + d, 这里的d也可以是负数和零,我们就称数列S为等差数列。 小易现在有一个长度为n的数列x,小易想把x变为一个等差数列。小易允许在数列上做交换任意两个位置的数值的操作,并且交换操作允许交换多次。但是有些数列通过交换还是不能变成等差数列,小易需要判别一个数列是否能通过交换操作变成等差数列。

输入要求: 输入包括两行,第一行包含整数n(2 ≤ n ≤ 50),即数列的长度;第二行n个元素x[i](0 ≤ x[i] ≤ 1000),即数列中的每个整数。

输出要求: 如果可以变成等差数列输出”Possible”,否则输出”Impossible”。

例如 输入: 3 3 1 2 输出: Possible

解题思路: 在各种各样的编程题中,有些是直接给出要求,比如从尾到头打印链表,我们只看题目就可以一抹了然,数据结构是链表,要求是从后向前打印。但是有时给的更像是一个应用题,这就好比小学时一个水管放水,一个水管注水的问题一样,好神奇…..这是网易的一道题目,说了半天就是要判断一列数字是不是等差数列,由于没有插入与删除操作,一个顺序存储结构就可以啦。 我们可以试着这样来解决,找到一列数(n个)中的最大max和最小min,如果max=min,则为公差为0的等差数列,如果不相等那么公差就是max-min/n-1,如果没办法除尽的话,那么不是等差数列,如果除尽,即求出公差error。 现在我们知道了一个数列的最大值,最小值,个数和公差,这样就知道了等差数列的每一个数,那么下面就可以逐个判断这些数是不是在数组中,由于不是排序的数组,二分法啥的也就用不了了,所以时间复杂度是O(n^2),那么有没有其他的方法可以优化时间复杂度呢? 由于我们知道数组中的最小值,那么如果是等差数列的话,数组中的每个数与最小值的差值,对error取模的结果应该都是0,这样我们就可以判断一列数是不是等差数列了,时间复杂度为O(n)。

代码实现:

#include "iostream"    
using namespace std;

int main()
{
    int str[50];
    int num;
    cin>>num;
    for (int i = 0;i<num;i++)
        cin>>str[i];
    int maxvalue =0;
    for (int i = 0;i<num;i++)
    {
        if (maxvalue<str[i])
          maxvalue=str[i];
    }
    int minvalue =maxvalue;
    for (int i = 0;i<num;i++)
    {
        if (minvalue>str[i])
            minvalue=str[i];
    }
    if (maxvalue==minvalue)
    {
        cout<<"Possible"<<endl ;
        return 0;
    }
    int flag =  (maxvalue-minvalue)%(num-1);
    if (flag != 0)
    {
            cout<<"Impossible"<<endl ;
            return 0;
    }
    int error =(maxvalue-minvalue)/(num-1);
    for (int j=0;j <num;j++)
    {
        if ((str[j]-minvalue)%error !=0)
            cout<<"Impossible"<<endl;
    }
    cout<<"Possible"<<endl;
    return 0;
}  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

扫码关注云+社区