「マス目上の経路」とは、例えば以下のようなものです。 引用：道順の場合の数を求めるテクニック | 高校数学の美しい物語 画像ではマス目の縁に沿って辿っていますが、今回考えるのはマス目からマス目へと辿る経路です。 画像のマス目では、左下の角から右…

前回の記事の続きです。 jpliterature.hatenablog.com 前回は、スタート地点から各地点までの歩数を求め、それを int型配列moves に格納しました。 今回は moves をもとに、スタート地点からゴール地点までの道のりを表示してみたいと思います。 実装方針 ・…

Java で幅優先探索をおこなうには、Queue というデータ構造を使います。 ja.wikipedia.org キューは先入れ先出し、すなわち、先に入れられたデータから順に取り出されるデータ構造です。 ところてん式といったほうがわかりやすいかもしれませんね。 では、こ…

本記事ではバブルソート（Bubble Sort）のアルゴリズムと実装を勉強します。 ja.wikipedia.org 長さ n の数列をバブルソートでソートするとき、 ・0 ~ n-2 番目までの最大値を n-1 番目にもってくる ・0 ~ n-3 番目までの最大値を n-2 番目にもってくる （中…

本記事では挿入ソート（Insertion Sort）のアルゴリズムと実装を勉強します。 ja.wikipedia.org 挿入ソートのアルゴリズムはとても単純……なはずなのですが、Wikipedia や AIZU ONLINE JUDGE にあったサンプルコードがよく理解できませんでした。そのため、挿…

Java で二分探索を実装する際、わざわざ左端と右端と中央をループの中であれやこれやしなくても、クラスライブラリの java.util.Arrays に二分探索をおこなってくれるメソッドが存在しています。 仮に、以下のような配列があったとします。 int[] ar = {2,4,…

以下の記事では、ビット全探索による部分集合の全列挙を勉強しました。 jpliterature.hatenablog.com 今回の記事では、同じことを再帰関数でやってみようと思います。 さて、再帰関数で部分集合を全列挙するにあたり、こんな問題を作ってみました。 問題文 …

プログラミング関連の書籍にありそうなタイトルですが、以下の記事の続編になります。 jpliterature.hatenablog.com 上記の記事では、ビット全探索を使って問題を解きました。しかし私自身、ビット全探索、もといビット演算子についてよく理解していません。…