Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 5월 19일 토요일

[Project Euler] 52. 2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수

52. 2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수
125874를 2배 하면 251748이 되는데, 이 둘은 같은 숫자로 이루어져 있고 순서만 다릅니다.

2배, 3배, 4배, 5배, 6배의 결과도 같은 숫자로 이루어지는 가장 작은 수는 무엇입니까?
Click

n의 배수가 같은 자릿수여야 하므로 탐색은 각 자릿수의 1/6만 하면 탐색시간을 많이 줄일 수 있다.
참고 : http://www.mathblog.dk/project-euler-52-integer-same-digits/
<script language="Javascript" type="text/javascript">
function func052(n1, n2){
    var arr = new Array();
    arr[0] = new Array();
    arr[1] = new Array();
    
    for(var i=1, temp=n1; temp>1; i++){
        arr[0][i] = ~~(temp%10);
        arr[1][i] = false;
        temp /= 10;
    }
    
    for(var temp=n2; temp>1; temp/=10){
        var t = ~~(temp%10);
        var check = false;
        for(var i=0; i< arr[0].length; i++){
            if(t == arr[0][i] && !arr[1][i]){
                arr[1][i] = true;
                check = true;
                break;
            }
        }
        if(!check)
            return false;
    }
    
    return true;
}
function p052(n){
    var check = false;
    
    for(var i=1; !check; i*=10){
        for(var j=i; j< i*10/n; j++){
            for(var k=1; k<=n; k++){
                check = func052(j, j*k);
                if(!check)
                    break;
            }
            if(check)
                break;
        }
    }
    alert(j);
}
</script>
경과시간 : 0.215

댓글 없음:

댓글 쓰기