我对纯粹功能性F#中的eratosthenes筛子的实施很感兴趣.我对实际筛子的实现感兴趣,而不是真正的筛子的天真功能实现,所以不是这样的:
let rec PseudoSieve list =
match list with
| hd::tl -> hd :: (PseudoSieve <| List.filter (fun x -> x % hd <> 0) tl)
| [] -> []
上面的第二个链接简要描述了一个需要使用多图的算法,据我所知,这在F#中是不可用的.给出的Haskell实现使用了一个支持insertWith方法的映射,我在F#功能映射中没有看到它.
有没有人知道将给定的Haskell映射代码转换为F#的方法,或者可能知道替代实现方法或筛选算法哪些有效且更适合功能实现或F#？
给定S长度的字符串(假设只有英文字符)n,我们可以使用以下算法计算回文子串的数量:
for i = 0 to |S| do
p1 = number of palindromes centered in i (odd length)
p2 = number of palindromes centered in i and i+1 (even length)
add p1 + p2 to total number of palindromic substrings of S
O(n^2)但是,上面的代码.
我对解决这个问题的算法很感兴趣O(n).我肯定知道一个存在,因为我听到多个人说它确实存在,并且问题存在于一个上限为1 000 000on 的本地在线评判网站上n,但我从未见过算法,似乎无法能够想出来.
更新:
我的一般想法是len[i] = length of the longest palindrome centered at the character 2i + 1为偶数长度的回文计算和类似的数组.通过良好的簿记,应该可以O(1)为每个角色计算这一点,这将使我们能够同时计算大量的回文.然而,我仍然坚持如何计算这一点.
我会接受一个使用O(n)甚至可能是 …
在河内塔问题是递归的一个经典问题.在其中一个上有3个带磁盘的挂钩,您必须按照给定的规则将所有磁盘从一个挂钩移动到另一个挂钩.您还必须使用最少的移动次数执行此操作.
这是一个解决问题的递归算法:
void Hanoi3(int nDisks, char source, char intermed, char dest)
{
if( nDisks > 0 )
{
Hanoi3(nDisks - 1, source, dest, intermed);
cout << source << " --> " << dest << endl;
Hanoi3(nDisks - 1, intermed, source, dest);
}
}
int main()
{
Hanoi3(3, 'A', 'B', 'C');
return 0;
}
现在,想象同样的问题,只有4个钉子,所以我们添加另一个中间挂钩.当面临必须在任何一点选择哪个中间挂钩的问题时,我们将选择最左边的一个,以防1个以上是免费的.
我有这个问题的递归算法:
void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
if ( nDisks == 1 )
cout << source << " …谷歌访谈期间我被问到这个问题.我们给出一个由字母-F,L,R组成的字符串. - 这是机器人遵循的指令
F-向前迈出一步.
向左转弯.
向右转.
字符串长度最多为2500个字符.
字符串无限次地运行.我们需要判断是否存在具有半径的圆,r(r可以是任何实数),这样机器人永远不会离开圆.我被困在这一点.我想到使用凸包,但如何检查无限次.用代码进行解释将不胜感激.请帮忙.提前致谢
给定一个数组A的N非负数,我感兴趣的是找到办法,你可以选择5个号码(数组中从不同的位置)的数量,使得它们的总和S.
有一个简单的解决方案O(N^3):
Let H be a hash table of (sum, position of leftmost element of sum)
for i = 0, N
for j = i + 1, N
H.add(A[i] + A[j], i)
numPossibilities = 0
for i = 0, N
for j = i + 1, N
for k = j + 1, N
numPossibilities += H.get(S - (A[i] + A[j] + A[k]), k)
其中H.get(x, y)返回散列中元素的数量,其总和具有相同的散列,x并且其最左边的元素大于k.
或者,我们可以将3个元素的总和添加到哈希表中,然后继续使用2个嵌套for循环.然而,复杂性仍然相同,我们只使用更多内存.
假设输入是相当随机的(因此没有最坏情况的哈希),是否有一种算法可以解决这个问题, …
我最近发现了一个竞赛问题,要求您计算字符串中必须插入的最小字符数(任何地方)以将其转换为回文结构.
例如,给定字符串:"abcbd"我们可以通过插入两个字符将其转换为回文:一个在"a"之后,另一个在"d"之后:"a d bcbd a ".
这似乎是一个类似问题的概括,要求同样的事情,除了字符只能在最后添加 - 这在使用哈希表的O(N)中有一个非常简单的解决方案.
我一直试图修改Levenshtein距离算法来解决这个问题,但还没有成功.任何有关如何解决这个问题的帮助(它不一定非常有效,我只对任何DP解决方案感兴趣)将不胜感激.
是否有任何有效的按位操作可以获得整数结束的设置位数？例如,11 10 = 1011 2将是两个尾随1位.8 10 = 1000 2将是0尾随1位.
有没有比线性搜索更好的算法呢？我正在实现一个随机跳过列表并使用随机数来确定插入元素时的最大级别.我在C++中处理32位整数.
编辑:汇编程序是不可能的,我对纯C++解决方案感兴趣.
我感兴趣的方法来改善或者想出了能够解决算法旅行商问题有关n = 100 to 200的城市.
我给出的维基百科链接列出了各种优化,但它在相当高的水平上这样做,我不知道如何在代码中实际实现它们.
工业有实力的求解器在那里,如协和,但这些办法,因为我想要的东西太复杂,而经典的解决方案,充斥搜索TSP所有在场的随机算法或经典的回溯或者动态规划算法,只有约工作20个城市.
那么,有没有人知道如何实现一个简单的(简单来说,我的意思是一个实现不需要超过100-200行代码)TSP求解器在至少100个城市的合理时间(几秒)内工作？我只对确切的解决方案感兴趣.
您可以假设输入将是随机生成的,因此我不关心专门用于破坏某种算法的输入.
我有兴趣编写类似于akinator的20个问题算法,并且在较小程度上,20q.net使用.后者似乎更关注对象,明确告诉你不要想到人或地方.可以说,akinator更通用,允许你从字面上思考任何东西,包括诸如"我的兄弟"之类的抽象.
这个问题是我不知道这些网站使用了什么算法,但从我读到的内容来看,他们似乎正在使用一种概率方法,在这种方法中,问题根据他们导致正确猜测的次数而具有一定的适应性.这个SO问题提出了几种技术,但含糊不清,我会对更多细节感兴趣.
那么,什么是一个准确有效的算法来播放二十个问题呢？
我对以下方面的细节感兴趣:
我意识到这可能并不容易,我不是要求代码或2000字的演示文稿.关于每个操作和底层数据结构的几句话应该足以让我开始.
我不明白为什么C#的Main函数默认是无效的(例如在控制台项目中).在C和C++中,标准明确指出main必须返回int,并且使用返回值是有意义的,因为我们可以检查来自外部程序的返回值,并查看C/C++应用程序是否成功完成或遇到错误.
所以我的问题是:
Main为void？