Go to Qiita Advent Calendar 2024 Top
LoginSignup
4
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@gin_135

Project Eulerをシェル芸で解いてみる(Problem 5)

Last updated at Posted at 2016-01-05

概要

Project Euler1は、数学的な問題解決能力を要求する、プログラミング問題集・オンラインプログラミングジャッジである。
一般的なオンラインプログラミングジャッジとは異なり、解答するプログラミング言語は、特に限定されていない。
フォームに入力した値だけで正誤を判別するため、適切なアルゴリズムさえ考案できれば、あらゆるプログラミング言語で解答することが可能である。
そのため、Web上では様々な手法による解答が公開されている。

しかし、シェル芸2による解答は、私が探した限りでは、殆ど見つからなかった。
そこで、私自身の勉強も兼ねて、Project Eulerをシェル芸で解いてみることにした。

本記事では、Project EulerのProblem 5を、シェル芸で解いた際の過程を述べる。

実行環境

  • Arch Linux (x86_64, 4.3.3-2-ARCH)
  • bash (4.3.42)
  • GNU coreutils (8.24)
  • gawk (4.1.3)

問題文

[原文 (https://projecteuler.net/problem=5)]

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

[日本語訳 (http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%205)]

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

正答は注釈3に記載する。

解法1

prob_005.sh
1	#!/bin/sh
2	
3	seq 20 10000000000 \
4	| # 20~10000000000の整数の生成
5	awk '{for(i=20; i>1; i--){if($0%i != 0){next}}; print; exit}'
6	  # 1から20の全ての整数で割り切れる、最小の数値の出力

解法1の解説

この解法による処理の詳細は、コードに記載してあるコメントの通りである。

ただし、この解法は、計算量が非常に大きいため、処理時間はとても長い。

解法2

prob_005_2_rev2.sh
1	#!/bin/sh
2	
3	seq 1 20 \
4	| # 1~20までの整数の出力
5	factor \
6	| # 素因数分解
7	awk '{for(i=2; i<=NF; i++){expp[$i]++}; for(fac in expp){print fac, expp[fac]}; delete expp}' \
8	| # 1~20の各整数における、素因数の指数の出力
9	sort -k 1n,1 -k 2rn,2 \
10	| # 1~20の整数を、それぞれ素因数の指数について、降順にソート
11	awk '$1 != o1 {print $1, $2; o1=$1}' \
12	| # 全素因数について、それぞれ指数が最大であるものを出力
13	tr ' ' '^' \
14	| # 算出式の出力1(基数^指数)
15	xargs \
16	| # 行->列変換
17	tr ' ' '*' \
18	| # 算出式の出力2(lcm)
19	bc
20	  # lcmの出力

解法2の解説

問題文より、1から20までの整数全てで割り切れるということは、1から20までの全整数の最小公倍数を求めれば良い。

初めに、解法2で用いる定理について説明する。
この解法では、算術の基本定理による、素数と最小公倍数の関係を利用する。

複数の正整数$n_1,\ n_2,\ n_3,\ ...,\ n_i$の最小公倍数を求めるとする。
その場合はまず、全ての正整数を素因数分解する。
そして、素因数分解で得られた全ての素因数について、指数が最大になるものを取り出す。
最後に、取り出した全素因数の総乗を算出すれば、最小公倍数を求めることができる。

具体例として、$12,\ 18,\ 42$の最小公倍数$lcm$を求める方法を示す。
まず、$12,\ 18,\ 42$を素因数分解する。

12 = 2^2 \times 3^1

18 = 2^1 \times 3^2

42 = 2^1 \times 3^1 \times 7^1

このとき、得られた素因数の基数は、$2,\ 3,\ 7$の3種類である。
そして、上記3種類の基数のうち、指数が最大になるものは、それぞれ$2^2,\ 3^2,\ 7^1$である。
よって、$12,\ 18,\ 42$の最小公倍数は、

lcm(12, 18, 42) = 2^2 \times 3^2 \times 7^1 = 252

となる。

今回は、この算出方法を実装すれば良い。

次に、ソースコードについて解説する。

まず、1から20までの全ての整数を、素因数分解する。
これは、3行目のseqと5行目のfactorによって、出力が得られる。

次に、素因数分解によって得られた素因数それぞれについて、指数を求める。
この処理をおこなう理由は、factorコマンドの出力形式にある。
factorは、ある数値の素因数を、指数形式ではなく、全て素数として出力する。

$ factor 18
18: 2 3 3

そのため、factorによる素因数の出力を、指数形式に変換する必要がある。
この処理は、7行目のawkによっておこなう。

そして、全ての素因数について、指数が最大になるものを取り出す。
この処理は、9行目のsortと、11行目のawkによっておこなう。
7行目のawkでの処理により、"<素因数> <指数>"の形式での出力が得られる。
そのため、指数が最大になる素因数を求める前準備として、sortで出力のソートをおこなう。
具体的には、まず1フィールド目の<素因数>について数値順にソートし、次に2フィールド目の<指数>について数値順に降順ソートをおこなう。
この処理による出力に対して、11行目のawkコマンドを用い、指数が最大になる素因数の行のみを抽出する。

最後に、$lcm$を算出する。
この処理は、13~19行目のtr、xargs、bcを用いておこなう。
具体的には、trとxargsを用いて$lcm$の算出式を出力し、それをbcに渡して、$lcm$を出力している。

以上が、解法2による、1から20までの整数全てで割り切れる最小の正の数を求める方法である。

参考にしたもの

  • 『コンピュータの数学』、Donald E.Knuth・Oren Patashnik・Ronald L.Graham 著、有澤 誠・安村 通晃・萩野 達也・石畑 清 訳、共立出版

雑記

  • 「こんな別解があるよ」や、「こうすればもっと効率化できるぜ」、「こう書けばエレガントですわよ」等の意見がありましたら、気軽に教えていただけますと幸いです🐺
  • 現在の進捗状況 -> https://github.com/gin135/Project_Euler/tree/master/sh

  • 解法1は、超力任せな方法。

    • ありえないくらい時間がかかるので、注意。
    • ↓こんな感じ。
    $ cat /proc/cpuinfo | grep 'model name' | uniq
model name	: AMD FX(tm)-8320 Eight-Core Processor
$ time sh prob_005.sh 1> /dev/null
109.03s user 2.78s system 105% cpu 1:46.29 total
    • ✝ 0(:3 )～ ✝
    • そもそも、この解法、正答が分からなければ、生成する整数の範囲を決められないんだよね......ダメじゃん。

  • 解法2の数学的な原理に関しては、参考書籍1.『コンピュータの数学』のpp.105~107に渡り、詳細に解説されています。

  • 解法2の11行目のawkについては、指数が最大の素因数の抽出と、lcmの算出の処理を、別コマンドに分けるべきだったかもしれない。

    • 1つのコマンドには、1つの処理を。
    • まあ、この程度の処理なら、1つのコマンドにまとめた方が、速いのかもしれないけれど。
    • (2016-01-06追記)やっぱり修正した。見た目は冗長になるけれど、1つのコマンドには1つの仕事をやらせた方が、処理内容が分かりやすいよね。
    • ↓古いコード。
prob_005_2_rev1.sh
1	#!/bin/sh
2	
3	seq 1 20 \
4	| # 1~20までの整数の出力
5	factor \
6	| # 素因数分解
7	awk '{for(i=2; i<=NF; i++){expp[$i]++}; for(fac in expp){print fac, expp[fac]}; delete expp}' \
8	| # 1~20の各整数における、素因数の指数の出力
9	sort -k 1n,1 -k 2rn,2 \
10	| # 1~20の整数を、それぞれ素因数の指数について、降順にソート
11	awk 'BEGIN {expp=1} $1 != o1 {expp *= $1^$2; o1=$1} END {print expp}'
12	  # 1~20の整数のうち、それぞれについて指数が最大である素因数だけを抽出し、{素因数^指数}を積算したもの(最小公倍数)を出力
  • 今回の内容とは、直接は関係無い話。『コンピュータの数学』、巷で言われているように名著だと思う。
    • ページ数と値段、原題の"Concrete"にビビって、今までずっと積読状態だったけれど...
    • 今回の問題を解くにあたり、きちんと読んでみたら、説明がとても分かりやすかった！
    • たった1つの概念に、何ページも費やして、非常に丁寧に解説してある。やっぱり良書。
    • (だが、ちゃんと理解できなかった。やっぱりダメじゃん...)

  1. About - Project Euler (https://projecteuler.net) ↩

  2. シェル芸の定義 >> シェル芸 - 上田ブログ (https://blog.ueda.asia/?page_id=1434) ↩

  3. 232792560 ↩

4
4
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?