하나의 고리, n 개의 점 이 있 습 니 다. 0 시 에서 출발 하여 k 보 를 거 쳐 원점 으로 돌아 가 는 방법 이 몇 가지 가 있 습 니까?

하나의 링, n 개의 점 이 있 습 니 다. 매번 한 걸음 만 걸 을 수 있 습 니 다. 원점 0 에서 출발 하여 k 보 를 거 쳐 원점 으로 돌아 가 는 방법 은 몇 가지 가 있 습 니까?
                     0
                  /         \
                 /           \
              2  ---------1    
지금 링 의 점 번 호 를 0 에서 n - 1, 즉 0 시 에서 출발 하여 다시 0 시 로 돌아 가 는 방법 은 몇 가지 가 있 습 니까?
우 리 는 다시 0 시 로 돌아 가면 오른쪽 에서 돌아 올 수도 있 고 왼쪽 에서 돌아 올 수도 있다 는 것 을 생각 할 수 있다. 즉, 먼저 옆 에 있 는 한 점 에 도착 해서 얼마나 돌아 오 는 방법 이 있 는 지 보면 된다.그래서 동태 계획 의 사상 을 활용 하여 우 리 는 전달 식 을 다음 과 같이 쓸 수 있다.
d(k, j) = d(k-1, j-1) + d(k-1, j+1);
d (k, j) 는 점 j 에서 k 보 로 원점 0 에 도달 하 는 방법 수 를 나타 내기 때문에 그 가 인접 한 점 이 k - 1 보 를 거 쳐 원점 으로 돌아 가 는 문제 로 전환 하여 문제 의 규 모 를 축소 할 수 있다.고리 의 문제 이기 때문에 j - 1, j + 1 은 0 에서 n - 1 의 범 위 를 초과 할 수 있 기 때문에 우 리 는 전달 식 을 다음 과 같이 바 꿀 것 이다.
 d(k, j) = d(k-1, (j-1+n)%n) + d(k-1, (j+1)%n);
문 제 는 k 단계 에서 k - 1 단계 로 바 뀌 었 기 때문에 프로그램 을 쓸 때 우 리 는 k 가 0 에서 점점 증가 하 는 순환 에 따라 쓴다. 그러면 k 단 계 를 계산 할 때 k - 1 단계 의 결 과 를 직접 사용 할 수 있다.
실례 는 다음 과 같다. n = 3, k = 4
k 증대 에 따라 계산 하 다
 
0
1
2
k=0
1
0
0
k=1
0
1
1
k=2
2
1
1
k=3
2
3
3
k=4
6
5
5
계산 k 단 계 는 k - 1 단계 의 값 과 만 관련 이 있 기 때문에 두 줄 의 배열 로 저장 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다:

/**
 *     ，  n  ，  0  ，       ，  k ，           
 */

#define N 100

int get_step_num(int n, int k)
{
	if (n==1){
		return 1;
	}

	if (n==2){
		if (k%2==0)
			return 1;
		else 
			return 0;
	}

	int arr[2][N] = {0};
	int flag = 1, i = 0, j = 0;

	arr[0][0] = 1;
	for (i=1; i