読者です 読者をやめる 読者になる 読者になる

Zodiacの黙示録

いかにも大学生といったような邪気(イノセンス)に満ちたブログ

Haskellで行列式を計算する

アドべンヌカレンヌー

この記事は

PMOB Advent Calendar 2016 - Adventarの21日目の記事です。

  • 前の記事[Not Found]
  • 次の記事[みせられないよ]

プログラムコード

まぁ前々回のブログでも書きましたけど、

今読んでる「関数プログラミング珠玉のアルゴリズムデザイン」って本の内容そのままです。

これです。

Amazon CAPTCHA

この行列式演算のアルゴリズムは、Chioのピボット濃縮アルゴリズムである。

Chió Pivotal Condensation -- from Wolfram MathWorld

ここみて。

Chioのピボット濃縮アルゴリズムだが、これは比較的速い。

どれくらい速いかとか、何で速いか、とかは、は忘れた。

自分で調べろ。人に聞くな。

以下がコード。

condense = map (map det . pair . uncurry zip) . pair
            where pair (x:xs)       = map ((,) x) xs
                  det ((a,b),(c,d)) = a * d - b * c

det       :: [[Integer]] -> Integer
det [[x]] = x
det xss   =
  case break ((/= 0) . head) xss of
    (yss,[])     -> 0
    (yss,zs:zss) -> let x = det (condense (zs : yss ++ zss))
                        d = head zs ^ (length xss - 2)
                        y = x `div` d
                    in if even (length yss) then y else -y

cd k = map (map det . pair . uncurry zip) . pair
        where pair (x:xs)       = map ((,) x) xs
              det ((a,b),(c,d)) = (a * d - b * c) `div` k

det'         :: Integer -> [[Integer]] -> Integer
det' k [[x]] = x
det' k xss   =
  case break ((/= 0) . head) xss of
    (yss,[])     -> 0
    (yss,zs:zss) -> let x = det' (head zs) (cd k (zs : yss ++ zss))
                    in if even (length yss) then x else -x

暇だったら加筆します。

ではでは。

Haskellで上位者問題を解く

アドセンスカレンダー

この記事は

PMOB Advent Calendar 2016 - Adventarの11日目の記事です。

  • 前の記事

後世に残すモノづくり - ざっきーの雑記ー

  • 次の記事[みせられません]

酒の神「バッカス

おはようございます。

しょうがないからBlack日課飲んでます。

こういう世の中なんですよ今の日本は。

資本主義と見せかけて社会主義っぽくもある気持ち悪さ。

そして根本的な教育の方針の欠陥。

大学とかこういう場に来て尚実感してこういう感想に至った次第です。

この国は終わりです。海外へ逃げる準備をした方がいいですよ皆さん。

色々な信念とか思想を人々はもっていますけれでも、

先入観とか言ったイドラは違います。これは良くないです。

「人間思ったほど客観視出来てはいない」それはそうですが、だから諦めるのか?という感じではあります。

冷静になって自分を切り離して客観視する努力は必要なのであります。

まぁせめてProkrustesbettのあやまちを犯さないようにしたい。

生きろ

最近生きながらにして死んでいる人が多い気がする。

ケルケゴールは「死に至る病」で、

「無自覚者も死に至る病を患う」といっています。

でもでも、無自覚者って、本人の感覚としては、

絶望を知らないんですから、とても幸せなんだと思いますけど。

いやでも、「人間は動物より勝っているからこそ、言いかえれば人間は自己であり精神であるからこそ、絶望することができるのである」
かもしれませんね。

人間の生きる骨は「愚鈍さ」と「慣れ」な気がしてきましたからね。

そもそも人間ってなんだろうって思うけれども、

「最低限の理性と、知的好奇心とか、精神を持っていて魂が輝いている生物」

こんな定義をしたら個人的にこの眼で見て人間だなと感じた人は少ない。

まぁこれは人間はこう有るべきみたいな、私の個人的な理想像でもあるので、

あんまり気にしないでくださいというか、些か強引すぎますかねぇ。

御託はいいから講釈垂れてよ

このフレーズは「げんがくさばいば」さんから拝借しました。

私の尊敬する人の一人です。

title的に考えますと今回は「Haskellで上位者問題を解く」ですね。

まぁ前々回のブログでも書きましたけど、

今読んでる「関数プログラミング珠玉のアルゴリズムデザイン」って本の内容そのままです。

これです。

Amazon CAPTCHA

今回は第二章です。

「上位者問題」ってご存知でしょうか。

説明いたしますと、配列の一つの要素に対して、その上位者とは、

その要素の右側に有り、その要素より大きい要素をいいます。

つまり、上位者は配列x[]で「 i \verb|<| jかつ x[i] \verb|<| x[j]のときのx[j]」ですかね。

例えば「APPLE」という文字列で考えた時に、

A;0,B;1..といったふうに割り当てた時、

それぞれの文字の持つ上位者の数、上位者数は、

[('A',4),('E',0),('L',0),('P',0),('P',0)]

となります。この場合、最大値はAの4となります。

こういったふうにして、文字列の最大上位者数を求めていきます。

当たり前だけどHaskellでな

今回もHaskellで、しかも分割統治法を使います。

皆さんの身近な分割統治法の例ですと、「クイックソート」とかそうですね。

問題を小さくして、その小さい問題を解いて元の大きさの問題を解いたことにする、というものだと思ってます。

まぁみなさんは生まれながらにしてHaskellはわかると思うので大丈夫でしょう。

以下がコードです。

import Data.List

join 0 txs [] = txs
join n [] tys = tys
join n txs@((x,c) : txs') tys@((y,d) : tys')
    | x < y  = (x,c+n) : join n txs' tys
    | x >= y = (y,d) : join (n-1) txs tys'

table [x] = [(x,0)]
table xs  = join (m-n) (table ys) (table zs)
              where m       = length xs
                    n       = m `div` 2
                    (ys,zs) = splitAt n xs

msc s = maximum $ map snd (table s)

これはさっきもいいましたが、

「文字列の最大上位者数」を求めます。

その関数はmscですね。msc (文字列)という風にご利用ください。

msc関数を説明しますと、その引数(s)をまずtable関数で受けます。

table関数はタプルにして、各文字とその上位者数の組にして、

その全部をリストにして返します。

table関数はO( n \log{n})らしいです。

となると当然mscも同じくそうなることがわかりますね。

終わりです。投げやりかもしれませんね。すみません、

ではでは。

そうだ俺が怠惰の罪だ

そういえば

この記事は

PMOB Advent Calendar 2016 - Adventarの8日目の記事です。

  • 前の記事

web.matsub.tech

  • 次の記事[🍆]

おはよう

おはよう。さっき起きたよ。

流石にヤバイ。単位大丈夫かしら。

それとね。僕はね、

C言語なんて書きたくない!!!」

「ポインタなんて知るか!!!しね!!!」

うーん。ポインタでごちゃごちゃやってるの読みにく過ぎる。

あれだ、でもちゃんとやるよ。

ただ、もうちょっと時間がいるな。

その前に、大学にちゃんと行かないとね。

それはそうと、ウィリアム・ギブスンの「ニューロマンサー」を、

今読んでいてはまってるんですけど、

サイバーパンク最高か。

お尻を出した子一等賞って感じである。

Haskellはいいぞ

Haskellの特殊な機能というわけではなくて、Haskellに有る機能、

便利な機能が集約されている。

つい最近、「一瞬でHaskellで円周率を一億桁計算する」みたいな、

そういう記事を見つけた。

一億桁を630秒くらいで計算してやるとかいうものであった。

これ↓

Haskellで円周率1億桁を計算する、あるいは円周率計算にHaskellの多倍長整数の改良を見る - 純粋関数空間


でもね、俺のPCでコンパイルして実行したら、390秒だった。

めっちゃ速かった。

恐らくだけど、ByteStringとか使ってbit列扱えるやつとか、

並列処理で速くなるっしょ!って

思ってたんだけど、

どうやらかなり複雑な実装されてるっぽい(わからなかった)

多倍長整数の演算がgmpによって実装されており、高速であるらしい。

並列処理もしてない。

並列化は意味なくて、やってもあんまり速くならないらしい。

そもそもの乗算、これは、FFTで実装されているらしいが、

これ自体を並列化しないと意味がないっぽい。

FFTってのは高速フーリエ変換のこと。

実装どうやってされてんの?

ってここで思ったわけで、ちょっと調べた。

以下が実装なのか?

Springerの「Intelligent Computer Mathematics」を参考にした。

-- Implementation of Cooley-Tukey algorithm in Haskell
fft   :: [Complex Double] -> [Complex Double]
fft f =  mix [fft (l @+ r), fft ((l @- r)@* w)]
        where (l, r)   = splitAt (length f `div` 2) f
              mix      = concat . transpose
              (@+) f g = zipWith (+) f g  -- @-, @* analog
              -- w is list of powers of an n-th primitive root of unit

-- FFT-based multiplication modulo x^n - 1 in Haskell
(%*%)     :: (Num a) => [a] -> [a] -> [a]
(%*%) f g = unlift $ ifft ((fft $ lift f) @* (fft $ lift g))
            -- where lift   :: (Num a) => [a] -> [Complex Double]
            --       unlift :: [Complex Double] -> [Int]
            -- ifft is the inverse fft, basicly thesame fft with
            -- different twiddle factors.
            -- And (@*) is still element-wise multiplication

Haskellの乗算はめっちゃ速い。

Computing the factorialで考えると、

NaiveC++よりNaiveHaskellの方が全然速いくらいである。

FFTだからなのだろうか。

おわり。

ではでは。

最小自由数とHaskell

「おはよう」

どうも。ゾディアックです。

最近は禁煙しまして、お酒が好きになりました。

やはり、神は二物を与えないということですね。

全く以て欲張りには生きにくい世界であります。

ああ、そういえば最近ドストエフスキーの「賭博者」を読了致しまして、

人の性質というか、破滅に落ちていく其れに抗えない、何か切ないというか、

ジーザスって感じです。おお!神よ!お赦しください...

はい。今はウィリアム・ギブスンの「ニューロマンサー」を読んでいます。

有名なやつです。いろいろ賞とか取ってる。SFのやつ。

ドストエフスキーを読んでから、まあ、悪い気分というわけではなかったんですが、

暗い気持ちになってしまったので、愉快になりたいなと思ったんで、このチョイスです(?)。

そろそろ本題に入りたいネ。

「お前何した」

ついにとうとうやっと「関数プログラミング珠玉のアルゴリズムデザイン」を読み始めたんです。

この本で出てくる関数型言語Haskellなんです(なにそれ?って聞くのはナシで)。

一年ほど前なんて、Haskell好き好き言っときながら、全く書けなかったし、

この本も、ページをめくっては「ヤバイ」とか言うだけでした。

そう。俺は成長してるのよ。

で、この本の第一章「最小自由数」に関して書く。

「最小自由数」

最小自由数ってのは、簡単に言うと、与えられた自然数の有限集合に含まれない最小の自然数のことです。

[3,5,2,9]だったら"0"が求めるべき最小自由数です。

この集合の中では"2"が最小の自然数でありますが、

この中に含まれない最小の自然数であるところの、

この場合"0"が最小自由数というわけです。

[2,0,4,3]でしたら最小自由数は"1"です。

これをできるだけ速く求めたいんですね。ここではそういうアルゴリズムと実装を考えるんです。

「方法」

この本で紹介されているのは2つあります。

一つは、「Haskellの配列を用いる方法」です。

もう一方は、「分割統治法を用いる方法」です。

先ずは一つ目から紹介します。

「配列を用いる方法」

もう正直眠いし、めんどくさいんで、本当に軽く説明させて頂きます。

その考えに行き着いた経緯的なのとか省きます。本買って読みましょう。高いけど。

引数はリストですが、リスト受け取ってその長さ分の配列を作ります。

有るor無いをBoolで表します。

配列のFalseで一番小さい数を答え(最小自由数)として出します。

以下がコード。

import Data.Array
import Data.Array.ST

search = length . takeWhile id . elems

checklist xs = runSTArray (do
                {a <- newArray (0,n) False;
                sequence [writeArray a x True | x <- xs, x <= n];
                return a})
                  where n = length xs

minfree = search . checklist

配列作った後に変えるのでStateモナドでモナります。

配列の長さより大きい数は無視します。あったらTrueで書き込み。

saerch関数はTrueの続く要素を取り出していって、最終的にその取り出した個数を返します(これが最小自由数と一致する)。

minfree [〜〜〜]みたいな感じで使います。ghciとか使ってロードして試してみましょう。

「分割統治法を用いる」

分割統治法っていうのは簡単に言うとアレです。

全部やると面倒い問題を分割して小さくして小さい方を解くみたいな感じではないでしょうか。

以下がコード。

import Data.List

minfrom a (n,xs) | n == 0    = a
                 | m == b-a  = minfrom b (n-m,vs)
                 | otherwise = minfrom a (m,us)
                    where (us,vs) = partition (<b) xs
                          b       = a + 1 + n `div` 2
                          m       = length us

minfree xs = minfrom 0 (length xs,xs)

再帰ですね。

ガード記法、惚れ惚れしますね相変わらず。

whereは局所定義っていうんですが、partition (条件) で、

([条件を満たすリスト],[条件を満たさないリスト])で分け、これが(us,vs)に対応して定義されます。

リストを与えられた値よりも小さいものとそうでないものに分割しています。

まぁ、プログラム見ていただければ""削ってる""ってのは分かって頂けると思います。

このプログラムは先程のものより20%速いそうです。本にそう書いてありますし。

なんか適当ですみません。なげやり過ぎますね(時間があったら加筆してもいいなとは思ってる)。

ではありがとうございました。おやすみなさい。

ではでは。

「Haskell」で「Look and Say 数列」を生成してみた

Haskell」について

どうも。ゾディアックです。

私はしがない大学生でございます。

今回は関数型言語で有名な「Haskell」で「Look and Say 数列」を生成してみました。

Haskellって何って言われたら、まあ、語らなくちゃいけなくなるのでアレなんですが、

まぁ、軽く言うと「純粋関数型言語」であるという説明でいいでしょう。

みなさんがよくご存知の、「C言語」は、俗に「手続き型言語」と言われております。

関数を書くときにごちゃごちゃしちゃいます。

直感的に書けません。数式で書けません。関数を引数にとれません。

そもそも関数っていうのはですね、数学の分野です。

関数の定義に倣って欲しいし、一つの引数を受け取って一つの返り値を返して欲しいですよね。

Haskellの関数は基本的に引数を一つしか取れません。

ですが、カリー化という手法で、「add x y = x + y」みたいな多価関数が実現出来ます。

こんな感じの言語を「関数型言語」って言うんじゃないの?って思ってます。

そして「純粋」っていうのが「副作用」が無いって意味なんですが話すと長くなり、面倒なのでやめておきます。

Haskell」の説明はこの程度にしときます(汗)

本題に入りましょう。

本題

「Look and Say 数列」とは

まず、「Look and Say 数列」っていうのは、

「1,11,21,1211,111221,312211,132221,...」って数列なんです。

法則性が見えますか...?

私は説明されるまでわかりませんでした(汗)答えを聞いてナルホドって感じでした。

答えを言うとですね、まず「見る」。

「1」です。そして「言う」。

"1"コの"1"です。

次の項は「11」になります(笑)。

「11」です。"2"コの"1"です。よって次の項は「21」になります。

わかります。「しね」って感じですよね(笑)。

この要領で生成していくんですね。

今回はこの数列を「Haskell」で生成してみようと言う話です。

Haskell」で書いてみる

まず実際のコードを

import Data.List

reverseRle :: [Char] -> [Char] 
reverseRle = concatMap (\s -> show (length s) ++ [head s]) . group

las :: [[Char]]
las = ["1"] ++ (map reverseRle las)

これだけです!Haskellはやっぱすげぇ!


そして、「group」関数を使いたいので、「Data.List」をインポートします。

「group」関数っていうのは、文字列が与えられた時に、
同じ要素が続いた箇所をグループにします。

「"AAABBBBBCC"」であったら「["AAA","BBBBB","CC"]」と返します。

そして、「reverseRle」は引数取ってねぇじゃんって思うかも知れませんが、違います。

引数は取ります。合成関数の「.」が効いてます。

「reverseRle a」としたら「a」が引数なんですが、

まずは「group」関数を適用して、次に「.」以前を適用します。

そしてその結果をラングレス圧縮します。そして「reverse」します。

ラングレス圧縮っていうのが、以下のコードで書けます。

import Data.List

rle :: [Char] -> [Char] 
rle = concatMap (\s -> head s : show (length s)) . group

入力は文字列、つまり[Char]じゃないとダメです。返り値も[Char]を返します。

例えば「rle "AAABBBBBCC"」とやったら、「"A3B5C2"」って返ってきます。

これが、「"3A5B2C"」になって欲しいので、「reverseRle」が必要なんですね。

そもそも何でラングレス圧縮するのかということですが、

課題の数列が、前の項の、同じ要素が続いた箇所をグループにし、その文字の連続回数とその文字をくっつけた数字(型的には[Char])を次の項とするような数列だからです。

「show」は「Int -> [Char]」です。「111」を「"111"」にして返します。

「length」は「"111"」であったら「長さ」を返すのでこの場合は「3」を返します。

「length」は「[Char] -> Int」なので、いじりやすくするために、文字列にしたいので、「show」で文字列に調整します。

「head s」で「s :: [Char]」なんですが、返り値が「Char」になってしまうので困ります。

"[ ]"でくくって[Char]にします。

先ほどの「reverseRle」ですが、無名関数(「\」のラムダ式)で、「s」として引数をとってますが、

「s」はgroupされた["1","11","21",...]とあったら、このなかの各要素に、

headとlengthしてshowした値をくっつけた値を返しています。

これは「map」関数で、各要素に対して、第一引数の関数を適用していきます。

「concatMap」関数ですが、これは第一引数で「map」して、結果を「concat」するものです。

例えば、「concatMap ("1"++) ["1","2"]」ってやりますと、

「"11"と"12"」が生成されて、最終的にこれらをくっつけるので、「"1112"」が返ってきます。

この関数だと、例えば、「s」が「"21"」だったら、「"1211"」を返します。

「"2" ++ "1"」でくっつけているんですね。「++」は文字列同士の結合です。

「:」はリストの先頭にくっつけます。

例えば、「"11" : ["21"]」でしたら、「["11","21"]」となります。

これで、reverseRle関数については分かって頂けると思います。

次行きます。「las」関数です。これは「"l"ook "a"nd "s"ay 数列」なので「las」です(わかりづらい)。

las関数は再帰的に定義されています。

las関数の中でlas関数が使われてますから「再帰的」ということです。

まずは、初項は「"1"」ですね。

そして、「map」関数で「reverseRle」関数をそれぞれの要素に適用してやります。

Haskellは「遅延評価」が採用されていますから、lasの値が決定されてねぇじゃんってならないんです。

初項は「"1"」ですから、先ほどの「reverseRle」関数をこれに適用させます。

すると返り値は「"11"」です。

今の段階でlasは["1","11"]です。

次に適用するのは、「"11"」です。返り値は「"21"」です。

今の段階でlasは["1","11"."21"]です。

この要領で次々に無限に生成できます。

定義的には無限リストです。

は?やばくね?って普通の人は思うかも知れませんが、さっきも言ったように、Haskellは遅延評価を採用していますから、大丈夫なんです。必要なときに評価するのです。

上の関数を、Haskellの式を対話的に評価したりプログラムを解釈実行したりできる、GHCiというGHCの対話環境を使って、loadして使うといいですね。

「ghci」でGHCiは起動できます。

そして「:l 「haskellファイル」」

でloadしてやります。

lasは無限リストなので、「take」とか「!!」を使ってやって処理しましょう。

「take 10 lst」ってやると、lstを10項分返してくれます。

「lst!!10」ってやると10項目じゃなくて11項目が返ってきます。Haskellのリストは0からですから。

まぁこんな感じです。ありがとうございました。

数学の心得(初心者が語る)

お詫び

お詫び

   今回は、僕の数学の集大成、なんですが、大したものはお見せできなかったのですが、はてなブログにおける数学の記法にあまり慣れていないため数式で書けませんでした。申し訳ないですね。

ではどんな記事を書くのか?

   今回の内容に関しては、数学というテーマで書かせていただきます。よろしくお願いいたします。任意の数学科の皆様は、温かい目でお見守りくださりますようここにお願い申し上げます。

本題

数学の初心者として

   数学の初心者としてまず重要なことがあって、それは、記号を覚えることだと思います。僕が今まで数学書を読んできて思うのですが、結構、当たり前のように記号が用いられており、初心者の方は特に、最初は記号の意味がわからなくてよく混乱すると思います。なのでまず、数学書を読む前に、最低限の記号は覚えておいたほうが良いかもしれません。よく使われるものを以下に挙げていきます。


\forall(for all) : "任意の"の意。「for all」のAです。"ターンエー"とも読むらしいです。

ex)
^\forallxF(x) : 全ての x に対して F(x) である。


\exists(exist) : "ある~"の意。「exist」のEです。"ターンイー"とも読むらしいです。

ex)
^\existsxF(x) : F(x) である x が存在する。


\exists! または \exists1 : "~が唯一存在する"の意。

ex)
^\exists^!xF(x) : F(x) である x が唯一つ存在する。


\to\mapsto :

ex)
f: \mathbb{R} \to \mathbb{R}, x \mapsto x^2-1 :

f: \mathbb{R} \to \mathbb{R}f が実数の集合 \mathbb{R} から実数の集合 \mathbb{R} への写像であることを意味し、x \mapsto x^2-1 はその写像が実数 x を実数 x^2-1 に写すことを意味する。


s.t. : "~となるような…"の意。「such that」の頭文字をとったものです。

ex)
^\existsx\in\mathbb{R}s.t.f(x)=0 :
f(x)=0 となるような実数 x が存在する。


とまあこんなところですかね。あと、数学的な言葉回しを挙げていきます。


「高々」:「多くとも」という意味。英語では at most。 高々4個は4以下を意味します。0でもよいのです。


「適当な」: 「適当な x に対し、f(x)>0となる」は、うまく x を選べば f(x)>0 となるということで、でたらめに x をとったときには f(x)<0 となるかもしれないということです。


「任意の」: これ結構誤解して使っている人多いですね。僕も最初の方は誤解してましたし(笑)。これは「全ての」という言葉で置き換えられるんです。「任意な x に対し」というと「x を一つ選んでくるのだが、どの一つをとってきても成り立つ」ということです。


「一意的、ユニーク」: 「唯一つ」とか「一意的である」とか言われる。意味は言わずとも分かりますよね?


「自明」: でました。邪悪な呪文ですよね。これで何度死にたくなったことか...数学に向かう者同士で力量差があったとき「これって自明だよね?(死ね)」「は、ハイッ!(死んできます!(白目))」ってなりますよね。意味は「証明する必要もなく明らかである」です。まあ当然人によって自明と言える段階が違いますよね。ジョルダンの曲線定理の証明の際にも「自明」うんちゃらでミスっているお方もいたらしいです。

実践

   ではこれらのことをふまえて、ちょっとした定義に触れてみましょうか。

Def. 関数 f: \mathbb{R} \to \mathbb{R} が点 x=a において連続である.とは

^\forall\varepsilon>0, ^\exists\sigma>0 s.t. |x-a|<\sigma
\Rightarrow |f(x)-f(a)|<\varepsilon.

ということなのですが、先ほどの知識で読めますか?是非やってみてください。

謝辞

   何かとんでもない記事を書いた気がしますので、間違いがあったらご指摘ください。また、参考にした文献は「数学ビギナーズマニュアル」という本で、これは初心者に打って付けの本なので初心者のお方は是非一度お読みください。
http://www.amazon.co.jp/2/dp/4535787557/ref=dp_ob_image_bkwww.amazon.co.jp


ぷよぐやみんぐしたぽよ~☆

序論

 どうも。ぞでぃあっくです☆ハタチ♥大学生していますっ♥趣味は数学とぷよぐやみんぐ!情報科大学生なのですが、最近は数学のお勉強にハマっています!
 でもでも今回は、最近講義で出された課題について書かせて戴きたいと思っておりますぽよ~

本題

 講義で出た課題というのは、「引数をmとnとし、m×n行列の各マスにポイントを割り振る。右と下に各マスを移動できるものとし、通ったマスのポイントを加算していく。左上から右下まで移動したときの最大総ポイントを答えよ。」というものです。「宝集めゲーム」っていうらしい(?)f:id:zodi_G12:20151213003318j:plainfig.1 課題の例(4×5の場合)

 最初は全く分からなかったが、後々よく寝た(睡眠学習した)ことで、瞬殺できまちた☆思いのほか達成感があったので、これについて記事を書こうと思った次第です。

解答

 では、僕の考えたアルゴリズムを紹介しましょう。
 全探査を全ての経路の総和を算出して、最も大きな値を最大値として返すものとするならば、このアルゴリズムは全探査ではないです。方針としては、「各マスにそのマスにたどり着くまでの総和を割り当てる」という考えで解いていきます。そのような考えを念頭に置くと、まず、1行と1列の各マスの値は進行方向の制限性により一意的です。よって、まず値を入れちゃいましょう。(fig.2)


f:id:zodi_G12:20151213004318j:plainfig.2 1行と1列の各マスに値を割り振る


 他のマスは、上のようにはいかないですよね。まあでも、「各マスにそのマスにたどり着くまでの総和を割り当てる」という方針に変わりはないです。ここで大事なのは進行のパターンです。2×2の正方行列を考えたときに、右斜め下のマスに進むためには2パターンしかないということです。なので、その2パターンでどちらの方が大きいか比べ(fig.3)、大きい方をマスに割り振れば良いのです。(fig.4)


f:id:zodi_G12:20151213004327j:plainfig.3 2×2正方行列における進路


f:id:zodi_G12:20151213010846j:plainfig.4 2×2正方行列における最大地値を取る進路


 まあそこまで難しくないですね?どうですか?あとはこれを念頭に置いて、各マスに確実な値を端から順次に埋めていけばできますね。因みに、このfig.1のような場合は、39が最大値となるはずですがどうでしょうかね。(fig.5)


f:id:zodi_G12:20151213012918p:plainfig.5 プログラム実行例


 それと僕の書いたコードも載せちゃいます///

/*simauta.c*/
#include <stdio.h>

#define N 100

int main(){
  int i, j;
  int takara[N][N] = {{0}}; //各マスに価値を割り振るために用意
  int ship[N][N] = {{0}}; //ある位置での宝の価値の総和を表すために用意
  int south, east;

  /* 行数の入力 */
  printf("south = ");
  while(scanf("%d", &south)!= 1||south < 1||south > N){
    printf("Wrong number of rows.\n");
    printf("south = ");
    while(getchar() != '\n');
  }

  /* 列数の入力 */
  printf("east = ");
  while(scanf("%d", &east)!= 1||east < 1||east > N){
    printf("Wrong number of rows.\n");
    printf("east = ");
    while(getchar() != '\n');
  }

  /* 要素の入力 */
  for(i = 0;i <= south - 1;i++){
    printf("Please input number at matrix[%d][0~%d]: ", i, east - 1);
    for(j = 0;j <= east - 1;j++){
      while(scanf("%d", &takara[i][j])!=1){
        puts("incorrect input.");
        while(getchar() != '\n');
      }
    }
  }

  /* [0〜east][0]と[0][0〜south]まで進行したときの宝の価値の和 */
  for(i = 0;i <= south - 1;i++){
    if(i == 0) ship[i][0] = takara[0][0];
    else ship[i][0] += takara[i][0] + ship[i - 1][0];
  }
  for(i = 0;i <= east - 1;i++){
    if(i == 0) ship[0][i] = takara[0][0];
    else ship[0][i] += takara[0][i] + ship[0][i - 1];
  }

  /* れっつ航海☆ */
  for(i = 1;i <= south - 1;i++){
    for(j = 1;j <= east - 1;j++){
      ship[i][j] += takara[i][j] + ((ship[i - 1][j] >= ship[i][j - 1]) ? ship[i - 1][j] : ship[i][j - 1]);
      printf("ship[%d][%d] = %d\n", i, j, ship[i][j]);
    }
  }
  
  printf("Max = %d\n", ship[south - 1][east - 1]);
  return 0;
}

 まあ、再帰でも書けると思います。(#それはそう)
 どうも御覧いだだきましてありがとうございます(^^)またこういった記事を書いていきたいと思っておりますのでよろしくです!ではでは~