Hatena::ブログ(Diary)

かけるの wilod aderl

2011-09-06

お題:FizzBuzz(Nパターン) を Scala で解いてみた

お題:FizzBuzz(Nパターン)より。


1から100までの数をプリントするプログラムを書け。

ただし、[3, "Fizz", 5, "Buzz", 7, "Hoge"] のような

“<数値>と<文字列>”が対となった、要素が偶数個のリストを受け取り、

数が<数値>の倍数のときは、対となる<文字列>をプリントすること。

数が複数の<数値>の倍数となっている場合、リストに指定された順で、<文字列>を結合しプリントすること。

数がすべての<数値>の倍数でない場合、数をプリントすること。


FizzBuzz はよくある問題。

それの応用問題といったところ。

勉強中の Scala を使って解いてみました。

解けてはいるんだけども、関数型っぽいかどうかと言われるとよくわからない。

以下解答(関数部分、コメントとかは略)

def fizbuzN(lst: List[Tuple2[Int, String]]): Unit = {
  Range(1, 100).toList.foreach(
	i => 
	  if (lst.forall(i%_._1!=0)) {
		println(i)
	  } else {
		lst.foreach(a => if (i%a._1 == 0) print(a._2))
		println
	  }
  )
}

もうちょい上手く書けそうなんだけどだめだったorz

2011-06-12

コラッツ予想とか

3n+1の問題とか、コラッツの問題とか、角谷の問題と呼ばれている、数学の未解決問題。

どんなのかと言うと、

自然数nを選び,

 [1] 奇数ならば,3倍して1をたす。

 [2] 偶数ならば,2で割る。

これを繰り返すと,どんなnを選んでも,いつかは,1になる」

っていう問題。

フェルマーの定理もそうだけど、問題文がシンプルなほど難しかったりする。


例えば9であれば

9→28→14→7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1

となって最後は1になる。

30くらいまでは暗算でも簡単に1になることがわかる(27を暗算でやったら凄いです)


解決したとかTwitterに流れてたけど、ソースの論文が英語だったので諦めた。


400兆まで頑張った記録があるらしいけど、そこまでしなくてもって感じがするのでちょっと考えてみる。




とっかかりが難しいので、1から順に考えてみる。

ただし、2のべき乗は明らかに1になるので略。

1⇒自明

2⇒自明

3→10→5→16→略

4⇒自明

5→16→略

6→3→上参照

7→22→11→34→17→52→26→13→40→20→10→5→上参照

8⇒自明

9⇒例参照

10→5→上参照

このようにすれば、偶数であれば、以前に計算したものに辿り着くので、奇数だけ考える。

奇数はまず、3n+1とすると偶数になり、2で割ることになるため、(3n+1)/2と省略できる。

ここで、もし(3n+1)/2が偶数ならば、(3n+1)/4となり(3n+1)/4 < nであるからすでに計算済みである。

奇数ならば、(3n+1)^2/4とよくわからない値になる。これが偶数だとしても元の数より大きいのでまだ続く。

まぁ、それをいつまでも繰り返して、元の数より小さくならなければ、それがコラッツ予想の反例となるわけ。

さて、そんな数があるのかどうか。

困ったときの背理法ということで、「コラッツ予想を満たさない開始数の奇数cがある」とする。

cを問題に従い計算していっても、cを下回ることはない。(理由は上)

しかし、2cは次にcになる。つまりcは開始数ではないので矛盾。


つまり、計算していき無限に増え続ける数はないと。


問題は、ループにはいるパターンである。

1→4→2→1はループになっているが、1があるおかげで、ループを脱出できる。

1がなければ無限ループである!

つまり「開始数cより小さくなることなく、cに戻る数」が反例となる。

ここからはもうわからないからプログラムを書こうと思う。とりあえず方程式っぽいものをメモ程度に残しておくことにしよう。

c = ((3c+1)/2)^n / 2^m

ただし、3^n > 2^(n+m), n > 3(n = 2, m = 0は1を含むループ)


ところでTwitterにあったあの論文は本当なのだろうか…http://twitter.com/alexbellos/status/76055483768766464

2011-02-26

Facebook の実名主義に関して

HN で Facebook やってる人たちが突然アカウントを削除された、という話が散乱していたので流行に乗って(ぇ


Facebook は、元々大学の中での SNS だったわけだから実名主義でも全く問題はなかったはず。アメリカでも、憲法の第一条に言論の自由が認められているくらいだし、何を言っても・・・という感じがする。アメリカの事情はあまり詳しくないけれど、他の SNS でも実名主義が基本なんじゃないかな。

ソーシャル・ネットワーク」ではその辺りは触れているのだろうか?


問題は日本に来てからだろう。というか、他の国のことは分からない。

日本の SNS は基本が匿名主義。 ミクシイとかいう(笑)な SNS は最初実名主義だったとかなんとか。知りませんけど。

なんで日本は匿名主義なのか、kakeru_13493 とかね。

そこで出てくるのが2ちゃんねるという恐ろしき掲示板。2ちゃんねるの住人たちの特定能力はまったく計り知れないものがある。

うっかりレイプはされるほうが悪いなんてことを言ってしまえば、発言者の本名(匿名であっても)・履歴経歴・過去の発言なんてあっさり割り出されてしまう。

また、自分の趣味とかが知られたくないという人もいる。実名で書いたものが知り合いに知られて引かれるなんてことも。変な(持ってるだけで立派だが)趣味は知り合いに知られず同じ趣味を持ってる人たちで楽しみたい、ということで。


あれ?日本は言論の自由はないんだっけか。

アメリカはきっと、日本では変な趣味と思われるものも、受け入れてもらえるんだろう。そういうところで米日の差が出てるんじゃないかな。


まぁどちらが良いとか悪いの話じゃない。実名主義Facebook のルールなので、「郷に入っては郷に従え」ということです。

実名が嫌ならば Facebook を使わなければいい、それだけの話なのだから。

かけるも Facebook は実名登録ですよ。Twitter などなどが HN なのは「When in Rome do as the Romans do」ということです。

2011-02-22

Scala はじめました。

今回はプログラミングのお話。ってタグ見りゃわかる。

興味ない人さよなら(笑)




タイトルの通りですが、Scala を勉強し始めましたよ。

Scala関数型のオブジェクト指向言語で、Java を改良したような言語。

というよりは Java の上位言語(互換性はないけど)と言ったほうが正しいかもしれない。JavaライブラリScala でほとんどが使える。


じゃあ何故 Scala なのか。

1つ目は、関数型言語を学びたかったから。

関数型言語の有名どころは Scala の他に Lisp, Erlang, Haskell なんかがある。関数型言語もそれぞれ細かく分類されるらしいけど違いがよくわかってない。一応、Prolog っていうのは見たことがある(あの講義では学んだとは言うまい)。


2つ目は、流行に乗るため。

最近 Scala は結構熱かったりする。関数型言語+並列処理+速度あたりだろうか。

TwitterRuby on Rails で構築されたそのインフラを徐々に Scala に置き換えているそうだ。

らしいし。


3つ目は、趣味と仕事。

かけるの得意言語は Ruby で、なんとなーく C とか扱える程度。

4月から会社できっと C++Java あたりが必要になる。

個人的には、Scala = 2*Java + Ruby くらいの言語だと思ってて、Scalaググると、「Java プログラマのための Scala」とか「Ruby プログラマのためのScala」なんて結構出てくる。

まぁ、Java ライブラリ使えて、記法Ruby に結構似てるからだいたい合ってるだろう。



そんなこんなで Scala の勉強を始めたわけです。わからない事だらけなので本読みながらググりながら。

4月までにそれなりのもの作れればいいなぁ、と思う。

なんもアイディアないけど。

2011-02-10

会社からの課題

内定先の会社から、いよいよ四月からの予定なんかも入ってきて気持ちも盛り上がってくる今日この頃。

働きたいでござる!働きたいでござる!

これが否定形になるのはいつかと思いながら。


どこでもあるだろうが、うちにも内定者の課題というものがある。当初は、情報系や簿記の勉強だったようだけれど、出された課題は「最新技術について、知識と応用」だった。

ここに会社からの愛を感じる。内定者が二人だけで、なおかつよく似た二人だからこそ今のうちに文章力をということだろう。よくわかってらっしゃる(笑)


内容に触れたりはしないけれど、課題を提出。

フィードバックを読ませてもらう。

研究の片手間仕事となってしまったし、穴だらけなのは承知の上だったが、そこらへんを綺麗に指摘してもらった。ありがたい。

しかし、一枚程度にまとめろというのはさすがに無理。先に気づいて(笑)


というわけで、内容を充実させて再提出ということに。ネタ切れの可能性があるから別のテーマでやりたかったのだが、同じ技術でやってくれとのこと。

うーむ。

この辺の感覚は内定者同士では合ってるようで、まだまだ会社に染まってないということだろうか。しかし、内定者同士では気が合うことが多い。少なくとも研修では一緒に行動することが多いだろうから助かる。


出されてる課題だけじゃなくて、個人的にも勉強はしてるけども、次はそこまで言われないように提出したいものだ。

さて、何枚書こうかな。5枚くらいかな。