1
내가 웹 사이트에이 문제를 직면하고 내가 아주 출력을 이해할 수 없다, 내가 그것을 이해 도와주세요 -정렬 알고리즘 : 출력
보고 정렬, 그것은 분류 될 때까지 무작위로 순서를 섞어 바보 알고리즘 . 그러나 여기서 우리는 약간의 변경을했습니다. 그래서 마지막 셔플 후에 몇 가지 첫 번째 요소가 올바른 위치에 끝나면 수정하고 더 이상 그 요소들을 섞지 않을 것입니다. 올바른 요소가있는 경우 마지막 요소에 대해 동일한 작업을 수행합니다. 예를 들어, 초기 시퀀스가 (3, 5, 1, 6, 4, 2)이고 하나의 셔플을 얻은 후에 (1, 2, 5, 4, 3, 6) 우리는 1, 2 및 6을 유지하고 같은 알고리즘을 사용하여 정렬 (5, 4, 3). 개량 된 알고리즘이 최초의 n 개의 자연수의 순서를 정렬하기위한 예상되는 셔플의 양을 계산합니다.
입력 :
2
6
10
출력 : 개선 된 알고리즘이 필요 셔플의 예상 된 양의 형태로 제 n은 자연수의 순서를 정렬하기 위해 각 테스트 케이스 출력
2
1826/189
877318/35343
환원 불가능한 분수. 나는 출력을 이해할 수 없다. 좋아
입력은 어떻게됩니까? 초기 서열이 (2, 6, 10)입니까? 그것은 이미 정렬되어 있습니다 ... –
@SimeonVisser : 2는 입력이 처음 2 개의 자연수를 포함한다는 것을 의미하지만, 마찬가지로 정렬되지 않은 오프 코스는 6 번째 자연수를 의미합니다. –
출력 값이 유리수가 될 수 있습니까? 즉, [1,2,3,4,5,6]을 주문하기 위해 요구되는 수정 된보고 르조 총 수가 186/189 ~ = 9.66 배가되는 것인가? 그 기대 값을 계산하는 좋은 방법을 생각할 수 없으므로이 의미를 테스트 할 수는 없지만 첫 번째 값인 2는 시퀀스 [1, 2]에 대한 올바른 대답입니다 ('1 + sum (1)/1.nfinity에서 n에 대해 n^2)'). – Blckknght