Ваш друг написал программу которая м раз запрашивает какие-то элементы из массива. так как доступ к этому массиву медленный, он попросил вас реализовать кэш при массива b, с гораздо более быстрым доступом. так как вам известны все запросы к массиву a, которые сделают программа вашего друга, то вашей основной является посчитать минимальное количество кэш - промахов, которые может случиться для этих запросов.

Показать ответ

Ответ:

tretekova86

26.10.2020 22:55

Объяснение:

Немного математики:

Вся заштрихованная область представляет собой решение некоторой системы уравнений. Например, I четверть координатной плоскости задается x > 0, y > 0. Этот случай относится к тому, что область принадлежит той самой I четверти.

Теперь у нас есть два варианта решения: проверить принадлежности x к отрезку (0; 7), а затем разбить на два условия: если точка принадлежит отрезку (0;5], то координата y должна принадлежать (0;5). Иначе если координата икс в отрезке [5;7), то координата y должна быть меньше некоторой линейной функции, проходящей через точки (5;5) и (7;0)

Второй вариант (он будет оптимальнее): сначала проверить принадлежность координаты y в отрезке (0;5). Если это так, то проверить выполнение условия 0 < x < f(y), где f(y) - это некоторая линейная функция.

Давайте найдем эту линейную функцию.

Если линейная функция задается уравнением y = kx + b, то справедлива система:

$\left \{ {{5k +b =5} \atop {7k + b=0}} \right.$

От второго отнимаем первое уравнение, получаем 2k = -5, или k = -2.5, а b будет при этом равно 17,5

Теперь найдем обратную функцию (решать будем по второму варианту)

$y = -2.5x + 17.5\\2y = -5x + 35\\35 - 2y = 5x\\x = 7 - 0.4y$

Теперь, точка считается внутри фигуры, если выполняется:

0 < y < 5

0 < x < 7 - 0.4y

Сама программа:

program task;

var x, y: real;

begin

writeln('Введите координаты точки х и y: ');

readln(x, y);

if ((y > 0) and (y < 5)) then begin

if ((x > 0) and (x < 7 - 0.4*y)) then writeln('Попадает')

else writeln('Не попадает')

end;

end.

0,0(0 оценок)

Ответ:

Марі2017

24.09.2020 01:31

Количество различных салатов R, которые можно приготовить, имея n продуктов и беря для приготовления k из них (k=2,3,... n-1), в математике определяется, как число размещений из n по k и определяется по следующей формуле:
$\displaystyle C_n^k= \frac{n!}{k!(n-k)!}$
Формула красивая, короткая, но неудобная для вычисления. В самом деле, надо найти три факториала, каждый из которых может оказаться достаточно большим числом. Но можно сделать небольшое преобразование и упростить вычисление.
$\displaystyle R=C_n^k= \frac{n!}{k!(n-k)!} = \frac{k!(k+1)(k+2)...(n-1)n}{k!(n-k)!}= \\ 
 \frac{(k+1)(k+2)...(n-1)n}{1\cdot2\cdot...\cdot(n-k)}=\prod_{i=1}^{n-k} \frac{k+i}{i}$

Но это было вычисление R только для конкретного k при заданном n.
Нам же нужно найти сумму R для всех k от 2 до n. И да, для k=n формула не предназначена, но зато мы и так понимаем, что для такого случая R=1.

Задача свелась к нахождению обычной суммы
$\displaystyle S=C_2^n+C_3^n+...+C_{n-1}^n+1=1+\sum_{i=2}^{n-1}C_i^n$

// PascalABC.NET 3.2, сборка 1370 от 24.12.2016
// Внимание! Если программа не работает, обновите версию!

function C(n,k:integer):integer;
begin
if n=k then Result:=1
else begin
    var p:=1.0;
    for var i:=1 to n-k do p:=p*(k+i)/i;
    Result:=Round(p);
    end;
end;

begin
var n:=ReadInteger('Кол-во продуктов: ');
var s:=1;
for var i:=2 to n-1 do s:=s+C(n,i);
Writeln('Кол-во салатов: ',s)
end.

Примеры:
Кол-во продуктов: 3
Кол-во салатов: 4

Кол-во продуктов: 5
Кол-во салатов: 26

Кол-во продуктов: 10
Кол-во салатов: 1013

0,0(0 оценок)

Популярные вопросы: Информатика