Берілген диапазондардағы жұп немесе тақ сандардың ықтималдығы туралы сұрақтар


Күрделілік дәрежесі қиын
Жиі кіреді Google Honeywell қиятын
Array

Біз ан массив бүтін сан, q сұраулар саны. Мұнда әр сұрауда сұраныстың түрін анықтайтын үш бүтін сан бар. Бұл дегеніміз, егер біз 0 берген болсақ, онда берілген диапазонда тақ санды таңдау ықтималдығын табуымыз керек дегенді білдіреді. Мұндағы ауқым бастапқы нүкте және аяқталу нүктесі ретінде анықталады. Сұраныстың кез-келген түрінің осы нақты шеңберінде. Әрбір сұрақтың шешуін табу керек. Әрбір сұрау келесі түрінде болады

TSE: егер сіз T = 0 берген болсаңыз, бұл берілген ауқымдағы жұп санды таңдау ықтималдығын (S: Starting Point, E: Ending Point) берілген массивтен табу керек дегенді білдіреді.

TSE: егер сіз T = 1 берген болсаңыз, онда берілген диапазонда тақ санды таңдау ықтималдығын (S: Starting Point, E: Ending Point) берілген массивтен табу керек дегенді білдіреді.

мысал

Кіру:

массив [] = {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. Массивті айналып өтіп, тақтың бар-жоғын тексеріңіз, содан кейін біз жасаған тақ санының массивін тақ [i] + 1 санына дейін, ал құрған жұп массивіне жұп [i] санына дейін толтырамыз, ал егер жұп сан болса, бірдей болады, тақ санды ағымдағы тақ жұп санға және тақ сан санға тақ сан санға сақтаңыз.
  3. Сұраныс санына дейін жүріп өтіп, оң, сол және 1 айырмашылықтарын сақтаңыз.
  4. Ықтималдықты табу үшін жұп немесе тақ санды таңдау керек пе, егер тақ сан болса, пробабтағы мәнді тақ санының [оң жақ] және тақ санның [сол жақ - 1] айырмасы ретінде сақтаңыз.
  5. Басқа мәні пробабта жұп сан [оң] және жұп санның [сол жақ - 1] айырмасы ретінде сақтайды.
  6. Пробабтың 0-ден аз немесе тең екенін тексеріп, содан кейін 0-ді басып шығарыңыз, егер ол темп-ке тең болса, содан кейін 1-ді шығарыңыз. Басқасы санауға болатын жағымдылықтардың жалпы санын табыңыз.
  7. Пробаб мәнін және сол жағымдылықты басып шығарыңыз.

Түсіндіру

Біз сақтау үшін екі массивті тақ санға және жұп санға құрамыз. Енді біз массивті айналып өтіп, массив элементінің тақ немесе жұп болғанын анықтаймыз. Біз жұп санды тақ санының массивіне сақтаймыз. Ал evenNumber-дің алдыңғы мәні, evenNumber-тің ағымдағы мәніне дейін, егер сан жұп болса, бірдей болады. Содан кейін тақ мәнін жұп сан нөміріне және тақ сан санының алдыңғы мәнін ағымдағы тақ сан санына сақтаңыз. Мұның бәрі массивті сәйкесінше құрылған массивтердегі сандармен толтыру және толтыру болып табылады.

Сұрау түрін, солға және оң жаққа диапазон ретінде алып, олардың айырмашылығын алыңыз. Берілген сұраныс қай типте екенін табамыз. Егер ол 1-ден үлкен болса, онда жұп санды таңдау ықтималдығын білу үшін тақ санды таңдауымыз керек. Басқа жағдайда біз жұп санның ықтималдығын диапазонда табамыз. Егер ол тақ болса, онда біз құрған тақ санының массивінің айырымын және жұп санының ықтималдығымен, жұп санының айырмасымен аламыз. Біз айырмашылықты пробабта сақтаймыз, егер пробаб 0-ден аз немесе оған тең болса, біз 0-ді шығарамыз, егер ол пробаб болса, к-ге тең болса, 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

Берілген диапазондардағы жұп немесе тақ сандардың ықтималдығы туралы сұраныстардың күрделілігін талдау

Уақыттың күрделілігі

O (q * n) қайда «Q» - сұраулар саны және «N» - бұл массивтегі элементтер саны

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.

анықтамалық