숫자 n이 있다고 가정합니다. x =rand() mod n을 고려하십시오. 여기서 rand() 함수는 0에서 10^100(둘 다 포함) 사이의 정수를 무작위로 균일하게 생성합니다. 그리고
$$Y =\sqrt{x+\sqrt{x+\sqrt{x+\sqrt{x+...}}}}$$
Y의 기대값을 찾아야 합니다. n의 값은 1과 5*10^6 범위에 있습니다.
따라서 입력이 n =5와 같으면 출력은 1.696
이 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 오류:=2235.023971557617
- 최대_n :=5 * 10^6
- pref :=목록은 처음에 하나의 0을 포함합니다.
- 1 ~ 5 * 10^6 범위의 i에 대해
- 삽입(pref의 마지막 항목 + (1 +(4*i + 1)^0.5) * pref 끝에 0.5
- n
- 반환 pref[n - 1] / n
- 총계 :=(4 *(n - 1) + 5)^1.5 / 6 - 5^1.5 / 6 - 오류
- ans :=0.5 + 총계 /(2 * n)
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n): err = 2235.023971557617 max_n = 5 * 10**6 pref = [0] for i in range(1, 5 * 10**6): pref.append(pref[-1] + (1 + (4 * i + 1)**0.5) * 0.5) if n < max_n: return pref[n - 1] / n else: total = (4 * (n - 1) + 5)**1.5 / 6 - 5**1.5 / 6 - err ans = 0.5 + total / (2 * n) return ans n = 5 print(solve(n))
입력
5
출력
1.69647248786