whileをやろう
プログラミングの鍵は途中脱出
このワークシートはMath by Codeの一部です。
＜whileをやろう＞
ここまで、juliaでやれていたことはgeobebraでもできた。
これは、関数・宣言型の記述、リスト中心という方向でも
順次、反復、条件分岐の３要素が実現できたからだ。
これで、これで安心というわけにはいかない。
forはsequenceコマンドリスト化できたけれども
whileはまだ置き換えられていない。
たとえば、whileでも終わりが見えているものなら
終わりまでの範囲でfor文で追いかけられる。
しかし、終わりが見えないで、途中で反復を脱出するwhile型を、関数型に翻訳するには
どうしたらよいだろうか。
whileを使いそうになる例を使って考えてみよう。
100以下の素数を列挙したいときどうするか。
よくあるのは、
2からNの平方根未満の整数ｐまでで順番にNをわり算してみる。
まずは、約数リストを作り、それを数えて約数の個数が２だったら素数といえる。
この考え方でプログラミングしてみよう。
julia
#================================================
#ｎの約数リストを作る関数
function divs(n)
#nの約数を速く求めるためには、ルートn以下の整数までで割ればよい。
divisors = []
res = round(n^0.5)
#小数表示の整数を整数表示にする
lim = Int(res)
for p= 1:lim
if n % p ==0
push!(divisors,p)
#juliaの整数の商は÷でよい。
if (p != n ÷ p)
push!(divisors,n ÷ p)
end
end
end
return divisors
end
function isPrime(N)
if length(divs(N))==2
return true
else
return false
end
end
filter(x -> isPrime(x),2:100)
#================================================
[OUT]
25-element Vector{Int64}:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
これを関数型にするとなんと１行でかける。
#========================================
filter(n->length(filter( m -> n % m==0,1:n))==2, 2:100)
#=======================================
順次的な調査はしてないから、ｎの平方根未満までを調べるというような制約はいらない。
これをgeogebraでやることもできる。
#================================================================
prims=KeepIf(Length(KeepIf(Mod(k,n)≟0,n,Sequence(k)))≟2,k,Sequence(100)
#================================================================
さて、手続き型でも、約数リストを作らないことで短縮できるね。
#================================================
function prime(n)
lim = Int(round(n^0.5))
for num in 2:lim
if n % num ==0
return false
end
end
return true
end
filter(x -> prime(x),2:100)
#================================================
Nの平方根未満の整数までで割り算を止めているのは割り算回数の節約のためだ。
もし、無駄を承知なら次のようなwhile文で延々とわり算しても判定はできる。
約数が見つかったときにwhileを脱出して関数も終了すればいいのだから。
100までの素数を１行で求める方法
＜whileの反復脱出をなしにしたい＞
よくあるwhile型の反復脱出プログラムを書こうとしたら、
このgeobebraテキストアプリが勝手に改造するバグがあるので、
かけない。
例えば、簡単にいうと、res=trueにしておく。
while resとかを先頭にかく。
中に、約数があればres=falseにして反復を脱出してreturn resする。
では、whileなしで関数型にしよう。
まずは、100で実験してみる。
[IN]julia
# n=100に対して、
# 2から100-1までのリストを作る。その要素である数ｍで100を割る。
# 割り切れたら0,それ以外なら1をマッピングする。
# こうやって、脱出条件となる情報をひたすらメモするのなら、
# 関数型・リスト型で行けそうだ！
n=100
try100=map(m-> n % m==0 ? 1 : 0 ,2:n-1)
println(try100)
#=====================
[OUT]
[1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
次は本番。
[IN]julia
# 2から100までの数nに対して、
# 2からn-1までのリストを作る。その要素である数mでnを割る。
# 割り切れたら0,それ以外なら1をマッピングする。0か1を要素とする99個のリストのリストができる。
# １つ１つのリストに対して、(n、0か1を合計）というタプルに変換する。
# nが素数なら2からn-1の間に約数がないから、合計は０になる。
# (n,0)のときに、nが素数になる。
res=map(n->(n,sum(map(m-> n % m==0 ? 1 : 0 ,2:n-1))),2:100)
println(res)
#=====================
[OUT]
[(2, 0), (3, 0), (4, 1), (5, 0), (6, 2), (7, 0), (8, 2), (9, 1), (10, 2), (11, 0), (12, 4), (13, 0), (14, 2), (15, 2), (16, 3), (17, 0), (18, 4), (19, 0), (20, 4), (21, 2), (22, 2), (23, 0), (24, 6), (25, 1), (26, 2), (27, 2), (28, 4), (29, 0), (30, 6), (31, 0), (32, 4), (33, 2), (34, 2), (35, 2), (36, 7), (37, 0), (38, 2), (39, 2), (40, 6), (41, 0), (42, 6), (43, 0), (44, 4), (45, 4), (46, 2), (47, 0), (48, 8), (49, 1), (50, 4), (51, 2), (52, 4), (53, 0), (54, 6), (55, 2), (56, 6), (57, 2), (58, 2), (59, 0), (60, 10), (61, 0), (62, 2), (63, 4), (64, 5), (65, 2), (66, 6), (67, 0), (68, 4), (69, 2), (70, 6), (71, 0), (72, 10), (73, 0), (74, 2), (75, 4), (76, 4), (77, 2), (78, 6), (79, 0), (80, 8), (81, 3), (82, 2), (83, 0), (84, 10), (85, 2), (86, 2), (87, 2), (88, 6), (89, 0), (90, 10), (91, 2), (92, 4), (93, 2), (94, 2), (95, 2), (96, 10), (97, 0), (98, 4), (99, 4), (100, 7)]
#これでは、素数以外もまざるから、タプルの第２要素==0のときの第1要素だけを抜き出せば、
素数一覧になる。
map(x->x[1],filter(x->x[2]==0,res))
これは、次のようにgeogebraでもいける。
Whileを使わなくても脱出条件の結果の記録を使えばいいんだね。
質問：他のwhileを使いそうなプログラムを適当に拾って、脱出条件をリスト化してから、リストを活用して、途中で中断した効果を再現することでうまく移植できますか。うまくいかないとしたら、その原因は何でしょうか。