1/17 第13回 いろいろなプログラミング言語，まとめ

前回までの補足

試験について

スライドに使われたプログラムと実行法

関数型プログラム言語

教育用計算機システムにインストールされているHaskell言語処理系は，GHC(Glasgow Haskell Compiler)とHugs(マニュアルはThe Hugs 98 User's Guide)の2つ．ここでは，hugsを使った実行法を示す． 
primes = sieve [2..]
   where sieve (p:xs) = 
       p : sieve [ x | x <- xs, x `mod` p > 0 ]
実行例(上のプログラムをprimes.hsという名前のファイルに保存しておく) 
ux103$ cat primes.hs
primes = sieve [2..]
   where 
     sieve (p:xs) = p : sieve [ x | x <- xs, x `mod` p > 0 ]
ux103$ hugs
__   __ __  __  ____   ___      _________________________________________
||   || ||  || ||  || ||__      Hugs 98: Based on the Haskell 98 standard
||___|| ||__|| ||__||  __||     Copyright (c) 1994-2001
||---||         ___||           World Wide Web: http://haskell.org/hugs
||   ||                         Report bugs to: hugs-bugs@haskell.org
||   || Version: February 2001  _________________________________________

Haskell 98 mode: Restart with command line option -98 to enable extensions

Reading file "/sw/share/hugs/lib/Prelude.hs":
                   
Hugs session for:
/sw/share/hugs/lib/Prelude.hs
Type :? for help
Prelude> :l primes.hs
Reading file "primes.hs":
                   
Hugs session for:
/sw/share/hugs/lib/Prelude.hs
primes.hs
Main> primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103{Interrupted!}
表示が止まらないので，[Ctrl]+[C](コントロールキーを押しながら[C]を押す)で止める
Main> :q
[Leaving Hugs]

論理プログラミング

教育用計算機システムにインストールされているProlog処理系はGNU Prolog(マニュアルはGNU-Prolog Manual)．以下ではその実行例を示す． 
mother(kishiyoko, abeshinzo).   % 岸洋子は安部晋三の母
father(abeshintaro, abeshinzo). % 安部晋太郎は安部晋三の父
father(abeshintaro, kishinobuo).        % 安部晋太郎は岸信夫の父
father(kishinobusuke, kishiyoko).       % 岸信介は岸洋子の父
parent(X,Y) :- father(X,Y).     % XがYの父ならばXはYの親
parent(X,Y) :- mother(X,Y).     % XがYの母ならばXはYの親
sibling(X,Y)    % ZがXの親でZがYの親ならば
  :- parent(Z,X), parent(Z,Y).  % XはYの兄弟
grandparent(X,Y)        % XがZの親でZがYの親ならば
  :- parent(X,Z), parent(Z,Y).  % XはYの祖父母
実行例(上のプログラムをfamily.plという名前のファイルに保存しておく) 
ux103$ gprolog
GNU Prolog 1.2.16
By Daniel Diaz
Copyright (C) 1999-2002 Daniel Diaz
| ?- consult('family.pl').
consult('family.pl').
compiling /home08/ktanaka/family.pl for byte code...
/home08/ktanaka/family.pl compiled, 10 lines read - 1492 bytes written, 22 ms

(2 ms) yes
| ?- sibling(abeshinzo,kishinobuo).
true ? (リターンキーのみ)
yes
| ?- grandparent(X,abeshinzo).
X = kishinobusuke ? (リターンキーのみ)
yes
| ?- halt.
halt.
ux103$

モンテカルロ法による円周率の計算

Ruby版 
n=1000000
m=0
n.times{
  x=rand　#0以上１未満の
  y=rand         #一様疑似乱数を返す
  if (x*x+y*y)<1.0 
    m+=1
  end
}
puts 4*Float(m)/n
C版 
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
  int n = 1000000;
  int m = 0;
  int i;
  double x,y;
  srand48(time(NULL));
  for (i = 0; i < n; i=i+1) {
    x = drand48();
    y = drand48();
    if ((x*x + y*y) < 1.0) {
      m += 1;
    }
  }
  printf("%f\n", 4*((double)m)/n);
}

オートマトン

Ruby版 
$automaton = [[0,1], [2,0], [1,2]]
def make_transitions(input)
  s = 0
  for i in 0..(input.size - 1)
    c = input[i] - ?0
    s = $automaton[s][c]
  end
  s
end
#
make_transitions("011001")
make_transitions("011011")
make_transitions("011101")
C版 
#include 
int automaton[3][2] = {{0,1},{2,0},{1,2}};

int make_transitions(char* input) {
  int s = 0, i, c;
  for (i = 0; input[i] != 0; i++) {
    c = input[i] - '0';
    s = automaton[s][c];
  }
  return s ;
}

int main(int argc, char* argv[]) {
  printf("%d\n", make_transitions("011001"));
  printf("%d\n", make_transitions("011011"));
  printf("%d\n", make_transitions("011101"));
}

数え上げ方式によるフィボナッチ数の計算

Ruby版 
def fib(x)
  i=0; fi=1; fi1=1
  while i < x
    i = i+1
    f2 = fi+fi1
    fi = fi1
    fi1 = f2
  end
  fi	
end
C版 
#include <stdio.h>

int fib(int x) {
  int i = 0, fi=1, fi1 = 1, f2;
  while (i < x) {
    i = i + 1;
    f2 = fi+fi1;
    fi = fi1;
    fi1 = f2;
  }
  return fi;
}

int main(int argc, char* argv[]) {
  printf("%d\n", fib(30));
  printf("%d\n", fib(50));
}

ACM/ICPCについて

今日の課題