ការដោះស្រាយបញ្ហា


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ បន្ទប់ពិសោធន៍ច្នៃប្រឌិត ២៤ * ៧ ក្រុមហ៊ុន Amazon DE Shaw ដេលីវ៉ាយ បានតាមរយៈការ
ការសរសេរកម្មវិធីឌីណាមិក Fibonacci គណិតវិទ្យា

សេចក្តីថ្លែងការណ៍បញ្ហា។

“ ការដោះស្រាយបញ្ហា” បញ្ជាក់ថាអ្នកមានបណ្តាញអគ្គិសនី 2 x អិន និងក្បឿងនៃទំហំ ៥ គុណ ៣ ។ ដូច្នេះ, រកចំនួនវិធីដើម្បីក្រឡាក្បឿងក្រឡាចត្រង្គដែលបានផ្តល់ឱ្យ។

ឧទាហរណ៍

3
2

ការពន្យល់: ការដោះស្រាយបញ្ហា

វិធីសាស្រ្តសម្រាប់បញ្ហានៃការដាក់ក្បឿង

យើងអាចដោះស្រាយបញ្ហានេះដោយប្រើការហៅខ្លួនឯង។ នៅក្នុងបញ្ហាយើងត្រូវដាក់ក្រឡាចត្រង្គនៃ 2xN ។ ដូច្នេះវានឹងពឹងផ្អែកលើចំនួនវិធីដើម្បីភ្ជាប់ក្រឡាចត្រង្គនៃទំហំ 2x (N-1) និង 2x (N-2) ។ តើយើងអាចនិយាយយ៉ាងដូចម្តេច?

ហេតុផលគឺសាមញ្ញជំនួសឱ្យការគិតដើម្បីដាក់ជួរឈរទី 1 នៅក្នុងក្រឡាចត្រង្គបន្ទាប់មកទីពីរនិងបន្តទៀត។ យើងកំពុងព្យាយាមរៀបជួរឈរទី ១ បន្ទាប់មកអិន ១ និងបន្តទៀត។ វិធីនេះដឹងថាប្រសិនបើយើងដាក់ក្រឡាក្បឿង ២ × ១ នៅលើជួរទី N ។ ឥឡូវនេះបញ្ហាត្រូវបានប្តូរទៅជាបញ្ហារងនៃក្រឡាចត្រង្គក្រឡាក្បឿងដែលមានទំហំ 2x (N-1) ។ ស្រដៀងគ្នានេះដែរប្រសិនបើយើងដាក់ក្បឿង 2 × 1 ពីរនៅក្នុងបណ្តាញ 1xN បញ្ហាត្រូវបានប្តូរទៅជាទំហំ 2x (N-2) ។ ឥឡូវនេះប្រសិនបើយើងអាចដោះស្រាយបញ្ហាទាំងនេះបានយើងអាចទទួលបានចម្លើយ។

ឧបមាថាក្រឡាក្បឿង [N] បង្ហាញពីចំនួនវិធីដើម្បីភ្ជាប់ក្រឡាចត្រង្គនៃទំហំ 2XN ។ បន្ទាប់មក ក្រឡាក្បឿង [N] = ក្បឿង [N-1] + ក្បឿង [N-2]។ ស្រដៀងគ្នានេះដែរក្បឿង [N-1] = ក្បឿង [N-2] + ក្បឿង [N-3] ។ ដូច្នេះបញ្ហាបង្ហាញពីរចនាសម្ព័ន្ធល្អប្រសើរបំផុត។ វាល្អប្រសើរជាងមុនក្នុងការរក្សាទុកលទ្ធផលសម្រាប់ក្រឡាក្បឿង [N-2] ពីព្រោះវាត្រូវបានគេប្រើពីរដង។ ប្រសិនបើយើងរក្សាទុកលទ្ធផលយើងនឹងមិនគណនាវាពីរដងហើយនឹងកាត់បន្ថយពេលវេលាស្មុគស្មាញយ៉ាងខ្លាំង។ ដូច្នេះយើងនឹងប្រើ ការសរសេរកម្មវិធីឌីណាមិក ដើម្បីដោះស្រាយបញ្ហា។

ការដោះស្រាយបញ្ហា

លេខកូដ

C ++ លេខកូដសម្រាប់បញ្ហានៃការដាក់ក្បឿង

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

int main(){
  int n;cin>>n;
  // create an array to store number of ways to tile a grid of size 2xi
  int tile[n+1];
  // base case
  tile[0] = 0; tile[1] = 1;
  for(int i=2;i<=n;i++)
    tile[i]  = tile[i-1] + tile[i-2]; // use recursive formula
  cout<<tile[n];
}
3
2

កូដចាវ៉ាសម្រាប់បញ្ហានៃការដាក់ក្បឿង

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    // create an array to store number of ways to tile a grid of size 2xi
    int tile[] = new int[n+1];
    // base case
    tile[0] = 0; tile[1] = 1;
    for(int i=2;i<=n;i++)
      tile[i]  = tile[i-1] + tile[i-2]; // use recursive formula
    System.out.println(tile[n]);
  }
}
3
2

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

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

O (N), ពីព្រោះដើម្បីដោះស្រាយបញ្ហាក្រឡាចត្រង្គក្រឡា 2xN ។ អ្នកត្រូវគណនាចម្លើយសម្រាប់ក្រឡាចត្រង្គក្រឡាក្បឿងដែលមានទំហំតូចជាងអិន។

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

O (N)ពីព្រោះយើងកំពុងរក្សាទុកលទ្ធផលសម្រាប់អនុវត្ថុទាំងអស់ហើយដូច្នេះទំហំដែលត្រូវការគឺលីនេអ៊ែរ។

សម្គាល់ៈយើងអាចដោះស្រាយបញ្ហាក្នុងចន្លោះអូ (១) និងម៉ោងអូ (N) ដោយប្រើអថេរពីរចុងក្រោយនិងទីពីរដែលនឹងរក្សាទុកតម្លៃរបស់ក្បឿង [N-១] និងក្រឡាក្បឿង [N-២] រៀងៗខ្លួន។ ឥឡូវចរន្ត = ចុងក្រោយ + វិនាទីចុងក្រោយហើយបន្ទាប់មកធ្វើបច្ចុប្បន្នភាពតម្លៃអថេរទៅតាមនោះ។ រូបមន្តដែលកើតឡើងវិញគឺដូចគ្នានឹងលេខរបស់ណតហ្វីលីណាស៊ីដែរ។ ដូច្នេះអ្នកក៏អាចដោះស្រាយបញ្ហានេះ O (log N) ពេលវេលាដោយប្រើរូបមន្តដើម្បីរកលេខ Fibonacci ។