Տրված տիրույթներում զույգ կամ կենտ թվերի հավանականության վերաբերյալ հարցումներ


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Google HONEYWELL Uber
Դասավորություն

Մենք տվել ենք դասավորություն ամբողջ թիվ, q հարցումների քանակ: Որտեղ յուրաքանչյուր հարցում պարունակում է երեք ամբողջ թիվ, որը սահմանում է հարցման տեսակ: Սա նշանակում է, որ եթե մենք տվել ենք 0, նշանակում է, որ մենք պետք է գտնենք տրված տիրույթում կենտ թիվ ընտրելու հավանականությունը: Որտեղ միջակայքը սահմանվում է որպես ելակետ և ավարտի կետ: Typeանկացած տեսակի որոշակի հարցման այս որոշակի տիրույթում: Յուրաքանչյուր հարցման համար պետք է լուծում գտնեք: Յուրաքանչյուր հարցում կլինի ձեւով

TSE. Եթե տվել եք T = 0, դա նշանակում է, որ դուք պետք է գտնեք տրված տիրույթում զույգ թիվ ընտրելու հավանականությունը (S: Մեկնարկային կետ, E: Վերջնակետ) տվյալ A զանգվածում:

TSE. Եթե տվել եք T = 1, ապա դա նշանակում է, որ դուք պետք է գտնեք տրված տիրույթում կենտ թիվ ընտրելու հավանականությունը (S: Մեկնարկային կետ, E: Վերջնակետ) տվյալ A զանգվածում:

Օրինակ

Մուտք:

զանգված [] = {2, 3, 4, 5, 6}

Հարցում 1: 1 1 3

Հարցում 1: 0 1 4

Արդյունք:

1 / 3

1 / 2

Բացատրությունը.

հարցման մեջ մենք տվել ենք T = 1, նշանակում է, որ մենք պետք է գտնենք ներառյալ 1 և 3 միջակայքում կենտ թիվ ընտրելու հավանականությունը:

հարցման մեջ մենք տվել ենք T = 0, նշանակում է, որ մենք պետք է գտնենք ներառյալ 1 և 4 միջակայքում զույգ թիվ ընտրելու հավանականությունը:

Տրված տիրույթներում զույգ կամ կենտ թվերի հավանականության վերաբերյալ հարցումներ

Ալգորիթմ

  1. Կենտ թվերի և զույգ թվերի համար ստեղծիր երկու զանգված, նույն չափի, ինչ տվյալ զանգվածը: Երկու զանգվածի առաջին տարրը սկզբնավորիր 0-ի:
  2. Անցեք զանգվածը և ստուգեք, արդյոք թիվը տարօրինակ է, ապա լրացրեք մեր կողմից ստեղծված oddNumber զանգվածի արժեքը մինչև կենդանի [i] + 1 թիվը և ստեղծեցինք զույգ զանգվածի համար նույնիսկ [i] թվին և նույնը, եթե գտնվի նույնիսկ զույգ թիվը, պահեք տարօրինակ թիվը ընթացիկ զույգ համարի զանգվածում, իսկ կենտ թվային զանգվածը `կենտ թվով զանգված:
  3. Անցեք հարցման քանակի անգամ և պահեք աջի, ձախի և 1-ի տարբերությունը:
  4. Ստուգեք, արդյոք մենք պետք է ընտրենք զույգ կամ կենտ համարը `հավանականությունը գտնելու համար, եթե կենտ թիվ է, ապա արժեքը հավանականության մեջ պահեք որպես կենտ համարի [աջ] և կենտ համարի [ձախ - 1] տարբերություն:
  5. Ուրիշը արժեքը պահեք probab- ում որպես evenNumber [աջ] և evenNumber [ձախ - 1] տարբերություն:
  6. Ստուգեք ՝ զոնդ փոքր է, թե հավասար է 0-ի, ապա տպեք 0. Ուրիշը, եթե հավասար է տեմպի, ապա տպեք 1. Ուրիշ գտեք առավելությունների ընդհանուր քանակը, որոնք կարելի է հաշվել:
  7. Տպեք արժեքի զոնդն ու այդ քանակի արտոնությունները:

բացատրություն

Մենք պատրաստվում ենք ստեղծել երկու զանգված `մեկը կենտ համարի և մեկը զույգի համար` պահելու համար: Այժմ մենք պատրաստվում ենք զանգվածը հատել և պարզել, թե զանգվածի տարրը տարօրինակ է կամ նույնիսկ տարօրինակ: Մենք պահելու ենք զույգ թիվը տարօրինակ թվերի զանգվածում: Եվ նույնիսկ հավասար թվով նախորդ արժեքը զույգ համարի ներկայիս արժեքին, նույնը պետք է հետևել, եթե համարը զույգ է: Ապա պահեք կենտ արժեքը զույգ համարի զանգվածին և կենտ թվով զանգվածի նախորդ արժեքին ներկայիս կենտ համարի ընթացիկ արժեքին: Այս ամենը ստեղծում և լրացնում է զանգվածը համապատասխանաբար ստեղծված զանգվածների թվերով:

Որպես միջակայք վերցրեք հարցման տեսակը, ձախ և աջ կետերը, ստացեք դրանց տարբերությունը: Մենք կգտնենք, թե տրված հարցումը որ տեսակի է: Եթե ​​այն 1-ից մեծ է, ապա մենք պետք է ընտրենք կենտ թիվ ՝ պարզելու համար զույգ թիվ ընտրելու հավանականությունը: Այլապես մենք կգտնենք զույգի թվի հավանականությունը տիրույթում: Եթե ​​դա կենտ է, ապա մենք կստանանք մեր ստեղծած կենտ Թվաքանակի զանգվածի տարբերությունը և նույնը նույն թվերի հավանականությամբ `զույգ թվերի տարբերությամբ Մենք կպահենք probab- ի տարբերությունը, և եթե probab- ը 0-ից փոքր է կամ հավասար, մենք կ տպենք 0, այլապես, եթե probab- ը հավասար է k- ի, տպիր 1. Այլապես մենք պետք է գտնենք առավելությունների ընդհանուր քանակը: Եվ վերջապես, տպեք արժեքի զննումն ու շնորհները:

Իրականացման

Տրված տիրույթներում զույգ կամ կենտ թվերի հավանականության վերաբերյալ հարցումների համար C ++ ծրագիր

#include<iostream>

using namespace std;

#define C 3

int getDivisor(int a, int b)
{
    if (a == 0 || b == 0)
        return 0;

    if (a == b)
        return a;

    if (a > b)
        return getDivisor(a - b, b);

    return getDivisor(a, b - a);
}

void solveQuery(int arr[], int n, int Q,int query[][C])
{
    int evenNumber[n + 1];
    int oddNumber[n + 1];
    evenNumber[0] = oddNumber[0] = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] & 1)
        {
            oddNumber[i + 1] = oddNumber[i] + 1;
            evenNumber[i + 1] = evenNumber[i];
        }
        else
        {
            evenNumber[i + 1] = evenNumber[i] + 1;
            oddNumber[i + 1] = oddNumber[i];
        }
    }
    for (int i = 0; i < Q; i++)
    {
        int right = query[i][2];
        int left = query[i][1];
        int T = query[i][0];

        int dif = right - left + 1;
        int probab;

        if (T)
            probab = oddNumber[right] - oddNumber[left - 1];
        else
            probab = evenNumber[right] - evenNumber[left - 1];

        if (!probab)
            cout << "0" << endl;

        else if (probab == dif)
            cout << "1" << endl;

        else
        {
            int div = getDivisor(probab, dif);
            cout << probab / div << "/" << dif / div << endl;
        }
    }
}

int main()
{
    int arr[] = { 2,3,4,5,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 2;
    int query[Q][C] = { { 1, 1, 3 },
        { 0, 1, 4 }
    };

    solveQuery(arr, n, Q, query);
    return 0;
}
1/3
1/2

Տրված տիրույթներում զույգ կամ կենտ թվերի հավանականության հարցումների համար Java ծրագիր

public class QueryProbability
{
    static int getDivisor(int a, int b)
    {
        if (a == 0 || b == 0)
            return 0;

        if (a == b)
            return a;

        if (a > b)
            return getDivisor(a - b, b);

        return getDivisor(a, b - a);
    }
    
    static void solveQuery(int []arr, int n, int Q, int [][]query)
    {
        int []evenNumber = new int[n + 1];
        int []oddNumber = new int[n + 1];
        evenNumber[0] = oddNumber[0] = 0;

        for (int i = 0; i < n; i++)
        {
            if ((arr[i] & 1) > 0)
            {
                oddNumber[i + 1] = oddNumber[i] + 1;
                evenNumber[i + 1] = evenNumber[i];
            }
            else
            {
                evenNumber[i + 1] = evenNumber[i] + 1;
                oddNumber[i + 1] = oddNumber[i];
            }
        }
        
        for (int i = 0; i < Q; i++)
        {
            int right = query[i][2];
            int left = query[i][1];
            int T = query[i][0];

            int dif = right - left + 1;
            int probab;
            if (T > 0)
                probab = oddNumber[right] - oddNumber[left - 1];
            else
                probab = evenNumber[right] - evenNumber[left - 1];

            if (probab <= 0)
                System.out.println("0");
            else if (probab == dif)
                System.out.println("1");

            else
            {
                int div = getDivisor(probab, dif);
                System.out.println(probab / div + "/" +dif / div);
            }
        }
    }
    
    static public void main (String[] args)
    {
        int []arr = { 2, 3, 4, 5, 6 };
        int n = arr.length;
        int Q = 2;
        int [][]query = { { 1, 1, 3 },
            { 0, 1, 4 }
        };

        solveQuery(arr, n, Q, query);
    }
}
1/3
1/2

Տրված տիրույթներում զույգ կամ կենտ թվերի հավանականության վերաբերյալ հարցումների բարդության վերլուծություն

Timeամանակի բարդություն

O (q * n) որտեղ "Q" հարցումների քանակն է և «Ն» զանգվածում տարրերի քանակն է

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է:

Մանրամասն