동적 프로그래밍 : 사이의 숫자 계산

Question

두 숫자 X 및 Y이 주어지면 숫자의 절반 이상이 같은 숫자가 몇 개 포함되어 있습니까? 예를 들어 1122 및 4444이 작동하는 반면 11234 및 112233은 작동하지 않습니다.

물론, 가장 간단한 방법은 Y에 1 X 및 증가에 모든 방법을 시작한 다음 각 번호를 확인하는 것입니다,하지만 X에 대한 경계로, 너무 느리고 Y는 100 및 10^18 사이 . 나는 그것이 동적 프로그래밍의 일부 형태이며, 숫자를 표현하기 위해 문자열을 사용해야한다고 생각하지만 훨씬 더 많이 얻을 수는 없다.

도움이 필요합니다. 감사!

Answer 1

분명히 다음 범위의 모든 숫자를 고려하여이 작업을 수행하지 않아도됩니다. 대신 번으로 번으로 생각하십시오. 예를 들어, 모든 길이의 숫자를 주어진 한정 수를 생성하는 함수를 설계하십시오. 예를 들어

, 5 자리, 당신은 2의 적어도 세 1의, 또는 세 개의 모든 숫자를 원하거나 ... 당신은 한 번에, 또는 어떻게 당신이 정확히 세 가진 사람들을 분리 할 필요가 있다고 할 수있다 그보다 더 많은 사람들이 1 명이야? 이제 당신이 그것에 대해 생각했다고

, 이것에 대해 생각하는 대신 이 모든 숫자, 단지 수을 생성하는. 예를 들어 세 개의 1과 두 개의 다른 숫자 자릿수의 경우 다른 자릿수가 9 * 9 쌍이됩니다 (11122 등을 두 번 계산하지 않도록주의하십시오). 가능한 한 다른 두 자릿수의 스왑을 사용하여 1을 10 가지 방식으로 정렬 할 수 있습니다. 문제는 숫자의 짝수 수량과 조금 다른

참고 : 더블 카운트 반반 번호를 방지하기 위해이 같은 111222.

않는 한 당신은 움직이는거야?

---

코멘트 03 TO 응답 12월

bobjoe628 @ :이 완전한 알고리즘 수 없습니다; 오히려, 당신을 시작하게하는 제안입니다. 예, 처리 할 몇 가지 조합 문제가 있습니다. 11122233에 대해서는 귀하의 우려를 이해할 수 있을지 확신하지 못합니다. 이러한 순열 문제와 마찬가지로 형제와 교환 할 수있는 각 자릿수를 처리해야합니다. 1을 배포하는 10C5 방법이 있습니다. 나머지 지점에는 2C를 배포하는 5C3 방법이 있습니다. 나머지 두 슬롯은 3 분 3 초입니다. 쉽게 사용할 수있는 알고리즘 (예 : 브라우저 검색)은 이러한 음모를 처리합니다.

숫자를 생성하는 알고리즘을 작성할 수 있습니다. 하나의 숫자 조합 만 필요하므로 예제를 제공 한 것처럼 숫자를 오름차순으로 생성하는 것이 안전합니다. 1111122233. 그 조합 코드는 그 숫자의 모든 순열을 포함해야합니다.

마지막으로 대부분의 언어는 사용자를 위해 순열과 조합을 수행하는 패키지를 지원합니다.

Answer 2

나는 몇 가지 단계를 설명합니다 :

첫 번째 단계 :

을 0 to X 및 0 to Y-1 사이에 계산에 의해 X 및 Y는 항상 간단하게 사이의 범위 문제의이 종류를 해결하기 위해, 다음을 빼기 결과. 당신이 0과 N 사이의 동일한 절반 이상 자신의 자리가 숫자를 계산 f(N) 같은 기능이있는 경우 즉, 당신의 최종 결과는 다음과 같습니다

f(X) - f(Y-1) 

두 번째 단계 :

다음으로 f (N)을 계산해야합니다. 이 함수를 2 개의 하위 함수로 나눕니다. 하나는 N과 같은 자릿수의 결과를 계산하기위한 것이고 다른 하나는 N보다 작은 수의 정규화 된 수를 계산하는 것입니다 (f_less라고 부름) . 예 : N이 19354 인 경우 0에서 9999 사이의 정규화 된 숫자를 계산 한 다음 다른 방법으로 10000에서 19354 사이의 즐겨 찾기 숫자를 계산합니다. 결과가 합산 된 후입니다. 다음은이 두 가지 방법을 구현하는 방법을 설명합니다.

세 번째 단계 : 여기

, 우리는 방법을 f_less 계산합니다. 당신은 수학으로 그것을 할 수 있지만, 나는 항상 이러한 작업을 해결하기위한 간단한 DP를 작성하는 것을 선호합니다. memoization을 사용할 수 있는지 또는 일부 루프를 사용하여 상향식으로 만들 수 있는지 여부에 관계없이 재귀 함수를 작성합니다 (필자는 연습으로 남겨 둘 것입니다).

long long f_less(int curDigit, int favNum, int favNumCountSoFar, int nonFavNum, int nonFavNumCountSoFar, int maxDigit){ 
    if(curDigit == maxDigit){ 
     //for numbers with even maxDigit there may be a case when we have 2 favorite numbers 
     //and we should count them only once. like 522552 
     if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1; 
     if(2*favNumCountSoFar >= maxDigit) return 2; 
     return 0; 
    } 
    long long res = 0; 
    for(int i=(curDigit==0?1:0);i<=9;++i) //skip the leading zero 
     if(i==favNum) 
      res += f_less(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar,maxDigit); 
     else 
      res += f_less(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1),maxDigit); 
    return res; 
} 

그리고 0에서 9까지의 모든 숫자를 호출

long long res = 0; 
for(int maxDigit = 1; maxDigit < NUMBER_OF_DIGITS(N); ++maxDigit) 
    for(int favNumber = 0; favNumber < 10; ++favNumber) 
     res += f_less(0, favNumber, 0, -1, 0, maxDigit); 

네 번째 단계 :

마지막으로 우리가 f_equal을 계산해야합니다. 여기서 우리는 재귀 함수에서 여전히 N 이하의 범위에 있는지 여부를 확인하기 위해 숫자를 문자열로 유지해야합니다. 여기 f_equal의 구현이다 (다시 메모이 제이션을 사용하거나 상향식 (bottom-up) 할) :

string s = NUM_TO_STRING(N); 
int maxDigit = s.size(); 
long long f_equal(int curDigit, int favNum, int favNumCountSoFar,int nonFavNum, int nonFavNumCountSoFar, bool isEqual){ //isEqual checks that whether our number is equal to N or it's lesser than it 
    if(curDigit == maxDigit){ 
     //for numbers with even maxDigit there may be a case when we have 2 favorite numbers 
     //and we should count them only once. like 522552 
     if(favNumCountSoFar*2 == maxDigit && favNumCountSoFar == nonFavNumCountSoFar) return 1; 
     if(2*favNumCountSoFar >= maxDigit) return 2; 
     return 0; 
    } 
    long long res = 0; 
    for(int i=(curDigit==0?1:0);i<=9;++i){ //skip the leading zero 
     if(isEqual && i>(s[curDigit]-'0')) break; 
     if(i==favNum) 
      res += f_equal(curDigit+1, favNum, favNumCountSoFar + 1, nonFavNum, nonFavNumCountSoFar, isEqual && (i==(s[curDigit]-'0'))); 
     else 
      res += f_equal(curDigit+1, favNum, favNumCountSoFar, i, (i==nonFavNum?nonFavNumCountSoFar+1:1), isEqual && (i==(s[curDigit]-'0'))); 
    } 
    return res; 
} 

을 그리고 전화 :

는

long long res = 0; 
for(int favNumber = 0; favNumber < 10; ++favNumber) 
    res += f_equal(0, favNumber,0, -1, 0, true); 

최종 결과는 res/2입니다. 이 코드는 테스트를 거쳤으며 잘 작동합니다.

Answer 3

부분 결합 응답입니다. 함수를 사용하여 완전한 대답을 구성하는 방법을 생략합니다.

(더 정교한 의견 동일한 코드 여기를 참조하십시오 https://repl.it/@gl_dbrqn/AllSteelblueJuliabutterfly), 가장 왼쪽의 숫자 (들), L 고정

L의 오른쪽에 R 자리 숫자에, 우리는 얼마나 많은 계산할 수 있습니다 우리는에 의해 (N/2) 또는 숫자 d 더 배포 할 수있는 방법 :

파이썬 코드

import math, operator, collections 

# Assumes L has at least one digit set 
# f({'string':'12', 'digit_frequencies':[0,1,1,0,0,0,0,0,0,0], 'num_digit_frequencies': 2}, 6) 
def f(L, N): 
    R = N - len(L['string']) 

    count = 0 
    counted = False 

    for digit_frequency in L['digit_frequencies']:  
    start = int(math.ceil(N/2.0)) - digit_frequency 
    if start > R: 
     continue 

    for i in xrange(start, R + 1): 
     if not (N & 1) and not counted: 
     if L['num_digit_frequencies'] == 1 and not digit_frequency and i == N/2: 
      count = count - choose(R, i) 

     if L['num_digit_frequencies'] == 2 and digit_frequency and not any([x > N/2 for x in L['digit_frequencies']]) and i + digit_frequency == N/2: 
      count = count - choose(R, i) 
      counted = True 

     m = 9**(R - i) 
     n = R - i + 1 
     k = i 

     count = count + m * choose(n + k - 1, k) 

    return count 


# A brute-force function to confirm results 
# check('12', 6) 
def check(prefix, length): 
    result = [x for x in xrange(10**(length - 1), 10**length) if len(str(x)) == length and str(x).startswith(prefix) and isValid(str(x))] 

    print result 
    return len(result) 

def isValid(str): 
    letters = collections.Counter(str) 
    return any([x >= math.ceil(len(str)/2.0) for x in letters.values()]) 


# https://stackoverflow.com/questions/4941753/is-there-a-math-ncr-function-in-python 
def choose(n, r): 
    r = min(r, n-r) 
    if r == 0: return 1 
    numer = reduce(operator.mul, xrange(n, n-r, -1)) 
    denom = reduce(operator.mul, xrange(1, r+1)) 
    return numer//denom 

Answer 4

를 숫자 0은 단지 소입니다 맞다. 실제로는 앞에 오는 0이 무한대이며 0보다 작은 숫자 (예 : 소수점 이하)가 있습니다 (예 : ...000000.000000...).

모든 정수의 경우 소수점 앞에 0이 아닌 숫자가 있으므로 소수점 다음에 숫자가 0 초 이상있는 것이 분명합니다. 따라서 모든 정수를 계산할 수 있습니다.

0에서 1 사이의 숫자는 무한합니다. 소수점 뒤에 0이 아닌 숫자가 있기 때문에 이들 모두에는 적어도 소수점 왼쪽에 0이 있습니다. 0과 -1 사이의 숫자에도 똑같이 적용됩니다.

컴퓨터가 저장할 수있는 거의 모든 부동 소수점 숫자에 대해 앞과 뒤의 모든 0을 취소 할 수있는 비트가 부족합니다.

카운트 할 수없는 유일한 숫자는 양수 및 음수 무한대이며 일부는 비 합리적인 숫자이며 모두 < = 1 또는> = -1입니다.

코드 :

float getCount(int x, int y) { 
    if(x == y) return 0.0; // Special case (no numbers are between x and y) 
    return INFINITY;  // The closest value to the correct answer that a computer can use 
}