ផលបូកអប្បបរមានៃគុណនៃលេខ n  


កម្រិតលំបាក រឹង
សួរញឹកញាប់ Accenture BlackRock ក្រុមហ៊ុន GE សុខភាព ដោយឡែកក្រុមហ៊ុន JP Morgan បានតាមរយៈការ
អារេ ការសរសេរកម្មវិធីឌីណាមិក

បញ្ហា“ ផលបូកអប្បបរមានៃការគុណនឹងលេខ n” ចែងថាអ្នកត្រូវបានផ្តល់ឱ្យ n ចំនួនគត់ ហើយអ្នកត្រូវបង្រួមអប្បបរមានៃផលបូកនៃលេខទាំងអស់ដោយយកធាតុពីរដែលនៅជាប់គ្នាហើយដាក់លេខបូករបស់វា ១០០ វិញរហូតទាល់តែចំនួនមួយនៅសល់។

ឧទាហរណ៍  

ផលបូកអប្បបរមានៃគុណនៃលេខ nពិន

10 20 30
1100

ការពន្យល់

ដំបូងយើងគុណ ១០ និង ២០ ដើម្បីទទួលបាន ២០០ បន្ទាប់មកដាក់មកវិញ (១០ + ២០)% ១០០ = ៣០។ ឥឡូវយើងមាន [៣០, ៣០] ។ បន្ទាប់មកគុណនឹង ៣០ * ៣០ = ៩០០ ។ ដូច្នេះចម្លើយគឺ ៩០០ + ២០០ = ១១០០ ។

ប្រសិនបើយើងបានគុណ ២០ និង ៣០ ដំបូងយើងនឹងទទួលបាន (២០ * ៣០) + (១០ * ៥០) = ១១០០ ដូច្នេះវិធីទាំងពីរនេះអាចទទួលបានលទ្ធផលដូចគ្នា។

វិធីសាស្រ្ត  

បញ្ហាស្នើឱ្យយើងរកផលបូកអប្បបរមាដែលអាចត្រូវបានរកឃើញដែលអ្នកបន្តគុណនឹងលេខហើយបន្ទាប់មកធ្វើលេខបន្ថែមរបស់ពួកគេ។ វិធីឆោតល្ងង់ដើម្បីដោះស្រាយបញ្ហាកំពុងប្រើ ការហៅឡើងវិញ។ បង្កើតការអនុញ្ញាតទាំងអស់ហើយបន្ទាប់មកពិចារណាថាការអនុញ្ញាតទាំងនេះបង្ហាញពីសូចនាករដែលគួរតែត្រូវបានគុណជាគូ។ ប៉ុន្តែវិធីសាស្រ្តនេះគឺត្រូវការពេលវេលាពីព្រោះជំនាន់នៃការអនុញ្ញាតិមានភាពស្មុគស្មាញពេលវេលាពិត។

ជំនួសឱ្យវិធីសាស្រ្តប្រើប្រាស់ពេលវេលានេះយើងគួរតែគិតអំពីដំណោះស្រាយផ្សេងទៀតដែលអាចគណនាលទ្ធផលក្រោមដែនកំណត់ពេលវេលា។ ឥឡូវ​នេះ ការសរសេរកម្មវិធីឌីណាមិក មកដល់ជំនួយរបស់យើង។ បញ្ហាគឺមានការប្រែប្រួលបន្តិចបន្តួចលើបញ្ហាគុណពហុខ្សែសង្វាក់ម៉ាទ្រីក។ នៅទីនេះក្នុងបញ្ហានេះដំបូងយើងគណនាចម្លើយសម្រាប់ធាតុ ២ បន្ទាប់មកធាតុ ៣ និងផ្សេងទៀត។ ដូច្នេះយើងរក្សាទុកអថេរពីរសម្រាប់រក្សាទុកសន្ទស្សន៍នៅក្នុងមុខងារហៅខ្លួនឯងដែលបញ្ជាក់ពីព្រំដែននៃលំដាប់។ បន្ទាប់មកទៀតយើងបែងចែកលំដាប់ជា ២ ផ្នែក។ ហើយបន្ទាប់មកដោះស្រាយអនុសញ្ញាណទាំងពីរនេះ។ ដំណើរការនេះនៅតែបន្តរហូតដល់យើងឈានដល់មូលដ្ឋាន។ ករណីមូលដ្ឋានគឺនៅពេលដែលសូចនាករទាំងពីរគឺដូចគ្នា។ បន្ទាប់មកដូចដែលយើងបានគណនាចម្លើយសម្រាប់អនុសញ្ញាសំគាល់ទាំងនេះយើងបញ្ចូលចម្លើយដើម្បីទទួលបានលទ្ធផលសម្រាប់បញ្ហាដំបូង។

សូម​មើល​ផង​ដែរ
កម្មវិធីសំរាប់បញ្ហាស្ពាននិងស្តុច

លេខកូដ  

កូដ C ++ ដើម្បីរកផលបូកអប្បបរមានៃគុណនៃលេខ n

#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

ការវិភាគស្មុគស្មាញ  

ស្មុគស្មាញពេលវេលា

O (N ^ ២), ពីព្រោះមានរដ្ឋ N ^ 2 ហើយដើម្បីគណនាលទ្ធផលសំរាប់រដ្ឋនីមួយៗយើងពឹងផ្អែកលើចំនួន N ប្រហាក់ប្រហែលនៃរដ្ឋ។ ដូច្នេះពេលវេលាស្មុគស្មាញគឺពហុធា។

ភាពស្មុគស្មាញនៃលំហ

O (N ^ ២), ពីព្រោះយើងបានបង្កើតតារាងឌីភីឌីឌី។ ដូច្នេះភាពស្មុគស្មាញនៃលំហរក៏មានពហុធាផងដែរ។