シェルソート - 理想のユーザ・インターフェイスを求めて
挿入ソートのコードを改良してシェルソートのコードを作成した。 正しく動作することは確認したが、自分にとっては実装するには複雑すぎてコードを見ただけでは正しいかどうか判断が難しい。アルゴリズムとしては明快なのであるが...。try and errorでようやく正しい答えを得ることができた。 """ Shell sort Aug. 09, 2007 """ data = [2,15,23,40,56,1,12,54,27,6,3,5,67,87,22,38,92] print data dsep = len(data)/2 while 1: for N in range(1, dsep): for i in range(N, len(data), N): tmp = data[i] j = i while tmp < data[j-N] and j>=N: data[j] = data[j-N
挿入法 - 理想のユーザ・インターフェイスを求めて
ついでに挿入法も試す。左から順番に比較してゆき、挿入する位置が確定するまで並んでいるデータを右へずらす。 """ insertion sort Aug. 07, 2007 """ data = [15, 23, 3, 56, 22, 9, 1, 3, 20, 11] print data for i in range(1,len(data)): tmp = data[i] j = i while tmp < data[j-1] and j>=1: data[j] = data[j-1] j -=1 data[j]=tmp print data
選択法 - 理想のユーザ・インターフェイスを求めて
バブルソートと似た整列アルゴリズムの選択法も試してみる。正常に動作することを確認。今回はfor文を2回使用した。 """ selection sort ver.1 Aug.07, 2007 """ value = [6,2,4,9,7,1,0,3,8,10,1,5] for i in range(0, len(value)-1): min = i for num in range(min+1, len(value)): if value[min] > value[num]: min = num dummy = value[min] value[min] = value[i] value[i] = dummy print value
バブルソート - 理想のユーザ・インターフェイスを求めて
バブルソートを実行するプログラムをPythonで作成する。精錬されればもっとエレガントに書けるのだろうが、とりあえず正常に動作することは確認した。 """ bubble sort ver.1 Aug. 7, 2007 """ height = [178, 175, 173, 165, 179, 155, 182, 177] nmax = len(height)-1 while nmax >=2: for num in range(0,nmax): if height[num] > height[num+1]: dummy = height[num] height[num] = height[num+1] height[num+1] = dummy # print num, height nmax = nmax-1 print height
二分探索とは - IT用語辞典
概要 二分探索（binary search）とは、データ検索アルゴリズムの一つで、一定の順序にソート(整列)済みのデータ群の探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法。 まず、データを降順（大きい順）あるいは昇順（小さい順）に並べ替え、探索したいデータが中央の要素より大きいか小さいかを調べる。これにより、データが全体の前半分にあるか後ろ半分にあるかを判定することができるため、存在しない側の半分は探索範囲から外すことができる。 半分になったデータ群の中央の要素と再び比較し、前半と後半のどちらにあるかを調べる。この操作を繰り返し行うことで、一回の操作ごとに探索範囲の大きさが半分になっていき、中央の要素が求めるデータに一致するか、探索範囲の要素数が一つになる（求めるデータは見つからなかったことが確定する）と探索は終了する。 値の大小は文字の索引順の前後関係などに適宜置き換
バックトラッキング - Wikipedia
英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Backtracking|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があり
ユークリッドの互除法とは - IT用語辞典
概要 ユークリッドの互除法（Euclidean algorithm）とは、二つの自然数の最大公約数を求める計算手順(アルゴリズム)の一つ。古代ギリシャの数学者ユークリッド(Euclid/エウクレイデス)の発見した古典的な手法で、紀元前4世紀頃に編纂された「原論」に掲載されており、記録に残る最古のアルゴリズムとも言われる。 二数の最大公約数は両者とも割り切ることができる自然数（公約数）のうち最大のものだが、これは大きい方を小さい方で割った余り（剰余）と小さい方との最大公約数に等しいという性質があり、これを利用して効率的に算出する。 aとbの2つの数（a≧bとする）の最大公約数を求める場合、まずaをbで割った余りb'を求める。次に、b'をaで割った余りa'を求める。さらに、a'をb'で割った余りを求め…と交互に余り同士の割り算を繰り返し、初めて割り切れた（余りが0になった）ときの除数（割る方の
XOR交換アルゴリズム - Wikipedia
XOR交換(エックスオアこうかん、XOR swap)は、コンピュータ・プログラミングのアルゴリズムの一種であり、排他的論理和(XOR)を使用して一時変数を使わずに同じデータ型のふたつの変数の(異なる)値を交換する操作である。 このアルゴリズムはXORの対称差という性質を利用したものである。すなわち、任意のA, Bについて、(A XOR B) XOR B = A が成立することである。 標準的な交換アルゴリズムでは一時的な格納場所が必要となる。x と y の値を交換する場合、以下のようになる。 y の値を一時格納域にコピーする：temp ← y y に x の値を代入する：y ← x x に一時格納域の値を代入する：x ← temp あるいは、x と y が整数ならば、以下のようなアルゴリズムで交換することができる。 x := x + y y := x - y x := x - y ただし、
末尾再帰 - Wikipedia
一般に再帰呼び出しが可能な言語では、サブルーチン呼び出しのたびにスタックに呼び出し先から戻るための情報を保存する。そのため再帰が深くなりすぎるとスタックオーバーフローでプログラムが異常終了する。 そのような場合、次のようにループに変換して回避する。 { 変換前 } function F (a1:T1, a2:T2, ..., an:Tn) : T0 begin P ; return func (b1, b2, ..., bn) ; end ; { 変換後 } function F (a1:T1, a2:T2, ..., an:Tn) : T0 begin loop P ; a1 := b1 ; a2 := b2 ; : an := bn ; end loop ; end ; { Ti は型、P は手続き、bi は値または a1～an に対する副作用を伴わない式である。 それ以外の識別子は変
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
幅優先探索 - Wikipedia
ドイツの都市間の接続を示した例 フランクフルトから幅優先検索を行った場合にできる木構造 幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree structure)やグラフ(graph)の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。 幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。
深さ優先探索（バックトラック法） - Wikipedia
深さ優先探索のイメージ 深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。 形式的には、深さ優先探索は、探索対象となる木の最初のノードから、目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。非再帰的な実装では、新しく見つかったノードはスタックに貯める。 深さ優先探索の空間計算量は幅優先探索の空間計算量より最悪のケースでは同じだが一般的なケースではずっと小さい。また、探索の種類によっては、分岐を選択するためのヒューリスティックな方
二分探索 - Wikipedia
二分探索アルゴリズムの視覚化。探索目標値は7である。 二分探索（英: binary search）もしくはバイナリサーチとは、計算機科学において整列配列（英語版）の中から目標の値の位置を見つけ出す探索アルゴリズム[1][2]。このアルゴリズムでは、探索目標と、配列の中央に位置する要素とをまず比較する。値が等しくない場合、目標が存在する可能性がない側の半分の部分配列を除外し、残りの半分について中央要素との比較を再び行う。この手続きを目標値が見つかるまで繰り返す。配列が空になって終了したなら、元の配列に目標値が存在しなかったということである。 二分探索は対数時間（英語版）で動作するアルゴリズムであり、最悪のケースにおいて比較演算を 回行う（ n は配列の要素数）[注釈 1][3]。二分探索は配列が特に小さくなければ線形探索より高速であるが、実行するには配列があらかじめソートされていなければなら
バックトラック法とは - IT用語辞典
概要 バックトラック法（backtracking method）とは、コンピュータで数学的な問題の解を探索するアルゴリズム(計算手順)の一種で、解の候補を虱潰しに試していくが、途中で解になり得ないと分かった候補群は間引く手法。 条件を満たす要素の組み合わせを求めるような問題に適用することができ、厳密に解を求めることができるが、すべての組み合わせを調べる総当り方式（全探索）よりは効率が良い手法として知られる。 複数の要素の組み合わせが条件を満たすか調べる問題で、いくつかの要素を決定してみて、それ以上何を組み合わせても条件を満たすことがないと判明したら、その組み合わせについては探索を終了し、一手前に戻って（backtrack：引き返す）別の組み合わせを試していく。 例えば、サイコロA、B、Cの3つを振って和が10以上のものをすべて列挙するという問題を全探索で解くと、（A,B,C）=（1,1,1
ソート - Wikipedia
ソート (英: sort) は、データの集合を一定の規則に従って並べること[1]。日本語では整列（せいれつ）、並べ替え（ならべかえ）、分類（ぶんるい）などと訳される[1]。 主に配列や連結リストのような、リストデータ構造に分類されるコレクション（コンテナ）に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、英: ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、英: descending order）という。 対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。 効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム
ハッシュ法
ハッシュ法（hashing）は、メモリ上でデータを高速に検索するための手法である。各種のツリー構造とは異なり、静的な配列だけで簡単に実装でき、効率も極めて高い。このため、非常に実用的な手法として重宝である。 配列上でデータを検索する手法には、ハッシュの他いくつかある。以下、単純な手法から順に説明していき、ハッシュ法の説明に至ることにしよう。 ある小さな会社の社員情報をメモリ上で処理する場合を考えてみよう。社員情報のキーとして社員番号（整数）を用いることだけを決めておき、その他については考えないことにする。 （１）単純配列 データの出現順に配列につめていく。もっとも単純かつ基本的な方法。 データの挿入は高速だが、検索は端から順に見ていく（リニアサーチという）しかないため、平均するとデータ件数（社員数）の半分について処理が必要となる。 この手法は遅いので、データ件数が多い場合には使われない・・
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
番兵