이제 막 수업들어갔는데 이해가 잘안가서 질문 드립니다..
코드는 이것이고 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"
등차수열의 합
등차수열의 합입니다. 다시 정석책을 꺼낼 때가 되었습니다.
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"