س Quالات مربوط به احتمال عدد زوج یا فرد در دامنه های داده شده


سطح دشواری سخت
اغلب در گوگل شرکت Honeywell حال بارگذاری
صف

ما داده ایم صف عدد صحیح ، تعداد q پرسش. جایی که هر پرس و جو شامل سه عدد صحیح است ، که نوعی پرس و جو را تعریف می کند. این بدان معناست که اگر 0 داده باشیم به این معنی است که باید احتمال انتخاب عدد فرد را در محدوده داده شده پیدا کنیم. جایی که محدوده به عنوان یک نقطه شروع و یک نقطه پایان تعریف شده است. در این محدوده خاص از هر نوع پرسش خاص. شما باید راه حل هر پرس و جو را پیدا کنید. هر پرسش به صورت

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 پیدا کنیم.

س Quالات مربوط به احتمال عدد زوج یا فرد در دامنه های داده شده

الگوریتم

  1. دو آرایه برای اعداد فرد و زوج ایجاد کنید ، به اندازه آرایه داده شده. اولین عنصر هر دو آرایه را در 0 شروع کنید.
  2. آرایه را رد کنید و بررسی کنید که آیا عدد فرد است سپس مقدار آرایه oddNumber را که ایجاد کردیم به تعداد فرد [i] + 1 و در آرایه زوج ایجاد کردیم به عدد زوج [i] و اگر همان عدد زوج پیدا شود همان را پر کنید ، عدد فرد را در آرایه زوج زوج فعلی و آرایه فرد را به آرایه فرد و عدد ذخیره کنید.
  3. تعداد دفعات جستجو را طی کنید و تفاوت راست ، چپ و 1 را ذخیره کنید.
  4. بررسی کنید که آیا باید عدد زوج یا فرد را برای یافتن احتمال انتخاب کنیم ، اگر یک عدد فرد باشد ، سپس مقدار را در احتمال به عنوان تفاوت عدد فرد [راست] و عدد فرد [چپ - 1] ذخیره کنید.
  5. در غیر این صورت مقدار را در احتمال به عنوان تفاوت evenNumber [راست] و evenNumber [چپ - 1] ذخیره کنید.
  6. بررسی کنید که آیا احتمال کمتر از 0 است یا مساوی آن است ، سپس 0 را چاپ کنید. اگر دیگری برابر با دما باشد ، سپس چاپ کنید 1. در غیر این صورت تعداد کل امتیازات قابل شمارش را پیدا کنید.
  7. احتمال مقدار و تعداد امتیازات را چاپ کنید.

توضیح

ما قصد داریم دو آرایه ایجاد کنیم که یکی برای تعداد فرد و دیگری برای ذخیره تعداد باشد. حال ، ما می خواهیم آرایه را رد کنیم و ببینیم که آیا عنصر آرایه فرد است یا حتی فرد است. ما عدد زوج را در آرایه oddNumber ذخیره خواهیم کرد. و مقدار قبلی evenNumber به مقدار فعلی evenNumber ، همان است که اگر عدد زوج باشد نیز دنبال می شود. سپس مقدار فرد را به آرایه evenNumber و مقدار قبلی آرایه oddNumber را به مقدار فعلی oddNumber ذخیره کنید. همه اینها به ترتیب ایجاد و پر کردن یک آرایه با اعداد در آرایه های ایجاد شده است.

نوع پرس و جو ، نقاط چپ و راست را به عنوان یک دامنه دریافت کنید ، تفاوت آنها را بدست آورید. خواهیم یافت که پرسش داده شده از کدام نوع است. اگر بزرگتر از 1 باشد ، پس باید یک عدد فرد را انتخاب کنیم تا از احتمال انتخاب عدد زوج مطلع شویم. در غیر اینصورت احتمال عدد زوج را در یک دامنه پیدا خواهیم کرد. اگر فرد باشد ، اختلاف آرایه oddNumber که ایجاد کرده ایم و با احتمال عدد زوج یعنی اختلاف زوج یکسان خواهیم داشت. ما اختلاف در probab را ذخیره خواهیم کرد ، و اگر probab کمتر از یا برابر با 0 باشد ، 0 را چاپ خواهیم کرد ، در غیر این صورت اگر probab برابر باشد با k ، چاپ 1. در غیر اینصورت ما باید تعداد کل امتیازات را پیدا کنیم. و در آخر ، مقدار و احتمالات مورد نظر را چاپ کنید.

پیاده سازی

برنامه C ++ برای سeriesالات مربوط به احتمال تعداد زوج یا فرد در دامنه های داده شده

#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

برنامه جاوا برای نمایشگر سوال در مورد احتمال زوج یا فرد در دامنه های داده شده

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

تحلیل پیچیدگی برای س Quالات مربوط به احتمال عدد زوج یا فرد در دامنه های داده شده

پیچیدگی زمان

O (q * n) جایی که "Q" تعداد سeriesالات است و "n" تعداد عناصر آرایه است

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است.

ارجاع