01.Blogs :
mocchi  

さんすうのもんだいをごりごりとく:改?

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について見てみると、違う組み合わせのものもあるようです)

posted on Wednesday, July 20, 2005 7:22 AM by mocchi


 
03.UPDATE CALENDAR :
<July 2005>
SunMonTueWedThuFriSat
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

05.MY LINKS :

07.Subscriptions :

Subscriptions


© Copyright 2005 Microsoft Corporation. All Rights Reserved.
Terms of Use | Privacy Statement | Code of Conduct | Hosted by MaximumASP for Microsoft
WHO-BAR