オフラインリアルタイムどう書く
- 第13回(9月6日) http://atnd.org/events/41603
- 第14回(9月28日) http://atnd.org/events/43076
の、参考問題「増やす減らす二倍する」
http://nabetani.sakura.ne.jp/hena/ord13updowndouble/
の実装例。
まだ出てない言語で出すべきだといかいうルールはないけど、groovy。
他の言語などの解答例は
http://qiita.com/Nabetani/items/89fb0e2e712d4b396535
から辿れます。
で。
//Groovy Version: 2.1.5 JVM: 1.7.0_07 Vendor: Oracle Corporation OS: Mac OS X
int solver( int src )
{
if ( src==0 ){
0;
} else if (( src & 3 )==3){
1+Math.min( solver(src-1), solver(src+1) )
} else if(src & 1){
1+solver(src-1)
} else {
1+solver(src>>1)
}
}
def test( src, expected )
{
String actual = solver( src.toInteger() ).toString();
println( [expected==actual ? "ok" : "***NG***", src, actual, expected ] )
}
/*0*/ test( "59", "9" );
/*1*/ test( "10", "5" );
/*2*/ test( "11", "6" );
いつも通り、テストデータの大半は省略。
で。
順当に行けばまずは幅優先探索。
でも全部やるのはちともったいないので逆にたどることにして
- 0 なら 0 手で到達可能。初期状態
- 2進数で下二桁が 11 の場合、[-1] を押した結果なのか[+1]を押した結果なのか判断しかねるので、両方試す。
- ２進数で下二桁が 01 の場合は [+1] を足した直後だと思うことにする。
- 偶数なら、[×2]を押した直後だろう
という方針にしてみた。
中途半端な感じ。
これで計算が終わるかどうかはちゃんと考えないとよくわからないんだけど、まあおわるみたいだからよしとする。
switch〜case にしてみてもよかったかも。