4
CS 인터뷰를 위해 공부하고 있으며 스스로 문제를 해결하고 재귀 적으로 해결하기로 결정했습니다.재귀 파스칼의 삼각형 행 큰 O 비용
내가 해결하려고하는 질문은 다음과 같습니다. 파스칼 삼각형의 n 번째 행을 찾는 재귀 함수를 작성하고 싶습니다.
Ex pascals(1) -> 1
pascals(2) -> 1,1
pascals(3) -> 1,2,1
나는이 기능을 해결했다고 생각합니다. 그것은 기본 함수로 시작하도록 도우미 함수를 필요로합니다.
function int[] nthPascal(int[] a, int n){
// in the case that the row has been reached return the completed array
if(n==1){
return a;
}
// each new row of pascal's triangle is 1 element larger. Ex 1, 11, 121,1331 etc.
int[] newA = new int[a.length()+1];
//set the ends. Technically this will always be 1.
// I thought it looked cleaner to do it this way.
newA[0]=a[0];
newA[newA.length-1]=a[a.length-1];
//so I loop through the new array and add the elements to find the value.
//ex 1,1 -> -,2,- The ends of the array are already filled above
for(int i=1; i<a.length; i++){
// ex 1+1 = 2 for 1,1 -> 1,2,1
newA[i]=a[i-1]+a[i]
}
//call the recursive function if we are not at the desired level
return nthPascal(newA,n-1);
}
/**
*The helper function
*/
public int[] helperPascal(int n){
return nthPascal(int[] {1},n);
}
제 질문은 어떻게 bigO 비용을 찾으십니까?
저는 일반적인 알고리즘 비용과 알고리즘을 찾는 방법을 잘 알고 있습니다. 이 재귀는 나를 혼란스럽게 만듭니다.
분명히 상수가 아니라는 것을 알고 있습니다. n, nlogn 등. 내 생각은 3^n이었습니다.
나는 예를 들어 검색과 발견 : Pascal's Triangle Row Sequence 및 What is the runtime of this algorithm? (Recursive Pascal's triangle)을. 그러나 그들은 내가 믿는 특정 위치에서 특정 요소를 찾으려고 노력하고 있습니다. 나는 파스칼의 삼각형을이 방법으로 구현하고 bigO 비용에 대해 이야기하는 사람을 찾을 수 없었다.
파스칼의 기능을 찾는 재귀 행을 작성하는 더 좋은 방법이 있기 때문에입니까? 각각의 재귀 호출의 경우 :
1)'nthFib'이란 무엇입니까?2) 헬퍼 함수의 올바른 구문은'return nthPascal (new int [] {1}, n);'3) 자바에서는 배열의 길이를 계산할 때'()'를 쓰지 말라. 문자열의 길이를 필요로 함). 4)'intA'는'int [...]'가 아니라'new int [...]'로 선언해야합니다. 나는 이것이 당신의 질문과 관련이 없다는 것을 깨닫습니다. – ajb
1) 오, 죄송합니다. 나는 파스칼이되어야한다고 말했습니다. 파스칼은 처음 엔 피보나치를하고있었습니다. 그리고 오, 자바 도움을 주셔서 감사합니다. 내가 자바로 코딩 한 이후로 꽤 오랜 시간이 걸렸습니다. 그리고 그것을하지 않고 연습하고 있습니다. – Tai