Biz verdik array tam ədəd, q sorğu sayı. Hər bir sorğunun bir növü müəyyənləşdirən üç tam ədədi olduğu yer. Bu o deməkdir ki, 0 vermişiksə, o deməkdir ki, verilən aralıqda tək say seçmək ehtimalı tapmalıyıq. Aralığın başlanğıc nöqtəsi və bitmə nöqtəsi olaraq təyin olunduğu yer. Hər hansı bir növ xüsusi sorğunun bu spektri daxilində. Hər bir sorğu üçün həll tapmalısınız. Hər sorğu şəklində olacaq
TSE: T = 0 verdiyiniz təqdirdə, bu A sıra içərisində (S: Başlanğıc nöqtəsi, E: Son nöqtə) cütlüyün seçmə ehtimalını tapmalı olduğunuz deməkdir.
TSE: T = 1 vermisinizsə, deməli, verilmiş A massivində verilən aralığa (S: Başlanğıc nöqtəsi, E: Son nöqtə) tək say seçmək ehtimalını tapmaq lazımdır.
Mündəricat
misal
Input:
massiv [] = {2, 3, 4, 5, 6}
Sorğu 1: 1 1 3
Sorğu 1: 0 1 4
Çıxış:
1 / 3
1 / 2
Explanation:
bir sorğuda T = 1 verdik, yəni 1 və 3 aralığında tək bir ədədi seçmək ehtimalını tapmaq məcburiyyətindəyik.
bir sorğuda T = 0 verdik, yəni 1 və 4 aralığında cüt say seçmə ehtimalını tapmaq məcburiyyətindəyik.
Alqoritm
- Tək sıra və cüt ədədlər üçün müəyyən bir sıra ilə eyni ölçüdə iki sıra düzəldin. Dizinin hər ikisinin ilk elementini 0-a başlayın.
- Massivdən keçin və rəqəmin tək olub olmadığını yoxlayın, sonra yaratdığımız təkNömrəli sıra dəyərini tək [i] + 1 sayına və düz [i] rəqəminə yaratdığımız cüt massivə, cüt ədəd tapılsa da eyni şəkildə doldurun, tək sayını cari tək cütNömrələr massivinə, tək nömrələr massivini isə təkNövlər cərgəsinə saxlayın.
- Sorğu sayına qədər keçin və sağ, sol və 1 fərqini saxlayın.
- Ehtimalı tapmaq üçün cüt say və ya tək say seçməli olduğumuzu yoxlayın, əgər tək bir rəqəm varsa, onda probab-da dəyəri tək ədəd [sağ] və tək say [sol - 1] fərqi kimi saxlayın.
- Başqa birində probAB-da dəyəri evenNumber [sağ] və evenNumber [sol - 1] fərqi kimi saxlayın.
- Probabın 0-dan az və ya bərabər olduğunu yoxlayın, sonra 0-ı yazdırın, temp-ə bərabərdirsə, başqa birini yazdırın. Else sayılacaq ümumi lütf sayını tapın.
- Qiymət probabını və bu sayda üstünlükləri yazdırın.
Izahat
Saxlamaq üçün biri tək, digəri cüt nömrə üçün iki massiv yaradacağıq. İndi serialı keçib sıra elementinin tək və ya tək olduğunu tapacağıq. Cüt ədədi tək ədəd sayına saxlayacağıq. Və evenNumber-un əvvəlki dəyəri, evenNumber-un cari dəyərinə, sayı cüt olduqda eyni izlənilməlidir. Sonra tək dəyəri cütNo sayı və oddNumber massivinin əvvəlki dəyərini cari tək ədədin cari dəyərinə saxlayın. Bütün bunlar sırasıyla yaradılan massivlərdə bir sıra yaratmaq və doldurmaqdır.
Sorğunun növünü, sol və sağ nöqtələri bir sıra olaraq götürün, aralarındakı fərqi əldə edin. Verilən sorğunun hansı növdə olduğunu tapa bilərik. Əgər 1-dən böyükdürsə, cüt say seçmə ehtimalını tapmaq üçün tək say seçməliyik. Əks təqdirdə, aralıqda cüt ədədin olma ehtimalını tapacağıq. Əgər təkdirsə, onda yaratdığımız tək ədəd aralığının fərqini və cüt say ehtimalı ilə, cüt sayın fərqini alacağıq. Fərqi probabda saxlayacağıq və probab 0-dan az və ya bərabərdirsə 0 yazacağıq, yoxsa probab k-ya bərabərdirsə, 1-i çap edin. Başqa bir şeyin ümumi sayını tapmaq lazımdır. Və nəhayət, dəyər probabını və üstünlüklərini yazdırın.
Həyata keçirilməsi
Verilən aralıqlarda cüt və ya tək rəqəmin ehtimalına dair sorğular üçün C ++ proqramı
#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
Verilən aralıqlarda cüt və ya tək sayın ehtimalı barədə sorğular üçün Java proqramı
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
Verilən aralıqlarda cüt və ya tək rəqəmin ehtimalına dair sorğular üçün mürəkkəblik analizi
Zamanın mürəkkəbliyi
O (q * n) hara "Q" sorğuların sayı və "N" massivdəki elementlərin sayıdır
Kosmik Mürəkkəblik
O (n) hara "N" massivdəki elementlərin sayıdır.
