Q01 10進数で回文

from プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

回答

seq 11 2 10000 | awk '{l=length($1);for(i=1;i<=int(l/2);i++)if(substr($1,i,1)!=substr($1,l-i+1,1))next;print}' | awk 'BEGIN{n=8}{a=$NF;b="";while(a>0){b=a%n b;a=int(a/n)}print b,$0}' | awk '{l=length($1);for(i=1;i<=int(l/2);i++)if(substr($1,i,1)!=substr($1,l-i+1,1))next
;print}' | awk 'BEGIN{n=2}{a=$NF;b="";while(a>0){b=a%n b;a=int(a/n)}print b,$0}' | awk '{l=length($1);for(i=1;i<=int(l/2);i++)if(substr($1,i,1)!=substr($1,l-i+1,1))next;print}' | sed 1q

1001001001 1111 585

real    0m0.012s
user    0m0.000s
sys     0m0.000s

コードが長いわりには、結構速いのでびっくりした。

解説

2進数で回文になる=末尾が0ではない=奇数を探せば良い

# 上限は何となく 10000 で仮決め
seq 11 2 10000 |

# 10進数で回文のものを抽出
# と言うか、先頭フィールドが回文になっているものを抽出
awk '{

  # 先頭フィールドの文字列長(この時点では10進数の値)を取得
  l=length($1);

  # 回文になっているかの判定
  # 1桁目から中間桁(奇数桁のときは中央桁の1つ前)までが、
  # 末尾桁目から中間桁(奇数桁のときは中央桁の1つ後ろ)までが一致するかをチェック
  for(i=1;i<=int(l/2);i++)
    if(substr($1,i,1)!=substr($1,l-i+1,1))

      # 一致しない場合、処理を中断し、次の値の処理に移る
      next;

  # 回文になっているので出力
  print
}' |

# 8進数を計算
awk '

# 基底を8にする
BEGIN{n=8}
{
  # 末尾のフィールドを変換対象にする
  a=$NF;

  # n進数を格納する変数を初期化
  b="";

  # 商が0になるまでnで割り続ける
  while(a>0){

    # 剰余を下位桁から結合する
    b=a%n b;

    # 商を次の計算対象にする
    a=int(a/n)
  }
  # n進数の計算結果を先頭にし、入力行を後ろに繋げて出力
  print b,$0
}' |

# 8進数で回文のものを抽出(10進数の時と同一ロジック)
awk '{l=length($1);for(i=1;i<=int(l/2);i++)if(substr($1,i,1)!=substr($1,l-i+1,1))next;print}' |

# 2進数を計算(8進数の時と同一ロジック)
awk 'BEGIN{n=2}{a=$NF;b="";while(a>0){b=a%n b;a=int(a/n)}print b,$0}' |

# 2進数で回文のものを抽出(10進数の時と同一ロジック)
awk '{l=length($1);for(i=1;i<=int(l/2);i++)if(substr($1,i,1)!=substr($1,l-i+1,1))next;print}' |

# 最初の数字を表示したら終了
sed 1q

備考

rubyに勝った
time ruby q01.rb

585

real    0m0.070s
user    0m0.060s
sys     0m0.000s

javascriptに勝った
time node q01.js

585

real    0m0.505s
user    0m0.430s
sys     0m0.070s

q01.{rb,js} は プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問 に記載のコードです。


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2017-08-16 (水) 23:06:30