숫자 n이 있다고 가정합니다. 다음과 같은 방법으로 길이가 n + 1인 배열 A를 생성해야 합니다. -
-
A[0] =0
-
A[1] =1
-
A[2 * i] =A[i] if 2 <=2 * i <=n
-
A[2 * i + 1] =A[i] + A[i + 1] if 2 <=2 * i + 1 <=n
마지막으로 배열 nums에서 최대 수를 찾아야 합니다.
따라서 입력이 n =5와 같으면 출력은 3이 됩니다.
-
A[0] =0
-
A[1] =1
-
A[2] =A[1] =1
-
A[3] =A[1] + A[2] =1 + 1 =2
-
A[4] =A[2]=1
-
A[5] =A[2] + A[3] =1 + 2 =3
-
A[6] =A[3] =2
따라서 최대값은 3입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
A :=0에서 n까지의 새 목록
-
A의 각 요소 i에 대해 수행
-
i가 0과 같거나 i가 1과 같으면
-
다음 반복으로 이동
-
-
그렇지 않으면 내가 짝수일 때
-
A[i] :=A[i/2의 정수]
-
-
그렇지 않으면
-
A[i] :=A[i/2의 정수] + A[(i/2의 정수) + 1]
-
-
-
A
의 최대 요소를 반환
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n):A =list(range(0,n+1)) for i in A:if i ==0 or i ==1:elif i%2 ==0 계속:A[i ] =A[i//2] else:A[i] =A[i//2] + A[(i//2) + 1] return max(A)n =5print(solve(n))입력
5출력
3