(http://bi.snu.ac.kr/~skim/lecture/programming)
| November 23, 2001 (16:40) from 211.47.146.204 | |
| Written by shooting star | Hits : 1927 , Lines : 66 |
| 19일 새벽.. 별똥별 떨어지던 날... |
|---|
|
어느 컴.공과 게시판에 올라왔던 글이라고하네요.. 하하 *^^* 제 목:[모인돌] 별똥별.. 소원.. 올린이:달같이 (양회석 ) 01/11/18 04:08 읽음:169 관련자료 있음 별똥별이 다 떨어지기 전에 소원을 세개 빌면.. 다 이루어 진다지.. 이런건 어떨까? "남은 소원의 갯수를 두배로 해주세요" 라는 소원을 계속 비는 거야. 처음 한번 빌면 (3-1)*2 = 4 개의 소원이 남고 다음엔 (4-1)*2 = 6 개.. 다음엔 (6-1)*2 = 10개.. (10-1)*2 = 18개... 소원을 n번 빌었을 때 남은 소원의 개수를 a(n) 이라 할때 a(n+1) = 2(a(n)-1) 이고 a(0) = 3 이고.. a(n+1) - a(n) = b(n) 이라 하면 b(n) = 2^n 이니.. 결국 일반항 a(n) = a(0) + [21~23 앗 오타 a(n) = a(0) + ∑2^n (1부터 n-1까지) 이니.. a(n) = 3 + 2^n - 2 = 1 + 2^n 이고.. 한번 소원을 비는데 필요한 인스트럭션의 개수는... 일단 소원의 총개수에서 하나를 빼는 것(SUB) 그리고 두 배하는 것 (MUL) 두개라고 가정하고.. 하나의 인스트럭션은 하나의 클럭이 소모된다고 가정하면.. 1GHz의 CPU로 소원을 빌고, 별이 떨어지는데 3초가 걸린다면.. 초당 5억번의 소원을 빌 수 있는 거고.. 3초동안 15억번의 소원을 비는 거군.. 그렇다면 별이 다 떨어질 때 소원의 개수는... 2^1500000000 하고도 하나 더 있군.. 아.. 오에스 빼달라는 소원은 언제 빌어야 하지... p.s. 1. 쓰고나서 생각해보니 소원 몇번 빌고나면 overflow나서 소원 갯수가 음수가 되버리겠군.. 2. 헉.. 생각해보니 반말로 썼네요..--; 죄송.. |
|
|