ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеМетоды и приемы программирования > Работа с целыми числами
Работа с целыми числами
Задачи, связанные со свойствами целых числе, весьма часто встречаются на начальных турах олимпиад школьников по информатике. Для того чтобы быть готовыми к их решению нужно изучить средства для работы с целыми числами в языках программирования.
          Так, например, в языке программирования Паскаль предусмотрен стандартный тип данных integer, значениями которого являются целые числа в диапазоне [–maxint..maxint]. Константа maxint является предопределенной, ее значение зависит от того, сколько байт памяти компьютера выделяется для размещения целого числа. То, что наибольшее допустимое значение целого число ограничено, является важным фактом, при решении многих олимпиадных задач. Например, целые числа типа integer в Turbo-Pascal являются не более чем пятизначными и их нельзя использовать для того, чтобы найти «счастливые» шестизначные номера.
          Над целыми числами в Паскале могут выполняться операции сложения, вычитания и умножения. Они имеют обычный смысл, однако не следует забывать об ограниченности данных целого типа, так как, например, при умножении может возникнуть переполнение значения (при перемножении двух трехзначных чисел получится шестизначное, а тип integer позволяет представлять не более чем пятизначные числа). В этом случае результатом будет «мусор», а не то, что ожидал получить программист. Эту особенность следует всегда иметь в виду.
          Особо следует рассмотреть операции целочисленного деления и нахождения остатка от целочисленного деления. В Паскале есть две операции деления. Одна из них обозначается косой чертой “/” – и выполняет вещественное деление, то есть результатом выполнения этой операции будет вещественное число (тип real). Кроме того, определена операция целочисленного деления, обозначаемая словом div. Результатом выполнения этой операции будет целое число, являющееся частным от деления двух целых чисел с остатком. Эту арифметическую операцию изучают в начальной школе и многие про нее забывают. Например, поделим 12 кирпичей на кучки по 5 штук. Выполним 12 div 5, получим 2 кучки по 5 кирпичей, и 2 кирпича будет в остатке. То есть, число 12=2*5+2.
          Для нахождения остатка от целочисленного деления в Паскале (и в Бейсике) введена операция mod. Ее результатом является целое число – остаток от деления целого делимого на целый делитель. Для нашего примера чтобы узнать, сколько кирпичей осталось нужно выполнить операцию 12 mod 5, ее результатом будет число 2. Рассмотрим несколько примеров использования операций целочисленного деления.
 
Пример 1. Напишем условие того, что целая переменная A кратна, целой переменной D.
 
В этом случае A делится на D без остатка, то есть остаток должен быть равен 0. Условный оператор на Паскале может быть записан следующим образом:
 
if A mod D=0 then begin
{действия}
end;
 
Пример 2. Найдем последнюю цифру в десятичной записи положительного значения целой переменной А.
 
Последняя цифра может быть получена как остаток от целочисленного деления переменной А на число 10. То есть, присвоить переменной B значение последней цифры A можно следующим образом:
B:=A mod 10;
 
Пример 3. Определить, сколько разрядов в десятичной записи положительно значения переменной A.
 
Чтобы решить задачу воспользуемся тем, что в результате целочисленного деления переменной A на 10, от десятичной записи ее значения отбрасывается младший разряд. Так, пусть A:=12121; B:=A div 10. В результате B будет иметь значение 1212. Если поделить нацело на 10 одноразрядное число, то частное будет равно 0. Используя эти свойства можно построить следующий алгоритм:
 
K:=0
Пока A>0
K:=K+1
A:=A div 10
Печать К.
 
Здесь переменная K увеличивается на 1 при отбрасывании очередного младшего разряда числа A. Соответствующая программа будет выглядеть так:
 
Program prim3;
Var A,K:integer;
Begin
Write(‘введите положительное целое число, A=’);
Readln(A);
K:=0;
While a>0 do
Begin
K:=K+1;
A:=A div 10
End;
Writeln(‘В десятичной записи введенного числа ‘,K,’ цифр’)
End.
 
Пример 4. Найти представление целого числа A в виде произведения простых множителей.
 
Есть простой способ разложения числа на простые множители. Например, представим в виде произведения простых множителей число 3212:
 
3212  | 2
166    | 2
83      | 83
1        |
 
Ответ: 3212=2*2*83
 
Алгоритм следующий: выбираем наименьше положительное число I (I>1) на которое делится (без остатка) заданное число A и делим на него A. Продолжаем делить частное на I пока оно кратно I. В противном случае, если частное не равно 1, находим следующее значение I, которому кратно частное, полученное в предыдущее операции. Если частное обратилось в 1, то разложение прекращается. Этот алгоритм можно реализовать следующей программой на Паскале:
 
Program prim4;
Var A,I:integer;
Begin
Write(‘введите положительное целое число, A=’);
Readln(A);
I:=2;
Write(a,’=’);
Repeat
While A mod I=0 do
Begin
Write(‘*’,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)).
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске
ebay coupons 2016