2016-04-21

AIZU ONLINE JUDGEのELISP解答例(ITP1_1_A~ITP1_2_C)

ITP1_1_A:Hello World

(message "Hello World")

ITP1_1_B:X Cubic

(progn (defun cubic ()
	 (let ((x (read)))
	   (* x x x)))
       (cubic))

ITP1_1_C:Rectangle

(progn (defun rectangle ()
         (let ((a (read))
	       (b (read)))
           (cons (* a b) (* 2 (+ a b)))))
       (rectangle))

ITP1_1_D:Watch

(progn (defun watch ()
         (let ((x (read)))
           (let ((s (% x 60)))
             (let ((m (% (/ (- x s) 60) 60)))
	       (let ((h (/ (- (/ (- x s) 60) m) 60)))
	         (list h m s))))))
       (watch))

ITP1_2_A:Small, Large, or Equal

(progn (defun small ()
	 (let ((a (read))
	       (b (read)))
	   (if (< a b) (message "a<b")
	     (if (> a b) (message "a>b") (message "a=b")))))
       (small))

ITP1_2_B:Range

(progn (defun range ()
         (let ((a (read))
	       (b (read))
	       (c (read)))
           (if (and (< a b) (< b c)) (message "YES") (message "NO"))))
       (range))

ITP1_2_C:Sorting Three Numbers

(progn (defun swap (x a b)
         (let ((c (elt x a)))
           (setf (elt x a) (elt x b))
           (setf (elt x b) c)
           x))
       (defun sort ()
	 (let ((a (read)) (b (read)) (c (read)))
	   (let ((x (list a b c)))
             (dotimes (j (1- (length x)))
               (dotimes (i (1- (length x)))
                 (if (> (elt x i) (elt x (1+ i)))
	             (swap x i (1+ i)))))
	     x)))
       (sort))

2016-03-29

Lispやってみた2

プログラミング

あれから少し経って、多少なりとも使えるようになりましたが、わからないことだらけです(^_^;)

例えば、文字列を出力しようとしても、カッコつきのまま出力されたり、複数の出力ができなかったり・・・

あとわかったことは、lispにもいろいろな方言があるということでしょうか。

私が使っているのは、Emacs Lisp(通称elisp)だと思います。

とりあえずは、少しでも良さげな解説サイトを探すことを

目標にしたいと思います（´-`）

2016-02-23

Lispやってみた

プログラミング

Lispを学び始めたんですが、いかんせんLispの解説サイトが少ない・・・
やはりマイナーなのでしょうか？
素数判定のプログラムすらまともに動かない(´・ω・｀)
なぜ興味を持ったかと言いますと、ラムダ計算ができそうなのが理由です。
良いと思った点は、とにかく簡潔に書けるということです。
カッコは"("と")"だけ使って、"{"や"}"は使いません。
あとは、Rubyと一緒で引数を区切る時に","を使いません。
ぜひLispが使える人のご教授を受けたいですね。

2015-12-07

ニコニコフィーチャー Part43 やまぶし

ニコニコ

2015-08-22

ニコニコフィーチャー Part42 BONN

ニコニコ

2015-08-22

スターリング数

数学

S(m,n)をm個の集合からn個の集合への全射の総数とする。
$S(m,n):=|\{f\in B^A|f:全射,|A|=m,|B|=n\}|$
以下の漸化式が成り立つ。
$S(m,0)=0^m\\ \displaystyle S(m,n)=n^m-\sum_{k=0}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)S(m,k)$
nを固定して求める。
$\displaystyle \begin{eqnarray} S(m,1)&=&1^m-\sum_{k=0}^{0}\left(\begin{matrix} 1 \\k\end{matrix}\right)S(m,k)\\ &=&1^m-\left(\begin{matrix} 1 \\0\end{matrix}\right)S(m,0)\\ &=&1^mー0^m\\ S(m,2)&=&2^m-\sum_{k=0}^{1}\left(\begin{matrix}2 \\k\end{matrix}\right)S(m,k)\\ &=&2^m-\left(\begin{matrix}2 \\1\end{matrix}\right)S(m,1)-\left(\begin{matrix}2 \\0\end{matrix}\right)S(m,0)\\ &=&2^m-2(1^m-0^m)-0^m\\ &=&2^m-2\cdot1^m+0^m\\ S(m,3)&=&3^m-\sum_{k=0}^{2}\left(\begin{matrix}3 \\k\end{matrix}\right)S(m,k)\\ &=&3^m-\left(\begin{matrix}3 \\2\end{matrix}\right)S(m,2)-\left(\begin{matrix}3 \\1\end{matrix}\right)S(m,1)-\left(\begin{matrix}3 \\0\end{matrix}\right)S(m,0)\\ &=&3^m-3(2^m-2\cdot1^m+0^m)-3(1^mー0^m)-0^m\\ &=&3^m-3\cdot2^m+3\cdot1^m-0^m\\ S(m,4)&=&4^m-\sum_{k=0}^{3}\left(\begin{matrix} 4 \\k\end{matrix}\right)S(m,k)\\ &=&4^m-\left(\begin{matrix} 4 \\3\end{matrix}\right)S(m,3)-\left(\begin{matrix} 4 \\2\end{matrix}\right)S(m,2)-\left(\begin{matrix} 4 \\1\end{matrix}\right)S(m,1)-\left(\begin{matrix} 4 \\0\end{matrix}\right)S(m,0)\\ &=&4^m-4(3^m-3\cdot2^m+3\cdot1^m-0^m)-6(2^m-2\cdot1^m+0^m)\\ &&-4(1^mー0^m)-0^m\\ &=&4^m-4\cdot3^m+6\cdot2^m-4\cdot1^m+0^m \end{eqnarray}$
どうやら、S(m,n)は次の式になるようだ。
$\displaystyle S(m,n)=\sum_{k=0}^n \left(\begin{matrix}n\\k\end{matrix}\right) (-1)^{n-k} k^m$
以下、数学的帰納法で証明する。
$\displaystyle \begin{eqnarray} S(m,n)&=&n^m-\sum_{k=0}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)S(m,k)\\ &=&n^m-\sum_{k=0}^{n-1}\left(\begin{matrix}n\\k\end{matrix}\right)\sum_{i=0}^k \left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\ &=&n^m-\sum_{k=0}^{n-1}\sum_{i=0}^k \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\ &=&n^m-\sum_{i=0}^{n-1}\sum_{k=i}^{n-1} \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\ \end{eqnarray}$
$\begin{eqnarray} \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right)&=&\frac{n!}{k!(n-k)!}\frac{k!}{i!(k-i)!}\\ &=&\frac{n!}{(n-k)!}\frac{1}{i!(k-i)!}\\ &=&\frac{n!}{i!}\frac{1}{(n-k)!(k-i)!}\\ &=&\frac{n!}{i!(n-i)!}\frac{(n-i)!}{(n-k)!(k-i)!}\\ &=&\left(\begin{matrix}n\\i\end{matrix}\right)\frac{(n-i)!}{(n-k)!(k-i)!}\\ \end{eqnarray}$
$\begin{eqnarray} S(m,n)&=&n^m-\sum_{i=0}^{n-1}\sum_{k=i}^{n-1} \left(\begin{matrix}n\\k\end{matrix}\right)\left(\begin{matrix}k\\i\end{matrix}\right) (-1)^{k-i} i^m\\ &=&n^m-\sum_{i=0}^{n-1}\sum_{k=i}^{n-1} \left(\begin{matrix}n\\i\end{matrix}\right)\frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i} i^m\\ &=&n^m-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m\sum_{k=i}^{n-1} \frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i}\\ \end{eqnarray}$
$\begin{eqnarray} \sum_{k=i}^{n-1} \frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i}&=&\sum_{k-i=0}^{n-i-1} \frac{(n-i)!}{(n-i-(k-i))!(k-i)!} (-1)^{k-i}\\ &=&\sum_{j=0}^{n-i-1} \frac{(n-i)!}{(n-i-j)!j!} (-1)^{j}\\ &=&\sum_{j=0}^{n-i-1} \left(\begin{matrix}n-i\\j\end{matrix}\right) (-1)^{j}\\ &=&-\left(\begin{matrix}n-i\\n-i\end{matrix}\right) (-1)^{n-i} + \sum_{j=0}^{n-i} \left(\begin{matrix}n-i\\j\end{matrix}\right) (-1)^{j}\\ &=&-(-1)^{n-i}+0^{n-i} \end{eqnarray}$
$\begin{eqnarray} S(m,n)&=&n^m-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m\sum_{k=i}^{n-1} \frac{(n-i)!}{(n-k)!(k-i)!} (-1)^{k-i}\\ &=&n^m-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m(-(-1)^{n-i}+0^{n-i})\\ &=&n^m+\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m(-1)^{n-i}-\sum_{i=0}^{n-1}\left(\begin{matrix}n\\i\end{matrix}\right)i^m 0^{n-i}\\ &=&\sum_{i=0}^{n}\left(\begin{matrix}n\\i\end{matrix}\right)i^m(-1)^{n-i}\\ &=&\sum_{k=0}^n \left(\begin{matrix}n\\k\end{matrix}\right) (-1)^{n-k} k^m \end{eqnarray}$
ちなみに、スターリング数はS(m,n)をn!で割ったものだ。

2015-08-21

ドットボックス 3×3 必勝

プログラミング数学

Dots&Boxesという外国のゲームの3×3の必勝手順を調べました。
結果は後手必勝となったんですが、問題はプログラムを走らせるとあまりにも早く結果が出るんですよね(-_-;)
プログラムが間違ってるのか私が間違っているのか・・・

#include<stdio.h>

bool dotbox(int *c);
bool turn(int *c);
void calq(int *c, bool *q);
void calsq(int s, int *sq);
bool winlose(int *c);
void printc(int *c);

int main(){
	int i;
	int c[24];
	int result;
	
	for (i = 0; i < 24; i++){
		c[i] = -1;
	}
	
	result = dotbox(c);
	printf("%d\n", result);
	return 0;
}
bool dotbox(int *c){
	int i,j,k;
	bool t;
	for (k = 0; k < 24; k++){
		if (c[k] == -1) break;
	}
	if (k == 24){
		return winlose(c);
	}else{
		for (i = 0; i < 24; i++){
			for (j = 0; j < 24; j++){
				if (c[j] == i) break;
			}
			if (j == 24){
				t = turn(c);
				c[k] = i;
				//printc(c);
				if (t == dotbox(c)){
					c[k] = -1;
					return t;
				}
			}
		}
		return !turn(c);
	}
}
bool turn(int *c){
	int i, j;
	int sq[9] = {};
	bool turn = 0, turnflag = 0;

	for (i = 0; i < 24; i++){
		if (c[i] == -1) break;
		calsq(c[i], sq);
		for (j = 0; j < 9; j++){
			if (sq[j] == 4){
				sq[j]++;
				turnflag = 1;
			}
		}
		if (turnflag == 1){
			turn = !turn;
			turnflag = 0;
		}

		turn = !turn;
	}
	return turn;
}
void calq(int *c, bool *q){
	int i, j;
	int sq[9] = {};
	bool turn=0,turnflag=0;

	for (i = 0; i < 24; i++){
		calsq(c[i], sq);
		for (j = 0; j < 9; j++){
			if (sq[j] == 4){
				q[j] = turn;
				sq[j]++;
				turnflag = 1;
			}
		}
		if (turnflag == 1){
			turn = !turn;
			turnflag = 0;
		}

		turn = !turn;
	}
}
void calsq(int s, int *sq){
	if (s == 0 || s == 1 || s == 12 || s == 15)
		sq[0]++;
	if (s == 1 || s == 2 || s == 13 || s == 16)
		sq[1]++;
	if (s == 2 || s == 3 || s == 14 || s == 17)
		sq[2]++;
	if (s == 4 || s == 5 || s == 15 || s == 18)
		sq[3]++;
	if (s == 5 || s == 6 || s == 16 || s == 19)
		sq[4]++;
	if (s == 6 || s == 7 || s == 17 || s == 20)
		sq[5]++;
	if (s == 8 || s == 9 || s == 18 || s == 21)
		sq[6]++;
	if (s == 9 || s == 10 || s == 19 || s == 22)
		sq[7]++;
	if (s == 10 || s == 11 || s == 20 || s == 23)
		sq[8]++;
}
bool winlose(int *c){
	int i;
	bool q[9];
	calq(c, q);
	int sen=0, kou=0;
	for (i = 0; i < 9; i++){
		if (q[i] == 0)
			sen++;
		else
			kou++;
	}
	if (sen>kou)
		return 0;
	else
		return 1;
}
void printc(int *c){
	int i;
	for (i = 0; i < 24; i++){
		printf("%d,", c[i]);
	}
	printf("\n");
}