ដំណោះស្រាយអេចអរអរ (x) ឡេឡេកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ក្រុមហ៊ុន google lyft ក្រុមហ៊ុន Microsoft Uber
ការស្វែងរកគោលពីរ គណិតវិទ្យា

ដូចដែលចំណងជើងនិយាយយើងត្រូវរកឫសការ៉េនៃលេខ។ ចូរនិយាយថាលេខគឺ x, បន្ទាប់មក Sqrt (x) គឺជាចំនួននោះ Sqrt (x) * Sqrt (x) = x ។ ប្រសិនបើឫសការ៉េនៃចំនួនមួយគឺជាតម្លៃគោលដប់បន្ទាប់មកយើងត្រូវត្រឡប់តម្លៃជាន់នៃឫសការ៉េ។

ឧទាហរណ៍

4
2
7
2

វិធីសាស្រ្ត (មុខងារដែលបានបង្កើតមុន)

នេះ គណិតវិទ្យា បណ្ណាល័យ C ++ និង lang.Math បណ្ណាល័យចាវ៉ាមានមុខងារដែលបានសាងសង់ជាមុនដើម្បីដាក់ឫសការេនៃចំនួនមួយ។ យើងអាចដាក់ពាក្យបាន ជាន់ () ដើម្បីជៀសវាងតម្លៃទសភាគណាមួយ។

ក្បួនដោះស្រាយ

  1. ប្រសិនបើលេខតិចជាង ២, ត្រឡប់ដោយខ្លួនឯង
  2. ហៅទូរស័ព្ទទៅ sqrt () មុខងារ
  3. ជាន់តម្លៃដែលទទួលបាន
  4. បោះពុម្ពលទ្ធផល

ការអនុវត្តដំណោះស្រាយឡេសកូដ (x) ឡេធីកូដ

កម្មវិធី C ++

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

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return floor(sqrt(x));
}

int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

កម្មវិធីចាវ៉ា

import java.lang.Math;

class sqrt_x
{
    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return (int)Math.floor(Math.sqrt(x));
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}
2

ការវិភាគស្មុគស្មាញនៃក្បួនដោះស្រាយដើម្បីរក Sqrt (x)

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

អូ (logN) ។ នេះ sqrt () មុខងារប្រើ ញូតុន - រ៉ាត់សុន វិធីសាស្រ្តក្នុងការគណនាឫសការ៉េនៃចំនួនដែលមានពេលវេលាស្មុគស្មាញនៃអូ (logN) ។

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

ឱ (១)។ ទំហំថេរត្រូវបានប្រើសម្រាប់អថេរ។

វិធីសាស្រ្ត (ការស្វែងរកគោលពីរ)

នៅទីនេះយើងអាចអនុវត្តការស្វែងរកគោលពីរលើជួរនៃលេខដែលចាប់ផ្តើមពី 1 ឡើងទៅ x / ២ដែល x = លេខដែលបានផ្តល់។ នៅទីនេះយើងអនុវត្តការស្វែងរកគោលពីរលើលំដាប់តម្រៀបដែលបានជ្រើសរើសជំនួសឱ្យជួរមួយ អារេ.

ដែនកំណត់ត្រឹមត្រូវត្រូវបានកំណត់ជា x / ២ ពីព្រោះរាល់លេខ x ធំជាង ២ ជាន់នៃឫសការេរបស់ពួកគេនឹងតិចជាង x / ២ ។ អាស្រ័យលើលទ្ធផលនៃការស្វែងរកគោលពីរយើងអាចលោតទៅខាងឆ្វេងឬខាងស្តាំនៃចន្លោះគំរូដើម។

Sqrt (x)

ក្បួនដោះស្រាយ

  1. បង្កើត ប្រព័ន្ធគោលពីរស្វែងរក () មុខងារត្រឡប់ជាន់នៃ sqrt (x)
  2. ចាប់ផ្តើមអថេរ យុទ្ធជន ដើម្បីទុកលទ្ធផល
  3. ប្រសិនបើលេខតិចជាង ២, ត្រឡប់ដោយខ្លួនឯង
  4. ដំបូង ចាកចេញ និង នៅខាងស្ដាំ តម្លៃជា ១ និង x / ២ រៀងៗខ្លួន
  5. រហូតមកដល់ ឆ្វេង <= ស្ដាំ:
    • រកឃើញពាក់កណ្ដាលនៃជួរនេះ ពាក់កណ្តាល = ឆ្វេង + ស្តាំ / ២
    • ក្នុងករណីការ៉េពាក់កណ្តាលស្មើនឹង x,  ត្រឡប់វាដូចដែលវាជាឫសការ៉េ
    • ប្រសិនបើការ៉េពាក់កណ្តាលគឺតិចជាង x, លោតទៅពាក់កណ្តាលខាងស្តាំដោយកំណត់ខាងឆ្វេង = ពាក់កណ្តាល + 1
    • បើមិនដូច្នោះទេលោតទៅពាក់កណ្តាលខាងឆ្វេងដោយកំណត់ស្តាំ = ពាក់កណ្តាល - 1 ហើយរក្សាទុកតម្លៃនេះ យុទ្ធជន
  6. បោះពុម្ពលទ្ធផល

ការអនុវត្តដំណោះស្រាយឡេសកូដ (x) ឡេធីកូដ

កម្មវិធី C ++

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

int binarySearch(int x)
{
    int left = 1 , right = x / 2 , mid , ans;
    long temp;

    while(left <= right)
    {
        mid = (left + (right - left) / 2);
        temp = (long)mid * (long)mid;
        //mid * mid can be large, so use long
        if(temp == x)
            return mid;
        if(temp < x)
            ans = mid , left = mid + 1;
        else
            right = mid - 1;
    }
    return ans;
}

int mySqrt(int x)
{
    if(x <= 1)
        return x;
    return binarySearch(x);
}


int main()
{
    int x = 7;
    cout << mySqrt(x) << '\n';
}

កម្មវិធីចាវ៉ា

import java.lang.Math;

class sqrt_x
{
    static int binarySearch(int x)
    {
        int left = 1 , right = x / 2 , mid , ans = 0;
        long temp;

        while(left <= right)
        {
            mid = (left + (right - left) / 2);
            temp = (long)mid * (long)mid;
            //mid * mid can be large, so use long
            if(temp == x)
                return mid;
            if(temp < x)
            {
                ans = mid;
                left = mid + 1;
            }
            else
                right = mid - 1;
        }
        return ans;
    }

    static int mySqrt(int x)
    {
        if(x <= 1)
            return x;
        return binarySearch(x);
    }

    public static void main(String args[])
    {
        int x = 7;
        System.out.println(mySqrt(x));
    }
}
2

ការវិភាគស្មុគស្មាញនៃក្បួនដោះស្រាយដើម្បីរក Sqrt (x)

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

O (logN), ខណៈដែលការស្វែងរកគោលពីរនៅតែបែងចែកចន្លោះគំរូទៅពាក់កណ្តាលរបស់វា។ ក្នុងករណីអាក្រក់បំផុតវាអាចបង្កើតបាន ការប្រៀបធៀប logN.

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

ឱ (១)។ ជាថ្មីម្តងទៀតទំហំថេរត្រូវបានប្រើសម្រាប់អថេរ។