Сколько раз выполнится оператор := внутри следующих циклов:
a := 0;
while a <= 5 do
while a <= 10 do
a := a + 1;
Сколько раз выполнится оператор := внутри следующих циклов:
a := 0;
while a <= 10 do
while a <= 20 do
a := a + 1;
Сколько раз выполнится оператор := внутри следующих циклов:
a := 0;
while a <= 20 do
while a <= 10 do
a := a + 1;
Найти все двузначные числа, которые делятся на сумму своих цифр. Решить, используя вложенные циклы.
В этой главе рассматриваются свойства натуральных чисел: делители чисел, простые числа, наибольший общий делитель и наименьшее общее кратное.
3.1. Делители чисел
Решим такое задание:
Дано число М, вывести на экран все его делители.
Как решать такое задание? Для начала надо вспомнить, что является делителем числа. Как известно, делителем числа А называют такое число В, что А делится на В без остатка. Например, делителями 12 являются числа:
1, 2, 3, 4, 6 и 12.
В каком промежутке находятся делители любого числа? В промежутке от 1 до самого числа. Следовательно, для поиска делителей числа М надо проверить все числа от 1 до М. И для каждого перебираемого числа проверять: делится ли на него М без остатка? Если да, то вывести его на экран.
Для того чтобы проверить, делится ли одно число на другое без остатка, надо найти этот остаток и сравнить его с нулём. Понятно, что если остаток равен 0, то первое число делится на второе.
Чтобы перебрать все числа из промежутка, надо использовать цикл. Здесь удобней всего использовать цикл For,так как нам заранее известно сколько раз выполнится цикл (М раз).
Реализуем сказанное выше в процедуре, вставленной в программу.
Program Deliteli_Chisla;
Var M : integer;
ProcedureDeliteli (M : integer);
vari : integer;
For i := 1 to M do
If M mod i = 0 { Если М делится на i }
Thenwrite (i, ’ ’);
writeln;
Write (’Введите число М: ’);
Readln (M);
Writeln (’Его делители следующие:’);
Deliteli (M);
Writeln ;
Writeln (’Нажмите ENTER для выхода.’);
Readln
End.
· Замените в процедуре цикл For на While.
· Переделайте эту программу так, чтобы она искала сумму всех делителей числа.
· * измените эту программу и процедуру так, чтобы вводилось два числа, а выводились только их общие делители, то есть такие числа, на которые делится и первое число, и второе.
3.2. Простые числа
Рассмотрим пример из предыдущего пункта, при М=97. Что в этом случае выведет на экран только что составленная нами программа? Два числа: 1 и 97. Как известно, те числа, которые делятся только на единицу и на себя называются простыми. Поэтому 97 – простое число. Если число имеет больше двух делителей, то оно называется составным.
Вы знаете из математики, что простых чисел существует бесконечно много(логично предположить, что составных чисел тоже бесконечно много). Вот первые 10 простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Обратите внимание, что число 1 простым не является (и к составным его тоже не относят). Простые числа играют в алгебре очень важную роль. Поэтому давайте составим функцию, которая определяет, является ли аргумент простым числом.
Как составить такую функцию? Здесь, в отличии от предыдущего примера, нам нужно будет не выводить делители на экран, а считать их. И по числу найденных делителей уже можно будет определить: является число простым или нет. Как мы только что выяснили, простое число имеет всего два делителя. Функция будет иметь результат логического типа (boolean): True – если аргумент простое число и False в обраттном случае.
Вот сама программа с функцией для поиска простого числа.
Program Prostota;
Var M : integer;
FunctionProstoe (p : integer) : boolean;
vari, s : integer;
s := 0;
For i := 1 to M do
If p mod i = 0
Thens := s + 1;
prostoe := s = 2 { [7] }
Write (’Введите число М: ’);
Readln (M);
If prostoe (M)
Then Writeln (’Это число простое.’)
Else Writeln (’Это число составное.’);
Writeln (’Нажмите ENTER для выхода.’);
Readln
End.
§ Измените программу так, чтобы она правильно работала с начальным данным 1.
§ Измените функцию так, чтобы она работала быстрее.
§ Составьте программу, которая найдет первые М простых чисел (число М вводится с клавиатуры).
3.3. Наибольший общий делитель двух чисел.
НОД двух чисел А и В – это макимальное число, на которое делится и А, и В.
Например:
НОД (14, 21) = 7, НОД (16, 24) = 8.
Давайте составим процедуру, для нахождения НОД двух чисел. Как это сделать?! Подумайте, прежде чем читать дальше! Ещё раз внимательно прочитайте определение.
Так как найденный делитель должен быть общим, то на него должно делиться и первое число, и второе. Кроме того, нам нужен максимальный такой делитель. Если мы будем перебирать все общие делители в возрастающем порядке, то интересующий нас делитель будет последним. Переведём всё сказанное с русского языка на Паскаль:
Procedure NOD (a, b : integer; var rez : integer);
Var i : integer;
For i := 1 to a do
If (a mod i = 0) and (b mod i = 0)
Thenrez := i;
End;
Составьте самостоятельно программу, которая будет использовать эту процедуру.
§ Переделайте процедуру так, чтобы она находила НОД трёх чисел.
§ Если в цикле перебирать числа не в возрастающем порядке, а в убывающем, то результатом будет первое найденное число (объясните почему). В этом случае процедура будет работать быстрее. Переделайте программу, чтобы она искала делители в убывающем порядке!
3.4. Наименьшее общее кратное двух чисел
НОК двух чисел А и В – минимальное натуральное число, которое делится без остатка на А и на В. Исходя из определения можно искать это число следующим образом. Начиная с числа А (или с В) перебирать натуральные числа до тех пор, пока не найдем такое, которое будет без остатка делиться и на А, и на В. Здесь удобней будет использовать цикл While. Цикл For не подходит, потому что мы не знаем заранее, сколько чисел нам придётся перебрать, пока найдём НОК.
В заголовке цикла While надо записать такое условие, которое будет верно до тех пор, пока мы не найдём нужное число. То есть пока проверяемое число не будет делиться и на А, и на В без остатка.
Процедура поиска будет такой:
Procedure NOK (a, b : integer; var rez : integer);
rez := a;
While not((rezmoda = 0) and(rezmodb = 0)) do
rez := rez + 1; { Увеличиваем i, пока оно не будет делится и на а, и на b }
rez := i
End;
· Напишите программу для поиска НОД с использованием этой процедуры.
· Как известно, НОК двух чисел всегда больше или равен большему из этих чисел. Переделайте процедуру так, чтобы она начинала искать с наибольшего числа.
· Имеет место следующая формула: НОК (А, В) = (А*В) / НОД (А, В)
Составьте программу для нахождения НОК с использованием этой формулы и процедурой для нахождения НОД.
4.Массивы
4.1. Определение и примеры
Очень часто приходится иметь дело с большим объёмом однотипных данных. Например, изменения курсов валют за последние 3 года, или температура внутри холодильной установки, которая измеряется каждый час и т.п. Все эти данные надо уметь не только хранить, но и обрабатывать, например, проводить статистические исследования.
Рассмотрим такой пример: список учеников в группе. Это множество данных строчного типа. Их удобно записать в виде таблицы, например:
№
Имя
Катя
Инга
Оля
Илона
Антон
Владимир
Эта таблица состоит из 6 строк. В каждой строке указан номер строки и соответствующее этому номеру имя. То есть, по номеру строки можно однозначно найти конкретное имя. Например, номеру 4 соответствует имя Илона. Получается, что мы можем говорить об имени, не называя его конкретно, а только говоря, под каким номером оно записано.
Таблицы бывают одномерными, как только что представленная и многомерными. Основное их различие – количество чисел-координат для указания элемента. В только что приведённом примере для указания имени нужно назвать только номер строки (например, номеру 3 соответствует имя Оля). Если же мы допишем ещё один столбик, чтобы указать список учащихся из двух групп,
№
Группа Евгения
Группа Леонарда
Катя
Мантас
Инга
Марта
Оля
Александр
Илона
Олеся
Антон
Бригитта
Владимир
Михаил
то для доступа к какому-нибудь имени надо указать, во-первых, номер строки, а во-вторых, имя учителя. Это уже многомерная таблица, точнее двухмерная. Школьный журнал будет примером 3-мерной таблицы, так как там для указания оценки необходимо выбрать название предмета, дату и имя ученика – три координаты!
Может быть вы помните, как в начальных классах на природоведении вы вели дневник природы. Каждый день нужно было отмечать, какая была температура, облачность, были ли осадки, куда дул ветер. Таблица какого типа это была? Подумайте, прежде чем читать дальше! (Ответ найдете в конце главы).
Итак, таблицы используют для хранения каких-то однотипных данных, будь то список учеников, цены в магазине, каталог фирм или оценки по математике. Для хранения этих данных удобно использовать компьютер, так как он позволяет не только хранить данные, но и обрабатывать их с приличной скоростью. Таблицу в компьютерной реализации принято называть массивом. В этом случае все элементы массива должны содержать однотипные элементы.
Как уже говорилось, массивы могут быть многомерными. От размерности массива зависит количество координат, которые надо указывать для доступа к элементу. В информатике мы пока будем рассматривать только одномерные массивы.
Чтобы начать работу с массивом, необходимо его описать. Описание массива располагается там, где описываются все переменные в таком виде:
Var A : array [1..10] of integer;
Этой строкой мы описали массив (array) А, состоящий из 10 ([1..10]) элементов. Каждый элемент – это целое (integer) число. Можно сказать, что мы определили сразу 10 переменных целого типа. Чтобы определить массив из вещественных чисел, надо вместо integer написать real.
Для доступа к элементам массива используются квадратные скобки, в которых записывают номер необходимого элемента:
A[1], A[2], A[5], A[10]
Давайте составим простенькую программу для работы с массивом. Пусть это будет программа, которая задаёт массив из трех целых элементов и находит их сумму.
Program Summa_Elementov_Massiva;
Var A : array [1..3] ofinteger;
S : integer;
Writeln (’Введите элементы массива: ’);
Readln (A[1], A[2], A[3]);
S := A[1] + A[2] + A[3];
Writeln (’Сумма элементов массива = ’, S);
End.
Эта программа имеет недостаток. Если вдруг придётся работать не с 3 элементами, а с 10, то эту программу придется подвергнуть значительной модификации. Если же мы захотим ввести массив из N элементов, то общая схема решения вообще окажется непригодной.
Поэтому все программы, которые мы составляем, должны обладать свойством массовости, то есть работать с меняющимися данными. Поэтому должна существовать возможность обращения не к конкретному элементу, а к элементу, номер которого записан в виде переменной. Это делается очень просто: в скобках вместо числа-константы записывается имя переменной (или даже выражение). Например:
A[m], A[i], A[2*i+1], A[A[1]]
Для того, чтобы обрабатывать поочерёдно несколько элементов, надо использовать цикл. Вот как изменится программа:
Program Summa_Elementov_Massiva;
Var A : array [1..3] ofinteger;
S, i : integer;
Writeln (’Введите элементы массива: ’);
For i := 1 to 3 do
Readln (A[i]);
S := 0; { Обнуляем сумму }
For i := 1 to 3 do
S := S + A[i];
Writeln (’Сумма элементов массива = ’, S);
End.
Можно еще улучшить эту программу, объединив оба цикла в один, но мы этого делать не будем, так как тогда вообще отпадёт необходимость в использовании массива: сумму чисел можно подсчитать и так. Но дальше вы увидете, что использование массивов иногда облегчает решение задач, а чаще без них просто невозможно составить программу.
Ответ на задание: Это многомерная, точнее двумерная таблица. Но в ней хранятся неоднотипные данные, а в массивах (то есть в компьютерной реализации таблиц) могут храниться только данные одного типа. Как, например, вы запишите, что сегодня было облачно и шёл дождь, используя целые числа[8]?
4.2. Операции с элементами массива
Теперь вы уже можете составлять несложные программки для обработки данных в массиве. Мы уже с вами находили сумму элементов массива. Давайте теперь составим программу, которая
запросит массив из 10 элементов и увеличит на единицу каждый её элемент.
Как и раньше, для ввода массива мы будем использовать цикл for. Для оптимизации программы можно сразу в этом же цикле увеличивать элементы массива. Вот как это можно сделать:
Program Povyshenie_Stipendii;
Var A : array [1..10] ofinteger;
i : integer;
Writeln (’Введите 10 элементов массива: ’);
For i := 1 to 10 do
Readln (A[i]);
A[i] := A[i] + 1; {выполнение задания}
Writeln (’После повышения получим:’);
For i := 1 to 10 do
writeln (i, ’-ый элемент равен ’, A[i]);
End.
В программе можно использовать сразу несколько массивов. В одном может храниться, например, зарплата, во втором – премия, а в третьем – общий доход. Тогда, зная значения элементов первых двух массивов, можно вычислить элементы третьего массива. Для массовости алгоритма запросим количество элементов для обработки. Тогда из всех 100 элементов массива будут задействованы только первые n элементов, где n – число обрабатываемых элементов, оно вводится с клавиатуры. В этом случае удобней описать массив таким образом:
Var A : array [1..n] ofinteger;
Но так делать нельзя, так как компьютер перед запуском программы должен знать сколько надо выделить ячеек памяти для хранения массива. Переменная n же принимает значение только после запуска программы. В результате все элементы массива с номерами больше n не будут задействованы в программе, а будут только зря занимать память компьютера. И с этим приходится смириться. Однако можно использовать константу.
while a <= 10 do