(Мендель А.В, Колегаева Е.М. Информатика 9-11 классы: подготовка учащихся к олимпиадам)
тема 1: Натуральные, целые, рациональные числа и операции над ними.
Пример1.
Напишем условие того, что целая переменная А кратна целой переменной D
В этом случае А делится на D без остатка, то есть остаток должен быть равен 0. Условный оператор на Паскале может быть записан следующим образом:
if A mod D = 0 then begin
{действия}
end;
Пример 2.
Найдем последнюю цифру в десятичной записи положительного значения целой переменной А.
Последняя цифра может быть получена как остаток от целочисленного деления переменной А на число 10. То есть присвоить переменной В значение последней цифра А можно следующим образом:
B:= A mod 10;
Пример 3.
Определить, сколько разрадов в десятичной записи положительного значения переменной А.
Чтобы решить задачу, воспользуемся тем, что в разультате целочисленного деления переменной А на 10 от десятичной записи ее значения отбрасывается младший разряд. Так, пусть А:=12121; B := A div 10. В результате В будет иметь значение 1212. Если поделить нацело на 10 число, то частное будет равно 0. Используя эти свойства, можно построить следующий алгоритм:
K:=0
Пока А>0
нц
К:=K+1
A:=A div 10
кц
Печатать К
Здесь переменная К увеличивается на 1 при отбрасывании очередного младшего разряда числа А. Соотвествующая программа будет выглядеть так:
program prim3;
Var a,k: integer;
begin
write('введите положительное число , А=');
readln(a);
K:=0;
While a>0 do
begin
k:=k+1;
a:=A div 10
end;
writeln(' В десятичной записи введенного числа',k,'цифр')
end.
Пример 4.
Найти представление целого числа А в виде произведения простых множителей.
Алгоритм следующий: выбираем наименьшее положительное число I (I>1), на которое делится без остатка заданное число А, и делим на него А. Продожаем делить частное на I, пока оно кратно I. В противном случае, если частное не равно 1, находим следующее значение I, которому кратно частное, полученное в предыдущей операции. Если частное обратилось в 1, то разложение прекращается. Этот алгоритм можно реализовать следующей прогроаммой на Паскале:
program prim4;
var a,i: integer;
begin
write('введите положительное целое число, А=');
readln(a);
i:=2;
write(a,'='();
repeat
while a mod i=0 do
begin
wtite('*',i);
a:=a div i;
end;
i:=i+1;
until a=1;
writeln;
end.
Внимательно посмотрите на эту программу и постарайтесь понять предложенное решение. Попробуйте найти ответ на вопрос, почему найденные таким образом делители числа являются простыми, а не составными числами.
В олимпиадных задачах часто нужно находить не только простые числа, но и все остальные множители заданного числа, напрмер при поиске совершенных чисел. Для этого можно использовать условие, сфоромулированное в примере 1. В таких задачах выбвает важно в целях оптимизации программы использовать тот факт, что елси найден один делитель какого-либо числа, то сразу получен и еще один делитель этого же числа. Напрмер, число 45 делится на 3, то есть 45 mod 3 = 0, частным от деления 45 на 3 является число 15, которое также делитель 45. То есть 45 = 3*15. В каждой паре делителей один меньше другого, либо оба делителя равны - число является квадратом этих делителей. Эти свойства позволяют ограничить перебор значений для поиска делителей числа квадратным корнем этого числа. и заменто ускорить работу программы.
Следует учитывать то, что функция "квадратный корень" SQRT имеет вещественный результат. Чтобы получить соответсвующее целое значение, нужно использовать функцию оругления - ROUND. На пример: K:=ROUND(SQRT(A)).
