<span style="background-color:#ffffff;"><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><i>Exercise 1.17</i></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"> The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure :<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;">(define (* a b)<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"> (if (= b 0)<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"> 0<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"> (+ a (* a (- b 1)))))<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;">This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.</span></span> <div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;background-color:#ffffff;"><br></span></div> <div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;background-color:#ffffff;">1) 문제에서 언급했던 fast-expt procedure. (b^n 을 짝수와 홀수로 나누어 연산하는 procedure)</span></div> <div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;background-color:#ffffff;"><br></span></div> <div><span style="background-color:#ffffff;"><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;">b^n = (b^n/2)^2 if n is even,<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;">b^n = b x b^n-1 if n is odd.<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;">(define (fast-expt b n)<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"> (cond ((= n 0) 1)<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"> ((even? n) (square (fast-expt b (/ n 2))))<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"> (else (* b (fast-expt b (- n 1))))))<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;">(define (even? n)<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"> (= (remainder n 2) 0))<br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><br></span><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;">O(log n) steps and O(log n) space.</span></span></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;"><br></span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">2) 문제 중간에서 곱셈을 반복되는 덧셈의 연산의 결과로 만드는 procedure를 fast-expt와 유사하게 바꾸라고 합니다. 그리고 그렇게 하면서 시간복잡도(?)를 O(n)에서 O(log n)으로 바꾸는 문제입니다.</span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;"><br></span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">제가 생각했던 procedure는</span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;"><br></span></font><span style="background-color:#ffffff;"><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"></span></span><div class="autosourcing-stub-extra"></div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"></span><div class="autosourcing-stub-extra"></div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"></span> <div><img src="http://thimg.todayhumor.co.kr/upfile/201607/14697623515e2d66f685dd4f3287af55b2cd8081c3__mn82294__w386__h172__f18570__Ym201607.jpg" width="386" height="172" alt="ab.png" style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;border:none;" filesize="18570"></div></div> <div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;">이거였는데, 연산이 되지 않더라구요. 아무리 생각해서 이게 맞는 것 같아서, 다른 사람들이 푼 것들을 보았는데 저와 비슷하거나 다르게 풀었는데 달랐던 점은,</span></div> <div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><br></span></div> <div><div style="text-align:left;"><img src="http://thimg.todayhumor.co.kr/upfile/201607/1469762599bcbdbce0b73f4fd5be372168f51a3727__mn82294__w386__h172__f18950__Ym201607.jpg" width="386" height="172" alt="fast.jpg" style="border:none;" filesize="18950"></div><br></div> <div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;">(* a b)로 하지 않고 "fast-multi" 같이 정의를 통해서 했더라구요.</span></div> <div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><br></span></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">제가 궁금한 점은,</span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;"><br></span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">exercise1.17 중간에서 보여줬듯이 (* a b)를 바꾸어 실행해보니 실행이 되었었는데,</span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">fast-expt와 유사한 procedure를 바꿀려고 할 때, (* a b)로 정의할 때는 안되고</span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">다른 것으로(예를들어 fast-multi) 정의할 때는 되는 이유가 궁금하네요.</span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;"><br></span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">일단 제가 추측하는 것은 * 곱셈이라는 연산자가 기본적인 것 때문에, 그러는 것이라는 생각도 들기는 합니다만,</span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">exercise에서 보여준 procedure는 실행이 되니, 제가 생각한 것은 아니라는 건데...</span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">아무리 생각해도 모르겠네요 ㅠㅠ 이것 때문에 이틀 동안 다음 문제로 못넘어갔네요.</span></font></div> <div><font face="나눔고딕, nanumgothic, se_NanumGothic, AppleSDGothicNeo-Regular, sans-serif, simhei"><span style="font-size:16px;line-height:30.4px;">알려주시면 감사하겠습니다.</span></font></div> <div><br></div> <div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><br></span></div> <div><span style="font-family:'나눔고딕', nanumgothic, 'se_NanumGothic', 'AppleSDGothicNeo-Regular', sans-serif, simhei;font-size:16px;line-height:30.4px;"><br></span></div> <div><br></div>
댓글 분란 또는 분쟁 때문에 전체 댓글이 블라인드 처리되었습니다.