Поиск наибольшего числа

Предположим, нам необходимо ввести с клавиатуры N чисел, найти из них наибольшее и вывести его. Для решения этой задачи предлагается следующий алгоритм:

1. Ввести первое число в переменную Max.
2. Ввести следующее число в переменную Next.
3. Если Next>Max, то Max:=Next.
Пункты 2 и 3 повторять, пока не будут введены все числа.
4. Вывести значение переменной Max.

Действительно ли будет напечатано наибольшее из N чисел? Докажем это.

После выполнения первого пункта в переменной Max находится наибольшее из уже введенных чисел. Это справедливо, т.к. введено лишь одно число.
Повторение пунктов 2 и 3, в сущности, представляет собой цикл, который выполняется, пока не будут введены все числа. Если перед очередным повторением цикла в Max находится наибольшее из введенных чисел, то после выполнения пунктов 2 и 3 там снова будет наибольшее из введенных чисел.
В последнем пункте значение Max будет выведено.

Этот пример показывает, что алгоритм можно доказать, как доказывают математическую теорему. Программируя доказательный алгоритм, можно не опасаться ошибок в алгоритме, конечно, если нет ошибок в доказательстве.

Program maximum;
Var N, max, next, k: integer;
Begin
Write('Введите количество чисел'); Readln(n);
Write('Введите число'); Readln(max);
k:=1;
repeat
Write('Введите число'); Readln(next);
K:=k+1;
If next>max then max:=next
Until k=n;
Writeln(max);
Readln
End.

Тренировочные задания.
1. Введите с клавиатуры 6 чисел и определите их среднее арифметическое.
2. Напишите программу, которая вводит целые числа с клавиатуры и складывает их, пока не будет введено число 0.
3. Напечатайте 20 первых степеней числа 2.
4. Найдите минимальное из N чисел.
5. Дано натуральное число. Выяснить, является ли оно простым, т.е. делится только на 1 и на само себя.

Урок 12

Вычислительные машины имеют дело не только с числами. Едва ли не больше времени они бывают заняты обработкой текста. В Паскале для этого есть специальный тип данных, который называется CHAR (от слова character - символ).

12.1.Тип CHAR (символьный или строковый или литерный).
Его значениями являются отдельные символы: буквы, цифры, знаки. Символьные константы заключаются в кавычки, например, 'A', 'B', 'C', '4', '7', ' '(пробел).

Символьные переменные описываются предложением:

Var имя переменной: char;

Символьные значения можно вводить и выводить, присваивать, сравнивать. Ниже приведен пример, где выполняются все эти действия.

Var x,y:char;
Begin
Write('Введите символ');
Readln(x);
Y:='A';
If x<y then write ('X') else write ('y');
{на экран буде выдан символ хранящийся в переменной
Х или Y в зависимости от проверки условия}
Readln;
End.

Сравнивать символы можно благодаря тому, что в машинной памяти они хранятся в виде целых чисел (кодов символов). Из двух символов большим считается тот, код которого больше. Символы упорядочены следующим образом:

'A'<'B'<...<'Z'
'a'<'b'<...<'z'
'0'<'1'<...<'9'
'а'<'б'<...<'я'
'А'<'Б'<...<'Я'

Для символов допустимы все шесть операций сравнения: =, <=,>=,<,>,<>.

12.2.Стандартные символьные функции.
В Паскале имеются стандартные символьные функции:

CHR(N) - возвращает в программу символ с кодом N,
ORD(S) - возвращает код символа S,
PRED(S) -возвращает предыдущий символ
SUCC(S) - возвращает следующий символ

Примеры:
CHR(128) = Б
ORD(':') = 58
PRED('Б') = А
SUCC('Г') = Д

Каждый символ имеет свой уникальный двоичный код. Коды всех символов сведены в таблицу. Первая половина таблицы стала международным стандартом, который называется ASCII - American Standard Code Information Interchange (читается "аски код") в ней кроме прочего содержится латинский алфавит, вторая имеет разные варианты для разных языков. Кириллица (русский алфавит) имеет несколько стандартов. В Паскале используется стандарт КОИ-8.

Пример использования переменной символьного типа.
Составить программу, по которой компьютер многократно вычисляет сумму А+В при различных значениях А и В. в конце каждого этапа появляется запрос о продолжении или прекращении вычислений: "Завершить программу?(Д/Н)".

Var A,B:real; { PROGRAM имя; не обязательное предложение}
C: char;
Begin
repeat
Write('Введите два числа'); Readln(a,b);
Writeln(a+b:0:2);
Writeln('Завершить программу?(Д/Н)');
Readln(с);
Until с='Д'; {программа завершит работу если будет введено Д}
Readln
End.

Тренировочные задания.
1. Что вернет функция CHR(ORD(X))?
2. Определить значения следующих функций (как правило таблица аски кодов есть в любом справочнике по программированию):
CHR(68)
ORD('d')
PRED(1)
SUCC('Я')
3. С клавиатуры вводится два числа. Составить программу сравнивающую эти числа и в зависимости от результата сравнения выводящую на экран нужный знак. Например: 3<5 или 3=3 или 3>2. Процедуру WRITE для вывода результата разрешается использовать только один раз.
4. Составить программу, по которой компьютер находит произведение нечетных чисел, начиная с единицы, и до тех пор, пока на вопрос, задаваемый после каждого шага вычислений: "Продолжить вычисления? (Д/Н)", отвечают 'Д'.

Урок 13

Сегодня мы познакомимся с оператором, который обеспечивает повторение цикла, управляемое переменной.

13.1. Цикл ПЕРЕСЧЕТ (прямой).
Формат оператора:

FOR переменная:= выражение 1 ТО выражение 2 DO оператор;

Переменная должна быть порядкового типа. Порядковыми называются все простые типы, значения которых можно расположить в возрастающем порядке. Из известных нам это: INTEGER, WORD, LONGINT, BYTE, CHAR. Выражение 1 и Выражение 2 должны быть того же типа, что и переменная. Чтобы цикл выполнился хотя бы раз выражение1 должно быть не больше выражения2.

Выполнение начинается с вычисления значений выражения1 и выражения2. затем переменная получает значение выражения1 и делается проверка, не превышает ли значение переменной выражения2. Если не превышает, выполняется оператор стоящий после служебного слова DO. После завершения оператора переменная получает следующее по порядку значение, и все повторяется, начиная с проверки.

Когда значение переменной становится равным выражению2, оператор выполняется последний раз.

ПРИМЕР 1. Напечатать ряд из повторяющихся чисел 20 в виде:
20 20 20 20 20 20 20 20 20 20

Код программы:

var i: byte;
begin
for I:=1 to 10 do write(20,' ');
readln;
end.

ПРИМЕР 2. Напечатать числа следующим образом:
10 10.4
11 11.4
...
25 25.4

Код программы (переменная используется не только для управления циклом но и для вывода на экран в качестве результата):

var i: byte;
begin
for I:=10 to 25 do write(I,' ',I+0.4:0:1);
{при сложении целого I и вещественного 0.4 получаем
вещественный результат, значит надо выполнить его
форматирование при выводе на экран}
readln;
end.

13.2. Цикл ПЕРЕСЧЕТ (обратный).
Возможен вариант оператора, когда переменная принимает последовательно убывающие значения.
Формат оператора:

FOR переменная:= выражение 1 DOWNТО выражение 2 DO оператор;

В этом случае, чтобы цикл выполнился хотя бы раз, выражение1 должно быть не меньше выражения2. Например:

For c:='z' downto 'а' do writeln(с);

Тренировочные задания.
1.Напечатать столбиком:
а) все целые числа от 20 до 35;
б) квадраты всех целых чисел от 10 до b (значение d вводится с клавиатуры; b>=10);
в) третьи степени всех целых чисел от а до 50 (значение а вводится с клавиатуры; а<=50);
г) все целые числа от а до b (значения а и b вводятся с клавиатуры; d>=a).

2. Напечатать числа следующим образом
25 25.5 24.8
26 26.5 25.8
...
35 35.5 34.8

3. Распечатать в столбик таблицу умножения на 7.

4. Вывести столбиком следующие числа: 2,1 2,2 2,3..., 2,8

5. Вывести столбиком следующие числа: 2,2 2,4 2,6..., 4,0 4,2

6. Вывести столбиком следующие числа: 4,4 4,6 4,8..., 6,2 6,4

Урок 14

Задача 1.
Дано натуральное число N. Определить, является ли оно простым, т.е. делится нацело только на 1 и на само себя. (Мы решали эту задачу в 12 уроке, но я хочу предложить вам другой алгоритм решения.)
Для решения необходимо проверить, делится ли исходное число на числа от 2 до N-1. Если число делится хотя бы на одно из чисел без остатка, то число N не будет простым. Мы можем уменьшить интервал проверяемых делителей так, как наибольший из возможных, это N/2. Введем так же дополнительную переменную F, она будет принимать значение 1, если обнаружится хотя бы один из делителей для исходного числа. Первоначально присвоим F значение 0, т.е. предположим, что число простое.
Переменные:
N - исследуемое число;
I - переменная цикла;
F - вспомогательная переменная.

Код программы.

Var I,n,f:word;
Begin
Write('Введите натуральное число');
Readln(n);
F:=0;
For I:=2 to n div 2 do if n mod I=0 then f:=1;
If f=1 then writeln('число',n:6,' не простое')
Else writeln('число',n:6,' простое');
Readln
End.

Количество выполнения циклов можно еще уменьшить. Ведь на самом деле если число N делится на какое-то число А без остатка (кроме 1 и самого себя), то оно имеет и второй делитель В=N/A, т.е. если число не простое то его всегда можно записать как N=A*B. При возрастании первого делителя, значение второго будет уменьшаться. Получается, что достаточно проверить все числа от 2 до SQRT(n), но так как результат вычисления корня вещественный, а параметр цикла должен иметь целое значение, применим функцию определения целой части числа TRUNC, и получим:

For I:=2 to trunc(sqrt(n)) do if n mod I=0 then f:=1;

Задача 2.
Даны натуральные числа M и N. Определить, являются ли они взаимно простыми. Взаимно простые числа не имеют общих делителей, кроме 1.

Для решения задачи:
- вводим натуральные числа М и N;
- в цикле от 2 до наименьшего числа порождаем I и проверяем, является ли оно одновременно делителем М и N;
- в зависимости от значения F выводим результат.

Var k,m,n,f:word;
Begin
Write('Введите 2 натуральных числа');
Readln(n,m);
F:=0;
if n>m then k:=m else k:=n; {k - наименьшее из 2-х чисел }
for I:=2 to k do if (n mod I=0) and (m mod I = 0) then f:=1;
If f=1 then writeln('числа не взаимно простые')
Else writeln('числа взаимно простые');
Readln
End.