蛙蛙推荐：算法练习：最大间隙问题
问题描述：最大间隙问题：给定的n个实数x1,x2...,xn，求这N个数在实轴上相邻两个数之间最大差值。假设对任何实数的下去整耗时是O(1),设计最大间隙问题的线性时间算法。
数据输入：
输入数据由文件名为input.txt的文本文件提供，文件的第一行有一个正整数N，接下来的一行有N个实数x1,x2...,xn
数据输出：
程序运行结束时，将找到的最大间隙输出到output.txt里
这是《算法设计与实验题解》里的一道题，原文中的算法分析是用c写的，我转换成了c#语言，如下
using System;
using System.Diagnostics;
using System.Collections;
using System.IO;
using System.Runtime.InteropServices;
namespace ZuiDaJianXi {
class Program {
static int MyFloor(double d) {
cast_struct c = new cast_struct { d = d - 0.499999999999 + 6755399441055744.0 };
return c.i;
}
struct cast_struct {
public double d;
public int i;
}
static unsafe int MyFloor2(double dval) {
dval = dval - 0.499999999999;
const double magic = 6755399441055744.0;
dval += magic;
return *(int*)&dval;
}
static void Main(string[] args) {
Random rnd = new Random();
double[] x = new double;
for (int i = 0; i Console.WriteLine("{0}",d));
Console.WriteLine("最大间隙为:{0},time={1}",
maxgap(x.Length, x), stop.ElapsedTicks);
stop.Reset();
stop.Start();
Console.WriteLine("最大间隙为:{0},time={1}",
maxgap2(x), stop.ElapsedTicks);
Console.ReadKey();
}
static double maxgap2(double[] x) {
Array.Sort(x);
double tmp = 0, left = x;
for (int i = 1; i tmp) tmp = thisgap;
}
return tmp;
}
static double maxgap(int n, double[] x) {
double minx = x, maxx = x;
//用n-2个等间距的点分割区间
//产生n-1个桶，每个桶i中用high和low
//分别存储桶i的数中的最大数和最小数
int[] count = new int;
double[] low = new double;
double[] high = new double;
//桶初始化
for (int i = 0; i
页:
[1]