魔法陣を解く 順列をすべて作ってから、魔法陣を満たすかチェックしてる。 対称解、枝切りなどは何も行っていない。 単純な全探索。rejectって書いた覚えないなって思ったらselect notのことか。 フォーマッター使うと勝手に変換されるのか def magicSquare …

各要素を選ぶか、選ばないかの問題を全探索で解く O(2^n)かかるが、とりあえずここまでをぱっと作れることが大切引数にiを使って、i番目の要素を選ぶことを表現する この書き方よく見るから覚えよう （個人的にはnを引数で渡して、マイナスしていきたいけど…

3×4の盤面でのナイト巡回問題 お気楽 OCaml プログラミング入門次のノードがわかる問題の全探索は ぱっとできるようになった気がする # 隣接リストバージョン $adjList = [ [5, 7], [6, 8], [3, 7], [2, 8, 10], [9, 11], [0, 6, 10], [1, 5, 11], [0, 2], […

動的計画法とは 再帰で表現したものを下から計算することで 計算の重複をなくすことが目的。再帰で解けるけど、計算量がやばいから動的計画法にしよう っていう発想だから、僕が問題を解く上では 動的計画法を意識せず、普段どおり再帰で解く。 計算量が指数…

再帰で解けるときは再帰でいい。下から積み上げていく解法のときに 動的計画法がぱっと使えるようになりたい。

螺旋本読んでもLISがわかんなかった。 以下のページがとてもわかり易かった。 最長増加部分列・最長共通部分列 [いかたこのたこつぼ]誤解してたこと ・Lは昇順に並んでいるから、これが最長増加部分列になると思ってた。 ・そうじゃなく、異なる長さの増加部…

# 素直にフィボナッチ def fib_normal(n) return 1 if n == 0 || n == 1 fib_normal(n - 1) + fib_normal(n - 2) end # メモ化 # 再帰の結果を配列に保存 # あくまで再利用がメイン $memo = [] def fib_memo(n) return $memo[n] = 1 if n == 0 || n == 1 ret…

def build_heap(arr) (arr.length / 2 - 1).downto(0) do |i| sift_down(arr, i) end arr end def heap_sort(arr) build_heap(arr) result =[] (arr.length - 1).downto(0) do |i| arr[0], arr[i] = arr[i], arr[0] result.push(arr.pop) sift_down(arr, 0) …

配列で表現された2分ヒープに対しての操作 完全2分木は配列で表現できる def deleteMin_heap(arr) arr[0] = arr.pop # 最後尾をrootへ sift_down(arr, 0) end # i番目の要素を適切な位置まで下げていく def sift_down(arr, i) leftIdx = 2 * i + 1 rightIdx …

ハッシュのオープンアドレス法では 格納場所に衝突が生じた際、再ハッシュを行う。そのやり方 hi(d) = ( h(d)+i ) mod B (i=1,2,...) 衝突したら次をチェックを繰り返す。iを足すだけだと配列の一番うしろを超えてしまう。 modすることで円のような感じにな…

## エラトステネスのふるいを用いて素数を求める def getPrime(num) return [2] if num == 2 return [2, 3] if num == 3 rootPrime = getPrime(Math.sqrt(num).floor) eratosu(rootPrime, num) end ## エラトステネスのふるい ## rootPrime:numの平方根より…

数Aの確率と同じで、すべてを数え上げれば解ける。 数え上げの手段として順列、組み合わせがある。 だから、これらでコードをさらっと書けるようにすれば、ほとんどの問題は解けるはず。 その上で実行時間、スタックオーバーフローなどの問題が生じたら違う…

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造作者: 渡部有隆出版社/メーカー: マイナビ出版発売日: 2015/01/30メディア: Kindle版この商品を含むブログを見る螺旋本を読み始める。 思ったよりも基礎から説明されててスラスラ読めそう

関数： ・引数を渡すと戻り値を返すもの ・外部の変数から影響を受けない（引数が同じなら戻り値も同じ） ・外部の変数に影響を与えない（グローバル変数などを変更しない）これだとインスタンスや配列などのオブジェクトを更新（状態の変更）ができない そ…

なっとく! アルゴリズム作者: アディティア・Y・バーガバ,株式会社クイープ出版社/メーカー: 翔泳社発売日: 2017/02/01メディア: 単行本（ソフトカバー）この商品を含むブログを見る再読した。 わかりやすくてよい。 特に動的計画法(ナップザック問題)はグリ…

就活でのwebプログラミングテストの対策としてAtCorderを使っていた時の話。・rubyはバージョンが2.3.3 配列のsumメソッドが実装されていない。・node.jsはバージョンが5.12 便利なメソッドはバージョン6から実装されてるからほとんど使えない。 就活でのweb…

今までインデントはデフォルトのままスペース2つを使っていた。 たまたまスペース4つのコードと触れる機会がありそっちになれるとスペース4つのほうが読みやすい気がしてきた。ということでスペース4つに変更してみる。あとスペース4つだと横に長くなるから1…

プログラミングってすごいスキルが必要なのかと思ってたけどそうじゃないのかも。 問題を適切な要素に分解して、こんがらがらずにできれば大概のものは作れるかも。 （フロントエンドの話です）となると作り始める前に全体像を把握するのがとても大切な気が…

predicate 意味：述語日本語の述語には2つ意味がある 1つ目は主語と述語。動詞とほぼ同義。 2つ目は数学用語の述語。 こっちの意味は 変数 ｘ の値を定めることで真偽を判定することができる主張を 『 述語 』 という。 命題論理と述語論理プログラミングに…

抽象度 reduce > mapどう使い分ける map 配列の各要素に関数を当てた配列を返すとき 注目するのはその要素に何をするかだけ （map_sqrt : list(int) => list(int), map_mod2 : list(int) => list(bool) )reduce 1,配列をなにかに変換するとき （sum : list(i…

1,漸化式を表現する // f(n)をf(n-1)を使って表せたら再帰関数は作れる // a(0) = 3 // a(n) = 2 * a(n-1) -1 let rec a = n => switch (n) { | 0 => 3 | _ => 2 * a(n - 1) - 1 }; // 1からnまでの総和 // sum(0) = 0 // sum(n) = n + sum(n-1) // 素数判定…

extract 抜き出す、取り出すextract(n, lst) lstからn番目だけ抜き出す 例） extract(3, ["a","b","c","d","e"]) = ("c", ["a","b","d","e"])

前からの結果が必要（回数を数えるcount, 経路を覚えとくpathList） ー> 補助関数を使う ー> countなどを引数として渡す（引数の意味はコメントに書いておくこと） 結果が複数あるもの ー> 結果が出たらaccに詰めて、引数として渡す ー> 最後にaccを返せば出…

listを受け取ったときの定石2つ 1,パターンマッチング 先頭のみで処理が完結するとき2,reduce(fold_left) 先頭以外の要素にも同様の処理をする必要があるとき図にしてみると、このreduceの使い方はパターンマッチングを複雑にしただけだね 先頭だけで済む「…

やっと8クイーン問題ができた（たぶん） /* lstの要素すべてがfを満たせばtrue */ /* isSafeでクイーンチェックに使用 */ let rec all = (f, lst) => switch (lst) { | [] => true | [_, ...rest] => f(lst) == true ? all(f, rest) : false }; /* リストを…

追記2 el = [1,2,3,4,5,6,7,8] だとして 今の値±(リストのidxの差)だと斜めにいるとみなせるから これをコードにしたらできそう追記2終わり追記 だめだ よく理解してないからできないのだろう 他のサイトを参考に実装しよう 追記終わり お気楽 OCaml プログ…

nCr = n-1Cr-1 + n-1Crｎ人からｒ人を選ぶ = hさんを選び、残りのn-1人からr-1人を選ぶ => n-1Cr-1 + hさんを選ばないで、残りのn-1人からr人を選ぶ => n-1Cr let add_to_each = (num, lst) => List.map(el => [num, ...el], lst); let rec combination = (r…

ocamlを使っていて出てきた略語のまとめ。aux 原語 ：auxiliary 意味 ：補助 使い方：補助関数の名前acc 原語：accumulator 意味：蓄積 使い方：再帰関数で引数として次に情報を渡すとき、rest_resultとかと同義、reduceのpreはこれhd 原語：head 意味：先頭…

ReasonMlによるマージソートの実装。 今まではよくわかんなかったけど、マージソートの意味がやっとわかった。 /* 目的：2つのリストを受け取ってくっつける */ /* merge: list(`a) => list(`a) => list(`a) */ /* 先頭の要素同士を比較して、小さい方を前に…

再帰には先頭再帰と末尾再帰がある。先頭再帰は最後まで呼び出してから帰ってくる。 シンプルでデータの流れがわかりやすい。末尾再帰は後ろを呼び出ながらデータを渡す。 データを引数として渡すから少し複雑になる。 でも、スタックオーバーフローが起こら…