頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
10兆までの素数のリストを作ってみませんか？
もしあなたがプログラマだったら、プログラムを書いて10兆までの素数のリストを作ってみてほしい。情報システムの開発に携わる人であれば、10兆までの素数のリストを出力するシステムの見積もりを考えてみてほしい。費用はどれくらいかかるか、納期はどれくらいか、あなたはどんな答を出すだろうか。仕様書はうまく書けるだろうか。 記者がこんなことをいうのは、自分で10兆までの素数のリストを作ってみて、とても面白かったからだ。図1のプログラムを書いて出力が成功するまで約2週間、夢いっぱいの楽しいひとときを過ごせた。予期せぬ問題も発生したけれど、最後にはコンピュータがまだまだ発展する可能性を持つと感じられた。素数のリストを作る演習は、プログラミングと情報システムにおける有益な演習の一つである。 アルゴリズムの有効性が納得できる この演習の面白い点は、まずアルゴリズムの有効性を納得できる点だ。素数（prime）は
検索エンジンを実装 (1)転置インデックス作成
今回はN-gramでテキストを分解します。N-gram法とは対象の文字列を一定のN文字単位で分解し、それの出現頻度を求める方法です。これによって、検索エンジンに使われる転置インデックスを作成したいと思います。転置インデックスの作成方法にはN-gramの他に形態素解析があります。両者の性能の長短は全文検索 – Wikipediaに詳しく載っています。 Javaソースコード(Make2gram.java) さて、まずは文字列を2単語に切り分けるプログラムを作成しました。データ構造は単純にArrayListで、出現頻度も求めていません。 import java.io.*; import java.util.*; /** * N-gram法 */ public class Make2gram { public static void main(String[] args) { final shor
オーダーを極める思考法
プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。今回は、計算量のオーダーについて学びながら、TopCoderのMedium問題を考えてみましょう。 プログラムの実行時間 業務としてプログラミングをされている方には釈迦に説法かもしれませんが、プログラムの実行に掛かる時間を把握しておくのは、プログラミングを行う上で基本的な注意点です。そしてこれは、TopCoderなどのコンテストでプログラムを組む際にもよく当てはまります。通常、こうしたことは感覚的に理解している方がほとんどだと思いますが、具体的にどれくらいのループを回すと何秒掛かる、といった基準を持っている人は少ないのではないでしょうか？ 非常に基本的なことですが、プログラムの実行時間に関して再確認しておきたいと思います。 TopCoderの制限に関して TopCoderでは、実行時間およびメモリ使
定番アルゴリズムを徹底理解！ - 今からでも遅くない！アルゴリズム入門：selfup
このパートでは，プログラミングを勉強するうえで欠かせないアルゴリズムの中でも定番中の定番を紹介します。ソート（並べ替え）やサーチ（検索）などの機能は今では標準のライブラリとして提供されています。実用的なプログラムを作るときにそのものずばりをいちいち書く機会は少ないかもしれません。しかし定番のアルゴリズムは，様々に形を変えて普段のプログラミングに登場します。 解説を読んで仕組みがわかったら，ぜひそれをプログラムにしてみてください。読んだだけではプログラムを書けるようにはなりませんし，プログラムを書いてみて初めて，実は十分に理解できていなかったと気付くことがよくあります。しかもアルゴリズムは特定のプログラミング言語に依存しないので，一度身に付ければ，後でどんな言語を学ぶ場合でも役に立ちます。 1番目から6番目まではソートのアルゴリズム，7番目から9番目まではサーチのアルゴリズムです。一つひとつ
[を] 転置インデックスによる検索システムを作ってみよう！
転置インデックスによる検索システムを作ってみよう！ 2007-11-26-5 [Algorithm][Programming] 転置インデックス[2007-06-17-6]による検索システムの実装は パフォーマンスを無視すれば意外と簡単です。 それを示すために Perl で簡単な検索システムを作ってみました。 検索方式は転置インデックス(Inverted Index)、 ランキングには TF-IDF[2005-10-12-1] を用いました。 検索対象ファイルは一行一記事で以下のフォーマットとします。 [記事ID][SPC][記事内容]\n 記事IDは数字、記事内容は UTF-8 の文字で構成されるものとします。 以下のようなサンプル test.txt を用意しました。 1 これはペンです 2 最近はどうですか？ 3 ペンギン大好き 4 こんにちは。いかがおすごしですか？ 5 ここ最近疲れ
![[を] 転置インデックスによる検索システムを作ってみよう！](https://cdn-ak-scissors.b.st-hatena.com/image/square/af37977ee866988286b95e74fff98500a190545c/height=288;version=1;width=512/https%3A%2F%2Fchalow.net%2Fimages%2Ftcl-logo-25.png){kind=logo}
一番右端の立っているビット位置を求める「ものすごい」コード - 当面C#と.NETな記録
一番右端の立っているビット位置(RightMostBit)を求めるコードで速いのないかなーと探していたら、ものっっっすごいコードに出会ってしまったのでご紹介。2ch のビット演算スレで 32bit 値のコードに出会って衝撃を受けて、その後 64bit 値版のヒントを見つけたのでコードを書いてみました。 この問題は ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか (Google book search で原著 Hacker's delight が読めたのでそれで済ませた) で number of trailing zeros (ntz) として紹介されています。bit で考えたときに右側に 0 がいくつあるかを数えるもの。1 だと 0、2 だと 1、0x80 なら 7、12 なら 2 といったぐあい。0 のときに表題どおりの問題として考えるといくつを返すの？ってことになるので、
ジャンル別ゲームの作り方とアルゴリズムまとめ - ネットサービス研究室
ゲームの作り方とアルゴリズムをジャンル別にまとめてみました。ゲーム制作や、プログラミングの勉強用にご活用ください。言語別ゲームプログラミング制作講座一覧もあわせてお読みください。 リンク切れがおきていたものは、URLを表示しておくので、Internet Archiveなどでキャッシュを表示させてみてください。 RPG ゲームの乱数解析 乱数を利用した敵出現アルゴリズムの解説 各種ゲームプログラム解析 FF、ドラクエ、ロマサガのプログラムの解析。乱数の計算など ダメージ計算あれこれ（http://ysfactory.nobody.jp/ys/prg/calculation_public.html） ダメージの計算式 エンカウントについて考えてみる エンカウント（マップでの敵との遭遇）の処理方法いろいろ RPGの作り方 - ゲームヘル2000 RPGのアルゴリズム ドルアーガの塔 乱数の工夫の
シムシティーの仕組み
シムシティーを作り始めていちばん最初に考えたのは、街を一種の生き物のように表現できないかってことだった。 僕が街についてどう考えているかはすでに説明したけど、大事なのは街を構成する建物とか道路じゃなくって、そこでどんな活動が行なわれているかってことだと思うんだ。道路を車が走り、電車が動き、人々が動き回り、常に要素が変化し続ける“動きのある”システム。街を表現する方法っていうと誰でも地図を思い浮かべると思うけど、僕は動きがない地図じゃなくって、たとえば飛行機から眺めた街、動きのある世界をディスプレイに表現しようって考えた。それこそが僕の考える街の姿だからね。 それともう一つ考えたことは、プレイヤーに伝える情報をできるだけわかりやすく、それも“面白い”って思えるような形で表現しようってことだった。シミュレーション・ソフトっていうとたいてい数値や図表がたくさん出てくるけれど、数字が並んでいるのを
講義資料 配列解析アルゴリズム特論I 情報生命科学基礎/演習 他 -渋谷哲朗
平成20年度 東京大学大学院 情報理工学系研究科・コンピュータ科学専攻 配列解析アルゴリズム特論I 4/10 4/17 4/24 5/1 5/8 5/15 5/22 5/29 (The problem to be reported - in English) 6/5 6/12 6/19 7/3 7/10 7/17 東京大学 理学部・情報科学科 情報科学特別講義３ （情報科学とバイオインフォマティクス） 6/10 7/15 7/22 東京大学大学院 新領域創成科学研究科・情報生命科学専攻 情報生命科学基礎/演習 5/27 6/17 京都大学大学院 薬学研究科・医薬創成情報科学専攻 情報科学概論 6/3 中央大学大学院 理工学系研究科・物理学専攻 物理学特別講義第二 TBA 創価大学工学部 生命情報工学科 TBA TBA 戻る Copyright (c) 2004- Tetsuo
ガベージコレクションの実装法と評価
1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい
クラスタリングによる迷路作成アルゴリズム
はじめに クラスタリングアルゴリズムにより、解くと絵が浮かび上がる 迷路を作成する方法を紹介する。 クラスタリングとは ウェブのリンク情報や、mixiの友人関係など、ネットワークの性質を 知りたいことがよくある。このとき、ネットワークの性質として このネットワークにおいて任意に選んだ要素Aと要素Bはつながっているか？ このネットワークは全体がつながっているか？ つながっていないとしたらいくつのグループに分かれるか？ 要素数最大のグループはどれか？ などの情報が欲しくなる。このような解析をするときに 必要となるのがクラスタリングである。 クラスタリングとは、同値関係のリストが与えられたときにグループ分けを することである。たとえば、 友達の友達は友達である と定義すると、友人関係は同値関係を作る。 その上で、 A君とB君は友達 C君とE君は友達 B君とD
連載：検索エンジンを作る｜gihyo.jp … 技術評論社
運営元のロゴ Copyright © 2007-2025 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10
2007年11月26日18:15 カテゴリMathLightweight Languages プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10 ぎくっ あなたが一番好きなアルゴリズムを教えてください。 また、その理由やどんな点が好きなのかも教えてください。 - 人力検索はてな なぜぎくってしているかというと、実はすでにアルゴリズム本の発注を受けているからなのだ。いつまでも伏せておくのもなんなので、ここにえいやっとdiscloseしてしまうことにする。 アルゴリズム大募集! C&R研究所 - トップページ その下書きもかねて、そこでも紹介しないわけに行かないメジャーなアルゴリズムをとりあえず10個紹介しておくことにする。 ユークリッドの互除法(Euclidean algorithm) その昔(数百年ほど前)は「アルゴリズム」といえば、「手順一般」を指すのではなく、この「互除法
「＋1」だけで四則演算をするには？
巨大な数同士の掛け算は？ もう1つの例として、大きな数値の取り扱い方について考えてみたいと思います。 人間は理論上、どんな大きな値でも計算することができます。ただし暗算の名人でなければ、紙と鉛筆を使うでしょう。紙に書ききれないぐらい大きな値だとしても、もう1枚紙を持ってきて継ぎ足せば、計算することができますね。 しかし、コンピュータが1つの変数で扱える数値の大きさは、32ビットや64ビットで表現できるものまでです。そういった1つの変数で扱えない大きな数字を扱うことになった場合、コンピュータにどう処理させますか？ （1） 53 （2） 53 ×72 ×72 ―― ―― 6 106 （3） 53 （4） 53 ×72 ×72 ―― ―― 106 106 21 ＋371 ――― 3816 それを考えるために、皆さんが実際に計算をするとき、
第10回 麻雀の役を判定する：ITpro
図1に示す(1)から(3)までの麻雀（マージャン）の手牌があります。「あがり牌」はすべて山からツモったものとし，リーチはかけていません。またドラやハイテイ＊1なども関係ないものとします。これらの役を判定して，親の場合の点数を計算するプログラムを作ってください。 「ややこしや～ややこしや～」というのは野村萬斎ですが，思わずそううなってしまうことがプログラミングをしているとよくあります。今回の麻雀の役判定は，考えれば考えていくほどややこしく，そうしたものの代表と言えるでしょう。排他処理や優先順位が複雑にからんでいて一筋縄ではいきません。 今回はややこしい組み合わせを解決する方法を考えてみます。麻雀になじみのない方も，ちょっとしたパズル気分で試してみてください。 麻雀の役を考える 麻雀を知らない方のためにルールをおおざっぱに説明しておきましょう＊2。麻雀の牌には，大きく分けて「萬子（マンズ）」「
スペル修正プログラムはどう書くか
Peter Norvig / 青木靖 訳 先週、2人の友人(ディーンとビル)がそれぞれ別個にGoogleが極めて早く正確にスペル修正できるのには驚くばかりだと私に言った。たとえば speling のような語でGoogleを検索すると、0.1秒くらいで答えが返ってきて、もしかして: spelling じゃないかと言ってくる(YahooやMicrosoftのものにも同様の機能がある)。ディーンとビルが高い実績を持ったエンジニアであり数学者であることを思えば、スペル修正のような統計的言語処理についてもっと知っていて良さそうなものなのにと私は驚いた。しかし彼らは知らなかった。よく考えてみれば、 別に彼らが知っているべき理由はないのだった。 間違っていたのは彼らの知識ではなく、私の仮定の方だ。 このことについてちゃんとした説明を書いておけば、彼らばかりでなく多くの人に有益かもしれない。Googleの
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Amazon.co.jp: Cによる探索プログラミング: 基礎から遺伝的アルゴリズムまで: 伊庭斉志: 本
emit.jp