标签: knuth

任何人都可以解释人或男孩测试如何返回-67的值？
我徒劳地试着写下结果,或用调试器跟踪它.任何帮助,将不胜感激.
可以在此处找到不同实现的列表.

我实现了这个函数来生成一个泊松随机变量

typedef long unsigned int luint;
luint poisson(luint lambda) {
    double L = exp(-double(lambda));
    luint k = 0;
    double p = 1;
    do {
        k++;
        p *= mrand.rand();
    } while( p > L);
    return (k-1);
}

其中mrand是MersenneTwister随机数生成器.我发现,当我增加lambda时,预期的分布将是错误的,其平均值在750左右饱和.是由于数值近似还是我犯了什么错误？

我有一个C++任务,我必须用我选择的容器设计一个天真的Knuth问题解决方案并研究生成的性能数据.见下面的问题:

从纽约到加利福尼亚,有三百万名男子名字端到端.每个参与者都得到了一张纸条,上面写下了他自己的名字和他身边的人的姓名.线路最西端的那个人不明白该怎么办,所以他扔掉了他的纸; 剩余的2,999,999张纸被放入一个巨大的篮子里并被带到华盛顿特区的国家档案馆.这里篮子的内容被彻底洗牌并转移到磁带上.

此时,一位信息科学家观察到磁带上有足够的信息来重建原始顺序的人员列表.一位计算机科学家发现了一种通过数据磁带进行重建的方法,只需使用数据磁带和少量随机存取存储器.这怎么可能？

[换句话说,给定1≤i<N的对(xi,xi + 1),以随机顺序,xi是不同的,如何获得序列x1 x2 ... .xN,将所有操作限制为串行技术,适用于磁带.当没有简单的方法来判断两个给定键中的哪一个在另一个之前时,这就是按顺序排序的问题;

根据我的研究,我决定使用unordered_map,而不是列表或法线贴图.我不明白的是提供给我们实现代码的天真解决方案:

考虑将论文作为(名称,名称)元组的集合,可以从这些元组建立继承者(西风邻居)和前任(东方邻居).

 - identify an individual xc

 - append xc to empty list

 - while xc has westerly neighbour

 - xc < westerly neighbour of xc

 - append xc to list

 - xc < head of list

 - while xc has easterly neighbour

 - xc < easterly neighbour of xc

 - prepend xc to list

我的第一个问题 - xc只是一个随机元素,因为容器的性质导致订单无法确定？

我的第二个问题 - 我们给出的名字是这样的文件:

Hazbgaei,Ckwkkkxa
Hrunmkoc,Usjgmunt
Cmkcwncb,Ycrnwzjl
Oygvmrhf,Hylmukiw
Jursaual,Gzrddsbg

那么天真的解决方案是说我应该拿第一个名字并把它放在一个列表中,然后是姓氏并将其放入不同的列表中？

道歉,如果我完全关闭,但我真的试图理解这一点!

唐纳德克努特有很多节目要在他的页面上阅读.但他们大多采用"奇怪的"CWEB格式......

什么是在Windows中使它们具有适当可读性的最佳方法？

我正在为我正在研究的C++项目实现一个Knuth shuffle.我试图从我的shuffle获得最无偏见的结果(我不是(伪)随机数生成的专家).我只是想确保这是最无偏见的shuffle实现.

draw_t是字节类型(typedef'd to unsigned char).items是列表中的项目数.我已经包含了random::get( draw_t max )下面的代码.

for( draw_t pull_index = (items - 1); pull_index > 1; pull_index-- )
{
    draw_t push_index = random::get( pull_index );

    draw_t push_item = this->_list[push_index];
    draw_t pull_item = this->_list[pull_index];

    this->_list[push_index] = pull_item;
    this->_list[pull_index] = push_item;
}

我正在使用的随机函数已被修改以消除模偏差.RAND_MAX分配给random::_internal_max.

draw_t random::get( draw_t max )
{
    if( random::_is_seeded == false )
    {
        random::seed( );
    }

    int rand_value = random::_internal_max;
    int …

我的教授解决了kmp失败函数如下:

index  1 2 3 4 5 6 7 8 9
string a a b a a b a b b
ff     0 1 2 1 2 3 4 5 1

从我在网上查看的其他文本中,我发现它可能是错的,我再次向他证实,他告诉我他是绝对正确的.有人可以向我解释为什么他会以简单的一步一步的方式认为这是对还是错？谢谢

我正在尝试将knuthBendix应用于大量的重写规则.因此,我尝试让它在不同的集合上并行工作.

例如,我尝试运行:

import Control.Parallel
import Control.Parallel.Strategies
import Math.Algebra.Group.StringRewriting

knuthBendixOptimized rs = as' `par` bs' `pseq` as' ++ bs' where
    (as, bs) = splitAt 3000 rs
    as' = knuthBendix as
    bs' = knuthBendix bs

我编译使用ghc -threaded,我执行通过+RTS -N.如果我并行运行其他算法,它就可以工作.但对于knuthBendix,它没有.

有人知道解决方案吗？

谢谢,弗兰兹

我在这里找到了一个声明，即数独算法 X的时间复杂度为 O(N^3)，其中 N 是棋盘大小。

这可能是合乎逻辑的，因为对于数独，要计算的二进制矩阵有 N^3 行。但这使得数独问题可以在多项式时间内解决，并且数独被称为 NP 问题，这意味着（据我所知）

• 不可能总是在多项式时间内求解

• 可以在多项式时间内验证解

那么数独算法 X 的时间复杂度是多少，是否有可能在多项式时间内解决数独问题？

谢谢！

这是一个例子:

1. [00] 2009年的二进制形式......
2. [05]其中一封信......
3. [10]四位量 - 半字节或十六进制数字......
4. [15]一千字节......
5. [M13]如果x是0和1的任何字符串......
6. [M20]证明或反驳......

[00],[05],[10],[15],[M13],[M20]是什么意思？

我试过了:

• 谷歌搜索 taocp exercises square brackets
• 寻找方括号内的数字模式.
  • 他们都增加和减少
  • 它们大多数但不是五个的倍数
  • 那些有M的人时不时出现
  • M是唯一的前缀
  • 代码是非唯一的
• 谷歌搜索 "the art of computer programming" exercises brackets
• 谷歌搜索 "the art of computer programming" M13
  • 查看http://dl.acm.org/citation.cfm?id=1312683,表示M表示里程碑.
• 谷歌搜索 "the art of computer programming" [00]
• 寻找书中的附录解释
• 考虑到那也是一些问题

没运气!

在 MMIX 机器mmix-doc第 3 页第 4 段的文档中：

我们使用记号代表由以下组成的数字 从位置开始的连续字节。（符号 表示将 k 的最低有效 t 位设置为 0，并且仅保留结果地址的最低 64 位。...

我需要找到所有可以用字符串中的字母组成的英语单词

 sentence="Ziegler's Giant Bar"

我可以制作一系列字母

 sentence.split(//)  

如何从Ruby中的句子中创建超过4500个英语单词？

[编辑]

最好将问题分成几部分:

1. 只制作10个字母或更少的字母数组
2. 可以单独查找较长的单词