epistemeさんが黒影さんの問題を総当りで解くC++のプログラムを書かれたエントリがあります。
http://jp.thespoke.net/BlogReader/SingleEntry.aspx?ID=38815
これはstlにあるnext_permutationという関数を利用して1-9の全ての並び方を順に列挙して
問題を総当りで解き、答えをmapのキーにいれることで昇順ソートする、というもののようです。
next_permutation・・・C++には、こんな便利な関数があるんですね。知りませんでした。他にも色々ありそうですね。
総当りの結果、キーが整数値となるなかで最大となるものに104は入っていない、ということが証明されましたので、一つ前の僕のエントリの答えは正しい答えの1つである、といえそうです。
ところで、この問題、異なる並び方で同じ答えになってしまうパターンも存在すると思います。しかし、epistemeさんのプログラムでは、キーの重複を許さない map を使っており、重複キーがでたときに以前の結果を上書きしてしまうため、最後に求めた1個だけが出力されてしまうことになるかと思います。そこで、epistemeさんのプログラムを代わりにキーの重複が許されるmultimapを使って書き換えてみました。
変更した部分は色をつけておきました。
#include <iostream>
#include <map>
#include <string>
#include <algorithm>
int main() {
double d[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
char s[] = "123456789";
std::multimap<double, std::string> record;
do {
record.insert(std::pair<double, std::string>(((d[0]*10.0+d[1])/d[2]
+ d[3]/d[4] + d[5]/d[6] + d[7]/d[8]) ,s));
std::next_permutation(d, d+9);
} while ( std::next_permutation(s, s+9) );
for ( std::multimap<double,std::string>::iterator
iter = record.begin();
iter != record.end(); ++iter ) {
std::cout << iter->second << ':'
<< iter->first << std::endl;
}
}
multimapでは[]を使うことができないようですので、代わりにinsertを使いました。たったそれだけの変更で済むようです。キー値が103となるものを貼ってみます。
981435276:103
981437652:103
981524376:103
981527643:103
981764352:103
981765243:103
98/1 + 4/3 + 5/2 + 7/6
98/1 + 4/3 + 7/6 + 5/2
.
.
.
103については、並びかたを変えただけで全て同じ組み合わせのようですね^^;
(キー値が102について見てみると、違う組み合わせのものもあるようです)