小编neo*_*989的帖子

我目前正在为我的算法类开发一个项目,我有点停滞不前.通过实施特定的更改,我们被分配了对书中合并排序的改进.我通过前两个变化工作得很好,但第三个变化是杀手.

合并排序(我们正在改进的排序)将输入数组的内容复制到临时数组中,然后将临时数组复制回输入数组.因此它递归地对输入数组进行排序,将两个已排序的一半放入临时数组中.然后它将临时数组中的两半合并在一起,将排序后的序列放入输入数组中.

改进之处在于这种双重复制是浪费的,可以不用.他的提示是:我们可以这样做,以便每次调用Merge只能在一个方向上复制,但是对Merge的调用会改变方向.

这可以通过模糊原始阵列和临时阵列之间的线来完成.

我并不是在寻找代码,因为我相信我可以编写代码.我只是不知道我应该做什么.教授已经离开了这一天所以我不能问他,直到下周我再次上课.

以前有人做过这样的事吗？或者可以为我解读并将其用于非专业术语:P

第一个改进,只要它使用插入排序,只要一个数组变得足够小,它将从时间上大大受益.

第二个改进是停止分配两个动态数组(分类的两半),而是分配1个大小为n的数组,这就是使用的数组而不是两个动态数组.这就是我做的最后一次.代码是:

//#include "InsertionSort.h"
#define INSERTION_CUTOFF 250
#include <limits.h>  // needed for INT_MAX (the sentinel)
void merge3(int* inputArray, int p, int q, int r, int* tempArray)
{
  int i,j,k;
  for (i = p; i <= r; i++)
  {
    tempArray[i] = inputArray[i];
  }
  i = p;
  j = q+1;
  k = p;
  while (i <= q && j <= r)
  {
    if (tempArray[i] <= tempArray[j])
    {
      inputArray[k++] = tempArray[i++];
    }
    else
    {
      inputArray[k++] = tempArray[j++]; …

我必须检查字符串是否可以从 Chomsky 范式的给定上下文中派生出来。我正在使用 C++。

维基百科文章上有很好的伪代码，介绍了 CYK 算法，但我不太明白。

有人会通过给我另一个 CYK 算法的伪代码来帮助我，或者在 wiki 文章中解释那个？

我需要帮助来理解如何为任何给定的二叉树编写漂亮的打印机.

我知道第一步是预先订购以获取所有节点.

我知道在前序遍历期间,这就是所有美丽将被实现的地方.

只是不知道如何开始.我有一个预订序遍历功能,但我不知道从哪里开始修改它或我应该只是自己的功能.

没有代码,只是询问别人如何去做的想法.

如果我绝望的话可能是后来的代码:P

具体来说,它应该是这样的: