이제 막 수업들어갔는데 이해가 잘안가서 질문 드립니다..
코드는 이것이고 for i = 1 to n do k=n+1-i; for j = k to n do x=x+y;
문제는 x=x+y 이 라인의 반복횟수인데
답은 (n(n+1))/2인데 왜 그렇지 좀 자세히 설명 좀 부탁드립니다..
군대 갔다와서 시작하는 수업인데 왜이렇게 이해가 안가는지..
등차수열의 합입니다. 다시 정석책을 꺼낼 때가 되었습니다.
1 <= i <= n 이고, k <= j <= n 인데,
k = n + 1 - i 이므로 1 <= k <= j <= n 입니다.
그러므로 1 이상 n 이하의 정수 중에서
정수 두 개를 중복 가능하게 고르면 (k, j) 관계의 경우의 수가 됩니다. (k <= j)
그러므로 x=x+y 문은 H(n, 2) = (n(n+1))/2 번 돕니다.
S(n) = sum(n-k+1, i=1..n) = sum(n-n-1+i+1, i=1..n) = sum(i, i=1..n)
nxn 행렬을 생각해 보면 요소의 수는 모두 n^2개 S(n)은 대각선 요소를 포함한 윗쪽 요소의 수이다. 따라서 S(n) = (n^2 - n)/2 +n = (n^2+n)/2 = n(n+1)/2
1 + 2 + ... + n = S(n) n + n-1 + ...+ 1 = S(n) ----------------------- (1+n)*n = 2S(n) S(n) = n(n+1)/2
가우스가 초등학교 때 했다던 그 계산... -- foldl (flip (:)) [] "universe"
텍스트 포맷에 대한 자세한 정보
<code>
<blockcode>
<apache>
<applescript>
<autoconf>
<awk>
<bash>
<c>
<cpp>
<css>
<diff>
<drupal5>
<drupal6>
<gdb>
<html>
<html5>
<java>
<javascript>
<ldif>
<lua>
<make>
<mysql>
<perl>
<perl6>
<php>
<pgsql>
<proftpd>
<python>
<reg>
<spec>
<ruby>
<foo>
[foo]
등차수열의 합
등차수열의 합입니다. 다시 정석책을 꺼낼 때가 되었습니다.
1
1 <= i <= n 이고, k <= j <= n 인데,
k = n + 1 - i 이므로 1 <= k <= j <= n 입니다.
그러므로 1 이상 n 이하의 정수 중에서
정수 두 개를 중복 가능하게 고르면 (k, j) 관계의 경우의 수가 됩니다. (k <= j)
그러므로 x=x+y 문은 H(n, 2) = (n(n+1))/2 번 돕니다.
S(n) = sum(n-k+1, i=1..n) =
S(n) = sum(n-k+1, i=1..n) = sum(n-n-1+i+1, i=1..n) = sum(i, i=1..n)
nxn 행렬을 생각해 보면 요소의 수는 모두 n^2개
S(n)은 대각선 요소를 포함한 윗쪽 요소의 수이다.
따라서 S(n) = (n^2 - n)/2 +n = (n^2+n)/2 = n(n+1)/2
1 + 2 + ... + n = S(n)
n + n-1 + ...+ 1 = S(n)
-----------------------
(1+n)*n = 2S(n)
S(n) = n(n+1)/2
가우스가 초등학교 때 했다던 그 계산...
--
foldl (flip (:)) [] "universe"
댓글 달기