0

ある種のソートアルゴリズムをC++で書き、それを疑似コードで書き上げようとしていますが、疑似で書くのはそれほど悪くはありませんが、頭の中で理解するのは苦労しているので、皆さんに質問します:

2つの整数（BとCとしましょう）とともにソートされていない配列を取り、AにBよりも大きくCよりも小さい要素が含まれている場合はTRUEを出力し、そうでない場合はFALSEを返すアルゴリズムを作成しようとしています。

For J <-- 1 to Length[A]
       Count <-- j+1
              while Count =< Length[A]

これは私の疑似コードの始まりです。最初から論理的なことのように思えたので、C ++で実装しましたが、ループを作成してぐるぐる回り、あまり進歩していないことに気付きました。私が言ったことすべてが理にかなっていて、誰かがそれをまとめて何らかの形の解決策を作成できることを願っています. ありがとう。

4

4 に答える 4

1

Steve McConnell のCode Completeから思い出すと、疑似コードは理想的には実際よりもはるかに英語に似ている必要があります。私の謙虚な意見では、実装へのジャンプが速すぎます。

これはどうですか：

for each element in array
    check to see if element is between B and C
    if element is between B and C
        return TRUE
    else
        continue loop
next

return FALSE

それがあなたの声明から私が収集するものです：

2つの整数（BとCとしましょう）とともにソートされていない配列を取り、AにBよりも大きくCよりも小さい要素が含まれている場合はTRUEを出力し、そうでない場合はFALSEを返すアルゴリズムを作成しようとしています。

于 2012-10-31T18:09:25.133 に答える
1

気になる状態をチェックする関数から始めます。与えられた数値が、指定された範囲内にあるかどうかを確認します。

boolean function in_range(A, B, C) {
    return (A > B) and (A < C);
}

そこから、配列をスキャンして関数を呼び出し、配列の各要素をA(および and として提供されたBandCとしてB)渡すという単純な問題になりCます。関数がtrue任意の時点で戻る場合は、スキャンを停止でき、外側の関数も true を返します (価値があるのは、C++11std::any_ofがこの種の状況を提供しているためです)。

于 2012-10-31T18:11:02.447 に答える
0

条件x>B&& x <Cに一致する配列内のxを検索しているだけです。線形検索を実行すると、検索を1回だけ実行する場合に実行されます。検索を複数回実行する必要がある場合（ログ（配列のサイズ）以外）は、最初に並べ替えてからバイナリ検索を実行するのが理にかなっています。

bool InRangeSearch(low, high)
{
  index = upper_bound(array, low);
  if(index==-1)
    return false;

  index2 = lower_bound(array, high);
  if(index2==-1)
    return true;

  return ((index2-1)>index);
}
于 2012-10-31T18:33:15.747 に答える
0

擬似コード:

Quicksort(A as array, low as int, high as int)
    if (low < high)
        pivot_location = Partition(A,low,high)
    Quicksort(A,low, pivot_location - 1)
    Quicksort(A, pivot_location + 1, high)

Partition(A as array, low as int, high as int)
     pivot = A[low]
     leftwall = low

     for i = low + 1 to high
         if (A[i] < pivot) then
             leftwall = leftwall + 1
             swap(A[i], A[leftwall])

     swap(A[low],A[leftwall])

    return (leftwall)

プログラムコード:

#include <stdio.h>

void quickSort( int[], int, int);
int partition( int[], int, int);


int  main() 
{
    int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};

    int i;
    printf("\n\nUnsorted array is:  ");
    for(i = 0; i < 9; ++i)      printf(" %d ", a[i]);

    quickSort( a, 0, 8);

    printf("\n\nSorted array is:  ");
    for(i = 0; i < 9; ++i)      printf(" %d ", a[i]);

    printf("\n\n " );
    return 0;

}



void quickSort( int a[], int l, int r)
{
   int j;

   if( l < r ) 
   {

        j = partition( a, l, r);
       quickSort( a, l, j-1);
       quickSort( a, j+1, r);
   }

}



int partition( int a[], int l, int r) {
   int pivot, i, j, t;
   pivot = a[l];
   i = l; j = r+1;

   while( 1)
   {
    do ++i; while( a[i] <= pivot && i <= r );
    do --j; while( a[j] > pivot );
    if( i >= j ) break;
    t = a[i]; a[i] = a[j]; a[j] = t;
   }
   t = a[l]; a[l] = a[j]; a[j] = t;
   return j;
}
于 2012-10-31T19:18:25.560 に答える