Некоторый исполнитель может выполнять над целыми числами кроме операций сложения, вычитания, умножения и деления еще две операции: с операции div вычисляется целое частное, с операции mod – остаток. Например: 5 div 2=2; 5 mod 2=1; 2 div 5=0; 2 mod 5=2
Покажем как с этих операций можно реализовать алгоритм работы кассира, выдающего покупателю сдачу (s) наименьшим количеством банкнот по 1000 (k1000), 500 (k500), 100 (k100) и 50 (k50).
k1000:= s div 1000
s:=s mod 1000
k500:= s div 500
s:=s mod 500
k100:= s div 100
s:=s mod 100
k50:= s div 50
Исполните алгоритм для s=234 и s=1299. Составьте соответствующие таблицы значений переменных.
ответ:Алгоритм Карацубы — метод быстрого умножения со сложностью вычисления nlog23. В то время, как наивный алгоритм, умножение в столбик, требует n2 операций. Следует заметить, что при длине чисел короче нескольких десятков знаков (точнее определяется экспериментально), быстрее работает обычное умножение.
Представим, что есть два числа A и B длиной n в какой-то системе счисления BASE:
A = an-1an-2...a0
B = bn-1an-2...a0, где a?, b? — значение в соотв. разряде числа.
Каждое из них можно представить в виде суммы их двух частей, половинок длиной m = n / 2 (если n нечетное, то одна часть короче другой на один разряд:
A0 = am-1am-2...a0
A1 = an-1an-2...am
A = A0 + A1 * BASEm
B0 = bm-1bm-2...b0
B1 = bn-1bn-2...bm
B = B0 + B1 * BASEm
Тогда: A * B = ( A0 + A1 * BASEm ) * ( B0 + B1 * BASEm ) = A0 * B0 + A0 * B1 * BASEm + A1 * B0 * BASEm + A1 * B1 * BASE2 * m = A0 * B0 + ( A0 * B1 + A1 * B0 ) * BASEm + A1 * B1 * BASE2 * m
Здесь нужно 4 операции умножения (части формулы * BASE? * m не являются умножением, фактически указывая место записи результата, разряд). Но с другой стороны:
( A0 + A1 ) * ( B0 + B1 ) = A0 * B0 + A0 * B1 + A1 * B0 + A1 * B1
Посмотрев на выделенные части в обоих формулах. После несложных преобразований количество операций умножения можно свести к 3-м, заменив два умножения на одно и несколько операций сложения и вычитания, время выполнения которых на порядок меньше:
A0 * B1 + A1 * B0 = ( A0 + A1 ) * ( B0 + B1 ) — A0 * B0 — A1 * B1
Окончательный вид выражения:
A * B = A0 * B0 + (( A0 + A1 ) * ( B0 + B1 ) — A0 * B0 — A1 * B1 ) * BASEm + A1 * B1 * BASE2 * m
Объяснение:
var a: array [1..10] of integer; //Объявление целочисленного массива а размером 10 эл.
i, s: integer; //Объявление двух целочисленных переменных
begin //начало
randomize; //Включает датчик случайных чисел(в PascalABC.NET можно не писать)
for i:= 1 to 10 do //Запускается цикл от 1 до 10
a[i]:=random(15-5+1)+5; //Текущему элементу присваивается случайное значение от 5 до 15. И так до тех пор, пока не закончится цикл, т.е. через 10 шагов
for i:= 1 to 10 do //Запускается цикл от 1 до 10
write (a[i], ' '); //Выводится текущий элемент массива. И так до тех пор, пока не закончится цикл, т.е. через 10 шагов
s:=0; //Переменной для суммы присваивается 0
for i:= 1 to 10 do //Запускается цикл от 1 до 10
if a[i] mod 3=0 then //Если текущий элемент массива делится на 3 без остатка тогда
s := s + a[i]; //к сумме прибавляется текущий элемент массива
write('сумма = ',s); //вывод сообщения и значение переменной s
end. //конец
2. Дан массив 16 1 8 2 4 4
к=0
со 2 по 6 делаем
если A[i-1] >=A[i] , делаем к=к+1
1 итерация: если A1>=A2 (A1=16, A2=1, 16>1, значит к=к+1 = 1)
2 итерация: если A2>=A3 (A2=1, A3=8, 1>8? нет, значит к остается прежним)
3 итерация: 8>2? да к=2
4 итерация: 2>4? нет к=2
5: 4>=4? да к=3
выводим к=3