monotonically တိုးပွားလာသော function သည်ပထမဆုံးအကြိမ်အပြုသဘောဖြစ်လာသည်ကိုရှာပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် American Express
Binary Search ကို သွေးခွဲနှင့်အောင်နိုင် ရှာဖွေခြင်း

ပြProbleနာဖော်ပြချက်

“ monotonically တိုးပွားလာသော function သည်ပထမဆုံးအကြိမ်အပြုသဘောဖြစ်လာသည်နေရာကိုရှာပါ” တွင် function တစ်ခုကိုကျွန်ုပ်တို့ပေးထားသည် "int, f (လက်မှတ်မထိုး int x)" တစ် ဦး ကြာပါသည် အနုတ်လက္ခဏာကိန်းပြည့်မဟုတ် 'x' ကို input အဖြစ်နှင့်တစ် ဦး ပြန်လည်ရောက်ရှိ ကိန်း output အဖြစ်။ The function ကို ဆိုလိုသည်မှာ f (x + 1) တန်ဖိုးသည် input x တိုင်းအတွက် f (x) ထက်သာလွန်သည်။ ပထမ ဦး ဆုံးအနေဖြင့် f () သည်အပြုသဘောဖြစ်လာသည့် 'n' တန်ဖိုးကိုရှာပါ။ f () monotonically တိုးပွားလာသောကြောင့် f (n + 1), f (n + 2) ၏တန်ဖိုးများသည်အပြုသဘောဖြစ်ရမည်၊ f ၏တန်ဖိုးများ (n-2), f (n-3) .. သည်အနုတ်ဖြစ်ရမည် ။ ကျွန်ုပ်တို့၏ရည်မှန်းချက်မှာအို (logn) အချိန်တွင် n ကိုရှာရန်ဖြစ်သည်။ သငျသညျမဆို input ကို x များအတွက်, f (x) အို (1) အချိန်အတွက်အကဲဖြတ်နိုင်ပါတယ်ယူဆလိမ့်မည်။

input ပုံစံ

function (f) တစ်ခုပါသောပထမနှင့်လိုင်းတစ်ခုတည်း။

Output အမျိုးအစား

integer value ပါ ၀ င်သည့်ပထမနှင့်တစ်ခုတည်းသော line သည် monotonically တိုးပွားလာသော function သည်ပထမဆုံးအကြိမ်အပြုသဘောဆောင်သောနေရာဖြစ်လာသည်။

နမူနာ

x^2 - 4x - 8
6

ရှင်းလင်းချက်: f (x) အပြုသဘောဖြစ်လာသည့်နေရာ x သည် ၆ ဖြစ်သည်။

algorithm

ဤနည်းလမ်းတွင်အဓိကစိတ်ကူးမှာ binary search ကိုအသုံးပြုရန်ဖြစ်သည်။ သို့သော် binary search အတွက်ကျွန်ုပ်တို့သည်နိမ့်ကျသောတန်ဖိုးများကိုလိုအပ်သည်။ algo အောက်တွင်တန်ဖိုးများကိုရှာဖွေ။ binary search ကိုမည်သို့အကောင်အထည်ဖော်မည်ကိုပြသည်။

1. f (i) သည်သုညထက်ကြီး။ ၊ i တန်ဖိုးကိုနှစ်ဆတိုးသည်။ ပြီးတာနဲ့ f (i) ကသုညထက်ကြီးတယ်၊ ပြီးရင် i ကိုအမြင့်ဆုံး၊ i / 2 ကိုအနိမ့်အမြင့်အဖြစ်ယူမယ်။

2. ယခု i / 2 နှင့် i ကြားတွင် f (i) ၏ပထမဆုံးအပြုသဘောဆောင်သောတန်ဖိုးကိုရှာပါ။ Binary ရှာဖွေမှု

3. မြင့်မားသောအမြင့်သို့မဟုတ်ညီမျှသည်အမြင့်မှီတိုင်အောင်, အလယ်ပိုင်းကိုရှာပါ

  • f (mid) သည်သုညထက်ကြီးပြီးအလယ်သည်အနိမ့်နှင့်ညီလျှင် f (mid -1) သည်သုညထက်ငယ်သည်သို့မဟုတ်ညီသည်ဆိုလျှင် f (mid> 0) && (mid == low || f (Mid-1)) ) <= 0), ထို့နောက်နှစ်လယ်ပိုင်းတွင်ပြန်လာ
  • f (mid) သည်သုညထက်ငယ်လျှင်ညာဘက်တစ်ဝက်ကိုပြန်လည်ရှာဖွေပါ။
  • f (mid) သည်သုညထက်ကြီးလျှင်၊ ဘယ်ဘက်တစ်ဝက်ကိုပြန်လည်ရှာဖွေပါ။

အကောင်အထည်ဖော်ရေး

C ++ ပရိုဂရမ်တစ်ခုသည် monotonically တိုးပွားလာသော function ကိုပထမဆုံးအကြိမ်အပြုသဘောဆောင်လာသည့်အချက်ကိုရှာရန်

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

int binarySearch(int low, int high); 
int f(int x) 
{ 
    return (x*x - 10*x - 20); 
} 

int findFirstPositive() 
{ 
  if (f(0) > 0) 
    return 0; 
  int i = 1; 
  while (f(i) <= 0) 
    i = i*2; 
  return binarySearch(i/2, i); 
} 

int binarySearch(int low, int high) 
{ 
  if (high >= low) 
  { 
    int mid = low + (high - low)/2; 
    if (f(mid) > 0 && (mid == low || f(mid-1) <= 0)) 
      return mid; 

    if (f(mid) <= 0) 
      return binarySearch((mid + 1), high); 
    else  
      return binarySearch(low, (mid -1)); 
  } 
  return -1; 
} 

int main() 
{ 
  cout<<findFirstPositive(); 
  return 0; 
}

Java ပရိုဂရမ်သည် monotonically တိုးပွားလာသော function သည်ပထမဆုံးအကြိမ်အပြုသဘောဆောင်လာသည်

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static int f(int x)  
    { 
        return (x*x - 10*x - 20);
    } 
    public static int findFirstPositive() 
    { 
        if(f(0)>0)
        {
            return 0;
        }
        int i = 1; 
        while(f(i)<=0) 
            i = i * 2; 
        return binarySearch(i / 2, i); 
    } 
    public static int binarySearch(int low, int high) 
    { 
        if (high >= low) 
        {    
            int mid = low + (high - low)/2;  
            if (f(mid) > 0 && (mid == low || f(mid-1) <= 0)) 
                return mid; 
            if (f(mid) <= 0) 
                return binarySearch((mid + 1), high); 
            else 
                return binarySearch(low, (mid -1)); 
        }
        return -1;
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        findFirstPositive();
    }
}
x*x - 10*x - 20
12

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (logn) - 'high' ကိုရှာရန်အဆင့်များမှာ O (Logn) ဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် O (Logn) အချိန်တွင် 'high' ကိုရှာနိုင်သည်။ Binary Search သည် high / 2 နှင့် high အကြားကြာသောအချိန်နှင့် ပတ်သက်၍ ကော။ 'high' ၏တန်ဖိုးသည် 2 * n ထက်နည်းရမည်။ high / 2 နှင့် high ကြားရှိ element အရေအတွက်သည် O (n) ဖြစ်ရမည်။ ထို့ကြောင့် Binary Search ၏အချိန်ရှုပ်ထွေးမှုသည် O (Logn) ဖြစ်ပြီး၊ အချိန်ရှုပ်ထွေးမှုသည် O (Logn) ဖြစ်သော ၂ * O (Logn) ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ဘာလို့လဲဆိုတော့ငါတို့ဒီမှာအရန်နေရာမဖန်တီးဘူး။