4色のオランダ国旗

Question

私は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*/ 

Answer 1

私はあなたのコードを実行し、あなたのコードは、あなたのプログラムの開発は、何もしないんせ無限ループ、に入ることに気づきました。 mainメソッド、sort0123(arr, arr_size);で

が呼び出され、このメソッド内で、while (mid <= hi)、ミッド= 6、HI = 9、それは6 <= 9を意味し、このためresaonであり、この条件があるため、それがに常に行くという事実を無限にtrueを返しますある時点でケース3、ケース3では、midおよびhiの値は変更されない。

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

Answer 2

オランダのフラグ集合についての点は、不変量が常に維持されている点です。な0000などの状態では... 11..XXX..222

1. loが常に半ばには、常に最初の未知
になります
2. 最初の「1」（存在する場合）になります
3. HIコードからケースのように思えるように注文0,1,3,2にソートされていると仮定し、4色のバリエーションについては、最後の未知

で常にある、ルールはする必要があります。

3. HIは、上記の規則に続き、最後不明

で常にある、コードは次の方法で変更する必要があります最後の3

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」のケースステートメントを交換します。

PS：簡単に問題を理解できるように質問を説明してください。