标签: pseudocode

以下伪代码来自The Algorithm Design Manual的在线预览版本的第一章(本PDF第7页).

这个例子是一个有缺陷的算法,但我仍然想要理解它:

[...]一个不同的想法可能是重复连接最接近的一对端点,这些端点的连接不会产生问题,例如过早终止循环.每个顶点都以其自己的单个顶点链开始.在将所有内容合并在一起之后,我们将最终得到一个包含其中所有点的链.连接最后两个端点为我们提供了一个循环.在执行此最近对启发式过程中的任何步骤中,我们将有一组可用于合并的单顶点和顶点不相交链.在伪代码中:

ClosestPair(P)
    Let n be the number of points in set P.
    For i = 1  to n ? 1 do
        d = ?
        For each pair of endpoints (s, t) from distinct vertex chains
            if dist(s, t) ? d then sm = s, tm = t, and d = dist(s, t)
        Connect (sm, tm) by an edge
    Connect the two endpoints by an edge

请注意,sm并且tm应该s …

我正在寻找检索记录的下一个和上一个记录而不运行完整查询的最佳方法.我有一个完全实现的解决方案,并想知道是否有更好的方法来实现这一点.

假设我们正在为一个虚构的蔬菜水果商建立一个网站.除了他的HTML页面,他每周都希望在他的网站上发布特别优惠列表.他希望这些商品位于实际的数据库表中,用户必须能够以三种方式对商品进行排序.

每个项目还必须有一个详细信息页面,其中包含有关提供的更多文本信息以及"之前"和"下一步"按钮."上一个"和"下一个"按钮需要指向相邻条目,具体取决于用户为列表选择的排序.

alt text http://www.pekkagaiser.com/stuff/Sort.gif？

显然,"西红柿,第一类"的"下一步"按钮必须是第一个例子中的"苹果,第1类",第二个中是"梨,第一类",第三个中没有.

详细信息视图中的任务是确定下一个和上一个项目,而不是每次都运行查询,列表的排序顺序是唯一可用的信息(假设我们通过GET参数得到它?sort=offeroftheweek_price,并忽略安全隐患) .

显然,简单地将下一个和前一个元素的ID作为参数传递是第一个想到的解决方案.毕竟,我们现在已经知道了ID.但是,这不是一个选项 - 它可以在这个简化的例子中工作,但在我的许多现实世界的用例中都没有.

我在CMS中的当前方法是使用我命名为"排序缓存"的东西.加载列表时,我将项目位置存储在名为的表中的记录中sortingcache.

name (VARCHAR)             items (TEXT)

offeroftheweek_unsorted    Lettuce; Tomatoes; Apples I; Apples II; Pears
offeroftheweek_price       Tomatoes;Pears;Apples I; Apples II; Lettuce
offeroftheweek_class_asc   Apples II;Lettuce;Apples;Pears;Tomatoes

很明显,该items列实际上填充了数字ID.

在详细信息页面中,我现在访问相应的sortingcache记录,获取items列,将其展开,搜索当前项ID,并返回上一个和下一个邻居.

array("current"   => "Tomatoes",
      "next"      => "Pears",
      "previous"  => null
      );

这显然很昂贵,仅适用于有限数量的记录并创建冗余数据,但我们假设在现实世界中,创建列表的查询非常昂贵(确实如此),在每个详细视图中运行它都是在问题,需要一些缓存.

我的问题:

• 您是否认为查找不同查询订单的相邻记录是一种很好的做法？

• 您是否了解性能和简单性方面的更好实践？你知道一些让它完全过时的东西吗？

• 在编程理论中,这个问题有没有名称？

• 名称"Sorting cache"是否适用于此技术并且可以理解？

• 是否有任何公认的常见模式可以解决这个问题？他们叫什么？

注意:我的问题不是建立列表,或者如何显示详细信息视图.这只是例子.我的问题是当重新查询不可能时确定记录的邻居的基本功能,以及到达那里的最快和最便宜的方式.

如果不清楚,请发表评论我会澄清.

开始赏金 - 也许有更多关于此的信息.

我需要将一些python和java例程转换为我的硕士论文的伪代码,但是在编写语法/样式方面遇到了麻烦:

• 一贯
• 容易明白
• 不太啰嗦
• 不太接近自然语言
• 与某些具体的编程语言不太接近.

你怎么写伪代码？有没有标准的建议？

我想知道一段代码,它实际上可以告诉我2D空间中的3个点是否在同一条线上.伪代码也足够了,但Python更好.

我有一个公共汽车/火车/ ...站的数据库和每个日期的到达/离开时间等等.我正在寻找一种方法来搜索两个位置之间的最快(最短/最便宜/最少过渡)之旅.我希望将来有任意位置,使用OpenStreetMap数据在停靠点之间以及从停止点到开始/结束之间行走,但是暂时我只想在数据库中的两个停靠点之间找到路径.

问题是我似乎无法找到关于这个主题的更多信息,例如这个维基百科页面有很多文本,其中绝对没有有用的信息.

我发现的是Google Transit中使用的GTFS格式.虽然我的城市没有提供公共数据源(甚至不是私人数据源),但我已经掌握了GTFS包含的所有重要信息,并且进行转换将是微不足道的.

有一些基于GTFS的软件,比如OpenTripPlanner,它也可以使用OpenStreetMap进行行人/汽车/自行车路由.

但是,路由代码没有很好地记录(至少从我发现的那个),我不需要整个事情.

我正在寻找的是对我可以使用的算法,它们的性能,可能是一些伪代码的一些很好的概述.

所以,问题是,给定一个停靠点,路线和到达/离开/出行时间列表,如何轻松找到从A站到B站的最快路径？

我需要编码最大似然估计来估计一些玩具数据的均值和方差.我有一个包含100个样本的矢量numpy.random.randn(100).数据应具有零均值和单位方差高斯分布.

我检查了维基百科和一些额外的来源,但我有点困惑,因为我没有统计背景.

是否有最大似然估计的伪代码？我得到了MLE的直觉,但我无法弄清楚从哪里开始编码.

Wiki表示采用了log-likelihood的argmax.我理解的是:我需要通过使用不同的参数来计算对数似然,然后我将采用给出最大概率的参数.我没有得到的是:我在哪里可以找到参数？如果我随机尝试不同的均值和方差以获得高概率,我何时应该停止尝试？

你如何为并行编程编写伪代码？特别是,您如何区分本地和共享变量？您如何表示分散,收集,减少,广播和点对点通信等操作？那有什么标准吗？

我有一个数字列表.我也有一定的金额.总和来自我的列表中的一些数字(我可能/可能不知道它的数量是多少).是否有快速算法来获取可能的数字列表？用Python编写会很棒,但伪代码也很好.(除了Python之外,我还读不出任何东西:P)

例

list = [1,2,3,10]
sum = 12
result = [2,10]

注意:我知道算法可以找到大小为n的列表中的哪些数字总和为另一个数字(但我无法读取C#,我无法检查它是否适合我的需要.我在Linux上,我尝试使用单声道,但我得到的错误,我无法弄清楚如何工作的C#:(
和我知道的算法来总结号码列表中的所有组合(但它似乎是相当低效的.我并不需要所有的组合.)

我正在尝试采用一系列3D点和一个平面,并根据它们所在平面的哪一侧将点分成2个阵列.在我进行大量调试之前,我想发布我正在计划做的事情,以确保我对如何做到这一点的理解能够奏效.

基本上我有3分的飞机,我使用(伪代码):

var v1 = new vector(plane.b.x-plane.a.x, plane.b.y-plane.a.y, plane.b.z-plane.a.z);
var v2 = new vector(plane.c.x-plane.a.x, plane.c.y-plane.a.y, plane.c.z-plane.a.z);

我取这两个向量的交叉乘积来得到法向量.

然后我循环遍历我的点阵并将它们转换为向量并根据法线计算点积.

然后我使用点积来确定该点所在的一侧.

这听起来像它会起作用吗？

这是我遇到的一个问题,并且没有确信我使用过最有效的逻辑.

例如,假设我有两棵树:一个是文件夹结构,另一个是该文件夹结构的内存"模型".我希望比较两棵树,并生成一个树中存在的节点列表而不是另一棵树 - 反之亦然.

是否有可接受的算法来处理这个问题？