끝없는 숫자에서 자릿수 합계의 첫 번째 발생 찾기

debugcn 에 게시 Dev

사용자 813801

Pi와 같은 끝없는 숫자의 경우 주어진 숫자 n에 대한 정확한 자릿수 합계를 찾는 방법은 무엇입니까?

예를 들면. n = 20 인 경우

Pi = 3.14159265358979323846264338327950288419716939 ...

첫 번째 발생은 1 + 4 + 1 + 5 + 9 = 20이므로 숫자 1에서 숫자 5까지입니다.

n = 30이면 9 + 2 + 6 + 5 + 3 + 5 = 30이므로 첫 번째 발생은 숫자 5에서 숫자 11까지입니다.

대답에는 작동하는 PHP 데모가 있어야합니다.

우리의

방법 1 (Ashwin Bhat에서 제안)

이 구현에서는 두 개의 피벗을 사용합니다. $pivot_a과 사이의 자릿수 합계 $pivot_b가 계산됩니다. 합계의 값에 따라 $pivot_b(합이 더 적 으면) 또는 $pivot_a(합이 더 큰 경우) 증가합니다. 합계가 $n이면 중단합니다. 피벗 값은 적절한 숫자 인덱스를 제공합니다.

$pi = "314159265358979323846264338327950288419716939";

$n = 30;

$pivot_a = $pivot_b = 0;
$sum = 0;

for( ; $pivot_b < strlen($pi); ) {

    if($sum < $n) {
        $sum += $pi[$pivot_b++];
    } elseif ($sum > $n) {
        $sum -= $pi[$pivot_a++];
    } else {
        print('Solution found from digit '.$pivot_a.' to '.$pivot_b.'.');
        exit;
    }
}

print('No match was found.');

방법 2

이 구현에서는 하나의 피벗 만 사용하여 숫자 합산을 시작합니다. 합이 원하는 값보다 크면 합을 0으로 재설정하고 피벗을 한 위치로 이동 한 다음 합산을 다시 시작합니다.


$pi = "314159265358979323846264338327950288419716939";

$n = 30;


// Let's sum up all the elements from $pivot until we get the exact sum or a 
// number greater than that. In the latter case, shift the $pivot one place.

$pivot = 0;
$sum = 0;

for($k=0 ; $sum != $n && $k < strlen($pi) ; $k++) {
    $sum += $pi[$k];

    print($pi[$k]);

    if($sum > $n) {
        print(' = '.$sum.'  fail, k='.($pivot+1).PHP_EOL);
        $sum = 0;
        $k = $pivot++;
    } elseif($sum < $n) {
        print("+");
    }
}

print(' = '.$n.' found from digit '.$pivot.' to '.$k.'.');

구현은 그다지 효과적이지 않지만 단계를 설명하려고합니다. 그것은 인쇄

3+1+4+1+5+9+2+6 = 31  fail, k=1
1+4+1+5+9+2+6+5 = 33  fail, k=2
4+1+5+9+2+6+5 = 32  fail, k=3
1+5+9+2+6+5+3 = 31  fail, k=4
5+9+2+6+5+3 = 30 found from digit 4 to 10.

이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.

침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제

에서 수정2021-04-1

몇 마디 만하겠습니다

0리뷰

로그인참여 후 검토

Related 관련 기사

기사