ዱካ ከከፍተኛው አማካይ እሴት ጋር


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ Cisco Epic ስርዓቶች ግሬይ ብርቱካናማ የ SAP ላብራቶሪዎች ታይምስ በይነመረብ
ሰልፍ ተለዋዋጭ ፕሮግራም ማትሪክስ

የችግሩ መግለጫ

ችግሩ “በከፍተኛው አማካይ እሴት ያለው ጎዳና” የ 2 ዲ ድርድር ወይም የቁጥር ቁጥሮች ማትሪክስ እንደተሰጠዎት ይናገራል። አሁን ከላይ-ግራ ህዋስ ላይ እንደቆሙ ያስቡ እና ወደ ታችኛው ቀኝ መድረስ ያስፈልግዎታል ፡፡ መድረሻውን ለመድረስ ወደ ታችኛው አቅጣጫ ወይም ወደ ትክክለኛው አቅጣጫ መሄድ ያስፈልግዎታል ፡፡ በመድረሻ ፣ እዚህ በታችኛው የቀኝ ሕዋስ ማለታችን ነው ፡፡ አንድ አማካይ ሁኔታ አለ ፣ ይህም ከፍተኛውን አማካይ እሴት በሚሰጠን በእንደዚህ ዓይነት መንገድ መሄድ ያስፈልግዎታል።

ለምሳሌ

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

ማስረጃ

ዱካ ከከፍተኛው አማካይ እሴት ጋር

ከላይ ግራ-ግራው ክፍል በሚከተለው መንገድ ተዛወርን-1-> 10-> 1-> 100-> 1. ስለዚህ ይህንን መደመር ጠቅላላ ድምር 113 ይሰጠናል አማካይ አማካይ ስለዚህ ከ 113/5 = 22.6 ጋር እኩል ይሆናል ፡፡

ቀረበ

አንድ ሰው የጭካኔ ኃይል አቀራረብን መምጣት ይችላል ፣ ይህም ወደ ታችኛው የቀኝ ሕዋስ ለመድረስ ሁሉንም ሊሆኑ የሚችሉ መንገዶችን ማመንጨት ነው ፡፡ አንዴ ሁሉንም ዱካዎች ከፈጠሩ። አሁን በእነሱ ላይ ይሂዱ እና በመንገድ ላይ የሚተኛውን የቁጥር ቁጥሮች ድምር ያግኙ። ስለዚህ አንዴ አንዴ ጠቅላላ ድምር ካለዎት ፡፡ ከእነዚህ መካከል ከፍተኛውን ድምር ይፈልጉ ፡፡

ግን ይህንን አካሄድ መጠቀም ወደ TLE ለመግባት እርግጠኛ ነው ወይም የጊዜ ገደቡን ይበልጣል ፡፡ ምክንያቱም እንዲህ ያሉት መንገዶች መፈጠር ወደ ጊዜያዊ ውስብስብነት ይመራቸዋል ፡፡ ስለዚህ በጊዜ እጥረቶች ውስጥ ያለውን ችግር ለመፍታት ፡፡ ቀልጣፋ መፍትሄ መፈለግ አለብን ፡፡ ግን ፣ እኛ እንዴት ማድረግ እንችላለን? ተለዋዋጭ ፕሮግራምን በመጠቀም ያንን ማድረግ እንችላለን ፡፡ ችግሩ ደግሞ ከከፍተኛው የመንገድ ድምር ችግር ጋር በጣም ይመሳሰላል ፡፡ በዚያ ችግር ውስጥ በ 2 ዲ ድርድር ውስጥ ከፍተኛውን የመንገድ ድምር መፈለግ አለብን ፡፡ እኛ የምናደርገው ተመሳሳይ ነገር ነው ፣ ግን በመጨረሻ አማካይ እንወስዳለን ፡፡

ስለዚህ ለ ተለዋዋጭ ፕሮግራም አቀራረብ. ከዲፕል ማትሪክስ ውስጥ እያንዳንዱ ሕዋስ ከላይኛው ግራ ጥግ ጀምሮ እስከ አሁኑ ህዋስ ድረስ መጀመር ከፈለግን ሊደረስበት የሚችል ከፍተኛውን ድምር የሚያመላክት ባለ 2 ዲ ዲፒ ድርድር እንፈጥራለን ፡፡ ስለዚህ አጠቃላይ ድግግሞሽ ግንኙነትን መጻፍ እንችላለን።

// የመሠረት ጉዳዮች
dp [0] [0] = አንድ [0] [0]
dp [i] [0] = dp [i-1] [0] + a [i] [0] // እዚህ እጀምራለሁ ከ 1 ኛ ረድፍ ጀምሮ እስከ የመጨረሻው ረድፍ ማትሪክስ እጀምራለሁ
dp [0] [i] = dp [0] [i-1] + a [0] [i] // እዚህ እጀምራለሁ ከ 1 ኛ አምድ እስከ የመጨረሻው ማትሪክስ አምድ እጀምራለሁ
// ተደጋጋሚ ግንኙነት
dp [i] [j] = max (dp [i-1] [j], dp [i] [j-1]) + a [i] [j] // ለሁሉም ሌሎች ህዋሳት

ከፍተኛ አማካይ ዋጋ ያለው ዱካ C ++ ኮድ

#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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (N ^ 2) በግብዓት ድርድር ላይ በቀላሉ ስለ ተሻገርን ፡፡ በእኛ ዲ ፒ ውስጥ ያለው ሽግግር O (1) ጊዜ ብቻ ወስዷል ፡፡

የቦታ ውስብስብነት

ኦ (N ^ 2) የ 2 ዲ ዲፒ ድርድር ስለፈጠርን ፡፡