បោះពុម្ពលំដាប់ Fibonacci ដោយប្រើអថេរ ២


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ដេលីវ៉ាយ រោងចក្រ Fourkites ការដំឡើង MAQ o9 ដំណោះស្រាយ PayU
ការសរសេរកម្មវិធីឌីណាមិក Fibonacci លំដាប់

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

បញ្ហា“ តំនើរការបោះពុម្ព Fibonacci ដោយប្រើ ២ អថេរ” ចែងថាអ្នកត្រូវព្រីនលំដាប់ Fibonacci ប៉ុន្តែមានការកំណត់ការប្រើប្រាស់តែ ២ អថេរប៉ុណ្ណោះ។

ឧទាហរណ៍

បោះពុម្ពលំដាប់ Fibonacci ដោយប្រើអថេរ ២

n = 5
0 1 1 2 3 5

ការពន្យល់

លំដាប់លទ្ធផលមានធាតុប្រាំដំបូងនៃស៊េរី Fibonacci ។

វិធីសាស្រ្ត

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

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

ប្រសិនបើយើងឃើញរូបមន្តហៅឡើងវិញ F (n) = F (n-1) + F (n-2) ។ យើងពឹងផ្អែកតែលើលេខ Fibonacci ពីរចុងក្រោយប៉ុណ្ណោះ។ ដូច្នេះយើងអាចរក្សាទុកតែលេខ Fibonacci ពីរចុងក្រោយដើម្បីរកលេខបច្ចុប្បន្នហើយនេះធ្វើឱ្យក្បួនដោះស្រាយដំណើរការក្នុងភាពស្មុគស្មាញអវកាស O ។

លេខកូដ

កូដ C ++ ដើម្បីបោះពុម្ពលំដាប់លំដោយ Fibonacci ដោយប្រើ ២ អថេរ

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

int main()
{
    int n;cin>>n;
    int last = 1, lastToLast = 0;
    if(n>=0)
        cout<<lastToLast<<" ";
    if(n>=1)
        cout<<last<<" ";
    for(int i=2;i<=n;i++){
        int cur = last + lastToLast;
        cout<<cur<<" ";
        lastToLast = last;
        last = cur;
    }
}
5
0 1 1 2 3 5

កូដចាវ៉ាដើម្បីបោះពុម្ពលំដាប់លំដោយ Fibonacci ដោយប្រើអថេរ ២

import java.util.*;
class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    	int last = 1, lastToLast = 0;
      if(n>=0)
          System.out.print(lastToLast+" ");
      if(n>=1)
          System.out.print(last+" ");
      for(int i=2;i<=n;i++){
          int cur = last + lastToLast;
          System.out.print(cur+" ");
          lastToLast = last;
          last = cur;
      }
  	}
}
5
0 1 1 2 3 5

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

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

O (N), ពីព្រោះយើងបានឆ្លងកាត់តែចំនួនធាតុដែលយើងត្រូវការដើម្បីបោះពុម្ព។ ដំបូងយើងបានគិតពីការដោះស្រាយបញ្ហាដោយប្រើការហៅខ្លួនឯងប៉ុន្តែនោះជាស្វ័យគុណភ្លាមៗ។ បន្ទាប់មកយើងកាត់បន្ថយភាពស្មុគស្មាញនៃពេលវេលារបស់យើងនៅពេលយើងប្រើ ការសរសេរកម្មវិធីថាមវន្ត។ ដោយសារតែអ្វីដែលយើងអាចដោះស្រាយបញ្ហាបានតាមពេលវេលាលីនេអ៊ែរ។

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

ឱ (១),  យើងបានដោះស្រាយបញ្ហាក្នុងភាពស្មុគស្មាញនៃលំហថេរពីព្រោះយើងបានប្រើតែអថេរពីរប៉ុណ្ណោះ។