大数据算法之实验算法分析三（附代码）

实验时间：2021年10月28日

给定 n 个无序实数 ，求这 n 个实数在实轴上相邻 2 个数之间的最大差值，要求线性的时间算法。
例如： 4 11 1 9 20 2 17
输出： 6

鸽舍原理：
找min、max，接着递归把n-2个数放在n-1个笼子
也称“抽屉原理”或利克雷原则，它是一个重要而又基本的数学原理，应用它可以解决各种有趣的问题，并且常常能够得到令人惊奇的结果，许多看起来相当复杂，甚至无从下手的问题，利用它能很容易得到解决。
原理1：把n+1个元素分成n类，不管怎么分，则一定有一类中有2个或2个以上的元素。
原理2：把多于m×n个物体放到n个抽屉里，那么一定有一个抽屉里有m+1个或者m+1个以
上的物体。
原理2-1：把m个元素任意放入n（n 其中 k= [m/n]([]表示向上取整）。
（抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有 n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素。” ）

#include 
#include 
#include 
#include 
using namespace std;

class Env
{
public:
    int data[10000];
    int pointer_max = 0;
    int pointer = 0;
    Env()
    {
        // test1.csv test2.csv test3.csv  共3个测试用例，请依次测试
        ifstream file("C:/Users/lenovo/Desktop/code/test_data/test3.csv", ios::in);     
        if (!file.is_open())
            cout << " 文件打开失败！" << endl;

        string temp;
        while (getline(file, temp))
        {
            data[pointer_max] = atoi(temp.c_str());
            pointer_max++;
        }
        file.close();
    }

    // int get_data()
    // {   
    //     if (!done())
    //         return data[pointer++];
    //     else
    //         return -1;
    // }
    // bool done()
    // {
    //     if (pointer < pointer_max)
    //         return false;
    //     else
    //         return true;
    // }
};

// 所有的代码都需要写在 Algo 类内，自行定义其他需要的变量或函数
class Algo
{
public:
    Algo()
    {
        cout << "algo ok" << endl;
    }

    int run(Env env)
    {
        //在此写入你的代码
        //env.data 为目标数组
        int n=10000;
        //max,min分别表示最大值最小值
        int max=env.data[0],min=env.data[0];
        //nmax,nmin分别表示最大值最小值的下标
        int nmax=0,nmin=0;
        //寻找最大值，最小值下标
        for(int i=0;i<10000;i++)
        {
            if(env.data[i]max)
            {
                max=env.data[i];
                nmax=i;
            }
        }
        //笼子初始化,创建n-1个桶，每个桶中有一个最大值r[i]，有一个最小值l[i]
        int count[10000],l[10000],r[10000];
        for(int i=0;ir[bucket])
                r[bucket]=env.data[i];
        }
        //定义ans为返回值,gap为间隙值
        int ans=0,gap=0,left=r[0];
        for(int i=0;ians)
                ans=gap;
            left=r[i];
        }
        return ans; //修改为返回正确的结果
    }
};



int main()
{
    Algo algo;
    Env env;
    time_t start=clock();
    int res=algo.run(env);
    time_t end=clock();
    cout<<"程序结果："< 
实验结果（含时间、空间、输出结果）： 
测试样例test1.csv:
 测试样例test2.csv:
 测试样例test3.csv: