本日( 2004/07/13 )は、講義がなかったので、講義資料はありません。
計算機の利点は、「単純なことの繰り返しを辛抱強く、速く実行できる」ことです。つまり、「虱潰」に向いているということです。
本日の演習では、「虱潰で問題を解く」ことを幾つか説明したいと思います。
「虱潰法」は、端的にいえば、「方程式に現れる全ての変数に関して、その取り得る範囲をすべて、考え、その中で、方程式を満す変数の組を求める」という方法です。
したがって、一番単純な構造は、do loopが一つと、if文が一つ。あと、問題によっては、入力があり、もちろん、結果の出力が含まれることになります。
program 虱潰 ! read(*,*) 隣のミケを捕まえる do 猫の全ての毛の根について if そこに虱がいたら then 虱を潰す ! write(*,*) 虱の死体を捨てる end if end do ! write(*,*) 猫の虱は全て潰した end
難しいのは変数の範囲と、チェックする条件です。これらは、いくらでも複雑になります。特に、変数の範囲に関しては、あらかじめ、問題を考え、その範囲をきちんと調べる必要があります。
方程式3x+y = 4の解は、変数x, yに関して、なんの仮定も置かなければ、無限の解をもちます。
このような方程式を不定方程式とよびます。
しかしながら、x,yの取り得る範囲を自然数に限定すれば、(x,y)=(1,1)の解しか存在しません。
このような問題をデオファントス方程式とよびます。
この方程式を、虱潰で解く場合は、具体的に、x, yの値を代入し、その計算した値が、方程式をみたすことを確認すればよいわけです。
ただし、問題は、どのような範囲に答えがあるか?ですが、係数と根が共に正の数であれば、個々の変数の値は、その総和に相当する右辺を越えることはありえないので、すくなくても、右辺の数を最大値とすればよいことがわかります。
例えば、7x+13y=192の場合は、x, yの範囲を、1-192にすれば良い(1)ことがわかります。
program futei
integer x
integer y
! x, y の値を 1 から 192 まで、虱潰す
do x = 1, 192
do y = 1, 192
if 7 * x + 13 * y == 192 then
! 方程式が満されたので結果を出力
write(*,*) '(x,y)=(', x, ',', y, ')'
end if
end do
end do
end
課題 a.1.1 次の不定方程式を、虱潰で解きましょう。 8x + 13y = 170
課題 a.1.2 次の不定方程式を虱で解きましょう。ただし、x, y, z の範囲は 1 から 20 とします。 x^2 + y^2 = z^2
つい最近まで、「フェルマー予想」よばれていた問題は、「x^n + y^n = z^n ( n > 2 )を満たす、自然数のx,y,zの組が存在しないこと」でした。
つまり、この根を、虱潰でとこうとしても、無駄骨(無限に計算をしなければならない)になります。つまり、虱潰の一つの問題点は、「少くても、答の範囲が予め判っていることが条件になる」ことです。そして、答があるかどうかの検証(存在証明になる)は、別に行わなければならないということです。
実際は、もっと、制限することができます。具体的には、y > 0なので、7x + 13 > 192よって、x < (192-13)/7となります。
同様に、yも制限することができます。
二つの自然数が与えられたときに、その二つの共通約数(公約数)で最大のものを、最大公約数とよびます。これを虱つぶしで解いてみましょう。
二つの自然数をM, Nとしますと、その約数は、当然、1 - M, 1 - Nでなければなりません。従って、公約数に成り得るのは、1 - (MとNの大きくない方)となります。
後は、その数が、M, Nを割切れる(2)かどうかを確認すればよいわけです。
program gcm
integer m
integer n
integer mn
integer rm
integer rn
integer d
integer gcm
! 最大公約数を求める二つの数 ( m, n ) を入力する
write(*,*) '二つの数の最大公約数を求めます'
write(*,*) '一つ目の数 (m) を入力してください'
read(*,*) m
write(*,*) '二つ目の数 (n) を入力してください'
read(*,*) n
! 二つの数、m, n の内、大きくない方を mn に入れる
if ( m < n ) then
mn = m
else
mn = n
endif
! d を 1 - mn に変化させ虱潰しで、最大公約数を求める
gcm = 1 ! 最大公約数候補として、とりあえず 1 を考える
do d = 1, mn
rm = m - ( m / d ) * d ! rm は m を d で割った余り
rn = n - ( n / d ) * d ! rn は n を d で割った余り
if rm == 0 .and. rn == 0 then
! d が m と n を共に割切れるので公約数
gcm = d
endif
end do
write(*,*) m, 'と', n, 'の最大公約数は', gcm
end
このプログラムのポイントは、1から順に、一つずつ、両方をを共に割切れる数(公約数)を求め、その中で、最後に出て来たもの(小さい方から調べるので、一番最後に見付かった物(3)が最大になる)を取り出すということです。
すでに、皆さんは、講義で、公約数を求める方法として、「ユークリッドの互法除」を学んでいます。今回の虱潰法に比べると、あまり直観的でない(なぜ、これで上手く行くかわからない.. )方法でした。
それに比べて、今回の虱潰法は、「ごく普通の考え方」を利用しており、互法除に比較すれば、素直なやり方であるといえると思います。
プログラムを考える上で、「解りやすい」ことは重要なポイントなのですが、なぜ、敢て、(比較的)解り難い方法が取られているのでしょうか?
実は、その理由は、「効率」です。
「ユークリッドの互法除」は、「虱潰法」に比較すると、圧倒的に高速なのです。
課題 a.2.1 三つの数の最大公約数を、虱潰法で求めるプログラムを作成しなさい。
課題 a.2.2
二つの数の最小公数
(4)
を、虱潰法で求めるプログラムを作成しなさい。
ある数dが、数Mを割切れるかどうかは、Mをdで割った余りrを求め、rが0かどうかで判定します。
余りrの計算は、Mをdで割った商( Fortranでは、M/dは、Mをdで割った商になる)を求め、その商とdの積をMから引けばよい( r = M - (M/d)*d )。
図の面積を求めるために、小学生の時にならった方法は、方眼紙にその図を記入し、その図の内側にある方眼の個数を数えることでした。
これと同じようにして、図形の面積を計算機に求めさせることができます。
例えば、半径100 cmの円の面積を、この方法で求めてみましょう。
方針は、この円が、1cm桝の方眼紙に書かれていると仮定し、その個々の方眼(桝)が、円の内側にあるかどうかを、それぞれ全て、調べます。
円の境界の部分では、円が方眼の内部を横切ることになるわけで、その場合に、その方眼が内側にあるか外側にあるかをどうするか考える必要がありますが、今回は、方眼の右上の点が円の内部に入っている(右上の点と原点との距離が半径以下)ならば、その方眼は内部の点であると定めることにします(5)。
program circle integer x integer y integer r integer s ! 半径は 100 cm r = 100 ! 発見できた内側の桝の個数を s で表す。最初は 0 個 s = 0 ! 方眼の左上の位置を x, y で表す do x = -r, r do y = -r, r if x*x + y*y < 100*100 then ! 桝の右上の点が円の内部だった。 s = s + 1 endif end do end do write(*,*) '半径', r, 'cm の円の面積は', s, '平方センチメートル' end
この方針では、方眼の細かさを細かくすれば、より正確になるということが予想できると思います。
課題 a.3.1 今度は、1mm の幅の方眼用紙を使った場合の面積を求めなさい。
課題 a.3.2 今度は、半径 10m ( 1000cm ) の円の面積を求めてみましょう。方眼が 1cm と 1mm の場合での結果の違いはどうだろうか ?
課題 a.3.3 上記の結果を利用して、円周率の値の近似値を求めてみなさい。
覆面算というパズルがあります。簡単に言えば、ある計算の中に現れる数字を全て英文字に置き換えておき、その計算の形から、その英文字に当る数字を予想するというものです。
ただし、同じ数字には、必ず同じ英文字が、異る数字には、異る英文字が割当られています。例えば、次のような覆面算を考えてみます
cb
+ cb
-----
baa
この問題を虱潰で計算するには、a, b, cに0から9までの数字を割り当て、更にこの式が成立するかどうかを確認します。
program fuku
integer a
integer b
integer c
! ue(1) : 1 の位, ue(2) : 10 の位, ue(3) : 100の位
integer ue(1:3) ! 上の数
integer shita(1:3) ! 下の数
integer wa(1:3) ! 和
integer kuri ! 繰上がり
! a, b, c, の数字を虱潰
do a = 0, 9
do b = 0, 9
do c = 0, 9
! 問題は
! cb
! + cb
! -----
! baa
! なので、計算式を作る
ue(1) = b
shita(1) = b
ue(2) = c
shita(2) = c
ue(3) = 0
shita(3) = 0
! 二つの数の和を求める。計算は、一桁ずつ行い、桁上りをチェック
kuri = 0
do keta = 1, 3
wa(keta) = ue(keta) + shita(keta) + kuri
if wa(keta) > 9 then
wa(keta) = wa(keta) - 10
kuri = 1
else
kuri = 0
end if
end do
! 計算結果が求める形であれば Okey
! 本当は、a, b, c が互いに異ることと、a と b が 0 でないという条件が必要
if wa(1) == a .and. wa(2) == a .and. wa(3) == b then
write(*,*) '答は', 'a=', a, 'b=', b, 'c=', c
end if
end do
end do
end do
end
課題 a.4.1 覆面算 ab + ca = cba を解きなさい。
課題 a.4.2 覆面算 send + more = money を解きなさい。
提出先
softa-2004@rep.s.cn.cst.nihon-u.ac.jp
ただし、次の点に注意してください。