気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2016/10/25 01:38
回答1件
0
本物のプログラマはPascalを使わない、つまり、問題がPascalで書かれている時点で間違っている。考えてもみて欲しい。現代におけるPascalなどDelphiとFree Pascalしかない。Delphiは買収の連続によって今やどの会社で開発しているかを正確に言える人はいない。Free Pascalは細々と続き、いつの間にか3.0.0になっているし、LazarusなんていうIDEまで出てきたが、教育関係以外で使っている人はいるのだろうか…。
ではどうすべきか、本物のプログラマはHaskellを使う、そう、Haskellを使えば全て解決する。
本当か?そう思うかも知れないが、問題文のPascalを早速Haskellで書き直してみればわかる。
Haskell
1import Control.Monad 2 3myGcd :: IO () 4myGcd = do 5 list <- map read . words <$> getLine 6 let x0 = head list :: Integer 7 let y0 = last list :: Integer 8 Control.Monad.when (x0 > 0 && y0 > 0) $ 9 print $ 10 "gcd(" ++ show x0 ++ ", " ++ show y0 ++ ") = " ++ show (gcd' x0 y0) 11 where 12 gcd' :: Integer -> Integer -> Integer 13 gcd' 0 y = y 14 gcd' x y = gcd' (y `mod` x) x 15 16main :: IO () 17main = myGcd
※ HaskellにはPrelude.gcd
が既にあるため、名前が被らないようにしている。
1.での考えは簡単だ。gcd' x y = gcd' (y `mod` x) x
が全てを物語っている。次の計算では、xがy mod xであり、yがxということだ。y = x * (y div x) + (y mod x)であるから、y mod x = - x * (y div x) + y = -q * x + yだ。あとはこれを行列計算に直すだけだ。
TeX
1\[ 2 \left( 3 \begin{array}{cc} 4 -q_n & 1 \\ 5 1 & 0 6 \end{array} 7 \right) 8\]
2.は1.があればそれほど苦労しない。最終的に(xn, yn)は(0, gcd(x, y))となる。xn = 0となる適当なnをとれば(0, gcd(x, y)) = A(x, y)となる行列Aが存在する。
3.についてはqiの数列を求めるようにしなければならない。これは前から順番に繋がる配列にすれば簡単にできる。qList x y = y `div` x : qList (y `mod` x) x
と言う形にするだけだ。あとは行列計算をfoldl'を使って順番にすれば良い。これで簡単にuは求まるだろう。ついでに4.もやってしまおう。vはu,x,y,gcd(x, y)から簡単に求められる。
Haskell
1import Control.Monad 2import Data.List 3 4myGcd' :: IO () 5myGcd' = do 6 list <- map read . words <$> getLine 7 let x0 = head list :: Integer 8 let y0 = last list :: Integer 9 Control.Monad.when (x0 > 0 && y0 > 0) $ do 10 putStrLn $ 11 "gcd(" ++ show x0 ++ ", " ++ show y0 ++ ") = " ++ show (gcd' x0 y0) 12 putStrLn $ 13 " = " ++ show (u x0 y0) ++ " * " ++ show x0 ++ " + " ++ 14 show (v x0 y0) ++ " * " ++ show y0 15 where 16 gcd' :: Integer -> Integer -> Integer 17 gcd' 0 y = y 18 gcd' x y = gcd' (y `mod` x) x 19 qList :: Integer -> Integer -> [Integer] 20 qList 0 _ = [] 21 qList x y = y `div` x : qList (y `mod` x) x 22 qq :: Integer -> Integer -> (Integer, Integer) 23 qq x y = foldl' (\c q -> (-q * fst c + snd c, fst c)) (1, 0) $ 24 qList x y 25 u :: Integer -> Integer -> Integer 26 u x y = snd $ qq x y 27 v :: Integer -> Integer -> Integer 28 v x y = (gcd' x y - u x y * x) `div` y 29 30main :: IO () 31main = myGcd'
見ての通り、問題の数式をそのままコーディングしただけで、答えは求まるのである。
投稿2016/10/25 11:18
総合スコア21733
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。