පව් (x, n) ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන අසන බ්ලූම්බර්ග් ඊ බේ ෆේස්බුක් ගෝල්ඩ්මන් සැක්ස් ගූගල් LinkedIn මයික්රොසොෆ්ට් ඔරකල් පේපෑල් Uber VMware වෝල්මාර්ට් ලැබ්
ද්විමය සෙවීම ගණිතය

“පව් (x, n) ලීට්කෝඩ් විසඳුම” යන ගැටළුවේ සඳහන් වන්නේ ඔබට අංක දෙකක් ලබා දී ඇති අතර ඉන් එකක් පාවෙන ලක්ෂ්‍ය අංකයක් වන අතර තවත් සංඛ්‍යාවක් පූර්ණ සංඛ්‍යාවක් වේ. නිඛිලය මඟින් on ාතකය නිරූපණය කරන අතර පදනම පාවෙන ලක්ෂ්‍ය අංකය වේ. පාදකයට වඩා on ාතයක් තක්සේරු කිරීමෙන් පසු වටිනාකම සොයා ගන්නා ලෙස අපට කියනු ලැබේ. පදනම negative ණ, ධනාත්මක හෝ ශුන්‍ය විය හැකිය. On ාතයට පූර්ණ සංඛ්‍යා පරාසයක් අතර ඕනෑම තැනක පැවතිය හැකිය. අපට නිමැවුමට බාධාවක් ද ලබා දී ඇත. ප්‍රතිදානය -10000 සිට +10000 අතර ඕනෑම තැනක වනු ඇත. ඉතින්, අපි උදාහරණ කිහිපයක් දෙස බලමු.

පව් (x, n) ලීට්කෝඩ් විසඳුම

උදාහරණයක්

Base: 2
Exponent: 10
Answer: 1024

පැහැදිලි කිරීම: 2 ^ 10 = 104 සඳහා වන අගය බැවින්, පිළිතුර. 2 10 ගුණයක් පුනරාවර්තන ගුණ කිරීමෙන් ද මෙය පරීක්ෂා කළ හැකිය.

Base: 2
Exponent: -10
Answer: 0.00098

පැහැදිලි කිරීම: on ාතයේ අගය ද -10 ලෙස වෙනස් කර ඇති නිසා පිළිතුර වෙනස් කර ඇත.

තිරිසන් බල ප්‍රවේශය

Pow (x, n) ලීට්කෝඩ් විසඳුම සඳහා වන තිරිසන් බලවේගය ඉතා සරල ය. අපට අවශ්‍ය වන්නේ on ාතකයන් ඇගයීමේ ක්‍රියාවලිය අනුකරණය කිරීමයි. On ාතයක් මූලික on ාතීය වාර ගණන ගුණ කිරීමෙන් පහසුවෙන් තක්සේරු කළ හැකිය. එබැවින්, අපගේ ප්‍රියතම ක්‍රමලේඛන භාෂාවලින් ලූපයක් භාවිතයෙන් අපට මෙය පහසුවෙන් අනුකරණය කළ හැකිය. සැලකිල්ලට ගත යුතු එක් දෙයක් නම්, කෙළවරේ ඇති නඩු ය. එක්කෝ on ාතකය පූර්ණ සංඛ්‍යාවේ උපරිම අගයට හෝ අවම අගයට සමාන වන විට නිඛිල. අපට පූර්ණ සංඛ්‍යාවේ අවම අගය ලෙස on ාතයක් ඇති විට, පිළිතුර 1 හෝ 0 විය හැකිය. පදනම 1 හෝ -1 නම්, පූර්ණ සංඛ්‍යාංකයේ අවම අගය ලෙස on ාතයක් තිබේ නම්, වෙනත් ආකාරයකින් 1 ලෙස පිළිතුරු ලැබෙනු ඇත. ඒ හා සමානව අපට ඇත්තේ 0 ක් පමණි නිමැවුමේ අවහිරතා 1 ට වඩා අඩු බැවින් on ාතයේ පූර්ණ අගය ලෙස දැක්විය හැකිය. මෙම අවහිරතා සැලකිල්ලට ගනිමින් මූලික on ාතීය වේලාවන් ගුණ කිරීම අනුකරණය කරමින් තිරිසන් බල කේතයක් ලෙස අපට ලිවිය හැකිය.

පව් (x, n) ලීට්කෝඩ් විසඳුම සඳහා කේතය

සී ++ කේතය

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

double myPow(double x, int n) {
    if (n == INT_MAX) return x;
    else if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
    if(n<0) x=1/x, n*=-1;
    double ans = 1;
    for(int i=0;i<n;i++)
        ans = ans*x;
    return ans;
}

int main(){
    cout<<myPow(2, 10);
}
1024

ජාවා කේතය

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static double myPow(double x, int n) {
        if (n == Integer.MAX_VALUE) return x;
        else if (n == Integer.MIN_VALUE) return (x == 1 || x == -1) ? 1 : 0;
        if(n<0) {
            x=1/x;
            n*=-1;
        }
        double ans = 1;
        for(int i=0;i<n;i++)
            ans = ans*x;
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.println(myPow(2, 10));
    }
};
1024.0

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත), මක්නිසාද යත් අපි පාදක on ාතීය වේලාවන් ගුණ කරන තුරු අපි ලූපය. මේ අනුව කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), අපට පිළිතුර පමණක් ගබඩා කළ යුතු බැවින් අපි තනි විචල්‍යයක් භාවිතා කරමු. මේ අනුව, අවකාශයේ සංකීර්ණතාව නියත ය.

පව් (x, n) ලීට්කෝඩ් විසඳුම සඳහා ප්‍රශස්ත ප්‍රවේශය

ප්‍රශස්තිකරණය කළ ප්‍රවේශය වේගවත් මොඩියුලෝ on ාතීය ඇල්ගොරිතම භාවිතා කරයි. අපට වේගවත් මොඩියුලෝ on ාතීයකරණය පුනරාවර්තන ආකාරයකින් හෝ ක්‍රියාකාරී ලෙස ක්‍රියාත්මක කළ හැකිය. වේගවත් මොඩියුලෝ on ාතීයකරණයේදී, අපි පාදම 2 හි බලයෙන් ගුණ කරමු. මෙයින්, අපි අදහස් කළේ අපි දිගටම පාදම ගුණ කිරීම ය. ඉතින්, පළමු පියවරේදී, පදනම තමාටම කොටු වේ. “B” මගින් දැක්වෙන පදනම යැයි සිතමු. එබැවින් පළමු පියවරේදී එය b ^ 2 බවට පත්වේ, ඊළඟ පියවරේදී එය b ^ 4, පසුව b ^ 8, පසුව b ^ 16, සහ එසේ වේ. දැන් අපි ගුණ කරන්නේ on ාතයේ බලයට අනුරූප වන මූලික බලයන් පමණි. එබැවින්, on ාතයක් ද්විමය ආකෘතියෙන් පරිවර්තනය කර on ාතීය ද්විමය ආකෘතියට අනුව පාදක ගුණ කිරීම දිගටම කරගෙන යන්න. උදාහරණයක් ලෙස, 3 ^ 6 ගණනය කරන්න. මෙහි පදනම = 3, on ාතීය = 6. ද්විමය ආකෘතියෙන් 6 පරිවර්තනය කිරීමෙන් එය 110 ක් බවට පත් වේ. දැන්, පළමු පියවරේදී, on ාතයට 1 තිබේදැයි පරීක්ෂා කර බලමු. b ^ 6 බවට පත්වේ. දැන්, 0 හි 2 එහි 6 වන අඩුම වැදගත් බිට් ලෙස ඇත, එබැවින් අපි පිළිතුරට b ^ 1 ගුණ කරමු. දැන් පිළිතුර b ^ 2 ට සමාන වේ. එවිට පදනම b ^ 2 බවට පත්වේ. 2 හි 4 වන අඩුම වැදගත් බිට් ලෙස 6 ඇති බැවින්, අපි පිළිතුරට b ^ 1 ගුණ කරමු. පිළිතුර දැන් b ^ 3 * b ^ 4 = b ^ 2 බවට පත්වේ. මේක තමයි අපිට ඕන වුණේ. ඇල්ගොරිතම ක්‍රියාත්මක කරන්නේ කෙසේදැයි සොයා ගැනීමට පහත ක්‍රියාත්මක කිරීම පරීක්ෂා කරන්න.

පව් (x, n) ලීට්කෝඩ් විසඳුම සඳහා ප්‍රශස්ත කේතය

සී ++ කේතය

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

double myPow(double x, int n) {
    if (n == INT_MAX) return x;
    else if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
    if(n<0) x=1/x, n*=-1;
    double ans = 1;
    while(n>0){
        if(n&1)
            ans *= x;
        x = x*x;
        n = n>>1;
    }
    return ans;
}

int main(){
    cout<<myPow(2, 10);
}
1024

ජාවා කේතය

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    public static double myPow(double x, int n) {
        if (n == Integer.MAX_VALUE) return x;
        else if (n == Integer.MIN_VALUE) return (x == 1 || x == -1) ? 1 : 0;
        if(n<0) {
            x=1/x;
            n*=-1;
        }
        double ans = 1;
        while (n>0){
            if(n%2 == 1) ans = ans*x;
            x = x*x;
            n = n>>1;
        }
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.println(myPow(2, 10));
    }
};
1024

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (ලොග්එන්), මන්දයත් අපි වේගවත් මොඩියුලෝ on ාතීයකරණය භාවිතා කළ අතර එය පාදකයට වඩා on ාතයක් ගණනය කිරීමට ල ar ු ගණක කාලය ගත වේ. අපට කාල සංකීර්ණත්වය බුද්ධිමත්ව සොයාගත හැකිය. අපි on ාතකය 0 වන තෙක් බෙදූ බැවින් මේ සඳහා අවශ්‍ය කාලය ලොග්එන් මත රඳා පවතී, එහිදී N යනු on ාතකය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), පිළිතුර ගබඩා කිරීම සඳහා අපි තනි විචල්‍යයක් භාවිතා කර ඇති බැවින්, අවකාශයේ සංකීර්ණතාව නියත ය.