c++ - 最低値を削除するにはどうすればよいですか?

Question

私は C++ にかなり慣れていないので、ランダムに生成された一連の数値の最小値を削除するためのコードを理解するのに助けが必要です。これまでの私のコードは次のとおりです。

   //Create array and populate the array with scores between 55 and 10
//  Drop lowest Score 

#include <iostream>
#include <cstdlib>//for generating a random number
#include <ctime>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;


//function prototype
int *random (int);


int main()
{   int *numbers; //point to numbers
    //get an array of 20 values
    numbers = random(20);
    //display numbers
    for (int count = 0; count < 20; count++)
        cout << numbers[count] << endl;
    cout << endl;


system("pause");
    return 0;
}

//random function, generates random numbers between 55 and 100 ??

int *random(int num)
{   int *arr; //array to hold numbers
    //return null if zero or negative
    if (num <= 0)
        return NULL;
    //allocate array
    arr = new int[num];
    //seed random number generator
    srand(time (0));
    //populate array
    for (int count = 0; count < num; count++)
        arr[count] = (rand()%(45) +55);
    //return pointer

    //
    return arr;
}

このコードの場合、関数が乱数を返した後、最低スコアをソートまたは検索してドロップするにはどうすればよいでしょうか?

  int main()
    {   int *numbers; //point to numbers
        //get an array of 20 values
        numbers = random(20);
        //display numbers
        for (int count = 0; count < 20; count++)
            cout << numbers[count] << endl;
        cout << endl;


    system("pause");
        return 0;
    }

あなたの提案は大歓迎です！

score 4 · Accepted Answer

一般に、配列内の最小値を見つけるには、次の疑似アルゴリズムに従うことができます。

min = array[0] // first element in array
for (all_values_in_array)
{
    if (current_element < min)
        min = current_element
}

ただし、静的配列から値を「削除」することはできません。動的コンテナー (ベクトルなど) を使用するか、最小値を最後の値と交換し、配列のサイズが 1 小さいふりをすることを検討できます。別の低レベルのオプションは、ヒープに独自の動的配列を作成することですが、これはおそらく探しているよりも複雑です。

ベクトルを使用すると、はるかに簡単になります。最下位の要素を削除するには、逆の順序で並べ替えてから、最後の要素を削除する必要があります。個人的には、ベクトルを使用することをお勧めします。

score 2 · Accepted Answer

最小の要素を見つける明白な方法は、を使用することstd::min_element()です。おそらく要素を保持するために使用したいでしょうstd::vector<T>が、これは絶対に必要というわけではありません。次のように、配列から最小値を削除できます。

if (count) {
    int* it = std::min_element(array, array + count);
    std::copy(it + 1, array + count--, it);
}

代わりに合理的に使用されていると仮定するとstd::vector<int>、コードは次のようになります。

if (!array.empty()) {
    array.erase(std::min_element(array.begin(), array.end()));
}

score 0 · Accepted Answer

最初に最小数のインデックスを見つけます。

int lowest_index=0, i;
for (i=0; i<20; i++)
    if (arr[i]<arr[lowest_index])
        lowest_index=i;

インデックスがわかったので、そのインデックスの後に続く数字を移動して、見つかったインデックスを上書きします。移動する数字の数は、19 から見つかったインデックスを引いたものになります。つまり、インデックス 2 (最初の数字はインデックス 0 であるため、3 番目の数字) が最小の場合、17 個の数字がそのインデックスの後に来るので、それが移動する必要がある数です。

memcpy(&arr[lowest_index],&arr[lowest_index+1],sizeof(int)*(19-lowest_index))

幸運を！

score 0 · Accepted Answer

私の意見では、あなたの問題に対する最も最適な解決策は、リンクされたリストを使用して数値を格納することです。このようにして、複雑さO(N) = Nのアルゴリズムを使用してリスト内の最小要素を見つけることができます。 user1599559 または Mikael Lindqvist によって指定されたメソッドを見つけるには、それを格納するリンクリスト内の Item( ItemX )へのポインタを最小値と共に格納するだけで済み、次にItem Xを削除するには、 Item X - 1がItem X +を指していることを伝えるだけです。1と項目 X によって割り当てられた空きメモリ

score 0 · Accepted Answer

配列を昇順に並べ替えます。
最小値は配列の先頭になります。

または、配列を降順に並べ替えて、最後の要素を削除します。

score 0 · Accepted Answer

他の人が言ったことに加えて、おそらく std::list のようなものを使用することもできます。ソートが組み込まれており、2 つの要素に対して独自の比較関数を定義することもできます。(ただし、int の場合、これは必要ありません)

まず、通常、ベクターまたはリストを、含まれる要素の型で型定義します。次に、リストの場合、イテレータを typedef します。これらはどちらも便利なだけですが、どちらも必須ではありません。

int を保持するリストを取得したら、それらを追加するだけです。習慣であり、それ以外のことを行う必要がないということは、新しい要素を追加するために .push_back を使用することを意味します。完了したら、リストを並べ替え、最小値 (最小の「インデックス」 - 最初の項目) を持つ要素を取得し、最後にその項目を削除します。

熟考するいくつかのコード:

#include <cstdio>
#include <cstdlib>
#include <list>


using namespace std;

typedef list<int> listInt;
typedef listInt::iterator listIntIter;

bool sortAsc(int first, int second)
{
    return first < second;
}

bool sortDesc(int first, int second)
{
    return first > second;
}

int main (void)
{
    listInt mList;
    listIntIter mIter;
    int i, curVal, lowestScore;

    for (i=1; i<=20; i++)
    {
        curVal = rand()%45 + 55;
        mList.push_back(curVal);
        printf("%2d. %d\n", i, curVal);
    }
    printf("\n");

    mList.sort();
//    mList.sort(sortAsc);  // in this example, this has the same effect as the above line.
//    mList.sort(sortDesc);

    i = 0;
    for (mIter=mList.begin(); mIter!=mList.end(); mIter++)
        printf("%2d. %d\n", ++i, *mIter);
    printf("\n");

    lowestScore = mList.front();
    mList.pop_front();
    printf("Lowest score: %d\n", lowestScore);

   return 0;
}

ああ、cout ではなく printf を使用するという選択も意図的なものでした。いくつかの理由があります。

printf("%d\n", someVar); 個人的な好み -よりも入力しやすいと思いますcout << someVar << endl;
サイズ - Windows で gcc を使用してビルドした場合、この例のリリースモード exe は 21kb です。cout を使用すると、同じ機能で 459kb に跳ね上がります。利益なしでサイズが 20 倍に増加しますか? 結構です！！

ここに std::list リファレンスがあります: http://www.cplusplus.com/reference/stl/list/

c++ - 最低値を削除するにはどうすればよいですか?

6 に答える 6

Related

Reference