代码之家  ›  专栏  ›  技术社区  ›  Samuel Novelinka

Pascal-反转计数错误输出的增强合并排序

  •  0
  • Samuel Novelinka  · 技术社区  · 7 年前

    我在学校做了一个家庭作业,要创建一个项目,计算整数数组中的倒数。我第一次尝试暴力,但正如我所料,我没有超过时间限制。因此,在进行了一些google搜索并试图完全理解mergeSort以及如何在其中实现反转计数之后,我编写了以下代码,不幸的是,该代码在正确排序数组的同时输出了错误的计数:

    procedure mergeSort(var arr, pomarr : array of longint; start, stop : 
    longint; var inv : longint);
    var
      mid,i,j,k : longint;
    begin
      mid := (start + stop) div 2;
      if (start < mid) then mergeSort(arr,pomarr,start,mid,inv);
      if (mid+1 < stop) then mergeSort(arr,pomarr,mid+1,stop,inv);
    
      i := start;
      k := start;
    
      while (i<= mid) and (j <= stop) do begin
        if (arr[i] < arr[j]) then begin
          pomarr[k] := arr[i];
          i += 1;
        end
        else begin
          pomarr[k] := arr[j];
          inv += mid - i;
          j += 1;
        end;
        k += 1;
      end;
      while (i <= mid) do begin
        pomarr[k] := arr[i];
        i += 1;
        k += 1;
      end;
      while (j <= stop) do begin
        pomarr[k] := arr[j];
        j += 1;
        k += 1;
      end;
    
      for k := start to stop do begin
        arr[k] := pomarr[k];
      end;
    end;  
    

    提前感谢您的帮助。我知道这只是一个声明中的愚蠢错误,但我似乎找不到它。

    1 回复  |  直到 7 年前
        1
  •  0
  •   Samuel Novelinka    7 年前

    所以我设法解决了我的问题。我问我的老师是什么导致了这个问题,他告诉我,在程序头声明变量类型和在程序体声明变量类型实际上是有区别的。之后,我通过创建数组类型修复了我的程序:

    type
      numlist = array[1..250000] of longint;
    

    并通过此类型在函数和其他任何地方声明我使用的数组。它确实起了作用。

    据我所知,如果您在不使用类型的情况下声明数组,迭代实际上从0开始,而不是像往常一样从1开始。老实说,我不知道这两个事实是如何关联的,但它解决了我的问题,现在它按预期运行。

    如果有人知道是什么导致了这个迭代的转变,请告诉我。事实上,我比以前更困惑了。