算法笔记 02_最大间隙问题(线性时间)


(注:该问题答案转自网友李春春的CSDN博客,转载请注明出处)

★问题描述: 
最大间隙问题:给定 n 个实数x1,x2,…,xn,求这 n 个数在实轴上相邻 2 个数之间的最大差值。假设对任何实数的下取整函数耗时 O(1),设计解最大间隙问题的线性时间算法。

★算法设计: 
对于给定的 n 个实数x1,x2,…,xn,计算它们的最大间隙。

★数据输入: 
输入数据由文件名为 input.txt 的文本文件提供。文件的第 1 行有 1 个正整数n。接下来的 1 行中有 n 个实数x1,x2,…,xn。

★结果输出:将找到的最大间隙输出到文件 output.txt。 

happysneaker.com


★C++ 代码如下(① 由 Visual Studio 2017 运行成功,注意可能运行出错,非代码问题,根据编译器错误提示修改细节;② input.txt 文件需要自己手动建立在工作文件夹)

#include"stdafx.h"
#include<iostream>
#define FILENAMELENGTH 50

//声明函数
template<class T>
int indexofmin(int n, T *x);

template<class T>
int indexofmax(int n, T *x);

//类
class CMaxGap
{
public:
   int m_nCount;     //数据的个数
   double m_dblMaxGap;   //最大间隙
   double *m_dblNumber;    //存放数据的数组

   CMaxGap(const char *filename);
   ~CMaxGap(); 
       
   double GetMaxGap(int n, double *x);    
   void Display();
};


//读入数据
CMaxGap::CMaxGap(const char *filename)
{
   FILE *fp = fopen(filename, "r");    
   if (fp == NULL)
   {     
      printf("无法打开该文件,可能不存在或位置不对! \n");     
      exit(0);
   }    
    
   //读入数据个数
   fscanf(fp, "%d", &m_nCount);
   m_dblNumber = new double[m_nCount];    
    
   //读入每个具体的数据
   for (int i = 0;i<m_nCount;i++)      
     fscanf(fp, "%lf", &m_dblNumber[i]);

   m_dblMaxGap = 0;
   fclose(fp);
}

CMaxGap::~CMaxGap()
{    delete[] m_dblNumber;
    m_dblNumber = NULL;
}

//获取n个数据的最大间隙,存放在以x为开始地址的单元中,数据下标为0,1,...,n-1
double CMaxGap::GetMaxGap(int n, double *x)
{  
  //找到最大最小数据,考虑到浮点型数据在传递过程中可能会有微小的变化
   //故采取取其下标的方式,在直接读取
   int minindex = indexofmin(n, x);    
   int maxindex = indexofmax(n, x);    
   double minx = x[minindex];    
   double maxx = x[maxindex];    
   
   //用n-2个点等分区间[minx,maxx],产生n-1个桶,桶编号1,2,...,n-2,n-1
   //且桶i的上界和桶i+1的下届相同
   double dblAvrGap = (maxx - minx) / (n - 1);    //每个等分区间大小,即每个桶的大小
   int *count = new int[n];        //实际分到每个桶的数据个数
   double *low = new double[n];    //实际分到每个桶的最小数据
   double *high = new double[n];    //实际分到每个桶的最大数据

   //初始化桶
   for (int i = 0;i<n;i++)
   {
      count[i] = 0;
      low[i] = maxx;
      high[i] = minx;
   }    
         int index;    //桶编号
         
      //将n个数放入n-1个桶中
        for (int i = 0;i<n;i++)
        {        
            //按如下规则将x[i]分配到某个桶(编号index)中
        //若x[i]=minx,则被分到第1个桶中(minx即为桶1的下界)
        //若x[i]=桶j的下界(也是桶j-1的上界),则按如下公式被分到桶j中(j>=1)
        index = int((x[i] - minx) / dblAvrGap) + 1;        
        
        //若x[i]=maxx,则被分到桶n中(max为桶n的下界桶n-1的上界)
        //但没有桶n,此时可人为将其移入桶n-1中,或者再加一个桶
        //该步操作不影响下面的求最大间隙
        if (index == n)
            index--;

        count[index]++;        
        //调整分到该桶的最大最小数据
        if (x[i]<low[index])
           low[index] = x[i];        
        if (x[i]>high[index])
           high[index] = x[i];
        }    
    
    /*
    除最大最小数据maxx和minx以外的n-2个数据被放入n-1个桶中
    由抽屉原理可知至少有一个桶是空的
    又因每个桶的大小相同,所以最大间隙不会在同一桶中出现
    一定是某个桶的上界(dblHigh)和其后某个桶的下界(dblLow)之间隙
    注意:该两桶之间的桶(即编号在该两桶编号之间的桶)一定是空桶
    即最大间隙在桶i的上界和桶j的下界之间产生(j>=i+1)
    */

    double dblMaxGap = 0, dblHigh = high[1], dblTempGap;    
    for (int i = 2;i<n;i++)
    {        
        if (count[i])    //该桶非空才计算
      {
          dblTempGap = low[i] - dblHigh;            
          if (dblMaxGap<dblTempGap)
            dblMaxGap = dblTempGap;
          dblHigh = high[i];
      }
    }    
    
    //释放
    delete[] count;
    count = NULL;    
    delete[] low;
    low = NULL;    
    delete[] high;
    high = NULL;

    m_dblMaxGap = dblMaxGap;    
    return dblMaxGap;
}

void CMaxGap::Display()
{    
        printf("该文件中一共存在 %d 个数: ", m_nCount);    
        for (int i = 0;i<m_nCount;i++)
    {        
        printf("%.2f ", m_dblNumber[i]);
    }    
    printf("\n");    
    printf("最大间隙为: %.2f ", m_dblMaxGap);    
    printf("\n");    
    printf("----------------------------------------------------\n");
}

//求数组中最小数据的下标
template<class T>
int indexofmin(int n, T *x)
{    
        int index;
    T temp = x[0];    
    for (int i = 1;i<n;i++)
    {        
            if (x[i]<temp)
        {
            temp = x[i];
            index = i;
        }
    }    return index;
}

//求数组中最大数据的下标template<class T>int indexofmax(int n, T *x)
{    
        int index;
    T temp = x[0];    
    for (int i = 1;i<n;i++)
    {        
            if (x[i]>temp)
        {
            temp = x[i];
            index = i;
        }
    }    
    return index;
}

//显示菜单
void show_menu()
{    
        printf("测试说明:\n");    
        printf("①按 i or I : 输入要测试文件的名字 \n");    
        printf("②按 q or Q 退出 \n");    
        printf("----------------------------------------------------\n");    
        printf("Please input the letter:");
}

void main()
{  
  char sinput[10];    
  char sfilename[FILENAMELENGTH];

  show_menu();    
  scanf("%s", sinput);    
  while (_stricmp(sinput, "q") != 0)
    {     
         if (_stricmp(sinput, "i") == 0)
        {        
            printf("请输入文件名:");            
            scanf("%s", sfilename);            
            
            //求文件中数据的最大间隙
            CMaxGap gap(sfilename);            
            double dblMaxGap = gap.GetMaxGap(gap.m_nCount, gap.m_dblNumber);
            gap.Display();
        }        
        
        //输入命令
        printf("Please input the letter:");        
        scanf("%s", sinput);
    }
}

happysneaker.com


Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论