프로그램 콘테스트를 해 보았습니다.

1년에 1회, MATLAB Expo라고 하는 집회? 같은 것이 있었으므로, 거기서 콘테스트를 해 보았습니다. 이런 UI 를 만들어, 「좋아하는 것을 풀어주세요」라고 써, 대량의 PC를 방치!


정답인지는 자동 채점!

채점은 "간단한 프로그램"을 평가합니다.

심플이란 무엇인가.

이번은, 정답인지 아닌지, 「노드 카운트」라고 하는 것을 사용해 프로그램의 단순함을 평가했습니다. 여기에 프로그램을 평가하는 프로그램이 있습니다.
htps : // jp. 마 t 후 rks. 코 m / 마 t b 센 t 등 l / 푸에에 x 찬게 / 34754

예를 들어, 「입력에 1 을 더해 출력해 주세요」라고 하는 문제라면, 이하와 같은 느낌이군요.

12점

function y = plus_one(x)
      y = x+1;
end

16점

function z = plus_one(x)
      z = x;
      y = z+1;
end

점수가 「낮은」 쪽이 우수한 성적이므로, 위가 우수!

※ 공백이나 코멘트나 개행이나 세미콜론은, 노드 카운트의 평가 대상외이므로, 안심하고 여백을 열자.

여러 사람의 정답을 보자!

예를 들어 이런 문제가 있었습니다. 모두가 좋아하는 피보나치입니다.

フィボナッチ数列： 1, 1, 2, 3, 5, ...

fib(1) --> 1
fib(5) --> 5
fib(50) --> 12586269025

となるような関数

f = fib(n)

を作成せよ。

채점은 1에서 50까지의 입력에 대해 1에서 12586269025가 올바르게 나오는지 여부를 봅니다.

가장 많았던 재귀의 해답(C 언어 같은 글쓰기)

교과서등에서 자주 보는 재귀군요. 이제 30점.

30점

function f = fib(n)

if n > 2
    f = fib(n-1) + fib(n-2);
else
    f = 1;
end

다만, 이 쓰는 방법이라고 정답은 나오지만 계산이 늦다. .
시험에 시간 계측.

tic
f = fib(50);
toc

経過時間は 687.018277 秒です。

11분 30초!
MATLAB이라면 그렇게 이렇게 쓰지 않는 편이 좋다.

루프를 빙글빙글 돌리는 패턴

두 번째로 많은 FOR 문이나 WHILE 문을 사용한 사람. 대표적인 쓰기가 이것이었습니다.

38점

function f = fib(n)

f = 0;
f1 = 0;
f2 = 1;
for x = 1:n
    f = f1 + f2;
    f2 = f1;
    f1 = f;
end

점수는 재귀보다 나쁘지만 계산은 빠르다.

tic
for n = 1:10000
f = fib(50);
end
t = toc/10000

t =

   1.7706e-07

너무 빠르기 때문에, 10000회 계산시킨 평균치를 취했습니다만 0.17(μs) 정도군요.

일반식으로 하는 패턴

반올림 오차가 나오기 때문에 round 하고 있습니다만, 계산이 많기 때문에 스코어가 좋지 않다.

37점

function f = fib(n)
f = round(((0.5+sqrt(5)/2)^n - (0.5-sqrt(5)/2)^n)/sqrt(5));

이런 식이군요.

F(n) = \frac{1}{\sqrt{5}}
\left(
\left( 
\frac{1+\sqrt{5}}{2} 
\right) ^n - 
\left( 
\frac{1-\sqrt{5}}{2}
\right) ^n 
\right)

계산 시간은 0.7 (μs) 정도.

(↑↑ 슈퍼 무성하게 $\TeX$ 썼다.)

행렬 계산 버리는 패턴 (섹시)

좋은 점수! 24점!

24점

function f = fib(n)
x = [1 1;1 0]^n;
f = x(2);

행렬 계산은, 이런 이야기군요.

   \left(
    \begin{array}{l}
      F_{n+2} \\
      F_{n+1}
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      F_{n+1} & F_n \\
      F_n & F_{n-1}
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      1 \\
      1
    \end{array}
  \right)

구체적으로 쓰면, $F_2 = 1, F_1 ​​= 1$ 가 초기치로서, 다음의 값은 이렇게 됩니다.

   \left(
    \begin{array}{l}
      F_3 \\
      F_2
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      F_2 \\
      F_1
    \end{array}
  \right)

　$F_4$ 때는 이렇게 되어,

   \left(
    \begin{array}{l}
      F_4 \\
      F_3
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      F_3 \\
      F_2
    \end{array}
  \right)

즉, $F_3, F_2$ 에 원래의 식을 대입해 [1 1;1 0] 의 제곱이 되면.

   \left(
    \begin{array}{l}
      F_4 \\
      F_3
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)
   \left(
    \begin{array}{l}
      F_2 \\
      F_1
    \end{array}
  \right)

그래서, 큰 수에 응용하면 이렇게 됩니다만,

   \left(
    \begin{array}{l}
      F_{52} \\
      F_{51}
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)^{50}
   \left(
    \begin{array}{l}
      F_2 \\
      F_1
    \end{array}
  \right)

최초의 식을 보면, 중간의 행렬은 이렇게 되어 있을 것이므로, 좌하의 값을 취하면 좋네요.

   \left(
    \begin{array}{cc}
      F_{51} & F_{50} \\
      F_{50} & F_{49}
    \end{array}
  \right) = 
   \left(
    \begin{array}{cc}
      1 & 1 \\
      1 & 0
    \end{array}
  \right)^{50}

계산 시간도 빠르고, 1 (μs) 정도!

도구 상자 사용 버리는 패턴 (최고)

노드 카운트는 툴박스 함수의 내용까지는 보지 않기 때문에, Symbolic Math Toolbox 를 사용한 녀석.

12점

function f = fib(n)
f = fibonacci(n);

12점! 함수를 알고 있으면 이것으로 좋다.

"단지, 에러 체크나 중복 코드가 있는 탓인지, 계산 시간은 0.03 초 정도로, 다른 것보다 조금 느린."

여러 사람의 프로그램을 보는 것은 재미 있습니다.

　일단 현재, 노드 카운트 관점에서 섹시한 MATLAB 프로그램은,

있다면 도구 상자를 사용합시다.

행렬 연산을 사용하자.

이군요. 그리고, 여기에 Octave 의 쓰는 법이 쓰여져 있지만, 아마 이쪽도 행렬처럼 쓰면 좋은 속도가 될지도.
htps : // 이 m/y_이라부/있어 ms/604b0987 아7c8에c52c65