で、ドラゴン曲線を生成する関数をSTLで書いてみる。
#include <string>
#include <algorithm>
std::string next_dragon(const std::string& dragon) {
struct flip { char operator()(char c) const
{ return c == 'L' ? 'R':'L'; } };
std::string tail(dragon.size()+1,'L');
std::transform(dragon.rbegin(),dragon.rend(),tail.begin()+1,flip());
return dragon + tail;
}
// おためし
#include
int main() {
std::string dragon = "";
for ( int i = 0; i < 10; ++i ) {
std::cout << (dragon = next_dragon(dragon)) << std::endl;
}
}
…んー、algorithmモノにはSTL強いわぁ♪
[追記] ここにいんすぱいあ（欧米か!）されて空間計算量をケチった版:
#include <vector>
#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>
typedef std::vector<bool> dragon_vector;
void next_dragon(const dragon_vector& dragon, dragon_vector& result) {
result.assign(dragon.begin(), dragon.end());
result.resize(dragon.size()*2+1);
dragon_vector::iterator iter = result.begin();
std::advance(iter, dragon.size());
*iter++ = false;
std::transform(dragon.rbegin(),dragon.rend(),
iter,std::logical_not<bool>());
}
int main() {
dragon_vector in, out;
for ( int i = 1; i < 50; ++i ) {
next_dragon(in, out);
std::cout << i << '\t' << out.size() << std::endl;
in.swap(out);
}
}
こいつでためしてみたところ、31回折れました。
折り目の数は21億超。