結城さんのはさみの問題

CodeIQで乗り遅れたのでgihyo.jpにあがってるのを解いてみた

第6回 ハサミを使うタイミング〜どうやって端を見つけるの?─結城浩からの問題

ブログとかで解答していいのか知らんし、あってるかもわからんのでなんかったら消します。
あと、自分で解きたいからネタバレイヤヨって人も見ないでください。


横の長さをx、縦の長さをyとしたときに
2で出来上がるのが必ず長さyの正方形。
3は ny <= x となるn個の正方形を作る。

なので切り取った左側をa、右側をbとすると

x = a + b
a = ny
x = ny + b

つぎに使うのがbなので

b = x - ny ( = x % y)

でこのbを新たなy, 今までyをxとしてbが0になるまでの計算回数-1が40になればおkと
(一回目の計算で0になるとはさみを使っていないので)

ここまでくるとお分かりのようにやってることがユークリッドの互除法と一緒なんですね。

ユークリッドの互除法

というわけで最大公約数ではなくそのときの回数を求めるRubyのコード

#はさみを使った回数なのでカウントは0から始める
def gcd_count(a, b, level = 0)
  if a < b
    puts "error"
    return 0
  end
  r = a % b
  if r == 0
    return level
  else
    gcd_count(b, r, level + 1)
  end
end

で、どうやって40回再帰されるaとbを見つけようかなと思ったんだけど、さすがいろんなあたい入れて試行錯誤するのも疲れるし、
間違って黄金比にでもあたったら一生計算が終わらなくなるwジャイロさんの黄金長方形と一緒で無限に回転するのですよwたぶん

という訳で計算回数の求めかたを調べてみたら

互除法

こんなページを見つけた。定理7.3の下の方に書いてある。

どうやらフィボナッチ数列を使えばいいみたい。

Fn % Fn-1 = Fn-2(n >3, n = 0, 1, 2, 3, 4 ...)

なのね

Fn = Fn-1 + Fn-2
-> Fn = 1 * Fn-1 + Fn-2

とかんがえると当たり前か

Fn = 3〜13くらいまでで手計算してみたところ
n-2が今回のはさみを使う回数と一致したっぽい
(う〜ん、上の定理と若干異なるのが気になる・・・)

雑な感じだけどフィボナッチ数列もこんなRubyで実装

def fib(count, level = 0, now1 = 1, now2 = 1)
  if level !=0 && level != 1
    tmp = now1 + now2
    now2 = now1
    now1 = tmp
  end

  if level == count
    return now1
  else
    return fib(count, level + 1, now1, now2)
  end
end

あとは40回にするために40 + 2で

x = fib(42)
y = fib(41)

puts fib(x, y) #=> 40
puts x           #=> 433494437
puts y           #=> 267914296

267914296x433494437

が答え、と。

以上



追記
この記事に関してですが、
挑戦受付が終了しているということで、問題ないということでした。

ブログ記事にかんしての注意事項などは下記のページに記載されています。
他の問題に関する情報もありますで
今後も追加されていくと思いますので、挑戦してみたいッ!
ってかたは一度ごらんになってみるといいと思います。

CodeIQの問題に挑戦しよう!

javaのあんまり知らないほうがいい知識

以下のようなクラスがあるとする


class A {
private int x;
}
このクラスに対して以下のメソッドがコンパイルエラーにならずにしかも実行時にもエラーにならずに記述できる場所がある

void hoge(A a) {
a.x = 10;
}
普通に考えるとプライベートなメンバへのアクセスなので、コンパイルは通らない

しかし、javaのprivateは同じ"クラス"からしかアクセスできない

なので同じクラスであれば別なインスタンスでもアクセスできる

なので


class A {
private int x;

void hoge(A a) {
a.x = 10;
}
}

は問題なく実行できる

まぁ

this.x = 10;

は大丈夫で

A a = this;
a.x = 10;

がNGなのは明らかに不自然だしね

まぁこれが役に立つのって、equalsメソッドのオーバーライドのときとかみたいにかなり限定されるけどね

C言語でオブジェクト指向的なことをする

気がつけばすっかり怠けていたブログ更新

今回は意味もなくC言語オブジェクト指向をしてみようと思ったので以下の3つを実装する方法について考えてみた

カプセル化

・継承

ポリモーフィズム


カプセル化

ヘッダファイルにメソッドとして必要な関数と同じシグニチャな関数へのポインタののみを持った構造体とコンストラクタ的な役割を持つ関数のプロトタイプを用意

コンストラクタは構造体へのポインタを引数か戻り値にする

メソッドの実装となる関数とコンストラクタの実装を別のソースに記述

また、必要な、プロパティはこのファイルのグローバル変数として定義

コンストラクタの実装はメモリ確保後に必要な初期化処理と構造体の関数へのポインタとメソッドの実装を結び付ける処理を行う

使う側はヘッダファイルをインクールドして構造体を使う
ソースは見えてない(extarnalするなよww)ので実質すべての処理を構造体の関数へのポインタを通して行うこととなりプロパティが隠蔽される


継承

簡単かつ単純な実装がいいので子クラスとして定義する構造体が親クラスとして定義されている構造体をメンバとして持つ

子クラスのコンストラクタで親クラスのコンストラクタを呼び出すのを忘れないこと


ポリモーフィズム

子クラス独自実装のメソッドとなる関数を用意し、継承の実装の際に子クラスのコンストラクタで親クラスの関数へのポインタの参照先をそちらにする

親クラスの変数に子クラスを入れることはできないが、子クラスから親クラスを取得して、メンバ関数を実行した際には子クラスの処理が走る


とりあえずこんな感じ

酔った勢いで書いているので何か問題があれば教えてください

flashからサーバサイドへのリクエスト

最近聞かれることが多いので
AS2.0と3.0の2本立て


まず, 最初に簡単な概要
flashからアクセスするといってもサーバサイドでやることは変わらない
リクエストを送信し, レスポンスとしてHTMLを返す. それだけ
ただ, リクエスト送信とHTMLの解析がブラウザかflashかの違いだけである
ただし, 異なる部分はflashが受け取ったHTMLはXMLとして解析するということと
それを解析するプログラムも実装する必要があるということである.
したがって, 単純にUIをRIA化するためだけにflash部分のみを新規実装するといった開発も可能だし, flashで処理するのに必要な値だけを非HTMLで返すことも可能である.


リクエストのパラメータについて
Webアプリケーションの開発経験がある方ならご存知だろうがクライアントからリクエストを送信する際に追加情報を送ることができる.
たとえばログイン画面のようなものであればログイン後の画面要求とともにIDやメールアドレス, パスワードのようにログイン認証に必要な情報も送る.
このパラメータが
パラメータ名とその値が一対一の対応関係になっているためサーバサイドではハッシュマップで扱われることが多い
flashから送る際もパラメータと値を対で送る.


ではソース
まずはAS3バージョン


//リクエスト
var req:URLRequest = new URLRequest();

//リクエストにアクセス先を設定
//相対パスでもおk
req.url = "http://neetomo.dip.jp/";

//送る方法をPOSTに設定
req.method = URLRequestMethod.POST;

//送る変数を設定
//URLVariablesのプロパティに値を設定する
//プロパティ名がリクエストのパラメータ名に対応
var uv:URLVariables = new URLVariables();
uv.FirstName = "流離の";
uv.LastName = "苦情人";

//リクエストにパラメータを設定
req.data = uv;

//外部にアクセスするための変数
var loader:URLLoader = new URLLoader();

//サーバにアクセスした後, レスポンスが帰ってきた時に行う処理をを第2引数で指定
//この際に処理を行うメソッドを指定すること
loader.addEventListener(Event.COMPLETE, onComplete);

//サーバにリクエストを送信する
loader.load(req);

//サーバ側から戻ってきた値を処理するメソッド
private function onComplete(e:Event):void {
//サーバから帰ってきたHTMLをXMLとして処理する
var loader:URLLoader = e.currentTarget as URLLoader;
var xmlData:XML = XML(loader.data);

//xmlDataに値が入ってる
//ここで各コンポーネントに値を設定したりなどの処理を行う
}

//String firstNmae = (String)request.getParameter("FirstName");
//のようにJSPのFormから値を送った時と同じ方法で取得



次にAS2.0バージョン

//結果を受け取るXML変数
var resultXML:XML = new XML();

//アクセス先
var url:String = "http://neetomo.dip.jp/";

//リクエストを送る変数
var lv:LoadVars = new LoadVars();

//リクエストのパラメータに設定する値
lv.FirstName = "流離の";
lv.LastName = "苦情人";

//リクエストを送信
//第一引数 -> アクセス先のURL
//第二引数 -> 結果を入れる変数(レスポンスとして帰ってきたHTMLをXMLとして処理する)
lv.sendAndLoad(url, resultXML, "POST");

//レスポンスが帰ってきたときに処理される関数
resultXML.onLoad = function (success) {
//resultXMLにxmlのデータが入っているのでthisを使って取得
//ここで各コンポーネントに値を設定したりなどの処理を行う
}



なお, 今回はレスポンスとして取得したXMLの処理方法については触れていないが
通常のflashでそれを扱うのとやり方は一緒なので割愛させてもらう.

twitter無能

少し前に思いついたこと
暇なときがあればやりたい
え?まだ作ってないのにこんなところに書くと誰かが先に作ってしまうかもって?
それはそれでいいんじゃない?誰かが実装したくなるほどのアイデアを出せたんならそれだけでも満足だよ
そもそもおいらが思いつくようなレベルのことなので誰かが既にやってると思う


twitterを利用した人工無能
以下のことを行う
・人口無能と会話したい人がtwitterのアカウントでログインする
・ログインした人のタイムライン上のtweetを取得(フォローしてる人のtweetがとってこれる)
・RT, @hoge, http://hoge.hogeなどを除去
・頻出する部分文字列を取得
・それらをキーワードとしてどれかのtweetを元に応答文を生成


大体こんな感じ


利点
・頻出の部分の字列を取得するので非言語依存かつ, 砕けた表現にも対応可
・ユーザがフォローしている人の最近のtweetが元になるのでタイムリーかつ興味のある内容を持ってこれる


問題点
・品詞情報がないのでストップワードの除去やステミングが難しい
・応答文生成が難しそう
→抜き出したキーワードが名詞などの応答文の一部として有効に使えるものかがわからない
→品詞に基づく規則性を求めることができない, 単一ユーザのタイムラインから得られる情報だけでは規則性を見出しづらい(これは推測)などマルコフ連鎖をしづらそうな環境がそろってる


大体こんな感じかな

いかにしてプログラムを書かないようにするか

プログラマにとってとっても大切なこと
理由は至って簡単で、プログラムは書くからバグがでるのであって書かなければバグは出ないから


え〜と、では具体的にどういうことかというと
・すでにあるものは使う
・同じことをなんども書かない(含コピペ)
・余計なコメントは書かない
まぁ、大体こんな感じか


どういうことかって言うと


・すでにあるものは使う
どこかの誰かさんが作って公開してくれているプログラムはインターネットの世界に旅立てばたくさん見つかるようになったし、組織内でもそこでつかってるライブラリとかがあると思う
そういうのはすでにいろんな人が使っていていろんな環境でうまく動いていることが既に確認されているもの
しかもバグがあったとしても、いろんな人が使っているので発見されやすい
使う側は修正されたものに置き換えるだけという手軽さ


・同じことをなんども書かない(含コピペ)
プログラムを書いていて関数(メソッド)って言葉を知らない人はいないと思う
まとめておけば同じことを何度も書く必要がなくなるし何かあってもそこだけ直せばいい


・余計なコメントは書かない
どうでもいいコメントは書くだけ時間の無駄
しかも書いた人が時間を無駄にするだけならいいが、読む人にとっても流れを追う邪魔をされるし、何らかの理由でソースを修正したが対応するコメントが修正されていないなんてことになったらもう大変だ
そもそも、コメントを書くという行為自体がソースと同じことを二度書いていることに他ならない(同じことをプログラミング言語 + 自然言語で書いている)
自然言語に翻訳できないようなプログラムを書いていてそれの説明を書く時間があるのであれば、読めるプログラムを書くのに時間をかけるほうがよっぽど有意義である


大体こんな感じ
プログラムを書かない努力をするってことは決して手抜きをするってことではないのであしからず