10

これは私の宿題だと認めます。タスク ステートメントには、標準入力によって入力されるグラフの位相順序を見つけるプログラムを作成する必要があると書かれていました。次に、教授のサーバーで採点するために提出する必要があります。

今はアルゴリズムの問​​題ではありません。それよりも技術的な問題です。私のコンピュータでは、.NET コンパイラ (csc) を使用していますが、教授のグレーディング マシンは何らかの形式のモノを使用しています。

採点者が私が 30/100 を得たと言うまで、それはうまくいきます。私の友人は、採点者の「手動入力システム」を使用することを提案したので、ここでは、隣接リスト用に 100000 個のリストの配列を作成するようにしました。

採点者は、数秒後、私のプログラムがクラッシュしたと報告しました。

Stacktrace:

at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke

これは私にとってちょっと奇妙で不安ですが、私はまだこれに対する答えを見つけていません. 繰り返しますが、このプログラムは私の PC で問題なく動作しました。

これはプログラムの私の部分です：

using System;
using System.Collections;
using System.Collections.Generic;

class topo{
public static void Main(){
    string[] ST = Console.ReadLine().Split(' ');
    int N=Convert.ToInt32(ST[0]), M=Convert.ToInt32(ST[1]);
    int[] ins = new int[N];  //node's total in-degrees
    List<int>[] E = new List<int>[N];

    for(int n=0;n<N;n++)    
        E[n] = new List<int>();

    for(int m=0;m<M;m++){
        ST = Console.ReadLine().Split(' ');
        int u = Convert.ToInt32(ST[0]);
        int v = Convert.ToInt32(ST[1]);
        E[u-1].Add(v-1);
        ins[v-1]++;
    }

    Queue S = new Queue();
    List<int> L = new List<int>(); //result list

    for(int n=0;n<N;n++){
        //add stranded nodes directly and don't process it
        if(ins[n]==0 && E[n].Count==0)
            L.Add(n);

        //put into queue
        else if(ins[n]==0)
            S.Enqueue(n);
    }

    while(S.Count>0){
        int n = (int) S.Dequeue();
        L.Add(n);
        foreach(int m in E[n])
            if(--ins[m]==0)
                S.Enqueue(m);
    }

    foreach(int n in L)
        Console.WriteLine(n+1);

}

}

どうもありがとうございました。すべての応答に感謝します。

編集：グレーダーの出力をもう一度見て、何か見逃していないかどうかを確認しましたが、実際に見落としていました。「syscal: 2」とありましたが、「プログラムが正常に終了しなかった」ということしかわかりません。

編集＃2：5000、10000などの範囲のさまざまなサイズのリストの配列を作成しようとするプログラムを作成しようとしました.40000の後、「手動入力システム」はプログラムがSystem.OutOfMemoryException. 学生が許可されているグレーダーのさまざまな部分をさらに詳しく調べたところ、教授がグレーディング パラメータを誤って構成し、発表されたよりもメモリが少なかったようです。(彼は「32MB」と言いましたが、約 16MB でプログラムがクラッシュします)

私は彼にエラーを報告しましたが、彼は (現在) 調査中です。

4

2 に答える 2

2

uorの値vが 1 未満の場合、次のコードは失敗します。

for(int m=0;m<M;m++){
    ST = Console.ReadLine().Split(' ');
    int u = Convert.ToInt32(ST[0]);
    int v = Convert.ToInt32(ST[1]);
    E[u-1].Add(v-1);
    ins[v-1]++;
}

u-1orv-1が負になるため、例外がスローされます。

于 2011-03-12T20:29:15.260 に答える