[id:lethevert:20070120:p3] 基本図形で曲がる回数は３回なので、計算過程は３分木に対応する。それを数値で表すには、３進数を使えばいいのではないか？ - ああ、違うな。４進数か？ とりあえず、忙しいので後で考える。

[id:nuc:20061213:p13] これで上手く行きそうだけど、未確認。

[id:nuc:20061213:p8] 任意の自然数nとそのが作図できそうな方法は思いついた。

[id:nuc:20050908:p1] こんな感じ？

[id:lethevert:20070118:p2] 数学の才能がないので、上手く数式化できないけれど、次のようなところまで考えた。 とりあえず、M=4のケースで考える。つまりQueueが４本になるわけだけれど、これを、Queue１本での確率でput、の確率でgetというように読み替え…

[id:lethevert:20070113:p1] とりあえず、特にひねりもなく。

最近、C系のインデントの好みが変わったので、.emacsを修正した。 (setq c-mode-hook '(lambda () (c-set-style "gnu") (setq c-basic-offset 1) (c-set-offset 'defun-open '+) (c-set-offset 'defun-block-intro '++) (c-set-offset 'class-open '+) (c-se…

http://blog.livedoor.jp/dankogai/archives/50748865.html id:sumimさんが「PerlはOOPと言ってよい（要約）」といっているのに対して、「Perl 5の$object->method(@messages)はOOP以外の何ものでもない。」と、見事に噛み合っていないつっこみを入れた例。

玄人むけにはid:sumimさんのところの解説を見てもらうとして、プログラマでない人に簡単な説明をする機会があったので、ちょっと考えて次のようなことをしゃべった。 オブジェクト指向を利用すると、プログラムをモジュールに分割して、各モジュールを他のモ…

Nノードのグラフが、どの１つの辺を取り除いても、連結ではなくなる場合に、辺の総数がN-1で循環がないことを証明せよ。

２分木は、左の枝が子ノードを、右の枝が兄弟ノードを指している一般的な木であると考えることができる。 ２つの２分木が、同型（isomorphic）な順序のない（unordered）木であるかを判断するプログラムを書け。

parent-childの関係がa[child]=parentで表されるような木とそれを表す整数配列を考える。 ２つの整数配列が渡されて、それが同型（isomorphic）な順序のない（unordered）木であるかを判断するプログラムを書け。

以下に定義するナップサック問題を、指定したそれぞれのやり方で解け。 0 1 2 3 4 item A B C D E size 3 4 7 8 9 val 4 5 10 11 13 ナップサックのサイズは17。 1. top-down dynamic programmingを用いて、各ステップで１つずつ最適な品物を選択する方法 2.…

の計算量を減らす。

[id:lethevert:20070111:p1] 昔、C++を書いていたこともあったのだけれど、もうすっかり忘れていて、苦労した。なれない言語だと、くだらない間違いでもなかなか見つけられない。 テストコードは、こういう感じで。 Matrix matrix1(); Matrix matrix2(); int…

奮闘中

n次のKoch曲線（＿／＼＿を基本図形としたフラクタル図形）を「α度回転し、1/(3^n)長の線分を引く」ことを繰り返して描く際に、i番目のαの値を、iの値から求めよ。 （ハノイの塔における、上記の例を参考にせよ）

ハノイの塔の問題で、i番目に動かす円盤は、整数iの下位ビットに0が連続している数に１を加えた数の番号の円盤である。

int値の下位ビットに0がいくつ連続しているかを数える関数を書け。 例） 6 (=..0110) -> 1 12 (=..1100) -> 2

http://sky.zero.ad.jp/~zaa54437/programming/clean/LanguageReport21/Chap5.html#sc8 一意型レコードの破壊的更新はサポートされていないらしいのだが、効率的なコレクションライブラリを作るには、必要な気がするが、そうでもないのだろうか？

M個のFIFO Queueを用意し、次のように２つの操作を定義する。 put : M個のQueueから、ランダムに１つ選んで、末尾に要素を追加する get : M個のQueueから、ランダムに１つ選んで、Queueが空でなければ先頭要素を取り出し、空ならば空を返す for (i=0; i

問題を書くだけ書いて、ゆっくり解いている暇がない。

http://www.shmula.com/31/my-interview-job-offer-from-googleより 元の問題は、問題になっていないので、元の問題を推測しながら。 you are at a party with a friend and 10 people are present including you and the friend. your friend makes you a w…

次のルールを持つ Random Queue を考える。 insertとremoveの２つの操作を持つ removeを呼ぶと、これまでにinsertした要素からランダムな１つを削除して、その要素を返す 1. 配列を用いて、insertとremoveがO(1)時間で完了する実装を示しなさい 2. リンクリ…

Dequeを用意する。アルファベット（大文字／小文字）と + と * からなる文字列を受け取り アルファベット大文字なら、それをDequeの先頭に加える アルファベット小文字なら、それをDequeの末尾に加える + なら、Dequeの先頭から取り出して、印字する * なら…

Stackを用意する。アルファベットと * からなる文字列を受け取り アルファベットなら、それをStackに積む * なら、Stackから取り出して、印字する という処理を行う。 1. EASYという文字列に、適当に * をいくつか挿入して、次の文字列を出力するような入力…

v2.xからはGame Libraryというのが標準添付されています。 http://cleangl.sourceforge.net/

[id:lethevert:20070108:p1] 1. 一般性を失うことなくグラフが連結であると言えるとしてから、帰納法。 2. 時間計算量を考えなければ簡単。 リンクを１つずつたどりながら、新しいノードが以前に出現していないかを毎回もう一度頭からたどり直して確認するこ…

多次元行列が疎（sparse）な場合、多次元配列の代わりに、多重リスト（multilist）を使って表現する方がよいこともある。その場合、各ノードが行列のセルに対応し、ノードには次元ごとにその次元での次の要素に対するリンクを持つ。値がゼロのセルに対応する…

Working Effectively With Legacy Code作者: Michael Feathers出版社/メーカー: Prentice Hall発売日: 2004/09/22メディア: ペーパーバック購入: 8人 クリック: 168回この商品を含むブログ (69件) を見る評判がよさそう。amazon.co.jpもamazon.comも両方とも…