[RUBY] Beispiel für die Implementierung der F06-Implementierung in Echtzeit

Problem: http://nabetani.sakura.ne.jp/hena/ordf06numit/ Implementierungslinks: https://qiita.com/Nabetani/items/deda571c9451bd7d3175

Ich denke, es ist eine Option, ein Memo zu erstellen, während es rekursiv aufgerufen wird. Personen, die Angst vor rekursiven Aufrufen haben, haben möglicherweise ihren eigenen Stapel. Wenn Sie jedoch erneut auftreten, ohne sich darüber Gedanken zu machen, sieht es so aus. Zuerst mit Rubin.

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 Links
1 1,1 1 Link
30  5745432,1032 1287 Abkürzung

Die meisten Testdaten werden weggelassen. "SolverNoMemo" ist eine Version ohne Notizen. Hier dauert es ungefähr 1 Minute. Wenn Sie ein Memo erstellen, dauert es weniger als eine Sekunde.

Dann mit C99. Dies ist nur die Version mit Memo.

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" );  
}

Dieses Problem wird in C nicht mehr lange.

Immerhin ist die Speicherverwaltung mühsam. Wenn Sie vergessen, es freizugeben, werden Sie es nicht bemerken.

Es gab Bedenken, dass es als Problem zu direkt sein könnte, aber es gab verschiedene Dinge auf dem Gebiet. Ich hoffe du genießt es.