সর্বাধিক গড় মান সহ পাথ


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় সিসকো এপিক সিস্টেম গ্রেআরেঞ্জ এসএপি ল্যাব টাইমস ইন্টারনেট
বিন্যাস ডায়নামিক প্রোগ্রামিং জরায়ু

সমস্যা বিবৃতি

"সর্বাধিক গড় মান সহ পাথ" সমস্যাটি বলে যে আপনাকে একটি 2 ডি অ্যারে বা একটি পূর্ণসংখ্যার একটি ম্যাট্রিক্স দেওয়া হবে। এখন বিবেচনা করুন যে আপনি উপরের-বাম কক্ষে দাঁড়িয়ে আছেন এবং নীচে ডানদিকে পৌঁছানোর প্রয়োজন। গন্তব্যে পৌঁছানোর জন্য আপনাকে নীচের দিকে বা ডানদিকে যেতে হবে। গন্তব্য দ্বারা, এখানে আমরা নীচের ডানদিকে ঘর বোঝায়। একটি শর্ত আছে, আপনার এমন পথে চলতে হবে যা আমাদের সর্বোচ্চ গড় মান দেয়।

উদাহরণ

3 3 // number of rows and columns
1 1 2
10 1 100
10 10 1
22.6

ব্যাখ্যা

সর্বাধিক গড় মান সহ পাথ

আমরা নীচের উপায়ে বাম দিকের ঘরটি থেকে সরে এসেছি: 1-> 10-> 1-> 100-> ১. সুতরাং এটি যোগ করা আমাদের মোট 1 যোগফল দেয় thus গড়টি 113/113 = 5 এর সমান হয় thus

অভিগমন

কেউ একটি ব্রুট ফোর্স পদ্ধতির সাথে আসতে পারে, যা নীচে-ডান কক্ষে পৌঁছানোর সম্ভাব্য সমস্ত উপায় তৈরি করা। একবার আপনি সমস্ত পাথ তৈরি করেছেন। এখন তাদের দিকে এগিয়ে যান এবং পথে থাকা সংখ্যার যোগফলের যোগফল সন্ধান করুন। সুতরাং, একবার আপনার সমস্ত অঙ্কগুলি হবে। এর মধ্যে সর্বোচ্চটি যোগফলটি সন্ধান করুন।

তবে এই পদ্ধতির ব্যবহারটি টিএলই-তে যেতে নিশ্চিত বা সময়সীমা অতিক্রম করবে। কারণ এ জাতীয় পাথের প্রজন্মটি সময়সীমার জটিলতায় বাড়ে। সুতরাং, সময় সীমাবদ্ধতায় সমস্যা সমাধানের জন্য to আমাদের একটি কার্যকর সমাধান খুঁজে বের করা উচিত। কিন্তু, আমরা কীভাবে এটি করতে পারি? ডায়নামিক প্রোগ্রামিং ব্যবহার করে আমরা এটি করতে পারি। এবং সমস্যাটিও সর্বাধিক পাথ সম সমস্যার সাথে খুব সাদৃশ্যপূর্ণ। এই সমস্যায়, আমাদের 2 ডি অ্যারেতে সর্বাধিক পাথ যোগফলটি সন্ধান করতে হবে। আমরা যা করতে যাচ্ছি একই, তবে শেষ পর্যন্ত, আমরা গড় নেব।

সুতরাং ডায়নামিক প্রোগ্রামিং পন্থা আমরা একটি 2 ডি ডিপি অ্যারে তৈরি করব যেখানে ডিপি ম্যাট্রিকের প্রতিটি কক্ষ সর্বাধিক পরিমাণকে বোঝায় যা আমাদের বাম কোণার উপরের অংশ থেকে বর্তমান ঘরের দিকে শুরু করার প্রয়োজন হলে প্রাপ্ত হওয়া সম্ভব। সুতরাং আমরা একটি সাধারণ পুনরাবৃত্তি সম্পর্ক লিখতে পারেন।

// বেস কেস
ডিপি [0] [0] = এ [0] [0]
dp [i] [0] = dp [i-1] [0] + a [i] [0] // এখানে আমি প্রথম সারির থেকে ম্যাট্রিক্সের শেষ সারি পর্যন্ত শুরু করছি
ডিপি [০] [আমি] = ডিপি [০] [আই -১] + এ [০] [আমি] // এখানে আমি ম্যাট্রিক্সের শেষ কলাম পর্যন্ত প্রথম কলাম থেকে শুরু করছি
// পুনরাবৃত্তি সম্পর্কিত
ডিপি [আমি] [জে] = সর্বোচ্চ (ডিপি [আই -১] [জে], ডিপি [আই] [জে -১]) + এ [আমি] [জে] // অন্যান্য সমস্ত কোষের জন্য

সর্বাধিক গড় মান সহ পাথের জন্য সি ++ কোড

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  int n,m; // number of rows and columns in input matrix
  cin>>n>>m;

  int input[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++)
      cin>>input[i][j];
  }

  int dp[n][m];
  dp[0][0] = input[0][0];
  for(int i=1;i<n;i++)
    dp[i][0] = dp[i-1][0] + input[i][0];
  for(int i=1;i<m;i++)
    dp[0][i] = dp[0][i-1] + input[0][i];

  for(int i=1;i<n;i++){
    for(int j=1;j<m;j++)
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + input[i][j];
  }

  // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
  cout<<(dp[n-1][m-1]/((double)n+m-1));
}
3 3
1 1 2
10 1 100
10 10 1
22.6

সর্বাধিক গড় মান সহ পাথের জন্য জাভা কোড

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); int m = sc.nextInt(); // number of rows and columns in input matrix

    int input[][] = new int[n][m];
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++)
        input[i][j] = sc.nextInt();
    }

    int dp[][] = new int[n][m];
    dp[0][0] = input[0][0];
    for(int i=1;i<n;i++)
      dp[i][0] = dp[i-1][0] + input[i][0];
    for(int i=1;i<m;i++)
      dp[0][i] = dp[0][i-1] + input[0][i];

    for(int i=1;i<n;i++){
      for(int j=1;j<m;j++)
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + input[i][j];
    }

    // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
    System.out.print(dp[n-1][m-1]/((double)n+m-1));
  }
}
3 3
1 1 2
10 1 100
10 10 1
22.6

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন ^ 2) যেহেতু আমরা কেবল ইনপুট অ্যারে পেরিয়েছি। এবং আমাদের ডিপিতে রূপান্তরটি কেবল ও (1) সময় নিয়েছিল।

স্পেস জটিলতা ity

ও (এন ^ 2) যেহেতু আমরা একটি 2D ডিপি অ্যারে তৈরি করেছি।