Posts List


2012년 3월 10일 토요일

[Project Euler]26. 1000 이하의 d 중에서 1/d 이 가장 긴 순환마디를 갖는 수는?

26. 1000 이하의 d 중에서 1/d 이 가장 긴 순환마디를 갖는 수는?
분자가 1인 분수를 단위분수라고 합니다. 분모가 2에서 10까지의 단위분수는 아래와 같습니다.


숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 "6"으로 0.166666...처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다.

d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까?

Click
그냥 나눈 뒤에 값을 계산하기에는 소수점 이하 모든 수가 나오지 않는데다 오차가 발생할 수도 있으므로 다른 방법을 찾아야 하는 문제군요.

저보다 먼저 문제를 풀은 다른분들은 어떻게 풀었나 한번씩 훑어보는데 Dev용식님의 블로그를 보니 나머지값을 가지고 계산하는 방법이 나오네요. 그보다 좋은 방법은 떠오르지 않아 같은 알고리즘으로 구현했습니다.

조금 개선했다고 하면 numCirculating 함수내부에 변수를 하나 줄이고 loop를 한번 줄였다는 것 일까요?
<script language="Javascript" type="text/javascript">
/* 순환마디의 수를 구함. */
function numCirculating(d){
    var remain_list = new Array();      //나머지값들을 넣을 list
    var remain = remain_list[0] = 1;    //초기값 설정.
    do{
        remain = remain * 10 % d;       //나머지 값.
        for(var i=0; i<remain_list.length; i++) //나머지 값이 list에 있는지 확인.
            if(remain_list[i] == remain)
                return remain_list.length - i;  //있다면 return.
        remain_list[remain_list.length] = remain;
    }while(remain != 0);            //나머지가 0이면 나누어 떨어졌으므로 순환이 없음.
    return 0;
}
/* 한계값 l 이전의 수 d에 대해 1/d의 순환마디가 가장 긴 d 값. */
function p026(l){
    var max_n = 0;          //최대 cycle 수
    var max_d = 0;          //최대 cycle 를 갖는 d 값.
    
    for(var i=2; i<l; i++){
        var temp = numCirculating(i);   //cycle 수를 얻음.
        if(temp > max_n){           //최대값 비교
            max_n = temp;
            max_d = i;
        }
    }
    return max_d;
}
</script>

댓글 5개:

  1. 이런 유형의 문제들은 개인적으로 풀이를 자랑(?)하고 싶은 문제들이지만 ㅋㅋ..

    단 28줄밖에 안되는 코드 앞에서 주름잡을 수는 없겠군요 ㅠㅠ

    답글삭제
    답글
    1. 더 짧게 하시는 분들도 계시던 걸요. 개인적으로 길이보다는 performance를 더 우선적으로 생각 하기도 하고....

      삭제
    2. 블로그 보니 수학을 전공하셨나봐요. 순환소수를 분수로 바꾸는 법 상당히 오랜만에 보네요.(까먹고 있던 것이기도하구요..^^)
      진도도 저보다 훨씬 많이 나가셨군요. 다음에 풀때 참고 좀 하겠습니다. ㅎㅎ..

      삭제
    3. 복수전공으로 수학+컴퓨터공학 하고있는 학생입니다 ^^;

      지식이 얇아서 모든 문제에 대해 수학적 이론을 펼치지는 못하고 brute-force로 풀이하는 것도 있지만, 참고해주신다면 감사하죠 (__)

      다만 제 코드에는 주석이 워낙 없어서 보시는데 불편하실듯 ㅠㅠ

      삭제
    4. 소스에 주석은 없지만 유추과정을 상세히 써놓으셨던데요. 생각지도 못한 접근도 많고 많은 도움이 될 것 같아서요 ^^

      삭제