GO FOR IT(2)実数の階乗

php

昨日に引き続き、GO FOR ITをやってみます。

問題

ある検索サイトに5!と入力するとその計算結果である120が表示されます。
その検索サイトに2.5!と入力するとなんと3.32335097と表示されます。
さらにその検索サイトに(-1.9)!と入力すると-10.5705641と表示されます。
きっとそれらの仕組みはとても難しくて企業秘密に違いないので是非ともこれらを実行するプログラムを作ってほしい。
ただし、君のPCは古いのでネットワークや便利で高度な数学関数は入っていません。
入っている数学関数はsin,cos,tan,log,pow,floorなどの初歩的な関数のみです、残念ながら。

i)入力された整数a(0<=a<=10)の階乗を求めるプログラムを作ってください。
ii)入力された実数a(0<=a<=10)の階乗を求めるプログラムを作ってください。
iii)入力された実数a(-1.9<=a<=-1.1)の階乗を求めるプログラムを作ってください。

i)は何度もやってるので省略します。
ii)は0以上である実数の階乗を求めるプログラムをつくれと言っています。

実数の階乗なんて初めて聞いたので色々と調べてみるとどうやらガンマ関数を使えばいいことがわかります。
ガンマ関数 - Wikipedia

しかし、問題の制約として簡単な関数のみ使用可能というのがあるので、積分計算をすることはできません。
ならば、近似するしかないなーということで、ガンマ関数についてもっとよく調べてみると、スターリングの近似というのがあるではありませんか。
スターリングの近似 - Wikipedia

近似の仕方がたくさん載っていますが、その中の「計算機向けの変形」という項目が使えそう。
特にGerg Nemes が2007年に提案した近似式が、簡単な関数のみで実装できそうです。
式はこちら。

あんなに難しそうな式をこんな単純にできるなんて数学出来る人はすごいですね。

0以上の実数の階乗を求めるプログラム

<?php
function compute($z){
	$z = $z + 1;
	$a = sqrt(2*pi()/$z);
	$b = 1/exp(1);
	$c = $z + 1/(12*$z-1/(10*$z));
	$d = pow($b*$c,$z);
	return $a * $d;
}

引数を2.5としたときの実行結果

3.3233471127805

答えが「3.32335097」なので精度は十分高いといってよいのではないでしょうか。

問題なのはiii)

問題なのは正ではなく負の階乗を求めるときです。
先にあげた近似式では、平方根の中にzがあるので、zが負になると根号の中身が負になってしまい、平方根の定義を満たせなくなってしまうのです。
平方根の中身が正になるように-1をかけてあげても正しい結果が得られませんでした。
一体どうすれば…？

追記

スターリングの近似は精度があまりよくないらしいです。。。

参考
SONY GOF FOR IT ~2問目: 実数の階乗~

追記2

ようへいくんのアイディアのおかげで出来ました。負の場合はΓ(z)=Γ(z+1)/zの性質を使って非負にしてあげればよかったんですね。

※なぜかzが1未満のときにスターリングの近似を行うと正しい値を返してくれなかったので、ここでは負の場合ではなく、1未満の場合にΓ(z)=Γ(z+1)/zを使って1以上になるまで変形するようにました。

iii)のプログラム

<?php
function gammaFunc($z){
	$a = sqrt(2*pi() / $z);
	$b = 1 / exp(1);
	$c = $z + 1 / (12*$z-1 / (10*$z));
	$d = pow($b*$c,$z);
	return $a * $d;
}

function compute($z){
	$result = 1;
	$z = $z + 1;
	while($z < 1){
		$z++;
		$result = $result * 1 / ($z-1);
	}
	return $result * gammaFunc($z);
}
echo compute(-1.9);

実行結果

−10.567934926951

正解は-10.5705641なので、やはり精度はあまりよくないみたいです。

GO FOR IT(1)人生の時計

php

Sonyのソフトウェアスペシャリスト認定コンテストの問題をやってみました。
5問あるのですが今日やったのは１番目の「人生の時計」という問題。
問題は以下になります。

ちょっとわかりにくいのですが、問題の「n歳まで生きる(n歳のときは生きていてn+1歳にはなれない)」は81歳になるギリギリ直前まで生きているということだと思います。


はじめは日付の計算も自分でやろうと思っていたのですが、月によって最大日数が変わるし、閏年もあるやらで超面倒だったので用意されている関数を使いました。
ただし、phpのタイムスタンプの有効範囲は、32ビット環境の場合1901年〜2038年までです。64ビットだと無制限で使えるみたいです。
僕の環境は32ビットなので上記の問題をやろうとするとできなくなります。
ですのでここでは、誕生日を僕の誕生日(1987年5月26日)にして、寿命を40年として解きました。

アルゴリズム

"産まれてから死ぬまでの日数"、"産まれてから今日までの日数"を出す
↓
前者を分母、後者を分子にとり、比を算出する
↓
一生を24時間にたとえたとき、比が1のときの時刻は24時0分0秒。比が0.5のときの時刻は12時0分0秒になるので、比を基準に考えた時、１時間=1/24、1分=1/24*60、1秒=1/24*60*60になることがわかる。
なので、先程求めた比の中に1時間が何個あるか、比からその差をとったものの中に1分が何個あるか、さらにその差をとったものの中に1秒が何個あるのか求めれば一生を24時間にたとえたときの時刻がでる。

プログラム

<?php
$birth_year = 1987;
$birth_month = 5;
$birth_day = 26;

$death_year = $birth_year + 40;
$death_month = $birth_month;
$death_day = $birth_day;

$birthdate = $birth_year."-".$birth_month."-".$birth_day; 
$deathdate = $death_year."-".$death_month."-".$death_day; 
$todaydate = strftime("%Y-%m-%d"); 

//産まれてから死ぬまでの日数
$from_birth_to_death = (strtotime($deathdate)-strtotime($birthdate))/(3600*24);
//産まれてから今日までの日数
$from_birth_to_today = (strtotime($todaydate)-strtotime($birthdate))/(3600*24);

//産まれてから死ぬまでの日数と産まれてから今日までの日数の比
$fraction = $from_birth_to_today/$from_birth_to_death;

// 1/24=1時間
$life_hour = floor($fraction/(1/24));
// 1/24*60=1分
$life_minute = floor(($fraction - $life_hour*(1/24))/(1/(24*60))); 
// 1/24*60*60=1秒
$life_second = floor(($fraction - $life_hour*(1/24)-$life_minute*(1/(24*60)))/(1/(24*60*60)));
print $life_hour."時".$life_minute."分".$life_second."秒"

結果

14時49分19秒

感想

15時前っておい。後悔のないよう生きようと思いました。

追記

id:Kshi_Kshiのようにクラス作ったほうが使いまわししやすいですね。また明日やってみようと思います。(サラっとクラス書けるようになりたいものです)

プログラム修正ver

<?php
date_default_timezone_set('Asia/Tokyo');
class TimeSet{
	public $year;
	public $month;
	public $day;

	public function __construct($year,$month,$day){
		$this->year = $year;
		$this->month = $month;
	        $this->day = $day;	
	}

	public function getDate(){
		return $this->year."-".$this->month."-".$this->day;
	}
}
	$n = 40;
	$birthdateObj = new Timeset(1987,5,26);
	$deathdateObj = new Timeset(1987+$n,5,26);
	$birthdate = $birthdateObj->getDate();
	$deathdate = $deathdateObj->getDate();
	$todaydate = strftime("%Y-%m-%d"); 

	//産まれてから死ぬまでの日数
	$from_birth_to_death = (strtotime($deathdate)-strtotime($birthdate))/(3600*24);
	//産まれてから今日までの日数
	$from_birth_to_today = (strtotime($todaydate)-strtotime($birthdate))/(3600*24);

	//産まれてから死ぬまでの日数と産まれてから今日までの日数の比
	$fraction = $from_birth_to_today/$from_birth_to_death;

	// 1/24=1時間
	$life_hour = floor($fraction/(1/24));
	// 1/24*60=1分
	$life_minute = floor(($fraction - $life_hour*(1/24))/(1/(24*60))); 
	// 1/24*60*60=1秒
	$life_second = floor(($fraction - $life_hour*(1/24)-$life_minute*(1/(24*60)))/(1/(24*60*60)));
	print $life_hour."時".$life_minute."分".$life_second."秒";

はてなブログはじめました

知ってる人も知らない人もこんにちは。しぶてぃーといいます。
趣味でプログラミングをしておりまして、簡単なWebサービスをいくつか作ったりしています。



さて、招待制のはてなブログですが、id：Kshi_Kshiが僕を招待してくれたのでとりあえずはじめてみました。Kshi_Kshi君ありがとう。



…しかしはじめてみたはいいものの、何を書けばいいのだろう。もともとはてなダイアリーでshibu_t最強伝説というショボイ上にあまり更新されないエンジニアブログを書いているわけですが、使いやすさははてなブログの方がよさそうなんですよね。なのでこちらをメインにしようかなーとも思ったんですけど、まだシンタックス記法が使えないらしいので移行はちょっと様子を見てからにしましょうか。



じゃあなおさらこっちに何を書くか迷うわけですが、僕はネット経由でニュースを見るのが好きでTech Crunchやはてぶなどを読んでいるのでその中からピックアップした記事や僕の意見などをこっちに載せたらいいのではなかろうか。よしそうしよう。

うーん、なんか早くも放置される匂いがプンプンしますが、この方向で行きたいと思います！

ではでは、これからよろしくお願いします。

初めてのスクレイピング

php

現在、友人とWebサービスを作る計画があり、そのサイトを作るためにスクレイピングが必要だったのでちょっと勉強してみました。

※追記
DOMツリー生成は時間がかかるのでネストが深くない場合は正規表現がオススメです

スクレイピングとは？

はてなキーワードによると「ウェブサイトのデータを必要な部分だけ抽出して利用すること」だそうです。
あるウェブサイトのデータをとってきたいときにそのサイトのAPIが提供されていればそのAPIを使用すればいいわけですが、提供されていない場合は、スクレイピングをする必要があるわけです。

例えば、WikipediaはAPIが提供されていないので必要なデータをとってきたいときにとってこれません。スクレイピングすればとってくることができます。
※Wikipediaはidをあまり指定しないサイト構成をとっているのでスクレイピングでデータをとってはこれるのですが、かなり面倒くさいです。

方法

たくさん方法があり、ライブラリも多く提供されていますが私は「PHP Simple HTML DOM Parser」を使いました。

実践

では実際にやってみましょう。
下記のサイトを参考にしました。
ITキヲスク | htmlSQLよりアツい!?jQueryみたいにセレクタでHTMLをparse(解析)する「PHP Simple HTML DOM Parser」

まずPHP Simple HTML DOM Parserダウンロードですが、PHP Simple HTML DOM ParserのDownload latest version form Sourceforge.　のリンク先にある緑色のボタンを押せばダウンロードできます。
使用するのは、「simple_html_dom.php」だけなのでこれを適当な場所に置いて使用します。

今回は中日ドラゴンズの投手陣たちの写真をとってきたいと思います。
中日ドラゴンズ 公式サイト - 選手名鑑

サイトの構成は以下のなっています。

写真はidがpitcherであるdivタグの子要素にある、classがplayer-photoであるdivタグ内のimgタグで管理されています。
このセレクタをfindファンクションの引数に記入してあげるとその情報がとってこれます。

今回はsrc属性が相対パスになっていたのでsrc属性だけを引っこ抜いてこちらで絶対パスになるように編集しています。

もしsrc属性だけではなくimgタグ全体をとってきたい場合は

$e->outertext;

としてください。
詳しくはこちらに載っています。PHP Simple HTML DOM Parserマニュアル

プログラム

<?php
include('./simple_html_dom.php');
$url="http://dragons.jp/teamdata/players";
$html = file_get_contents($url);
$htmlEnco = mb_convert_encoding($html, "UTF-8", "auto");
$htmlDom = str_get_html($htmlEnco);
foreach($htmlDom->find('#pitcher .player-photo img') as $e){
	echo "<img src=\"";
	echo "http://dragons.jp";
	echo $e->src;
	echo "\" width=\"85\" height=\"94\">";
}
?>

結果

実行するとこうなります

最後に

今回はノーマルなサイトを取り上げましたが、mixiやFacebookなどのログインしないとみれないサイトのデータをとってきたい場合はHTTP Clientを使えばスクレイピングできます。これを使えばあなたの気になっている子の画像データをFacebookからしこたま落とすことができるのです。素晴らしい…！←
また、通信方式がSSL(https)方式の場合はHTTP Classを使用すればできるみたいです。SSLの場合はまだ自分もやったことがないのでできたらUPしようと思います。

重複なしの乱数生成

javascript

夏のインターンで必要になり作ったやつです．ファイル整理してたらでてきたのでメモがわりにうｐ．
0〜num-1までの整数を重複なしにnum個生成するプログラムです．
値は配列に格納されます．

プログラム

//重複なしに乱数を発生させるプログラム
function random_num(num){
	//乱数の配列生成
        var random = new Array();
	for (i = 1; i < num; i++) {
	  random[i]=Math.floor(Math.random()*num);
	}
	var j;
	random[0]=Math.floor(Math.random()*num);

　　　　//配列内に重複してるものがあるか探査．あったら重複しなくなるまで乱数発生
	for (i = 1; i < num; i++) {
	  j = 0;
	  while(j<i){
	    while(random[i] == random[j]){
	      random[i]=Math.floor(Math.random()*num);
	      j=0;
	    }
	    j++;
	  }
	}

	return random;
}

部分集合を求めるプログラム

php

説明

授業の課題で部分集合を求めるプログラムを書いたので晒してみる。
{a,b,c}の部分集合は{},{a},{b},{c},{ab},{ac},{bc},{abc}の８つ。これを求めるプログラムを書きました。

他にもやり方があるのかもしれませんがここでは２進数のビット列に文字が対応することを利用します。
以下の表をみればやり方を理解してもらえると思います。

10進数 2 進 数 部分集合
c b a
0 0 0 0 φ
1 0 0 1 a
2 0 1 0 b
3 0 1 1 ab
4 1 0 0 c
5 1 0 1 ac
6 1 1 0 bc
7 1 1 1 abc

つまり部分集合の個数は、２の{文字の数}乗通り(上記の例では２の３乗＝８通り)あることになります。
以下のプログラムでは文字が3個以下の場合しか対応していません。4個以上に対応させるためにはifを増やす必要があります。
全然スマートじゃないのでもっとスマートなやり方知りたい…

プログラム

<?php

$data = array();
$str = array();
//部分集合を列挙したい文字列の長さ
$n=3;
//0〜$nまでの整数を２進数に置き換え、配列に格納する
for($i=0;$i<pow(2,$n);$i++){
array_push($data,decbin($i));
}

for($i=0;$i<pow(2,$n);$i++){
	//1桁目が1のとき
	if(substr($data[$i],strlen($data[$i])-1,1)=="1"){
		//nullじゃないなら文字列連結
		if(isset($str[$i])){
			$str[$i].="a";
		//$str[$i]がnullなら
		}else{
			$str[$i]="a";
		}
	}
	//桁数が2ケタ以上のとき
	if(strlen($data[$i])>1){
		//2桁目が1のとき
		if(substr($data[$i],strlen($data[$i])-2,1)=="1"){
			//nullじゃないなら文字列連結
			if(isset($str[$i])){
				$str[$i]=$str[$i]."b";
			//$str[$i]がnullなら
			}else{
				$str[$i]="b";
			}
		}
	}
	//桁数が3ケタ以上のとき
	if(strlen($data[$i])>2){
		//3桁目が1のとき
		if(substr($data[$i],strlen($data[$i])-3,1)=="1"){
			//nullじゃないなら文字列連結
			if(isset($str[$i])){
				$str[$i]=$str[$i]."c";
			//$str[$i]がnullならそのまま格納
			}else{
				$str[$i]="c";
			}
		}
	}
}
if(!isset($str[0])){
	$str[0]="φ";
}

print_r($str);
?>

追記

id=Kshi_Kshiが僕が書いたのよりも、もっとスマートなスクリプトをpythonで書いてくれたので僕もphpで書き直してみました。Kshi_Kshi君ありがとう。

彼の書いたスクリプトはこちらからご覧になれます。
部分集合を求めるスクリプト

僕が前に書いたスクリプトはfor文１つで部分集合を求めていたわけですが、それをやめてfor文の入れ子構造にして自動化しちゃえばいいよねって話。今考えるとなんであんな面倒くさいやり方したんだ俺ｗ

プログラム

<?php
$dec = array();
$result = array();
$input=array("a","b","c");
//部分集合を列挙したい文字列の長さ
$n=count($input);

//0〜$nまでの整数を２進数に置き換え、配列に格納する
for($i=0;$i<pow(2,$n);$i++){
array_push($dec,decbin($i));
}

//上記で生成した2進数を１つずつチェック
for($i=0;$i<pow(2,$n);$i++){
	//上記でチェックした2進数の１桁１桁をチェック
	for($j=0;$j<strlen($dec[$i]);$j++){
		//もし１ならその桁数目の文字を結合する
		if(substr($dec[$i],strlen($dec[$i])-1-$j,1)=="1"){
			$result[$i] = $result[$i].$input[$j];
		}
	}
	//空集合チェック
	if(!isset($result[$i])){
	$result[$i]="φ";
	}
}

print_r($result);
?>

JSONPを用いてYouTube APIを使用する

php jsonp javascript

説明

ここではあるキーワードで検索したときの、YouTubeの検索結果を表示するプログラムを作ってみます。

JSONPを使ったYouTube APIの使い方については上を、JSONPについては下のサイトを参考にしました。
Developer's Guide: JSON-C / JavaScript
JSONPを使ってJavaScriptだけでマッシュアップ

今回のJSONPを使うためのプログラムの流れは以下の通りです。

showResult関数を実行

↓

渡すURLを生成

↓

そのURLを引数にしてcallJSONP関数を実行(ここまでをshowResult関数で行なっている)

↓

callJSONP関数が実行され、
scriptタグが生成される
srcには先程のURLが指定されている
（通常jsではクロスドメインアクセスができないのだが、scriptタグを用いると，ドメインの異なるサーバに置いているスクリプトファイルを読み込むことができる。このscriptタグを用いてデータを取得する方法をJSONPという）

↓

その生成したscriptタグが読み込まれるとコールバック関数であるshowMyVideos2関数が実行され、動画プレイヤーがphpファイルのobjectタグに、サムネが指定したdivタグに埋め込まれる。
（jsの部分はDeveloper's Guide: JSON / JavaScriptの下にあるYouTube JSON codelabを参考にしました）

結果はこんな感じです。中日ドラゴンズをクエリとしたときの検索結果を表示しています。サムネイルをクリックするとobjectタグに埋め込まれている動画がクリックされた動画に切り替わります。


結果


ソースコード

test.php

<html>
<head>
	<script type="text/javascript" src="http://swfobject.googlecode.com/svn/trunk/swfobject/swfobject.js"></script>
	<script language="JavaScript" src="./js/showResult.js"></script>
	<link rel="stylesheet" type="text/css" href="./css/main.css" />
</head>
<body>
<form action="<?php echo $_SERVER["PHP_SELF"]; ?>" method="get">
<input type="text" value="" name ="formquery" size=40>
<input type="submit" name="submit">
</form>
	
<?php
	
	//GETされたとき
	if($_SERVER["REQUEST_METHOD"]=="GET"){
		//登録ボタンが押されたとき
		if(isset($_GET["submit"])){
			$getflag="1";
			$phpquery=$_GET["formquery"];
		}	
	}
	if($getflag=="1"){
		echo $a;
	}

?>

<script type="text/javascript">
	//送信された内容を表示
	var getflag = "<?php echo $getflag;?>";
	if(getflag=="1"){
		var jsquery="<?php echo $phpquery;?>";
		jsquery=
		showResult(jsquery);
	}
</script>

<div id="playerContainer" style="width: 20em; height: 180px; float: left;">
	<object id="player"></object>
</div>

<div id="videos2"></div>
</body>
</html>

showResult.js

function showResult(query){
	var enco_query = encodeURI(query);  
	var url = "http://gdata.youtube.com/feeds/api/videos?q=" + enco_query + "&alt=json-in-script&callback=showMyVideos2&max-results=30&format=5";  
  	callJSONP( url );
}

//JSONPを実行する関数  
function callJSONP(url) {  
  var target = document.createElement('script');  
  target.charset = 'utf-8';  
  target.src = url;  
  document.body.appendChild(target);
}  

function loadVideo(playerUrl, autoplay) {
  swfobject.embedSWF(
      playerUrl + '&rel=1&border=0&fs=1&autoplay=' + 
      (autoplay?1:0), 'player', '480', '400', '9.0.0', false, 
      false, {allowfullscreen: 'true'});
}

function showMyVideos2(data) {
  var feed = data.feed;
  var entries = feed.entry || [];
  var html = ['<ul class="videos">'];
  for (var i = 0; i < entries.length; i++) {
    var entry = entries[i];
    var title = entry.title.$t.substr(0, 20);
    var thumbnailUrl = entries[i].media$group.media$thumbnail[0].url;
    var playerUrl = entries[i].media$group.media$content[0].url;
    html.push('<li onclick="loadVideo(\'', playerUrl, '\', true)">',
              '<span class="titlec">', title, '...</span><br /><img src="', 
              thumbnailUrl, '" width="130" height="97"/>', '</span></li>');
  }
  html.push('</ul><br style="clear: left;"/>');
  document.getElementById('videos2').innerHTML = html.join('');
  if (entries.length > 0) {
    loadVideo(entries[0].media$group.media$content[0].url, false);
  }
}

main.css


#playerContainer{
	position:absolute;
	top:40px;
}


.titlec {
  font-size: small;
}

ul.videos li {
  float: leftt;
  width: 10em;
  margin-bottom: 1em;
}

ul.videos
{
  position: absolute;  
    top: 430;
  margin-bottom: 1em;
  padding-left : 0em;
  margin-left: 0em;
  list-style: none;
}