javascript - 알고리즘: 주어진 숫자에서 합이 이 숫자와 같을 수 있는 방법은 몇 가지입니까?

Question

예를 들어 8은 4 더하기 4, 2 더하기 5 더하기 1 등이 될 수 있습니다. 길은 몇 개 있고, 모든 길을 함께 나열하세요

Answer 1

1. 실수에는 답이 없습니다

2. 음수에는 해결책이 없습니다

3. 숫자의 개수가 아주 단순해야 한다면, 2개라면 그 중 절반을 열거하고, 2개 이상이라면 아래 알고리즘을 참고해서 고정된 길이로 수정하면 됩니다

4. 숫자가 확실하지 않으면 0이 존재할 수 없으니 참고하세요

수식의 길이에 따라 재귀를 순회합니다. 정리할 수 있고 효율성도 상당하기 때문입니다

으아악

처음에 제가 생각한 방식은 매번 1~n 수식 결과를 재귀적으로 캐시하는 것이었습니다. 공간을 낭비하고 반복적으로 탐색하는 데 매우 느립니다. 으아악

Answer 2

실수라면... 이 질문은 말이 안 됩니다

2개씩 덧셈을 작성하세요

여기에 재귀를 작성하세요... 저는 재귀에 대해 조금밖에 모릅니다. .

R

으아악

S

Answer 3

조건을 충분히 주지 않았다고 해서 해결 방법은 없고, 양의 정수로 하면 됩니다. 가장 간단한 재귀에서는 시간 복잡도가 허용되지 않습니다. n=100인 프로그램은 즉시 충돌합니다
제가 사용하는 동적 프로그래밍은 행렬을 사용하여 s[i,j]를 저장하여 해당 결과를 저장하므로 매번 이전 결과를 다시 계산할 필요가 없습니다.
그 중 si, j, i=n, ​​j로 시작하는 조합의 개수, 0이 되는 경우가 없으므로 s[i,0]을 넣은 것이 s[i,1]입니다. +s[i,2]+. ..+s[i,j]
의 결과, 예를 들어 s[5,1]은 n=5, 1+1+1+1+1, 1+1+를 의미합니다. 1+2, 1+1+1+ 3, 1+1+1+4, 1+2+2, 5가지 경우,
실제로 이 방법에 따르면 s[i,1]임을 쉽게 알 수 있습니다. =s[i-1,0], 즉
s [i,0]=s[i,1]+s[i,2]+...+s[i,j]
s[i,0] =s[i-1,0]+s[i ,2]+...+s[i,j]
그 중에서 반복되는 조건을 제거하면 s[i,i]만 계산하면 되는데,
s[i,0]=s[i-1,0] +...+s[i,i]
s[i,i]=1이므로
s[i,2]만 계산하면 됩니다. +s[i,3]+...+s[i 결국 ,i-1] 결과
다음 숫자 조합은 이전 조합으로 이어지기 때문에
s[i, 1] = s[i-1,0],
s[i,j] = s[i-j,k], 여기서 j > 1, j <= k <= i
다음은 의사 코드입니다

으아악

다음은 PHP로 구현되었습니다

으아악

si,j>1을 계산하면 이전 조합 개수를 미리 저장할 수 있고 공간을 통해 시간을 교환할 수 있어 더욱 최적화할 수 있을 것 같습니다.
도움이 되길 바랍니다

Answer 4

이것에는 분할 함수 P라는 함수가 있습니다
이전에 이것과 관련된 작은 알고리즘 질문을 한 적이 있습니다: 신의 90억 이름
하지만 제 질문에는 정수 분할 수만 필요하고 특정 조합은 포함되지 않습니다. 위 기사에 관련됨 拆分函数P

Answer 5

이런 종류의 알고리즘 논리에는 특정 제한이 있는 것이 가장 좋습니다. 요소 번호와 대상 번호의 지정된 수는 있다고 잠정적으로 생각합니다.

자바 버전:

으아악

C# 버전:

으아악

루비 버전:

으아악

파이썬 버전:

으아악

주어진 조건이 양수이면 배열을 1~N으로 변경합니다. 음수에도 동일한 논리가 적용됩니다.

Answer 6

이 알고리즘은 비교적 간단합니다.
분해할 숫자가 18과 같은 짝수이면 거의 결과는 (18/2+1) 조합이 됩니다. 그러면 첫 번째 숫자는 0부터 증가하고 두 번째 숫자는부터 시작됩니다. 최대값을 줄이면 됩니다
홀수 17이면 1을 더한 후 2로 나누면 다시 (18/2)가 되고, 그러면 첫 번째 숫자는 0부터 증가하기 시작하고, 두 번째 숫자는 최대값에서 감소합니다.