රෝම සිට පූර්ණ සංඛ්‍යා ලීට්කෝඩ් විසඳුම


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

“රෝමානු සිට පූර්ණ සංඛ්‍යාව” දක්වා වූ ගැටලුවේදී අපට ලබා දී ඇත්තේ a පේළියකි එහි යම් ධන නිඛිලයක් නිරූපණය කරයි රෝම සංඛ්‍යාත්මක ස්වරූපය. පහත දැක්වෙන වගුව භාවිතා කර පූර්ණ සංඛ්‍යා බවට පරිවර්තනය කළ හැකි අක්ෂර 7 කින් රෝම ඉලක්කම් නිරූපණය කෙරේ:

රෝම සිට පූර්ණ සංඛ්‍යා ලීට්කෝඩ් විසඳුම

සටහන: දී ඇති රෝම ඉලක්කම්වල පූර්ණ සංඛ්‍යා අගය 4000 ට වඩා වැඩි හෝ සමාන නොවේ.

උදාහරණයක්

IX
9
CXXIX
129

පැහැදිලි කිරීම # 1

IX පූර්ණ සංඛ්‍යා 9 කි

පැහැදිලි කිරීම # 2

CXXIX = C + XX + IX = 100 + 20 + 9 = 129

ප්‍රවේශය (වමේ සිට දකුණට)

අපට අරාවෙහි වමේ සිට දකුණට සමත් විය හැකි අතර, එහි ඇති සෑම අක්ෂරයකටම අනුරූප අගය එකතු කරන්න. නමුත්, රෝමානු ඉලක්කම් වල සුවිශේෂී අංගය වන්නේ ඉහළ අගයකට වඩා අඩු පූර්ණ සංඛ්‍යාවක් සහිත අක්‍ෂරයක් සිදුවුවහොත් එහි ප්‍රති result ලය ඒවායේ වෙන වෙනම නොවේ.

උදාහරණයක් ලෙස, අපි පසුව අක්ෂර එකතු කළහොත් රෝමන් වල IX 1 + 10 = 11 ට සමාන විය යුතුය. නමුත්, IX = 9, ලෙස එය පෙර සිදු වේ X සමෝධානික වටිනාකමෙන් අඩුය. එබැවින්, ප්රති result ලය ලෙස සලකනු ලැබේ I සිට අඩු කරනු ලැබේ X. එබැවින් IX = 9.

එමනිසා, අපට සෑම අක්ෂරයකම පූර්ණ අගය සරලව එකතු කළ නොහැක. ඉහත සඳහන් නඩුව සඳහා අප ඒ අසල ඇති චරිතය ද පරීක්ෂා කළ යුතුය. මේ ආකාරයෙන්, අපට දී ඇති රෝම සංඛ්‍යාත්මක නූල අවශ්‍ය පූර්ණ සංඛ්‍යාවක් බවට පරිවර්තනය කළ හැකිය.

ඇල්ගොරිතම

  1. ශ්‍රිතයක් සාදන්න getInteger () තනි රෝමානු චරිතයක වටිනාකම එය වෙත ආපසු යැවීමට ස්විච්චය නඩු
  2. ආරම්භ කරන්න ප්රතිඵලය අවශ්‍ය පූර්ණ සංඛ්‍යා ගබඩා කිරීමට
  3. නැවතත්, ආරම්භ කරන්න දැනට සහ ඊලඟ සෑම පුනරාවර්තනයක් සඳහාම අදාළ අක්ෂරවල වත්මන් සහ ඊළඟ පූර්ණ සංඛ්‍යා වල අගය ගබඩා කිරීමට
  4. I = 0 සඳහා අනුකරණය කරන්න i <එන්  (N = අරාවේ ප්‍රමාණය)
    • If i අරාවෙහි අවසාන දර්ශකය වේ, අපට ඊළඟ අක්ෂරයක් නොමැත, එබැවින් පූර්ණ සංඛ්‍යා අගය එකතු කරන්න නූල් [i] ආපසු එන්න ප්රතිඵලය
    • භාවිතා කරමින් වත්මන් සහ ඊළඟ අක්ෂරවල පූර්ණ සංඛ්‍යා අගය ලබා ගන්න getInteger ()
    • If වත්මන් <= ඊළඟ
      • එක් කරන්න දැනට සඳහා ප්රතිඵලය
      • වැඩි කිරීම i 1 කින්, එනම්, i++
    • එසේ නැතහොත්
      • එක් කරන්න ඊලඟ - දැනට සඳහා ප්රතිඵලය
      • වැඩි කිරීම i 2 කින්, එනම්, i + = 2
  5. ප්‍රති .ලය මුද්‍රණය කරන්න

රෝමානු සිට පූර්ණ ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

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

int getInteger(char c)
{
    switch(c)
    {
        case 'I' : return 1;
        case 'V' : return 5;
        case 'X' : return 10;
        case 'L' : return 50;
        case 'C' : return 100;
        case 'D' : return 500;
        case 'M' : return 1000;
        default : return -1;
    }
}

int romanToInt(string s)
{
    int n = s.size() , result = 0 , current , next , i = 0;
    while(i < n)
    {
        if(i == n - 1)
        {
            result += getInteger(s[i]);
            return result;
        }
        current = getInteger(s[i]) , next = getInteger(s[i + 1]);
        if(current >= next)
            result += current , i++;
        else
            result += next - current , i += 2;
    }
    return result;
}

int main()
{
    string s = "CXXIX";
    cout << romanToInt(s) << '\n';
    return 0;
}

ජාවා වැඩසටහන

class roman_to_int
{
    public static void main(String args[])
    {
        String s = "CXXIX";
        System.out.println(romanToInt(s));
    }

    static int getInteger(char c)
    {
        switch(c)
        {
            case 'I' : return 1;
            case 'V' : return 5;
            case 'X' : return 10;
            case 'L' : return 50;
            case 'C' : return 100;
            case 'D' : return 500;
            case 'M' : return 1000;
            default : return -1;
        }
    }

    static int romanToInt(String s)
    {
        int n = s.length() , result = 0 , current , next , i = 0;
        while(i < n)
        {
            if(i == n - 1)
            {
                result += getInteger(s.charAt(i));
                return result;
            }
            current = getInteger(s.charAt(i));
            next = getInteger(s.charAt(i + 1));
            if(current >= next)
            {
                result += current;
                i++;
            }
            else
            {
                result += next - current;
                i += 2;
            }
        }
        return result;
    }
}
129

රෝමානු සිට පූර්ණ සංඛ්‍යා ලීට්කෝඩ් විසඳුම දක්වා වූ සංකීර්ණ විශ්ලේෂණය

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

මෙන්න, අපි එක් වරක් නූල හරහා ගමන් කරමු. අපට පූර්ණ සංඛ්‍යා සීමාවක් 4000 ට වඩා අඩු බැවින්, නූල් ප්‍රමාණය සැමවිටම නියත අගයක් වනු ඇත. එබැවින් කාලය සංකීර්ණ වේ ඕ (1).

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

ඕ (1), අපි භාවිතා කරන්නේ නියත මතක අවකාශයක් පමණි.

ප්‍රවේශය (දකුණේ සිට වමට)

ඒවා ක්‍රියාත්මක කිරීමේදී දකුණේ සිට වමට සහ වමේ සිට දකුණට ඇති වෙනස. දකුණේ සිට වමට ගමන් කිරීමේදී, අරාවෙහි දෙවන අන්තිම දර්ශකයෙන් අපට ආරම්භ කළ හැකිය, අවසාන අක්ෂරයේ පූර්ණ සංඛ්‍යා අගය යම් විචල්‍යයක ගබඩා කරයි. අවසාන අක්‍ෂරයේ ඒකාග්‍ර අගය අපි ප්‍රති result ලයට පෙර තබා ගනිමු. දැන්, අපි දකුණේ සිට වමට ගමන් කරන විට, වර්තමාන අක්‍ෂරයේ පූර්ණ සංඛ්‍යා අගය අප දුටු අවසාන (පෙර / දකුණ) මූලද්‍රව්‍යයට වඩා අඩු දැයි අපි සෑම පියවරකදීම පරීක්ෂා කරමු. එය අවසාන අගයට වඩා අඩු නම්, අපි මෙම අගය ප්‍රති .ලයෙන් අඩු කරමු. එසේ නොමැති නම්, අපි එය අපගේ ප්රති .ලයට එකතු කරමු. මෙම ක්‍රියාවට නැංවීම මුළුමනින්ම පදනම් වී ඇත්තේ විශාල වටිනාකමක් ඇති කුඩා චරිතයකට පෙර කුඩා වටිනාකමක් ඇති අරුතකින් අදහස් කරන්නේ එය දෙවැන්නෙන් අඩු කළ යුතු බවයි.

මෙම ප්‍රවේශය පෙර ප්‍රවේශය මෙන් මෙහෙයුම් ගණනට බොහෝ දුරට සමාන වන නමුත් සෑම ක්‍රියාවලියක් සඳහාම අවසාන මූලද්‍රව්‍යය පරික්ෂා කිරීමෙන් අප ඉවත් වන බැවින් වඩාත් පහසු වේ.

ඇල්ගොරිතම

  1. ශ්‍රිතයක් සාදන්න getInteger () ඉහත ආකාරයට සමාන වේ
  2. හි ඇති අන්තිම අක්‍ෂරයේ පූර්ණ සංඛ්‍යා අගය ගබඩා කරන්න පෙර
  3. ආරම්භ කරන්න ප්රතිඵලය සමානයි පෙර
  4. සිට i = N - 2 තුරු i> = 0:
    1. වත්මන් අක්ෂරයේ පූර්ණ සංඛ්‍යා අගය ලෙස ගබඩා කරන්න දැනට
    2. If දැනට කට වඩා අඩු පෙර
      1. අඩු කරන්න දැනට සිට ප්රතිඵලය, එනම්, ප්රතිඵලය -= දැනට
    3. එසේ නැතහොත්
      1. එක් කරන්න දැනට දක්වා ප්රතිඵලය, එනම්, ප්රතිඵලය += දැනට
  5. ප්‍රති .ලය මුද්‍රණය කරන්න

රෝමානු සිට පූර්ණ ලීට්කෝඩ් විසඳුම ක්‍රියාත්මක කිරීම

සී ++ වැඩසටහන

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

int getInteger(char c)
{
    switch(c)
    {
        case 'I' : return 1;
        case 'V' : return 5;
        case 'X' : return 10;
        case 'L' : return 50;
        case 'C' : return 100;
        case 'D' : return 500;
        case 'M' : return 1000;
        default : return -1;
    }
}

int romanToInt(string s)
{
    int n = s.size();
    int prev = getInteger(s[n - 1]) , result = prev , current;
    for(int i = n - 2 ; i >= 0 ; i--)
    {
        current = getInteger(s[i]);
        if(current < prev)
            result -= current;
        else
            result += current;
        prev = current;
    }
    return result;
}

int main()
{
    string s = "CXXIX";
    cout << romanToInt(s) << '\n';
    return 0;
}

ජාවා වැඩසටහන

class roman_to_int
{
    public static void main(String args[])
    {
        String s = "CXXIX";
        System.out.println(romanToInt(s));
    }

    static int getInteger(char c)
    {
        switch(c)
        {
            case 'I' : return 1;
            case 'V' : return 5;
            case 'X' : return 10;
            case 'L' : return 50;
            case 'C' : return 100;
            case 'D' : return 500;
            case 'M' : return 1000;
            default : return -1;
        }
    }

    static int romanToInt(String s)
    {
        int n = s.length();
        int prev = getInteger(s.charAt(n - 1)) , result = prev , current;
        for(int i = n - 2 ; i >= 0 ; i--)
        {
            current = getInteger(s.charAt(i));
            if(current < prev)
                result -= current;
            else
                result += current;
            prev = current;
        }
        return result;
    }
}
129

රෝමානු සිට පූර්ණ සංඛ්‍යා ලීට්කෝඩ් විසඳුම දක්වා වූ සංකීර්ණ විශ්ලේෂණය

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

නැවතත්, අපි එක් වරක් නූල හරහා ගමන් කරමු. ඉහත සාකච්ඡා කළ පරිදි, කාලය සංකීර්ණ වේ ඕ (1).

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

ඕ (1), අපි භාවිතා කරන්නේ නියත මතක අවකාශයක් පමණි.