-4

2 色と 3 色のソリューションを試しましたが、4 色では解決できません。

助けてください。

でしょうrrbb????yyygggか？緑の旗をどのように交換しますか?

以下の解決策を試しましたが、最後の黄色を緑色に交換してもうまくいきません。

  public class count123 {

// Java program to sort an array of 0, 1 and 2,3

    static void sort0123(int a[], int arr_size)
    {
        int lo = 0;
        int hi = arr_size - 1;
        int mid = 0,temp=0;
        int h2=arr_size - 1;
        while (mid <= hi)
        {
            switch (a[mid])
            {
            case 0:
            {
                temp = a[lo];
                a[lo] = a[mid];
                a[mid] = temp;
                lo++;
                mid++;
                break;
            }
            case 1:
                mid++;
                break;
            case 2:
            {
                temp = a[mid];
                a[mid] = a[hi];
                a[hi] = temp;

                hi--;
                h2=hi;
                break;
            }
            case 3:{
                temp = a[mid];
                a[mid] = a[h2];
                a[h2] = temp;
            //  h2--;
                //hi=h2;
                break;

            }
            }
        }
    }

    /* Utility function to print array arr[] */
    static void printArray(int arr[], int arr_size)
    {
        int i;
        for (i = 0; i < arr_size; i++)
            System.out.print(arr[i]+" ");
            System.out.println("");
    }

    /*Driver function to check for above functions*/
    public static void main (String[] args)
    {
        int arr[] = {0, 1, 0,1,2,2,0,3,3,0,0,1};
        int arr_size = arr.length;
        sort0123(arr, arr_size);
        System.out.println("Array after seggregation ");
        printArray(arr, arr_size);
    }
}
/*This code is contributed by Devesh Agrawal*/
4

6 に答える 6

2

私はあなたのコードを実行し、あなたのコードが無限ループに入ることに気付きました。これにより、プログラムは何もしなくなります。

main メソッドでは、sort0123(arr, arr_size);が呼び出され、このメソッド内では while (mid <= hi)、 mid = 6 および hi = 9 となり6 <= 9ます。これは、この理由により、ある時点で常にケース 3 に移行するという事実により、この条件が無限に true を返すことを意味します。ケース 3 では、mid と hi の値は変更されません。

コードを実行できるようにするには、midand/orの値hiを論理的に変更する必要があります。これにより、プログラムは希望どおりに動作できます。

于 2016-10-09T19:02:07.937 に答える
1

オランダの旗の集約に関するポイントは、不変条件が常に維持されることです。0000...11..XXX..222 のような状態で

  1. lo は常に最初の '1' になります (存在する場合)
  2. mid は常に最初の unknown になります
  3. やあ、いつも最後は不明

4 色のバリエーションの場合、コードのように 0、1、3、2 の順序で並べ替えると仮定すると、次のようにルールを微調整する必要があります。

  1. こんにちはは常に最後の 3 です
  2. h2 は常に最後に不明です

上記の規則に従って、コードを次のように変更する必要があります。

while (mid <= h2)

. . .

case 2:
        {
            temp = a[mid];
            a[mid] = a[hi];
            a[hi] = temp;

            hi--;
            h2--;
            break;
        }
case 3:{
            temp = a[mid];
            a[mid] = a[h2];
            a[h2] = temp;
            h2--;
            break;

        }

0、1、2、3 の順に並べ替えるには、'2' と '3' の case ステートメントを交換するだけです。

PS: 人々が問題を簡単に理解できるように、わかりやすい質問にしてください。

于 2016-10-15T14:41:24.077 に答える