totarget.c

問題はこちら
http://nabetani.sakura.ne.jp/hena/ord13updowndouble/

再帰処理でひたすら、目的の値になるルートを探すアルゴリズム。
たぶん、テストデータ全ての結果がでるまで、ものすごく時間かかりそうなので、
あまり良いアルゴリズムではないと思います。
でも、面白いコードになったので、載せてみました。

探索開始の値は0ではなく２からにして、最大でも１回の探索の計算量が3の25乗回になるようにしてます。
再帰処理で探索する深さを1ずつ増やし、毎回２から再計算しています。
このため、遅いです。

最初の条件((v <= 2 && c > 2) || v > t+1 || c >= i)でなるべく枝切りして、計算量を削減してます。

別解はこちら
http://qiita.com/saihon2013/items/7aad77be492ddd57c8c6

# include <stdio.h>
# include <stdlib.h>

int solve(const int t, const int v, const int c, const int i)
{
  return 
    ((v <= 2 && c > 2) || v > t+1 || c >= i) ? 0:
    (t == v) ? 1:
    (solve(t,v<<1,c+1,i)) ? 1:
    (solve(t,v +1,c+1,i)) ? 1:
    (solve(t,v -1,c+1,i)) ? 1: 0;
}

void test(const char * const input, const char * const ans)
{
  int t = atoi(input), i;
  for(i=2; solve(t,2,2,i+1)!=1; i++);
  printf("%d\t%s\n", i, (atoi(ans) == i) ? "OK": "NG");
}

int main()
{
/*0*/ test( "59", "9" );    
/*1*/ test( "10", "5" );    
/*2*/ test( "11", "6" );    
/*3*/ test( "12", "5" );    
/*4*/ test( "13", "6" );    
/*5*/ test( "14", "6" );    
/*6*/ test( "15", "6" );    
/*7*/ test( "16", "5" );    
/*8*/ test( "17", "6" );    
/*9*/ test( "18", "6" );    
/*10*/ test( "27", "8" );    
/*11*/ test( "28", "7" );    
/*12*/ test( "29", "8" );    
/*13*/ test( "30", "7" );    
/*14*/ test( "31", "7" );    
/*15*/ test( "32", "6" );    
/*16*/ test( "33", "7" );    
/*17*/ test( "34", "7" );    
/*18*/ test( "35", "8" );    
/*19*/ test( "41", "8" );    
/*20*/ test( "71", "9" );    
/*21*/ test( "1023", "12" );    
/*22*/ test( "1024", "11" );    
/*23*/ test( "1025", "12" );    
/*24*/ test( "1707", "17" );    
/*25*/ test( "683", "15" );    
/*26*/ test( "123", "10" );    
/*27*/ test( "187", "11" );    
/*28*/ test( "237", "12" );    
/*29*/ test( "5267", "18" );    
/*30*/ test( "6737", "18" );    
/*31*/ test( "14796", "20" );    
/*32*/ test( "18998", "20" );    
/*33*/ test( "23820", "20" );    
/*34*/ test( "30380", "21" );    
/*35*/ test( "31119", "21" );    
/*36*/ test( "33301", "20" );    
/*37*/ test( "33967", "21" );    
/*38*/ test( "35443", "22" );    
/*39*/ test( "35641", "22" );    
/*40*/ test( "43695", "23" );    
/*41*/ test( "44395", "23" );    
/*42*/ test( "44666", "22" );    
/*43*/ test( "987", "14" );    
/*44*/ test( "1021", "13" );    
/*45*/ test( "1019", "13" );    
/*46*/ test( "1015", "13" );    
/*47*/ test( "1007", "13" );    
/*48*/ test( "1011", "14" );    
/*49*/ test( "1003", "14" );    
/*50*/ test( "983", "14" );    
/*51*/ test( "999", "14" );    
/*52*/ test( "2731", "18" );    
/*53*/ test( "6827", "20" );    
/*54*/ test( "10923", "21" );    
/*55*/ test( "27307", "23" );    
/*56*/ test( "43691", "24" );    
/*57*/ test( "109227", "26" );    
/*58*/ test( "174763", "27" );
  return 0;
}