スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

最小頂点被覆問題(minmum Vertex Cover)の近似アルゴリズムの実装

最小頂点被覆問題(minmum Vertex Cover)の近似アルゴリズムの実装をしますよ.

この記事はゆるふわです.不可解な点があれば鵜呑みにせず,信用できる資料に当たってください.
例えば,論文はもちろん,英wikipedia,大学の講義資料などがあります.

2017/06/16 追記 多項式時間で計算できる最小頂点被覆問題についてを書きました.



続きを読む

スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

特定の自然数を出現させないような、乱数を生成する

こちらも必要になったのをきっかけに。


以前に「1からnまでの乱数をm個重複せずO(m)でランダムに選ぶrubyのプログラム」を書いた。

これを一般化した、「特定の自然数を出現させないような、乱数を生成するプログラム」が必要になったので、記事にします。


何がしたいか分かりやすくするために1つの例を挙げてみる。

例えば、1から10までの整数を一様分布で選ぶ。これを1000回行う。
結果は次のようになった。左から1番目の数字は1が選ばれた回数、左から2番目は2が選ばれた回数、以降同様。
83 107 90 94 95 103 120 112 91 105 
ここで、4つの数字1,5,7,8が乱数によって選ばれないように指定する。
回数をリセットし、もう一度上と同様の操作を行う。
0 162 178 162 0 175 0 0 165 158 
確かに、1,5,7,8が選ばれず、他の値が一様分布の確率で選ばれている、と言える。


続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

tag : アルゴリズムとデータ構造

偏りのある乱数を生成する

整数乱数が欲しいので、実数の話はしません。



偏った乱数が欲しくなったので、コードを書いてみようと思う。

正規分布や二項分布のような数学的なものが欲しいのではなく、ゲームとか適当な実装に使えるような手抜き乱数が欲しい。

続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

Brainfuckのメモリに複数の数値をスタックする

ブロク編集のリソースを某プロコンに費やしているので記事を全然書いていなかったのですが、
1ヶ月制限広告が出そうなので何か書く。

ちょっと前の記事の通り、brainfuckについてはあまり良く知らないです。


省略のため、この記事では次のような表現をします。
  • 初期ポインタ位置をメモリ0番地とする。つまり、初期状態から「>」でメモリ1番地に移動する。
    メモリ%$i$%番地を%$M_i$%と表記する。


brainfuckで、次のようなことをしたいです。

%$n$%個の要素から成る数列%$a_1,a_2,...,a_n$%が与えられる。各要素の値は1byteに収まる。
各数列の要素%$a_i$%を%$M_i$%にセットしたい。%$M_0$%は作業領域として使用しても良い。


いや、もう少し難しくしたかったんですが。



続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

探索問題

特に難しい話ではないんだけれども。復習を兼ねて。


こんな問題を考える。

横Wマス縦Hマスのフィールドがあります。
フィールド上には床マスと岩マスの2種類のマスがあります。

岩があるマスは通り抜けることが出来ません。
ただし、岩の移動先が床マスである場合、岩を押すことが出来ます。

床マスのうち、1箇所をスタート地点、別の1箇所をゴール地点とします。
スタート地点からゴール地点に到達できるでしょうか?

…どこかで似たようなコンテストがあった気がしますが。

入力はこんな感じ。期待される答えはYES。
外周2マスは岩マスであることが保証されている。つまり、ちゃんと実装すれば外枠判定を実装しなくても良い。
12 10
@@@@@@@@@@@@
@@@@@@@@@@@@
@@....@..@@@
@@.S.@.@.@@@
@@...@@@@@@@
@@..@@.@..@@
@@@@.@@.G.@@
@@...@....@@
@@@@@@@@@@@@
@@@@@@@@@@@@


2016/10/25 修正

続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

tag : アルゴリズムとデータ構造 Ruby

ブログ移転のお知らせ
ブログをshonen.hateblo.jpに移転します. 新規の記事はこちらに投稿します.
プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
995位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
199位
アクセスランキングを見る>>
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。