hossy online - といぼっくす

_ [プログラミング] 同じ問題を色々なプログラミング言語で解いてみた 弐

前回で一段落で、今回はあとがきのはずだったのですが、色々あってもう少し続けてみます。

Ruby / (40! / (20! * 20!))

階乗な方法、このように書き換えることができました。

• 40! / (20!*20!)
• (40!/20!) / 20!
• (40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*21)/20!
• (40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*21) / (20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1)
• 40/1*39/2*38/3*37/4*36/5*35/6*34/7*33/8*32/9*31/10*30/11*29/12*28/13*27/14*26/15*25/16*24/17*23/18*22/19*21/20

こうすると、どの時点でも整数ですし、途中の値が一番大きくなるのが最後 20 で割る直前ですから double 型で十分扱える精度。無限精度の整数なんて不要で、多分どの言語でも大丈夫でした。あああ。

これをコードに直すと、

p (1..20).inject(1){|r,x|r*(41-x)/x}

36文字。前のエントリは何だったのでしょう(-・;

C++ / (40! / (20! * 20!))

同じ方針で、2パターン + 比較対象にそのまま答えを書いたもの。

// A: 答えをそのまま書いた
#include "stdafx.h"
#include 
 
int _tmain(int argc, _TCHAR* argv[])
{
  std::cout << 137846528820;
  return 0;
}

// B: 計算。#include は省略
int _tmain(int argc, _TCHAR* argv[])
{
  std::cout << 40LL/1*39/2*38/3*37/4*36/5*35/6*34/7*33/8*32/9*31/10
      *30/11*29/12*28/13*27/14*26/15*25/16*24/17*23/18*22/19*21/20;
  return 0;
}

// C: メタ関数。#include は省略
template <int N, int K>
struct Func
{
  static const long long value = Func<N, K-1>::value * (2*N-K+1) / K;
};
 
template <int N>
struct Func<N, 0>
{
  static const long long value = 1;
};
 
int _tmain(int argc, _TCHAR* argv[])
{
  std::cout << Func<20, 20>::value;
  return 0;
}

最後のは関数呼び出しをしているようにコード中からは見えるのですが、この関数の計算は実行時でなくてコンパイル時に行っているようで。3通り全て、Visual C++ 2010 の混合モードで見てみると、以下のように "0x20 * 2**32 + 0x184B1B34 = 137846528820" と、出力したい値がそのまま書かれていました。

  std::cout << Func<20, 20>::value;
00A5139E  mov         esi,esp  
00A513A0  push        20h  
00A513A2  push        184B1B34h  

...コンパイラ、頑張り過ぎではないでしょうか(-・;

Haskell / (40! / (20! * 20!))

pi8027さん から前のエントリにツッコミを頂きました。ありがとうございます。

func :: Integer -> Integer
func n = factorial(n*2) `div` (factorial(n) * factorial(n)) where
  factorial :: Integer -> Integer
  factorial 1 = 1
  factorial n = n * factorial(n-1)
 
func 20

この where 以下の階乗計算は、"fractional n = product [1..n]" で置き換えられるそうです。ああ（汗）。というわけでこう短くなります。

func n = factorial(n*2) `div` (factorial(n) * factorial(n)) where
  factorial n = product [1..n]

ついでに、C++の最後の例の方法をそのまま書き換えたものも。

main = print $ func 20 20 where
  func n 0 = 1
  func n k = func n (k-1) * (2*n-k+1) `div` k

Haskell / 数え上げ

同じくpi8027さんから頂いたコメントより。

main = print $ l!!20!!20
l = repeat 1:map (snd.mapAccumL (\a b -> (a+b,a+b)) 0) l

main = print $ iterate (scanl1 (+)) (repeat 1)!!20!!20

...ええと、最初にこれを見たときに、何が起こっているのかさっぱり分からずに、リファレンス検索ツール [href] を使って一つ一つ読んでいきました。ここでは下側の方だけを。以下、これがすらすら読める方には読み飛ばしてください。

まず、関数の区切り方を変えます。

main = print((iterate (scanl1 (+)) (repeat 1))!!20!!20)

!! は配列の要素を返すもので、他の言語では [] や () になる事が多いです。print はそのまま表示するで、結局、

(iterate (scanl1 (+)) (repeat 1)) で得られる二次元配列の [20, 20] 番目を表示する

という事を表しています。

次、(repeat 1)。これは、1 が無限の続く配列。[1, 1, 1, 1, ...]。無限と言っても、最後に [20, 20] 番目が欲しいとなると、その計算に必要な所まで無駄なく調べるそうです。

その次、(scanl1 (+) l)。2つめの引数で指定した配列に対して、1つめの引数で指定した演算方法でつなぎ合せ、その場所まで計算した配列を返します。 ...言葉より、下の表を見た方が早いかと。

そして、この (scanl1 (+)) を 0回, 1回, 2回... と無限に繰り返した結果の配列を返すのが iterate関数。こうして二次元配列ができ、137846528820 という値が [20,20] 番目を見ることで取り出せるのでした。

Rubyで有限な範囲で書くとこんな感じ。

n = 20
ary = [[1]*(n+1)]
n.times do |i|
  ary.push (0..n).collect {|j|
    (0..j).inject(0){|r,x| r + ary[i][x]}
  }
end
puts ary[n][n]

これをワンライナー（一行プログラム）で書けてしまうとは。Haskell凄い。

pi8027さん、どうも色々とありがとうございました。

あとがき

もう1つか2つ後のエントリに。

一言先に。前のエントリが、他にもぼけぼけしている書き方が混じっていないか不安になってきました（汗）。