N සංඛ්‍යා වල ගුණ කිරීමේ අවම එකතුව  


දුෂ්කරතා මට්ටම Hard
නිතර අසනු ලැබේ ඇක්සෙන්චර් කළු ගල් GE සෞඛ්යාරක්ෂණය ජේපී මෝගන් පේපෑල්
අරා ගතික වැඩසටහන්කරණය

“N සංඛ්‍යා වල ගුණ කිරීමේ අවම එකතුව” යන ගැටළුවෙහි දැක්වෙන්නේ ඔබට n ලබා දී ඇති බවයි නිඛිල වරකට යාබදව ඇති මූලද්‍රව්‍ය දෙකක් ගෙන එක් අංකයක් ඉතිරි වන තෙක් ඒවායේ එකතුව 100 නැවත ලබා දීමෙන් ඔබ සියලු සංඛ්‍යා වල ගුණ කිරීමේ එකතුව අවම කළ යුතුය.

උදාහරණයක්  

N සංඛ්‍යා වල ගුණ කිරීමේ අවම එකතුවපින්

10 20 30
1100

පැහැදිලි කිරීම

පළමුව, අපි 10 ලබා ගැනීම සඳහා 20 සහ 200 ගුණ කර නැවත (10 + 20)% 100 = 30. දැන් අපට [30, 30] ඇත. ඉන්පසු 30 * 30 = 900 ගුණ කරන්න. මේ අනුව පිළිතුර 900 + 200 = 1100 වේ.

අපි මුලින්ම 20 සහ 30 ගුණ කළ යුතුව තිබුණා නම් (20 * 30) + (10 * 50) = 1100 ලැබෙනු ඇත. මේ අනුව ක්‍රම දෙකම එකම ප්‍රති .ලයක් ලබා ගැනීමට ඉඩ තිබුණි.

ප්රවේශය  

ගැටළුව අපෙන් ඉල්ලා සිටින්නේ ඔබ සොයා ගත හැකි අවම මුදල සොයා ගැනීමයි, එනම් ඔබ දිගින් දිගටම යුගල වශයෙන් ගුණ කර ඒවා එකතු කිරීම සිදු කරයි. ගැටළුව විසඳීම සඳහා බොළඳ ප්‍රවේශයක් භාවිතා කරයි පුනරාවර්තනය. සියලු ප්‍රේරණයන් උත්පාදනය කර මෙම ප්‍රේරණයන් යුගල වශයෙන් ගුණ කළ යුතු දර්ශක නිරූපණය කරන බව සලකන්න. නමුත් මෙම ප්‍රවේශය කාලය ගතවන බැවින් ප්‍රේරණයන් උත්පාදනය කිරීම සඳහා සාධකමය කාල සංකීර්ණත්වයක් ඇත.

මෙම කාලය ගතවන ප්‍රවේශය වෙනුවට, කාල සීමාව යටතේ ප්‍රති result ලය ගණනය කළ හැකි වෙනත් විසඳුමක් ගැන අප සිතිය යුතුය. දැන් ගතික වැඩසටහන්කරණය අපේ ආධාරයට එනවා. ගැටළුව සම්මත මෙට්‍රික් දාම ගුණ කිරීමේ ගැටලුවට වඩා සුළු විචලනයකි. මෙන්න මෙම ගැටලුවේදී අපි මුලින්ම මූලද්රව්ය 2 ක් සඳහා පිළිතුර ගණනය කරමු, පසුව මූලද්රව්ය 3 ක් සහ යනාදිය. එබැවින් අනුක්‍රමයේ මායිම දැක්වෙන පුනරාවර්තන ශ්‍රිතයක දර්ශක ගබඩා කිරීම සඳහා අපි විචල්‍ය දෙකක් තබා ගනිමු. ඉන්පසු අපි අනුක්‍රමය කොටස් 2 කට බෙදුවෙමු. ඉන්පසු මෙම උපප්‍රශ්න දෙක විසඳන්න. අපි මූලික නඩුවට පහර දෙන තුරු මෙම ක්‍රියාවලිය දිගටම කරගෙන යයි. මෙහි මූලික අවස්ථාව වන්නේ දර්ශක දෙකම එක හා සමාන වන විට ය. මෙම උපප්‍රශ්න සඳහා පිළිතුර ගණනය කර ඇති බැවින් ආරම්භක ගැටළුව සඳහා ප්‍රති result ලය ලබා ගැනීම සඳහා අපි පිළිතුරු ඒකාබද්ධ කරමු.

මෙයද බලන්න
පාලම සහ පන්දම් ගැටළුව සඳහා වූ වැඩසටහන

කේතය  

N සංඛ්‍යා වල ගුණ කිරීමේ අවම එකතුව සොයා ගැනීමට C ++ කේතය

#include <bits/stdc++.h>
using namespace std;
int dp[5][5];
int sum(int i, int j, int a[]){
  int ans = 0;
  for (int k=i;k<=j;k++)
    ans=(ans+a[k])%100;
  return ans;
}

int minimumSum(int i, int j, int a[]){
    if(i==j)return 0;
  if (dp[i][j] != INT_MAX)
    return dp[i][j];
    // divide the problem into subproblems
  for(int k=i;k<j;k++)
        dp[i][j] = min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
  return dp[i][j];
}

int main() {
  int a[] = {10, 20, 30};
  int n = sizeof(a) / sizeof(a[0]);
  for(int i=0;i<5;i++){
        for(int j=0;j<5;j++)
            dp[i][j] = INT_MAX;
  }
  cout<<minimumSum(0,n-1,a);
}
1100

N සංඛ්‍යා වල ගුණ කිරීමේ අවම එකතුව සොයා ගැනීමට ජාවා කේතය

import java.util.*;
class Main{
  static int dp[][] = new int[5][5];
  static int sum(int i, int j, int a[]){
    int ans = 0;
    for (int k=i;k<=j;k++)
      ans=(ans+a[k])%100;
    return ans;
  }

  static int minimumSum(int i, int j, int a[]){
      if(i==j)return 0;
    if (dp[i][j] != Integer.MAX_VALUE)
      return dp[i][j];
      // divide the problem into subproblems
    for(int k=i;k<j;k++)
          dp[i][j] = Math.min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
    return dp[i][j];
  }

  public static void main(String[] args)
  {
    int a[] = {10, 20, 30};
    int n = a.length;
    for(int i=0;i<5;i++){
          for(int j=0;j<5;j++)
              dp[i][j] = Integer.MAX_VALUE;
    }
    int ans = minimumSum(0,n-1,a);
    	System.out.print(ans);
  	}
}
1100

සංකීර්ණ විශ්ලේෂණය  

කාල සංකීර්ණත්වය

ඕ (එන් ^ 3), N ^ 2 ප්‍රාන්ත ඇති නිසා සහ එක් එක් ප්‍රති result ලය ගණනය කිරීම සඳහා අපි ආසන්න වශයෙන් N ප්‍රාන්ත සංඛ්‍යාවක් මත රඳා පවතී. මේ අනුව කාල සංකීර්ණතාව බහුපද වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (එන් ^ 2), අපි 2D DP වගුවක් නිර්මාණය කර ඇති නිසා. මේ අනුව අවකාශයේ සංකීර්ණතාව ද බහුපද වේ.