Вычисление полиномов

Рассмотрим несколько методов вычисления полиномов и оценку cкорости вычисления значения

Program polinom1;

{вычисление полинома= P₀+P₁ X+P² X² +...P_n-1 X^n-1 +P_n Xⁿ }

Const n=8;

Var

i:integer;

p:array[0..n] of real;

natiga, {результат}

daraga:real; {степень}

Begin

read(x);

For i:=0 to n do read(p[i]);

natiga:=p[0];

write(natiga)

End.

При вычислении полинома в составном операторе {1} операции + и * выполняются 2n+n*(n+1)/2 раз.

При вычислении полинома в составном операторе {2} 3(n+1) раз выполняются операции + и * из них (n+1) операций + (более быстрые)..

Program polinom3; {вычисление полинома методом Горнера =P₀+X(P₁+X(P₂+...X(P_n-1+ XP_n)...)) }

Const n=8;

Var

i:integer;

p:array[0..n] of real;

natiga :real; {результат}

Begin

read(x);

For i:=0 to n do read(p[i]);

natiga:=0;

For i:=0 to n do natiga:=natiga*x+p[n-i] { 3 };

write(natiga)

End.

При вычислении полинома в операторе { 3 } 3(n+1) раз выполняются операции + и *. Из них 2(n+1) операций + (более быстрые).

Program polinom4; {вычисление полинома методом Горнера = P₀+X(P₁+X(P₂+...X(P_n-1+XP_n)...)) }

Const n=8;

Var

i:integer;

p:array[0..n] of real;

natiga :real; {результат}

Begin

read(x);

For i:=0 to n do read(p[i]);

natiga:=0;

For i:=0 downto n do natiga:=natiga*x+p[i] { 4 };

write(natiga)

End.

При вычислении полинома в операторе { 3 } 2(n+1) раз выполняются операции + и *. Из них n+1 операций + (более быстрые).

Факториал

Y=n!

Var y,n,i:integer;

Begin

Read(n);

write(y)

End.

Но при n>13 значение Y не представимо типом integer, поэтому можно применить int64. Но и здесь мы быстро дойдем до предела. Для этого типа n допустимо до 20.

Для решения этой задачи при больших значений необходимо самому написать фрагмент программы реализующий операцию умножения. Эта реализация требует определенный тип данных для представления получившегося числа. Так например, разряды этого числа могут представлятся как символы десятичных цифр в строковой переменной, либо как десятичные числа в массиве целых чисел. Далее рассмотрим вариант реализации через массив на языке Pascal и через длиную арифметику н языке Python.

При m=100 n может принимать значение до 70. Если вектор фактор объявить array[1..m] of byte, то m может принимать значение до 64000. При появлении ограничений по аппаратной реализации арифметки арифметические задачи можно решать с помощью программной реализации необходимых арифметических операций.

Сортировка

Существуют сотни методов решения задач сортировки последовательности чисел.

Их можно классифицировать в следующие четыре типа:

1. универсальный комбинаторный метод – перебор;

2. исключая по одному элементы из процесса решения;

3. разбивая элементы по группам и отдельно решая задачу сортировки для подмножества, затем объединяя упорядоченные множества вместе;

4. сортировать с учетом особенностей заданной последовательсти элементов.

Рассмотрим примеры этих методов.

Program1 perebor;

Const k=4; { длина вектора}

Var variant:array[1..k] of 1..k; {перестановка}

Procedure perebor_i(j:Integer; {номер ответа в подстановке}

zapr:set of 1..k {множество выбранных элементов});

Var i:Integer; { подбираемый элемент}

Bar:integer; { }

Begin { в j-ую позицию перестановки}

Bar:=true;

For I:=2 to k do if varint[I-1]>variant[I] then bar:=false

if bar then

begin

For I:=1 to k do write(varint[I]);

Halt

End;

If j>0 Then

For i:=1 to k do

If not (i in zapr) Then

Begin variant[j]:=i;perebor_i(j-1,zapr+[i]) End;

End;

Begin perebor_i(k,[ ]) End.

Время работы при переборе равно n!.

Сортировка отделением элемента от последовательности.

Program maximum;

{Поиск максимального элемента и установка в конец}

Const n=10;

Var y,max,i,j:integer;

x:array[0..n] of real;

Begin

For i:=0 to n do Read(x[i]);

For j:=0 to n-1 do

Begin

max:=j;

For i:=j+1 to n do If (x[max]>x[i] then max:=i

{смена значений}

y:=x[max]; x[max]:=x[j]; x[j]:=y;

Write(x[j],' ')

End

End.

Время работы при данном методе равно n*(n-1)/2.

Упорядочение последовательности методом слияния.

Program slianie;

Const n=8;

Var x,y:Array[1..n] of >Integer;

i,j1,j2,h:Integer;

Procedure joint(i1,i2:integer);

{Слияние двух упорядоченных последовательностей.}

Var L,i,j:integer;

Begin

L:=0;

j:=0;

For i:=0 to 2*h-L do

If j>=h Then

Begin y[i1+i]:=x[i1+L]; L+=1 End

Else

If L>=h Then

Begin y[i1+i]:=x[i2+j];j+=1 End

Else

If x[i1+L]>x[i2+j] Then

Begin y[i1+i]:=x[i1+L]; L+=1 End

Else Begin y[i1+i]:=x[i2+j]; j+=1 End

End;

Begin

For i:=1 to n do Read(x[i]);

h:=1;

While h<n do

Begin

j1:=1;

For i:=1 to n do y[i]:=0;

While j1+h<=n do

Begin j2:=j1+h; joint(j1,j2); j1:=j1+2*h End;

If j1<=n Then

For i:=j1 to n do y[i]:=x[i];

x:=y;

h+=h

End;

Write('вектор=');

For i:=1 to n do Write(x[i]:3)

End.

Время работы при использовании метода слияния равно n log₂n.

Последовательности с ограничениями

Program raznie;

{ Задана последовательность из различных значений. Для каждого элемента исходной последовательности определяется его порядковый номер в упорядоченной последовательности и ставится в соответствующее место упорядоченного массива .}

Const n=10;

Var i,j,k:Integer;

y,x:array[0..n] of Real;

Begin

For i:=0 to n do Read(x[i]);

For i:=0 to n do

Begin

k:=0;

For j:=0 to n do

If x[i]>x[j] then k:=k+1;

y[k]:=x[i]

End;

For i:=1 to n do Write(y[i])

End.

Время работы при данном методе равно n*n.

Program achkich;

{ Задана последовательность чисел X₁,X₂, ... ,X_n, где X_i принимает значения 1, 2 или 3. При решении этой задачи используется вектор R, где подсчитываются число элементов равных его индексу.}

Const n=10;

Var i,j:Integer;

r:array[1..3] of Integer;

x:array[1..n] of integer;

Begin

For i:=1 to n do Read(x[i]);

For i:=1 to 3 do R[i]:=0;

For i:=1 to n do

R[x[I]]:= R[x[I]]+1;

Write('Упорядоченная последовательность (');

For i:=1 to n do Write(x[I],' ');

Write(') = (')

For j:=1 to 3 do For i:=1 to r[j] do Write(j,' ');

Write(')')

End.

Время работы при данном методе равно n действий по вводу, счету числа значений от 1 до 3 и выводу.

13.2. 6. Фальшивая монета

Решение этой задачи приведем на татарском языке.

I. Дано n одинакого наминала манет. Одна из манет фальшивая и отличаетсясвоим весом. Также даны равноплечные весы. Сколько минимальное число взвешиваний позолят вычислить фальшивую манетту?

А) В случае если зарание легкости или тежелости фальшивой манеты.

Решение :

1) n=2.

За одно взвешивание выясняется. (ответ:1).

2) n=3.

Берем 2 манеты и кладем в 2 чаши. Если вес будет одинаковый, то третья манета бдет фальшивая. Если же веса будут разные, то по тяжести узнаем, какая из них фальшивая.

Ответ определяется одним взвешиванием. (ответ: 1)

3) n=3^k.

Все манеты разбиваем на 3 равные по числу группы. Две из нихложим на разные чаши. Если вес будет одинаковый, фальшивая манета в третьей группе. Если вес будет не равний, то по тяжести узнаем в какой группе.

Продолжаем делит группу на 3 части взвешивать.

Фальшивая манетааза k выясняется. (ответ: k)

4) 3^k-1<n<3^k.

Имеющиеся манеты разбиваем 3 группы[5] аналогично взвешиваем две груупы с одинаковым числом манет. Если равны, то в третьей группе, иначе в групе , где весы показавают фальшивую манету.

Если фальшивая манета окажется в третье группе, то дополняем до 3^k-.

Далее продолжаем как в А.3).

Фальшивая манета находится за k взвешиваний. (ответ: k)

Б) Если не известно,что тяжелее или легче фальшивая манета:

1) n=2.

Ответ: нет решения

2) n=3.

Две манеты ложатся на разные чаши.

Если будет равной, то третья манета будет фальшивой. Если вес будет разной, то третья манета не фальшивая. И вторую манету меняем на третью. Если вес этих манет будет равным, то вторая манета будет фальшивой, иначе первая манета фальшивая.

Таким образом, за 2 взвешивания определяется фальшивая манета. (ответ: 2)

3) n=4.

Взявь первые 2 взвешиваем.

Если вес будет равным, то эти манеты не фальшивые. В этом случае фальшивая манета либо третья, либо четвертая. Поэтому вторую манету заменим на третью. Если они равны, то четвертая манета, иначе третья.

Если вес разный, то фальшивая первая или вторая. Заменив вторую манету на третью не фальшивую манету, взвешиваем. Если вес одинаковый, то вторая фальшивая манет, иначе третья.

За два взвешивания можно найти фальшивую манету среди четырех. (ответ: 2)

4) n=5.

Первые 4 манеты по 2 ложим на чашу весов. (1,2 ? 3,4)

При равном весе фальшивая манета пятая, иначе пятая манета не фальшивая.

Если окажется неравной (1,2 > 3,4), убрав четвертую манету, на позицию четвертого положив вторую, а на место второй пятую, произведем взвешиввание (1^>,5 ? 2^>,3^<). Если вес будет равный, то четвертая манета фальшвая. Если (1^>,5 > 2^>,3^<), то 1^> или 3^< манета фальшивая. Одну из них заменим начетвертую манету и выясним какая из них фальшиивая. Если (1^>,5 < 2^>,3^<), то вторая манета фальшивая. Если (1^>,5 = 2^>,3^<), то четвертая манета фальшивая.

Фальшивую манету среди 5 манет можно 3 взвешивания определить. (ответ: 3)

5) При n=6,7,8,9 можно также за 3 найти фальшивую манету. (ответ: 3)

6) n=10, 11, 12.

Разбиваем манеты на группы по 3:

1,2,3; 4,5,6; 7,8,9; 10 {11,12}

Первые две группы ставим на чаши весов. Далее действуем как в 3) и 2).

В этих случаях требуется 3 взвешивания. (ответ: 3)

7) n=3^k.

Манеты на три равные группы делим.

Если вес одинаковый, то фальшивая манета в третьей группе. И так продолжаем до тех пор пока не появятся не равные группы.

Иначе вторую группу меняем на третью группу. После этого взвешивания определяется группа с фальшивой манетой и легче она или тяжелее не фальшивой манеты. Далее приеняя А.3) находим фальшивую манету.

Среди 3^k манет фальшивая манета находится за k+1 взвешиваний (ответ: k+1)

8) 3^k-1<n<3^k. (3^k-1<n<=3^k-1+3^k-2)

Среди N манет фальшивая манета находится за k взвешиваний. (ответ: k)

11) 3^k-1<n<3^k. (3^k-1+3^k-2<n<3^k)

В этом случае применяя А 3) и Б 7) среди N манет фальшивая находится за k+1 взвешиваний. (ответ: k+1)

Поменяем немного условия.

II.Дано n мешков денег одного достоинства. Один из мешков набит фальшивыми монетами отличающихся от настоящих на один грамм. Каким образом одним взвешиванием на электронных весах, определяющих вес с точностью в один грамм определить мешок с фальшивыми монетами?

Решение:

Перенумируем все мешки. Из каждого мешка число манет равное номмеру мешка. Взвесим выбранные манеты. В резултате вес этих манет будет 1a+2a+3a+4a… +la+l+…+na=n(n+1)a/2+l, где а – вес одной манеты. n(n+1)a/2 вес истинных манет. Добавка l указывает номер мешка с фальшивыми манетами.

Для решния этой задачи нужно одно взвешивание.

III.На базар один крестъянин привез 80-ти колограммовые мешки с ячменью. На базаре торговля зерном идет килограммами. Для торговли на равноплечных весах крестьянину надо заказать у кузнеца гири. Стоимость одной гири – мешок зерна. Какое минимальное число гирей нужно заказать, чтобы одним взвешиванием можно было бы отвесить требуемый вес.

Решение:

Часто, ответом звучит набор 1, 2, 4, 8, 16, 32, 64 кг гирь, позволяющих определить вес зерна как сумму степеней 2 на равноплечных весах. В этом случае надо заказать 7 гирей.

Но на равноплечных весах гири можно размещать с двух сторон.[6] Вместо 2 кг гири можно заказать3кг:

1 кг зерна= 1 кг гиря,

2 кг зерна + 1 кг гиря = 3 кг гиря,

3 кг зерна = 3 кг гиря,

4 кг зерна = 3 кг гиря + 1 кг гиря.

Теперь уже вместо 4 кг можно заказать более тяжелую гирю. Или с помощью 8 кг, которая в нашем наборе есть, можно взввесить либо вместо него 9 кг

5 кг зерна + 3 кг гиря = 8 кг гиря ó 5 кг зерна + 3 кг + 1 кг гиря = 9 кг гиря,

6 кг зерна + 3 кг гиря = 8 кг гиря + 1 кг гиря ó 6 кг зерна + 3 кг гиря = 9 кг,

7 кг зерна + 1 кг гиря = 8 кг гиряó 7 кг зерна + 3 кг гиря = 9 кг гиря + 1 кг,

8 кг зерна = 8 кг гиря ó 8 кг зерна +1 кг гиря= 9 кг гиря.

9 кг зерна = 9 кг гиря

10 кг зерна = 9 кг гиря + 1 кг гиря,

11 кг зерна + 1 кг гиря = 9 кг гиря + 3 кг гиря,

12 кг зерна = 9 кг гиря + 3 кг гиря,

13 кг зерна = 9 кг гиря + 3 кг гиря + 1 кг гиря.

Вместо 16 кг гири можно взять 27 кг,

14 кг зерна + 1 кг гиря + 9 кг гиря + 3 кг гиря = 27 кг гиря.

С помощью этих четырех гирь (1,3,9,27) можно взесить до 40 кг.

А с 41 до 80 можно определять зерна,который можно оставить. Оставляемыый вес от 1 до 40 кг.

Шуның белән сатучыга 4 гер җитә. Сатучы җиһазлар өчен 5 сум түләп сату итә ала.