問題(和訳)

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2036

回答例(ver.2)

$ seq 999999 | paste - <(seq 999999|rev) | awk '$1==$2{a="";b="";p=$1;while(p){q=p%2;a=q""a;b=b""q;p=int(p/2)}print $1,a,b}' | awk '$2==$3{a+=$1;print $1,$2}END{print "answer:",a}'

1 1
3 11
5 101
7 111
9 1001
33 100001
99 1100011
313 100111001
585 1001001001
717 1011001101
7447 1110100010111
9009 10001100110001
15351 11101111110111
32223 111110111011111
39993 1001110000111001
53235 1100111111110011
53835 1101001001001011
73737 10010000000001001
585585 10001110111101110001
answer: 872187
 
real    0m0.593s
user    0m0.490s
sys     0m0.100s

解説(ver.2)

awk の中から外部コマンド(bc, rev)を呼ぶと遅いので、なるべくawkで済ませます。これだけで劇的に処理時間が短縮されます。

 # 100万未満の数を生成
 seq 999999 | 
 
 # ひっくり返してくっつける
 paste - <(seq 999999|rev) | 
 
 # 回文数ならば、、、
 awk '$1==$2{
 
   # 2進数表記(a)と、逆にひっくり返したもの(b)を生成
   a="";
   b="";
   p=$1;
 
   # ひたすら2で割り、余りを結合していく
   while(p){
     q=p%2;
     a=q""a;    # 2で割った余りを上位桁へくっつける
     b=b""q;    # 上記と反対に、下位桁へくっつける
     p=int(p/2)
   }
 
   # 結果を表示
   print $1,a,b
 
 }' |
 
 # 2進数表記が回文数ならば、、、 
 awk '$2==$3{
 
   # 合計値を求める
   a+=$1;
 
   # (おまけ)回文数を表示する
   print $1,$2
 
 }END{
 
   # 答えを表示する
   print "answer:",a
 
 }'

回答例 (ver.1)

$ time seq 999999 | paste - <(seq 999999|rev) | awk '$1==$2{print $1}' | sed 's/[0-9]*/& obase=2;ibase=10;&/' | awk '{"echo \047"$2"\047|bc"|getline f;print $1,f}' | awk '{"echo "$2"|rev"|getline f;print $0,f}' | awk '$2==$3{print $1,$2}' | awk '{a+=$1}END{print a}'

872187

real    0m10.554s
user    0m5.628s
sys     0m12.919s

10秒ちょいだからまぁいいか。

解説

 # 100万未満の整数
 seq 999999 | 
 
 # 回文を作って並べる
 paste - <(seq 999999|rev) | 
 
  # 10進数で回文のものを抽出
  awk '$1==$2{print $1}' | 
 
 # bcで2進数を作るためのコマンド生成
 sed 's/[0-9]*/& obase=2;ibase=10;&/' | 
 
 # bcで2進数に変換
 awk '{"echo \047"$2"\047|bc"|getline f;print $1,f}' | 
 
 # 2進数の回文を作って並べる
 awk '{"echo "$2"|rev"|getline f;print $0,f}' | 
 
 # 2進数で回文のものを抽出
 awk '$2==$3{print $1,$2}' | 
 
 # 答えを計算
 awk '{a+=$1}END{print a}'

備考

こんな時にしか輝けない rev に愛の手を!


トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-03-24 (日) 07:44:02