急勾配の判定
Posted feedbacks - C++
計算量はO(n)ですが、リストを尻から舐めてくと多少は無駄な計算が抑えられるかなー、と。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
template <typename T>
struct not_steep_slope {
T sum_;
not_steep_slope() : sum_(0) {}
bool operator()(T v) {
if (v <= sum_) return true;
sum_+=v;
return false;
}
};
template <typename T>
bool is_steep_slope(const std::vector<T>& v) {
return std::find_if(v.rbegin(), v.rend(), not_steep_slope<T>()) == v.rend();
}
template <typename T>
void check(const std::vector<T>& v) {
std::cout << "(";
std::copy(v.begin(), v.end(), std::ostream_iterator<T>(std::cout, ","));
std::cout << ") => " << is_steep_slope(v) << "\n";
}
int main() {
std::cout.setf( std::ios::boolalpha );
std::vector<int> v;
check(v);
v.push_back(1);
check(v);
v.front() = 0;
check(v);
v.clear();
v.push_back(32);
v.push_back(16);
v.push_back(8);
v.push_back(4);
v.push_back(2);
v.push_back(1);
check(v);
v[1] = 15;
check(v);
return 0;
}
|
nobsun
#8891()
Rating1/1=1.00
有限の長さの数列で，各要素の値が，その要素の後ろにある残りの列に含まれるすべての要素の和よりも大きい列を「急勾配の列」ということにします（空列の和は0とします）．
任意の長さ（ただし有限の長さの）数列を与えられたとき，それが「急勾配の列」であるかどうかを判定する述語関数を定義してください．
必須ではありませんが，効率についてコメントがあれば面白いかもしれませんね．
[ reply ]