끝에 도달하기 위한 최소 홉 수를 찾는 C 프로그램

최대 수를 나타내는 음수가 아닌 정수 배열이 제공됩니다. 이 요소에서 앞으로 나아갈 수 있는 단계입니다. 포인터는 처음에 배열의 첫 번째 인덱스 [0 인덱스]에 위치합니다. 당신의 목표는 끝까지 도달하는 것입니다 최소 단계 수로 배열에 대한 인덱스입니다. 연결할 수 없는 경우 배열의 끝을 확인한 다음 가장 큰 정수를 인쇄합니다.

순진한 접근 방식은 초기 {main} 구성 요소부터 시작하여 첫 번째 요소에서 액세스할 수 있는 모든 구성 요소를 재귀적으로 호출하는 것입니다. 처음부터 끝까지의 최소 점프 범위는 액세스 가능한 첫 번째 요소에서 끝까지 도달하는 데 필요한 최소 점프 범위를 사용하여 계산됩니다.

minJumps(start, end) = Min ( minJumps(k, end) )
for all k accessible from the start

여기서는 하향식 동적 프로그래밍 접근 방식을 사용합니다. 우리는 Hashmap을 사용하여 하위 문제 결과를 저장하고 솔루션을 만들 때마다 먼저 하위 문제가 해결되었는지 확인한 다음 사용합니다.

Input: { 1, 2, 4, 1, 2, 2, 1, 1, 3, 8 }
Output: Minimum number of steps = 6 {1-->2-->4-->1-->3-->8}

설명

첫 번째 요소는 1이므로 2로만 갈 수 있습니다. 두 번째 요소는 2이므로 최대 2단계(예: 4 또는 1)로 이동할 수 있습니다. 1부터 4까지, 그리고 등등.

최소 숫자를 찾는 동적 프로그래밍 방법의 복잡성 배열의 끝에 도달하기 위한 점프 횟수는 O(n^2)이고, 공간 복잡도는 O(n)

Example

실시간 데모

#include<stdio.h>
#include<limits.h>
int min_steps (int arr[], int n){
   int steps[n];
   int i, j;
   if (n == 0 || arr[0] == 0)
      return INT_MAX;
   steps[0] = 0;
   for (i = 1; i < n; i++){
      steps[i] = INT_MAX;
      for (j = 0; j < i; j++){
         if (i <= j + arr[j] && steps[j] != INT_MAX){
            steps[i] = (steps[i] < (steps[j] + 1)) ? steps[i] : steps[j] + 1;
            break;
         }
      }
   }
   return steps[n - 1];
}
int main (){
   int arr[100];
   int n;
   printf ("Enter size of the array:");
   scanf ("%d", &n);
   printf ("Enter elements in the array:");
   for (int i = 0; i < n; i++){
      scanf ("%d", &arr[i]);
   }
   printf ("Minimum number of steps : %d", min_steps (arr, n));
   return 0;
}

Output

Enter size of array : 7
Enter elements in the array :2 1 1 5 2 1 1
Minimum number of steps : 3

위 내용은 끝에 도달하기 위한 최소 홉 수를 찾는 C 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!