問題 : http://nabetani.sakura.ne.jp/hena/ordf06numit/
実装リンク集 : https://qiita.com/Nabetani/items/deda571c9451bd7d3175
再帰呼び出ししつつメモ化するの一択だと思うけどどうだろう。
再帰呼び出しが怖い人はスタックを自分で持ったりするんだろうけど、気にせず再帰するとこんな感じ。
まずは ruby で。
ruby2.4.2
class Solver
def initialize( f, g )
@f=f
@g=g
@memo={}
end
def solve( root, num )
return 0 if root<num
return @memo[root] ||= ( root==num ? 1 : 0 ) + solve( @f[root], num ) + solve( @g[root], num )
end
end
class SolverNoMemo
def initialize( f, g )
@f=f
@g=g
end
def solve( root, num )
return 0 if root<num
return ( root==num ? 1 : 0 ) + solve( @f[root], num ) + solve( @g[root], num )
end
end
def solve( src )
Solver.new(
->(x){ x/2-10 },
->(x){ x*2/3 }
).solve( *src.split(?,).map(&:to_i) ).to_s
end
DATA.map{ |line|
num, src, expected = line.split(/\s+/)
actual = solve( src )
ok = actual == expected
p [ ok ? "ok" : "**NG**", src, actual, expected ]
ok
}.all?.tap{ |x| puts( x ? "okay" : "something wrong" ) }
__END__
0 123,4 5 リンク
1 1,1 1 リンク
30 5745432,1032 1287 略
テストデータの大半は省略。「SolverNoMemo
」は、メモのないバージョン。こちらだと1分ぐらいかかる。
メモ化すれば、1秒かからない。
続いて C99 で。
こちらはメモ化ありのバージョンのみ。
c99
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int solve_impl( int root, int num, int * buffer )
{
if ( root<num ){
return 0;
}
if ( root==num ){
return 1;
}
if ( buffer[root] ){
return buffer[root];
}
int a=solve_impl( root/2-10, num, buffer) + solve_impl( root*2/3, num, buffer);
buffer[root]=a;
return a;
}
char const * solve( char const * src )
{
int root = atoi(src);
char const * comma = strchr( src, ',' );
int num = atoi( comma+1 );
int * buffer = calloc( sizeof(int), root+1 );
int ans = solve_impl( root, num, buffer );
free( (void*)buffer);
char s[100];
sprintf( s, "%d", ans );
return strdup(s);
}
void test( char const * src, char const * expected )
{
char const * actual = solve( src );
_Bool okay = 0==strcmp( actual, expected );
printf( "%s %s->%s / %s\n", (okay ? "ok" : "**NG**"), src, actual, expected );
free( (void*)actual );
}
int main(void)
{
/*0*/ test( "123,4", "5" );
/*1*/ test( "1,1", "1" );
/*2*/ test( "2,1", "1" );
/*30*/ test( "5745432,1032", "1287" );
}
この問題なら、C言語でも大して長くならない。
やっぱりメモリの管理が面倒だね。free し忘れても気づかないし。
問題としては一直線すぎるかという懸念もあったんだけど、現場ではいろいろあったり。
楽しんでいただければ幸いです。