C++ プログラミング | 回転されたソート済みベクトル | 最小要素

はじめに

この実験では、回転されたソート済みベクトルの最小要素を見つけるための C++ プログラムを作成します。ソート済みベクトルは、事前に知らないいくつかのピボット要素で回転させることができます。

必要なライブラリをインクルードして名前空間を宣言する

まず、必要なライブラリをインクルードして名前空間を宣言する必要があります。このコードは ~/project/main.cpp ファイルに記述されます。ステップ 1 の完全なコードを以下に示します。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

最小要素を見つける関数を作成する

回転されたソート済みベクトルの最小要素を見つけるために、findMin という名前の関数を作成します。この関数では、ベクトルの各要素をループして、その要素が最小要素であるかどうかをチェックします。要素が最小であるかどうかをチェックするロジックは、コードブロックのコメントに説明されています。ステップ 2 の完全なコードを以下に示します。

int findMin(vector<int> &m)
{
    int i;
    int n = m.size();
    for (i = 0; i < n; i++)
    {
        if (i == 0)
        {
            // 最初の要素をチェックする
            if (m[i] < m[n - 1] && m[i] < m[1])
                break;
        }
        else
        {
            // その他のすべての要素をチェックする
            if (m[i] < m[i - 1] && m[i] < m[(i + 1) % n])
                break;
        }
    }
    return m[i % n];
}

コードをテストするためのメイン関数を書く

メイン関数では、v という名前のベクトルを作成し、いくつかの要素で初期化します。その後、findMin 関数を呼び出して、ベクトル内の最小要素を見つけます。最後に、最小要素を出力します。ステップ 3 の完全なコードを以下に示します。

int main()
{
    vector<int> v = {4, 5, 6, 7, 1, 3, 2};
    int n = v.size();
    int minimum = 0;
    cout << "The elements of the given vector are: ";
    for (int i = 0; i < n; i++)
    {
        cout << v[i] << " ";
    }
    minimum = findMin(v);
    cout << "\n\nThe Minimum element in the given vector is: " << minimum << endl;
    return 0;
}

コードをコンパイルして実行する

ターミナルウィンドウで、cd コマンドを使用して main.cpp ファイルがあるディレクトリに移動します。次に、以下のコマンドを使用してコードをコンパイルします。

g++ main.cpp -o main

エラーがなければ、以下のコマンドを使用して実行可能ファイルを実行します。

./main

以下の出力が表示されるはずです。

The elements of the given vector are: 4 5 6 7 1 3 2
The Minimum element in the given vector is: 1

この出力は、ベクトル内の正しい最小要素をコードが見つけたことを確認しています。

まとめ

この実験では、回転されたソート済みベクトル内の最小要素を見つけるための C++ プログラムを作成しました。ベクトル内の各要素をループして、その要素が最小要素であるかどうかをチェックすることでこれを達成しました。最後に、最小要素をコンソールに出力しました。この実験があなたのプログラミング学習の旅に役立ったことを願っています。