FORTRANプログラミング謔X回多重分岐と再帰手続 - ax

木村拓馬
FORTRAN プログラミング
–第９回多重分岐と再帰手続–
木村拓馬
2014 年 11 月 19 日 13:00
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
1/14
木村拓馬
再帰処理
.
再帰処理
.
サブルーチンや関数が自分自身を呼び出す処理を再帰処理（recursive process），
呼び出すことを再帰呼び出し（recursive call）という．
問題によっては再帰処理により読みやすい簡潔なプログラムがかける
ふつう再帰呼び出しごとに記憶領域が確保されメモリ効率が悪い
ふつう DO 文で書いたほうが実行速度が速い
注意して使用しないと終わらないかも
問題によっては再帰処理により読みやすい簡潔なプログラムがかける
.
.
再帰的関数（RESULT は省略できない?[3]）
.
RECURSIVE [型宣言] FUNCTION 関数名 [（仮引数名並び） [RESULT （結果名）]]
.
..
END
FUNCTION [関数名]
.
.
再帰的サブルーチン
.
RECURSIVE SUBROUTINE サブルーチン名（仮引数）
.
..
END
SUBROUTINE [サブルーチン名]
.
関数が直接又は間接に，その関数自身又はその同じ副プログラム内の ENTRY 文で定義された関数を呼び出す［このような呼出しを，
再帰的 (recursive) であるという。］場合には，手続接頭辞 RECURSIVE を書かなければならない [1]
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
2/14
木村拓馬
例：フィボナッチ数
.
フィボナッチ数（Fibonacci numbers）
.



0,
n = 0,




fn = 
1,
n
= 1,




 fn−1 + fn−2 , n = 2, 3, 4, · · ·
で定義される数 fn を n 番目のフィボナッチ数という．
フィボナッチ数を並べたフィボナッチ数列は，
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584,· · ·
と続く．
.
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
3/14
木村拓馬
.
例：フィボナッチ数 (ex9.1.f90) .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22.
.. Download
.. Download
.. Download
! Fibonacci sequence + recursive function
program rei_recursive1
implicit none
integer:: i, n
write(*,’(’’n-th Fibonacci number:\n input a positive integer n-->’’,$)’)
read(*,*) n
do i=1,n
write(*,*) fib(i)
end do
contains
recursive integer function fib(i) result (fib_i)
integer, intent(in) :: i
if (i<=0) then
fib_i=0
elseif(i<=2) then
fib_i=1
else
fib_i=fib(i-1)+fib(i-2)
endif
return
end function fib
end program rei_recursive1
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
4/14
木村拓馬
.
例：フィボナッチ数 (ex9.2.f90) .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25.
.. Download
! Fibonacci sequence + recursive subroutine
program rei_recursive2
implicit none
integer:: i, n, fib_i
write(*,’(’’n-th Fibonacci number:\n input a positive integer n-->’’,$)’)
read(*,*) n
do i=1,n
call fib(i,fib_i)
write(*,*) fib_i
end do
end program rei_recursive2
recursive subroutine fib(i,fib_i)
integer, intent(in):: i
integer:: fib_i, fib_1,fib_2
if (i<=0) then
fib_i=0
elseif(i<=2) then
fib_i=1
else
call fib(i-1,fib_2)
call fib(i-2,fib_1)
fib_i=fib_1+fib_2
endif
return
end subroutine fib
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
5/14
木村拓馬
.
例：ふつう再帰処理は遅い．ex9.2.f90 よりは速い例 (ex9.2a.f90) .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25.
.. Download
! Fibonacci sequence + recursive subroutine
program rei_recursive2
implicit none
integer:: i, n
integer,allocatable:: fibs(:)
write(*,’(’’n-th Fibonacci number:\n input a positive integer n-->’’,$)’)
read(*,*) n
allocate(fibs(n))
i=1
call fib()
write(*,*) fibs
contains
recursive subroutine fib()
if(i>n) return
if(i<1) return
if(i<=2) then
fibs(i)=1
else
fibs(i)=fibs(i-1)+fibs(i-2)
endif
i=i+1
call fib()
return
end subroutine fib
end program rei_recursive2
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
6/14
木村拓馬
.
例：ふつう再帰処理は遅い．DO 構文を使ったほうが速い (ex9.2b.f90) .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15.
.. Download
! Fibonacci sequence
program rei_recursive_nashi
implicit none
integer:: i, n, fib1=1, fib2=1, fib3=1
write(*,’(’’n-th Fibonacci number:\n input a positive integer n-->’’,$)’)
read(*,*) n
write(*,*) fib2
write(*,*) fib3
do i=3,n
fib1=fib2
fib2=fib3
fib3=fib1+fib2
write(*,*) fib3
end do
end program rei_recursive_nashi
.
注意）
.
以上の例と，次ページの演習では，実際は再帰を使う必要がない
（よって使わない方が良いと思う）．
今回は再帰処理の使い方だけ覚えてほしい．
再帰処理を使った方が良いかもしれない例は
Appendix を見よ．
.
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
7/14
木村拓馬
.
演習 9.1（pr9.1.f90）
.
正整数 n について，あられ数問題を確認するプログラムを作ってみよう．
1. 再帰処理を用いること．
. 「何回の操作で１に到達するか」も出力すること．
. 出来れば，あられ数列も出力すること．
2
.
3
.
あられ数問題
.
自然数 n について，
「それが奇数なら３倍して 1 を加え，偶数なら２で割る」
という操作によって得られる数をあられ（霰）数という．
「あられ数列はいつかは１に到達するだろうか？」
という問題をあられ数問題（3n+1 問題，コラッツ問題とも）いう [4]．
例：
n = 1 のとき，1 → 4 → 2 → 1，と 3 回の操作で 1 に到達．
n = 3 のとき，3 → 10 → 5 → 16 → 8 → 4 → 2 → 1，と 7 回の操作で
1 に到達．
.
この操作で 1 に到達するまでに出現する数のあられ数列は，
例えば，{1, 4, 2, 1}, {3, 10, 5, 16, 8, 4, 2, 1}．
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
8/14
木村拓馬
参考文献
[1] JIS X 3001-1:2009 (プログラム言語 Fortran – 第 1 部:基底言語)
[2] 戸川隼人: 「ザ・Fortran90/95」, サイエンス社 (1999)
[3] derkeiler.com:「Bug in g95 with recursive function calls?」
http://coding.derkeiler.com/Archive/Fortran/comp.lang.fortran/200412/103index.html
[4] M. ラインズ著，片山孝次訳：数, 数,… 不思議なふるまい，岩波書店（1989）
[5] 数学セミナー編集部編：数学 100 の問題数学史を彩る発見と挑戦のドラ
マ，日本評論社（1999）
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
9/14
木村拓馬
Appendix
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
10/14
木村拓馬
多重ループ・多重分岐と再帰処理
.
総当たり
.
「いろいろな組み合わせの中で最適なものを探す」ときなど，効率はともかく，
「可能な
組み合わせを全て試して比較する（総当たり）
」は一つのやり方．
.
.
例：1,2,3 をシャッフル (ex9.3a.f90) .. Download
.
1
2
3
4
5
6
7
8
9
10
11
12
13.
program narabe
implicit none
integer :: n=3, i, j, k
do i=1,n
do j=1,n
if (i==j) cycle
do k=1,n
if (i==k .or. j==k) cycle
write(*,*) i,j,k
end do
end do
end do
end program narabe
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
.
実行すると
.
1
1
2
2
3
.3
2
3
1
3
1
2
3
2
3
1
2
1
11/14
木村拓馬
多重ループ・多重分岐と再帰処理
.
総当たり
.
「いろいろな組み合わせの中で最適なものを探す」ときなど，効率はともかく，
「可能な
組み合わせを全て試して比較する（総当たり）
」は一つのやり方．
.
.
実行すると
.
.
.
Download
例：1,2,3,4 をシャッフル (ex9.3b.f90) .
1 2 3 4
.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16.
program narabe
implicit none
integer :: n=4, i, j, k, l
do i=1,n
do j=1,n
if (i==j) cycle
do k=1,n
if (i==k .or. j==k) cycle
do l=1,n
if (i==l .or. j==l .or. k==l) cycle
write(*,*) i,j,k,l
end do
end do
end do
end do
end program narabe
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
1
1
1
1
1
2
2
2
2
2
2
3
3
3
3
3
3
4
4
4
4
4
2
3
3
4
4
1
1
3
3
4
4
1
1
2
2
4
4
1
1
2
2
3
4
2
4
2
3
3
4
1
4
1
3
2
4
1
4
1
2
2
3
1
3
1
3
4
2
3
2
4
3
4
1
3
1
4
2
4
1
2
1
3
2
3
1
2
12/14
.
木村拓馬
総当たりは DO 構文で実現できるが，組み合わせが多いとプログラムが長くなったり，組み合わせ
.の数を可変にするのが容易ではない場合があるかも ⇒ DO 構文を再帰呼び出しすると良いかも
.
例：1,2,· · · ,n をシャッフル，n は READ(ex9.3c.f90) .. Download
program narabe
integer :: n
integer,allocatable :: list(:)
write(*,’(’’input an integer-->’’,$)’); read(*,*) n
allocate( list(n) )
call narabere(n,0,list)
deallocate( list )
end program narabe
recursive subroutine narabere(n,m,list)
integer::i,j,n,m,flag
integer::list(n)
if (m==n) then
write(*,*) list
return
end if
do i=1,n
flag=0
do j=1,m
if (list(j)==i) then
flag=1
exit
end if
end do
if (flag==0) then
list(m+1)=i
call narabere(n,m+1, list)
end if
end do
end subroutine narabere
1.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29.
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
.
実行すると
.
input an
1 2 3 4
1 2 3 5
1 2 4 3
1 2 4 5
1 2 5 3
1 2 5 4
1 3 2 4
1 3 2 5
1 3 4 2
1 3 4 5
1 3 5 2
1 3 5 4
1 4 2 3
1 4 2 5
1 4 3 2
1 4 3 5
1 4 5 2
1 4 5 3
1 5 2 3
1 5 2 4
1 5 3 2
1 5 3 4
1 5 4 2
1 5 4 3
2 1 3 4
2 1 3 5
2 1 4 3
2 1 4 5
integer-->5
5
4
5
3
4
3
5
4
5
2
4
2
5
3
5
2
3
2
4
3
4
2
3
2
5
4
5
3
13/14
木村拓馬
演習
.
演習 9.2（pr9.2.f90）
.
1,2,3,· · · ,n の数字が書かれたカードがそれぞれ 1 枚ずつある．
このうち 3 枚を並べてできる奇数を列挙するプログラムをつくってみよう．
再帰処理を用いること
n は read すること
.
終わった方は“ 3 枚 ”を“ m 枚 ”にできるかやってみよう（m も read する）
n=4 のとき，
123，143，
213，231，241，243，
321，341，
413，421，423，431，
n=5 のとき，
123，125，135，143，145，153，
213，215，231，235，241，243，245，251，253，
315，321，325，341，345，351，
413，415，421，423，425，431，435，451，453，
513，521，523，531，541，543，
FORTRAN プログラミング,–第９回多重分岐と再帰手続– ( 2014 年 11 月 19 日 13:00 )
14/14

Download Report