Sqrt (x) راه حل کد


سطح دشواری ساده
اغلب در آمازون سیب بلومبرگ گوگل چطوری مایکروسافت حال بارگذاری
جستجوی دودویی ریاضی

همانطور که عنوان می گوید ، ما باید ریشه مربع یک عدد را پیدا کنیم. بگذارید بگوییم عدد است x, پس Sqrt (x) عددی است به گونه ای که Sqrt (x) * Sqrt (x) = x. اگر ریشه مربع یک عدد مقداری اعشار باشد ، باید مقدار کف ریشه مربع را برگردانیم.

مثال

4
2
7
2

رویکرد (توابع از پیش ساخته شده)

La ریاضی کتابخانه C ++ و زبان ریاضی کتابخانه جاوا دارای توابع از پیش ساخته شده برای برگرداندن ریشه مربع یک عدد است. می توانیم اقدام کنیم کف() برای جلوگیری از هر مقدار اعشاری

الگوریتم

  1. اگر تعداد کمتر از 2 است ، خود را برگردانید
  2. با ... تماس بگیر sqrt () تابع
  3. مقدار بدست آمده را طبقه بندی کنید
  4. نتیجه را چاپ کنید

پیاده سازی Sqrt (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)

پیچیدگی زمان

O (ورود به سیستم) La sqrt () تابع از نیوتن-رافسون روش محاسبه ریشه مربع یک عدد که دارای پیچیدگی زمانی O (logN) است.

پیچیدگی فضا

O (1). از فضای ثابت برای متغیرها استفاده می شود.

رویکرد (جستجوی دودویی)

در اینجا ، ما می توانیم جستجوی دودویی را در طیف وسیعی از اعداد از ابتدا شروع کنیم 1 بالا رفتن به x / 2که در آن x = تعداد داده شده است. در اینجا ، ما جستجوی باینری را در یک ترتیب مرتب شده انتخاب شده به جای یک پیاده سازی می کنیم صف.

حد راست به صورت تنظیم شده است x / 2 زیرا برای هر عدد x ، بزرگتر از 2 ، کف ریشه مربع آنها کمتر از x / 2 خواهد بود. بسته به نتیجه جستجوی دودویی ، می توانیم به نیمه چپ یا راست فضای نمونه اصلی برویم.

Sqrt (x)

الگوریتم

  1. ایجاد یک binarySearch () عملکرد طبقه بازگشت sqrt (x)
  2. مقداردهی اولیه را انجام دهید استاندارد تا نتیجه را ذخیره کند
  3. اگر تعداد کمتر از 2 است ، خود را برگردانید
  4. مقدماتی ترک کرد و راست مقادیر به ترتیب 1 و x / 2 می باشد
  5. تا زمان چپ <= راست:
    • وسط این محدوده را پیدا کنید ، وسط = چپ + راست / 2
    • در صورت مربع میانه برابر است با x,  همانطور که ریشه مربع است آن را برگردانید
    • اگر مربع وسط کمتر از باشد x، با تنظیم چپ = وسط + 1 به نیمه راست بپرید
    • در غیر این صورت ، با تنظیم right = mid - 1 به نیمه چپ بروید و این مقدار را در ذخیره کنید استاندارد
  6. نتیجه را چاپ کنید

پیاده سازی Sqrt (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.

پیچیدگی فضا

O (1). باز هم ، از فضای ثابت برای متغیرها استفاده می شود.