标签: math

请考虑以下代码:

0.1 + 0.2 == 0.3  ->  false

0.1 + 0.2         ->  0.30000000000000004

为什么会出现这些不准确之处？

我正在寻找最快的方法来确定一个long值是否是一个完美的正方形(即它的平方根是另一个整数):

1. 我通过使用内置Math.sqrt() 函数以简单的方式完成了它,但我想知道是否有办法通过将自己限制为仅整数域来更快地完成它.
2. 维护查找表是不切实际的(因为大约有2 ^31.5个整数,其平方小于2 ⁶³).

这是我现在正在做的非常简单直接的方式:

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

_{注意:我在许多Project Euler问题中使用此函数.因此,没有其他人必须维护此代码.而这种微优化实际上可以产生影响,因为部分挑战是在不到一分钟的时间内完成每个算法,并且在某些问题中需要将此函数调用数百万次.}

我尝试过不同的问题解决方案:

• 经过详尽的测试后,我发现0.5不需要添加Math.sqrt()的结果,至少在我的机器上没有.
• 的快速逆平方根增快,但它给了不正确的结果对于n> = 410881.然而,所建议BobbyShaftoe,我们可以使用FISR劈对于n <410881.
• 牛顿的方法慢了一点Math.sqrt().这可能是因为Math.sqrt()使用类似牛顿方法的东西,但在硬件中实现,因此它比Java快得多.此外,牛顿的方法仍然需要使用双打.
• 一个修改过的牛顿方法,它使用了一些技巧,只涉及整数数学,需要一些黑客来避免溢出(我希望这个函数适用于所有正64位有符号整数),并且它仍然比它慢Math.sqrt().
• 二进制斩甚至更慢.这是有道理的,因为二进制斩波平均需要16遍才能找到64位数的平方根.
• 根据John的测试,or在C++中使用语句比使用语句更快switch,但在Java和C#中,or和之间似乎没有区别switch.
• 我还尝试制作一个查找表(作为64个布尔值的私有静态数组).然后or我会说,而不是开关或声明if(lookup[(int)(n&0x3F)]) { test } else return false; …

给定两个日期范围,确定两个日期范围是否重叠的最简单或最有效的方法是什么？

举个例子,假设我们有通过日期时间变量表示的范围StartDate1来EndDate1 和 StartDate2到EndDate2.

我有一段时间有一个有趣的面试经历.问题开始很简单:

Q1:我们有包含数字的袋子1,2,3,..., 100.每个数字只出现一次,因此有100个数字.现在从包里随机挑出一个号码.找到丢失的号码.

当然,我之前听过这个采访问题,所以我很快回答了以下问题:

A1:嗯,这些数字的总和1 + 2 + 3 + … + N是(N+1)(N/2)(见维基百科:算术系列之和).因为N = 100,总和是5050.

因此,如果包中存在所有数字,则总和将是精确的5050.由于缺少一个数字,总和将小于此数值,差异就是该数字.所以我们可以在O(N)时间和O(1)空间中找到丢失的数字.

在这一点上,我认为我做得很好,但突然之间,这个问题发生了意想不到的变化:

Q2:这是正确的,但是现在如果缺少两个数字你会怎么做？

我之前从未见过/听过/考虑过这种变化,所以我惊慌失措,无法回答这个问题.面试官坚持要知道我的思考过程,所以我提到也许我们可以通过与预期产品进行比较来获得更多信息,或者可能在从第一遍获得一些信息后再做第二遍,但我真的只是拍摄在黑暗中而不是实际上有一条清晰的解决方案.

面试官确实试图鼓励我说有第二个等式确实是解决问题的一种方法.在这一点上,我有点不高兴(因为事先不知道答案),并询问这是一般的(阅读:"有用")编程技术,还是只是一个技巧/问题答案.

面试官的回答让我感到惊讶:你可以概括一下找到3个缺失数字的技巧.实际上,您可以将其概括为找到k个缺失的数字.

Qk:如果行李中缺少k个号码,您会如何有效地找到它？

这是几个月前,我仍然无法弄清楚这种技术是什么.显然有一个?(N)时间下限,因为我们必须扫描所有数字至少一次,但是访问者坚持解决技术的时间和空间复杂度(减去O(N)输入扫描的时间)在k而不是N中定义.

所以这里的问题很简单:

• 你会如何解决Q2？
• 你会如何解决Q3？
• 你怎么解决Qk？

澄清

• 通常有1个 …

这是由语言定义的吗？是否有定义的最大值？在不同的浏览器中是不同的？

float('nan')结果是南(不是数字).但我该如何检查呢？应该很容易,但我找不到它.

在JavaScript中,我如何获得:

1. 给定整数进入另一个整数的整数倍？
2. 剩下的？

如何计算纬度和经度指定的两点之间的距离？

为了澄清,我想要以公里为单位的距离; 这些要点使用WGS84系统,我想了解可用方法的相对准确性.

我上次采访时遇到的一个问题:

设计一个函数f,这样:

f(f(n)) == -n

Run Code Online (Sandbox Code Playgroud)

哪里n是32位有符号整数 ; 你不能使用复数运算.

如果您无法为整个数字范围设计此类功能,请将其设计为可能的最大范围.

有任何想法吗？

我无法理解这一点,这更随机？

rand()

要么

rand() * rand()

我发现它是一个真正的脑筋急转弯,你能帮助我吗？

编辑:

直观地,我知道数学答案将是它们同样随机,但我不禁想到,如果你将两者相乘的话"运行随机数算法"两次,你会创造一些比随机更随机的东西它一次.