재귀를 사용하는 정수 나누기 및 몇 가지 다른 흥미로운 제한

Question

나는 내 자신의 교화를 위해 Java에서 퍼즐을 푸는 중입니다. 나는 가이라는 퍼즐을 디자인 한 사람에 의한 해결책이라고 말했지만, 나는 그것을 스스로 발견 할 수 없다.

는 자연수 클래스는 단순히 문자열을 사용하여 자연수 를 저장하는 클래스입니다 자바

/** 
* Divides a natural number by two. 
* 
* @param n 
*   The number to be divided 
* @updates n 
* @ensures n = floor(n/2) 
*/ 
private static void split(NaturalNumber n) {...} 

에 다음 메소드를 구현 :

여기에 퍼즐입니다. (즉, 그것은 Integer.MAX_VALUE보다 훨씬 더 큰 숫자를 저장할 수 있습니다.)

가

클래스 인스턴스의 내부 문자열 값 "0" 경우 반환 사실이 instance methods 및 inherited methods뿐만 아니라 NaturalNumber.isZero() 방법을 제공, 허위 그렇지 .

그것은 NaturalNumber.divideBy10() 방법 은 본질적으로 int로서 돌려, 수 떨어져 가장 오른쪽 자리를 뜨고 인스턴스의 내부 값을 업데이트하는 것이 주목할 가치가있다.

기본 클래스에서 정적 속성을 사용하여 값을 저장하지 마십시오. 마찬가지로 정적 도우미 메서드를 작성하지 마십시오.

n을 다른 데이터 유형으로 변환하고 조작하지 마십시오. 외부 라이브러리를 사용하지 마십시오.

또한 split()은 재귀를 사용하여 구현해야합니다.

나는 다음과 같은 근처 솔루션을 밖으로 일이 : 위 단순히 긴 나눗셈을 수행

private static void split(NaturalNumber n) { 
    // Initialize local variables. 
    String stringBuffer = ""; 
    int numerator = 0; 
    int quotient = 0; 
    int remainder = 0; 

    int thisDigit = n.divideBy10(); 

    if (n.isZero()) { 
    quotient = thisDigit/2; 
    remainder = thisDigit % 2; 
    n.transferFrom(new NaturalNumber2(quotient * 10 + remainder)); 
    } else { 
    split(n); 
    numerator = n.divideBy10() * 10 + thisDigit; 
    quotient = numerator/2; 
    remainder = numerator % 2; 
    if (!n.isZero()) { 
     stringBuffer += n.toString(); 
    } 
    stringBuffer += Integer.toString(quotient * 10 + remainder); 
    n.transferFrom(new NaturalNumber2(stringBuffer)); 
    } 
} 

. 그러나 호출 스택의 마지막 프레임은 불필요하게 나머지 작업을 솔루션 끝에 추가합니다.

n이 0이되기 위해 두 번 빼야하는 횟수를 계산하여 n에서 재귀 적으로 2를 뺀 유사한 문제에 대한 솔루션을 보았습니다. 그러나 이러한 솔루션은 반환 값이있는 메서드에 의존합니다. 이 퍼즐은 반환 값이 필요하지 않습니다.

split() 및 내부 루프에 대한 하나의 함수 호출을 사용하여 퍼즐을 해결하는 방법을 볼 수도 있습니다. 그러나 솔루션은 n에서 작동하기 위해 루프에 의존해서는 안된다고 들었습니다.

솔루션에 대한 통찰력이있는 사람이 있습니까?

Answer 1

n의 자릿수가 a...yz이라고 가정합니다. y이 짝수 인 경우 n/2의 자릿수는 a...y/2과 z/2의 연결입니다. y이 홀수 인 경우 Y = y - 1으로 지정하십시오. 그런 다음 n/2의 숫자는 a...Y/2과 1z/2의 연결입니다.다음과 같이

우리는이를 구현할 수 있습니다

private static void split(NaturalNumber n) { 
    int z = n.divideBy10(); 
    int y = n.divideBy10(); 

    if (n.isZero()) { 
     // Base case. 
     int result = (y * 10 + z)/2; 
     n.multiplyBy10(result/10); 
     n.multiplyBy10(result % 10); 
    } else if (y % 2 == 0) { 
     n.multiplyBy10(y); 
     split(n); 
     n.multiplyBy10(z/2); 
    } else { 
     n.multiplyBy10(y - 1); 
     split(n); 
     n.multiplyBy10((10 + z)/2); 
    } 
} 

덧붙여, 이러한 방법 이름이 끔찍한이며, NaturalNumber s는 가변 만드는 것은 이상한 디자인의 선택입니다.