BashでProject Euler 1を解くいろんなパターン

公開日:2019-01-09
最終更新:2019-01-14

全13パターン。

#!/bin/bash  

set -eu  

# Problem 1 「3と5の倍数」  
# 10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.  
# 同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.  

# bashの制御系コマンドを使用  
euler_001::func01() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  local _sum=0  
  local i  
  for i in $(seq $_limit); do  
    if [[ $((i % _num_a)) -eq 0 || $((i % _num_b)) -eq 0 ]]; then  
      ((_sum += i))  
    fi  
  done  
  echo $_sum  
}  

# whileコマンドを使用  
euler_001::func02() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  local _sum=0  
  local i  
  while read -r i; do  
    if [[ $((i % _num_a)) -eq 0 || $((i % _num_b)) -eq 0 ]]; then  
      ((_sum += i))  
    fi  
  done < <(seq $_limit)  
  echo $_sum  
}  

# awkを使用  
euler_001::func03() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  seq $_limit | awk -v num_a=$_num_a -v num_b=$_num_b '  
    BEGIN {  
      sum = 0  
    }  
    ($1 % num_a == 0 || $1 % num_b == 0) {  
      sum += $1  
    }  
    END {  
      print sum  
    }  
  '  
}  

# bcコマンドを使用  
euler_001::func04() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  echo $(bc << __EOM__  
    sum = 0  
    for (i = 0; i <= $_limit; i++) {  
      if (i % $_num_a == 0 || i % $_num_b == 0) {  
        sum += i  
      }  
    }  
    print sum  
__EOM__  
  )  
}  

# パイプを使用(Part1)  
euler_001::func05() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  (seq $_num_a $_num_a $_limit; seq $_num_b $_num_b $_limit) \  
    | sort -n \  
    | uniq \  
    | tr '\n' '+' \  
    | sed -e 's/+$/\n/' \  
    | bc  
}  

# パイプを使用(Part2)  
euler_001::func06() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  seq $_limit \  
    | factor \  
    | awk '{print $0" "}' \  
    | grep " [${_num_a}${_num_b}] " \  
    | awk -F: '{a += $1} END {print a}'  
}  

# パイプを使用(Part3)  
euler_001::func07() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  seq $_limit \  
    | sed "0~${_num_a}b; 0~${_num_b}!d" \  
    | paste -sd+ \  
    | bc  
}  

# ファイルを使用  
euler_001::func08() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  temp_dir=$(mktemp -d)  
  pushd $temp_dir >/dev/null 2>&1  
  touch $(seq $_num_a $_num_a $_limit | paste -sd' ') \  
    $(seq $_num_b $_num_b $_limit | paste -sd' ')  
  echo * \  
    | tr ' ' '+' \  
    | bc  
  popd >/dev/null 2>&1  
  rm -r $temp_dir  
}  

# 算術式展開を使用  
# 多重ループの場合は利用不可  
euler_001::func09() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  local _sum=0  
  local i  
  eval let "i={1..$_limit},'((i % $_num_a == 0 || i % $_num_b == 0)) && ((_sum += i))'"  
  echo $_sum  
}  

# 算術式を使用  
# 多重ループでも対応可能  
euler_001::func10() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  local readonly __while='__depth = 0, __break = 0, __loop ,__break '  
  local readonly __loop='__depth++ ,__break || (__break = !__cond) || ((__body), __depth < 64 && (__loop, __loop)), __depth--'  
  local readonly __cond="i < $_limit"  
  local readonly __body="((i % $_num_a == 0 || i % $_num_b == 0) && (_sum += i)), i++, loop"  

  local _sum=0  
  local i=0  
  set +u  
  echo $((__while, _sum))  
  set -u  
}  

# ここからは数学Bの話  

# 15で割った余りで考える. 15m+0, 15m+1, …, 15m+14 のうち,   
# 3または5で割り切れる数は 15m+0, 15m+3, 15m+5, 15m+6, 15m+9, 15m+10, 15m+12 であり, 合計は 105m+45 である.  
# m=66の時 15mは990となる. したがって,以下の式は990未満についての求めるべき総和を与える.  
# ∑ m=0から65までの(105m+45)であり、105/2*65⋅66+2970  
# これに 990, 993, 995, 996, 999 を加えれば回答が得られる.  

# また,3あるいは5の倍数の総和は, 3の倍数の総和と5の倍数の総和の合計から, 15の倍数の総和を引いた値である.  
# したがって,与えられた数 p の倍数の総和さえ求められれば良い. これは m=⌊1000/p⌋ と置けば,以下の式で求められる.  
# Σ i=1からmまでのpi = p*m(m+1)/2  
# p=3 の時の m は 333,p=5 の時の m は 199,p=15 の時の m は 66 であるから, 求める回答は以下の式で与えられる.  

# $limitまでの$factorの倍数の総和を算出する。  
msum() {  
  local readonly _factor="$1"  
  local readonly _limit="$2"  
  # Σ i=1からmまでのpiを算出 -> p*m(m+1)/2  
  local readonly _m=$(( (_limit - 1) / _factor ))  
  echo $(( _factor * _m * (_m + 1) / 2 ))  
}  

# 最大公約数(The greatest common divisor)を算出  
gcd() {  
  local _num_a="$1"  
  local _num_b="$2"  

  local _tmp  
  if [[ $_num_a -lt $_num_b ]]; then  
    ((_tmp = _num_a, _num_a = _num_b, _num_b = _tmp))  
  fi  

  local _r=$((_num_a % _num_b))  
  until [[ _r -eq 0 ]]; do  
    ((_num_a = _num_b, _num_b = _r, _r = _num_a % _num_b))  
  done  
  echo $_num_b  
}  

# 最小公倍数(The least common multiple)を算出  
lcm() {  
  local _num_a="$1"  
  local _num_b="$2"  

  echo $((  
    _num_a * _num_b / $(gcd $_num_a $_num_b)  
  ))  
}  

# Σ i=1からmまでのpiを算出  
euler_001::func11() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  echo $((  
    $(msum $_num_a $_limit) + $(msum $_num_b $_limit) - $(msum $(lcm $_num_a $_num_b) $_limit)  
  ))  
}  

# awkの場合  
euler_001::func12() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  echo "" | awk -v num_a=$_num_a -v num_b=$_num_b -v limit=$_limit '  
    function gcd(num_a, num_b,    tmp, r) {  
      if (num_a < num_b) {  
        tmp = num_a  
        num_a = num_b  
        num_b = tmp  
      }  

      r = num_a % num_b  
      while (r != 0) {  
        num_a = num_b  
        num_b = r  
        r = num_a % num_b  
      }  
      return num_b  
    }  

    function lcm(num_a, num_b) {  
      return num_a * num_b / gcd(num_a, num_b)  
    }  

    function msum(factor, limit,    m) {  
      m = int((limit - 1) / factor)  
      return factor * m * (m + 1) / 2  
    }  

    END {  
      lcm_result=lcm(num_a, num_b)  
      print msum(num_a, limit) + msum(num_b, limit) - msum(lcm_result, limit)  
    }  
  '  
}  

# bcの場合  
euler_001::func13() {  
  local readonly _limit="$1"  
  local readonly _num_a="$2"  
  local readonly _num_b="$3"  

  echo $(bc << __EOM__  
    define gcd(num_a, num_b) {  
      if (num_a < num_b) {  
        tmp = num_a  
        num_a = num_b  
        num_b = tmp  
      }  

      r = num_a % num_b  
      while (r != 0) {  
        num_a = num_b  
        num_b = r  
        r = num_a % num_b  
      }  
      return num_b  
    }  

    define lcm(num_a, num_b) {  
      return num_a * num_b / gcd(num_a, num_b)  
    }  

    define msum(factor, limit) {  
      m = (limit - 1) / factor  
      return factor * m * (m + 1) / 2  
    }  

    lcm_result=lcm($_num_a, $_num_b)  
    print msum($_num_a, $_limit) + msum($_num_b, $_limit) - msum(lcm_result, $_limit)  
__EOM__  
  )  
}  

time euler_001::func01 9999 3 5  
time euler_001::func02 9999 3 5  
time euler_001::func03 9999 3 5  
time euler_001::func04 9999 3 5  
time euler_001::func05 9999 3 5  
time euler_001::func06 9999 3 5  
time euler_001::func07 9999 3 5  
time euler_001::func08 9999 3 5  
time euler_001::func09 9999 3 5  
time euler_001::func10 10000 3 5  
time euler_001::func11 10000 3 5  
time euler_001::func12 10000 3 5  
time euler_001::func13 10000 3 5
記事が少しでもいいなと思ったらクラップを送ってみよう!
0
+1
勉強したことのメモ

よく一緒に読まれている記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる

技術ブログをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

技術ブログを開設する

Qrunchでアウトプットをはじめよう

Qrunch(クランチ)は、ITエンジニアリングに携わる全ての人のための技術ブログプラットフォームです。

Markdownで書ける

ログ機能でアウトプットを加速

デザインのカスタマイズが可能

技術ブログ開設

ここから先はアカウント(ブログ)開設が必要です

英数字4文字以上
.qrunch.io
英数字6文字以上
ログインする