LoginSignup
0

More than 5 years have passed since last update.

オフラインリアルタイムどう書く F06 の実装例

Posted at

問題 : 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 し忘れても気づかないし。

問題としては一直線すぎるかという懸念もあったんだけど、現場ではいろいろあったり。
楽しんでいただければ幸いです。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0