C++で関数の値がAに最も近い数値をリストから検索する方法

関数 F(n) = P − (0.006 × n) があるとします。ここで P はあらかじめ与えられた定数です。さらに、整数のリストと数値 A が与えられたとき、リストの中から「F(n) の値が A に最も近くなる」要素を見つけるのがこの問題の目的です。

例として、P = 12、A = 5、リストが {1000, 2000} の場合を考えてみましょう。まず、F(1000) = 12 − (0.006 × 1000) = 6、次に F(2000) = 12 − (0.006 × 2000) = 0 と計算できます。A = 5 に最も近い値は 6 であるため、答えは 1000 となります。

解法の考え方

アプローチは非常にシンプルです。リスト内の各要素 n に対して F(n) を順番に計算し、それぞれの F(n) と A の絶対差 |F(n) − A| を比較します。この絶対差が最小となる要素 n が求める答えになります。

C++による実装例

#include<iostream>
#include<cmath>
using namespace std;
int nearestValue(int P, int A, int N, int arr[]) {
   int ans = -1;
   float temp = (float)INFINITY;
   for (int i = 0; i < N; i++) {
      float term = P - arr[i] * 0.006;
      if (abs(term-A) < temp) {
         temp = abs(term - A);
         ans = i;
      }
   }  
   return arr[ans];
}
int main() {
   int P = 12, A = 5;
   int array[] = {1000, 2000, 1001};
   int N = sizeof(array)/sizeof(array[0]);
   cout << "Nearest value is: " << nearestValue(P, A, N, array) << endl;
}

実行結果

Nearest value is: 1001

上記のプログラムでは、リスト {1000, 2000, 1001} の中から F(n) が A = 5 に最も近くなる要素を探しています。F(1000) = 6、F(2000) = 0、F(1001) = 5.994 と計算できるため、A = 5 に最も近い 5.994 を持つ 1001 が出力されます。

このアルゴリズムの計算量は O(N) です。リストの要素数に比例した時間で処理が完了するため、実用的な範囲のデータサイズであれば十分に高速に動作します。