配列の中で一番近い値を求める。
配列の中で一番近い値を求める。
つまり近似値を求める関数はないものでしょうか？
たとえば500という数字があった場合。
515
505
489
という配列の数字があった場合。
500に一番近い数字は505ともとめる
関数はないものでしょうか？
＞関数はないものでしょうか？
そのものずばりはない気がします。
でも配列をソートして探索して近い値を探す方法が考えられます。
515
505
489
↓
489
505
515
として505付近で
abs(500-489)=11
abs(500-505)=5
の数が小さいほうを選択するとか。
ソート後の探索にはバイナリサーチなどを使うどか。
すべての中で最も近い、ということだと最低１回は全要素を見る必要がある
ソートなど不要だと思うよ。頭から最後まで順に総なめしながら、
目標値との差が最小なものを保持すればそれでいい
近傍値が複数個有る場合の選択方法を決めておく必要がある
500 に対して 501 と 499 が両方存在する場合にどう取り扱うのか？
> ソートなど不要だと思うよ。
ですね、目標値との差が最も近い"ふたつ"を覚えておけばよさそう。
その"ふたつ"が目標値と同じだけ異なっていたときどうするかは別問題。
> 目標値との差が最も近い"ふたつ"を覚えておけばよさそう。
あー、ダメダメ。
↓とりあえずこんなところで。
#include <iostream>
#include <algorithm>
#include <iterator>
#include <functional>
template<typename T>
struct norm : std::binary_function<T,T,T> {
T operator()(T x, T y) const { return std::max(x-y,y-x); }
};
template<typename T>
struct norm_less : std::binary_function<T,T,bool> {
T value_;
norm_less(T v) : value_(v) {}
bool operator()(T x, T y) const { norm<T> f; return f(x,value_) < f(y,value_); }
};
int main(){
const int N = 8;
int data[N] = { 1, 2, 3, 3, 5, 5, 6, 7 };
int target = 4;
norm<int> n;
int min_norm = n(*std::min_element(data, data+N, norm_less<int>(target)),target);
for ( int i = 0; i < N; ++i ) {
if ( n(target,data[i]) == min_norm ) std::cout << data[i] << ' ';
}
}
えっと、あえて訊きますけど
int data[] = { -2147483647, -1, 0, 1, 2147483647};
int target = 2147483647;
な場合に正しい値を得るにはどうしませう
あー... 差の絶対値を求めるときにオーバーフローするってかー...
template<typename T>
struct norm : std::binary_function<T,T,T> {
T operator()(T x, T y) const { return x > y ? x - y : y - x; }
};
ってことでいかがっすか?
...ダメだー orz
俺もあまりいい解がうかばないんだけど、この程度で許してたもれ
template<typename T>
struct norm : std::binary_function<T,T,T> {
T operator()(T x, T y) const {
T diff((x>y)?x-y:y-x);
if (diff<0) diff=std::numeric_limits<T>::max();
return diff;
}
};
テンプレートのソースが理解できるなら、そもそもこんな質問はして来ない気がするんだけど…そう思うのは俺だけ？
> テンプレートのソースが理解できるなら、そもそもこんな質問はして来ない気がするんだけど…
そうかもしれないし、そうでないかもしれない。
いずれにせよキモは:
1. 配列のアタマからケツまで舐めて、基準値に一番近い値xをひとつ見つける。
2. 再度配列をアタマからケツまで舐めて(1)で求めた"xと基準値との差"と同じ差を持つ要素を列挙する。
# 一個見つけるだけでいいのなら、(2)は不要。
俺もそう思う。元発言をネタにして楽しませてもらってるのは否定しない
ただ単に探すだけのＣサンプルを提示してみる。
先の問題点はそのまま残してあるし、それ以外にもまずいとこがある。
探すだけなら無駄な処理もやってる。見つけて修正、は宿題にしとこう。
int find_nearest(int target, const int* a, size_t n) {
int result=*a;
int nearest_err=abs(*a-target);
for (--n,++a; n>0; --n,++a) {
int err=abs(*a-target);
if (err<nearest_err) { nearest_err=err; result=*a; }
}
return result;
}
| ツイート |  |