Computer >> Máy Tính >  >> Lập trình >> C ++

Đường dẫn tổng tối thiểu trong mảng 3-D trong C ++

Chúng ta được cung cấp một khối lập phương có thể được tạo thành bằng cách sử dụng mảng 3-D dưới dạng khối lập phương [chiều dài] [chiều rộng] [chiều cao]. Nhiệm vụ là tính toán đường dẫn tổng nhỏ nhất sẽ đạt được bằng cách đi ngang qua khối lập phương và do đó in ra kết quả.

Hãy cho chúng tôi xem các tình huống đầu ra đầu vào khác nhau cho việc này -

Trong - int cube [length] [breadth] [height] ={{{2, 4, 1}, {3, 4, 5}, {9, 8, 7}}, {{5, 3, 2}, { 7, 6, 5}, {8, 7, 6}}, {{3, 2, 1}, {4, 3, 2}, {5, 4, 3}}}

Hết - Đường dẫn Tổng tối thiểu Trong Mảng 3-D là:15

Giải thích - chúng ta được cho một hình lập phương có chiều dài, chiều rộng và chiều cao. Bây giờ, chúng ta sẽ tính toán đường dẫn tổng nhỏ nhất trong mảng 3-D. Vì vậy, nó sẽ bắt đầu từ 2 + 4 + 1 + 3 + 5, tức là 15.

Trong - int cube [length] [breadth] [height] ={{{1, 2}, {7, 8}}, {{3, 5}, {9, 16}}}

Hết - Đường dẫn Tổng tối thiểu Trong Mảng 3-D là:24

Giải thích - chúng ta được cho một hình lập phương có chiều dài, chiều rộng và chiều cao. Bây giờ, chúng ta sẽ tính toán đường dẫn tổng nhỏ nhất trong mảng 3-D. Vì vậy, nó sẽ bắt đầu từ 1 + 2 + 5 + 16, tức là 24.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

  • Nhập một mảng 3-D để tạo thành một khối với các giá trị kiểu số nguyên. Truyền dữ liệu vào hàm dưới dạng Minimum_SubPath (khối lập phương).

  • Bên trong hàm Minimum_SubPath (khối lập phương)

    • Tạo một mảng có cùng kích thước với khối lập phương và khởi tạo arr [0] [0] [0] thành khối lập phương [0] [0] [0].

    • Bắt đầu vòng lặp FOR từ i đến 1 cho đến khi chiều dài của một khối lập phương và đặt arr [i] [0] [0] thành arr [i-1] [0] [0] + cube [i] [0] [0].

    • Bắt đầu vòng lặp FOR từ j đến 1 cho đến chiều rộng của hình lập phương và đặt arr [0] [j] [0] thành arr [0] [j-1] [0] + cube [0] [j] [0]

    • Bắt đầu vòng lặp FOR từ k đến 1 cho đến khi chiều cao của hình lập phương và đặt arr [0] [0] [k] thành arr [0] [0] [k-1] + cube [0] [0] [k]

    • Bắt đầu vòng lặp FOR từ i đến 1 cho đến chiều dài của một khối và bắt đầu một vòng lặp khác FOR từ j đến 1 cho đến độ rộng của một mảng và đặt min_val thành Minimum (arr [i-1] [j] [0], arr [i] [ j-1] [0], INT_MAX) và arr [i] [j] [0] thành min_val + cube [i] [j] [0]

    • Bắt đầu vòng lặp FOR từ i đến 1 cho đến chiều dài của một khối và bắt đầu một vòng lặp khác FOR từ k đến 1 cho đến chiều cao của một mảng và đặt min_val thành Minimum (arr [i-1] [0] [k], arr [i] [ 0] [k-1], INT_MAX) và arr [i] [0] [k] =min_val + cube [i] [0] [k]

    • Bắt đầu vòng lặp FOR từ k đến 1 cho đến chiều cao của một khối và bắt đầu một vòng lặp khác FOR từ j đến 1 cho đến chiều rộng của một mảng và đặt min_val thành Minimum (arr [0] [j] [k-1], arr [0] [ j-1] [k], INT_MAX) và arr [0] [j] [k] =min_val + cube [0] [j] [k]

    • Bắt đầu vòng lặp FOR từ i đến 1 cho đến chiều dài của một khối và bắt đầu một vòng lặp khác FOR từ j đến 1 cho đến chiều rộng của một mảng và bắt đầu một vòng lặp khác từ k đến 1 cho đến chiều cao của một khối và đặt min_val thành Minimum (arr [i-1 ] [j] [k], arr [i] [j-1] [k], arr [i] [j] [k-1]) và arr [i] [j] [k] =min_val + cube [ i] [j] [k]

    • Trả về arr [length-1] [breadth-1] [height-1]

  • Bên trong hàm Minimum (int a, int b, int c)

    • Kiểm tra NẾU a nhỏ hơn b và a nhỏ hơn c rồi trả về a.

    • Khác, trả lại c

    • Nếu khác IF, b nhỏ hơn c thì trả về b

    • Khác, trả lại c

Ví dụ 

#include<bits/stdc++.h>
using namespace std;
#define length 3
#define breadth 3
#define height 3

int Minimum(int a, int b, int c){
   if(a < b){
      if(a < c){
         return a;
      }
      else{
         return c;
      }
   }
   else if(b < c){
      return b;
   }
   else{
      return c;
   }
}
int Minimum_SubPath(int cube[][breadth][height]){
   int i, j, k;
   int arr[length][breadth][height];
   arr[0][0][0] = cube[0][0][0];

   for(i = 1; i < length; i++){
      arr[i][0][0] = arr[i-1][0][0] + cube[i][0][0];
   }
   for(j = 1; j < breadth; j++){
      arr[0][j][0] = arr[0][j-1][0] + cube[0][j][0];
   }
   for(k = 1; k < height; k++){
      arr[0][0][k] = arr[0][0][k-1] + cube[0][0][k];
   }
   for(i = 1; i < length; i++){
      for(j = 1; j < breadth; j++){
         int min_val = Minimum(arr[i-1][j][0], arr[i][j-1][0], INT_MAX);
         arr[i][j][0] = min_val + cube[i][j][0];
      }
   }
   for(i = 1; i < length; i++){
      for(k = 1; k < height; k++){
         int min_val = Minimum(arr[i-1][0][k], arr[i][0][k-1], INT_MAX);
         arr[i][0][k] = min_val + cube[i][0][k];
      }
   }
   for(k = 1; k < height; k++){
      for(j = 1; j < breadth; j++){
         int min_val = Minimum(arr[0][j][k-1], arr[0][j-1][k], INT_MAX);
         arr[0][j][k] = min_val + cube[0][j][k];
      }
   }
   for(i = 1; i < length; i++){
      for(j = 1; j < breadth; j++){
         for(k = 1; k < height; k++){
            int min_val = Minimum(arr[i-1][j][k], arr[i][j-1][k], arr[i][j][k-1]);
            arr[i][j][k] = min_val + cube[i][j][k];
         }
      }
   }
   return arr[length-1][breadth-1][height-1];
}
int main(){
   int cube[length][breadth][height] = { { {2, 4, 1}, {3, 4, 5}, {9, 8, 7}},
      { {5, 3, 2}, {7, 6, 5}, {8, 7, 6}},
      { {3, 2, 1}, {4, 3, 2}, {5, 4, 3}}};
   cout<<"Minimum Sum Path In 3-D Array are: "<<Minimum_SubPath(cube);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau 

Minimum Sum Path In 3-D Array are: 15