Вариант 1
var a,b:longint; function NOD(x,y:longint):longint; { функция поиска наиб. общ. делителя } begin if x<>0 then NOD:=NOD(y mod x,x) else NOD:=y; end; function NOK(x,y:longint):longint; { функция поиска наим. общ. кратного } begin NOK:=( x div NOD(x,y) ) * y; end; begin { основная программа } readln(a,b); writeln( 'НОД этих чисел = ', NOD(a,b) ); writeln( 'НОК этих чисел = ', NOK(a,b) ); end.
Вариант 2 Переборный алгоритм
var a, b, d: integer; begin write('Введите два числа: '); readln(a, b); if a < b then d := a + 1 else d := b + 1; {так как мы используем цикл с постусловием, необходимо минимальное значение увеличить на один, иначе цикл repeat, в силу своих конструктивных особенностей, не учтет это минимальное число и не сделает его кандидатом в НОД. Например, 5 и 25.} repeat d := d - 1 until (a mod d = 0) and (b mod d = 0); write('NOD = ', d) end.
Вариант 3
var m,n,r:integer; label lb; begin write('Введите первое число:');readln(m); write('Введите второе число:');readln(n); lb:r:=m mod n; if r=0 then writeln('НОД = ',n) else begin m:=n; n:=r; goto lb; end; end.
Вариант 4 Алгоритм Евклида с вычитанием
Пусть a и b — целые числа, тогда верны следующие утверждения:
Все общие делители пары a и b являются также общими делителями пары a — b, b;
И наоборот, все общие делители пары a — b и b являются также общими делителями пары a и b; НОД(A, B) = НОД(A — B, B), если A > B; НОД(A, 0) = A.
Доказательство:
Если t — произвольный общий делитель a и b, то он делит и разность a — b. Действительно, из a = t * u и b = t * v следует, что a — b = t * u — t * v = t * (u — v). То есть t — также общий делитель а — b и b. Обратно, если t — произвольный делитель общий делитель a — b и b, то он делит и их сумму a — b + b = a. Это можно доказать аналогично предыдущему. Поэтому t — также общий делитель a и b. Делаем вывод, что множество общих делителей a и b совпадает с множеством делителей a — b и b. В частности, совпадают и наибольшие общие делители этих пар. Наибольшее целое, на которое делится число a, есть само число а. Число 0 делится на любое число. Отсюда наибольший общий делитель а и 0 равен а. Доказанная формула(3) позволяет свести вычисление наибольшего делителя одной пары к вычислению наибольшего общего делителя другой пары, в которой числа уже меньше. Очевидная же формула (4) дает нам понять, когда надо остановиться.
var a, b: integer; begin write('a = '); readln(a); write('b = '); readln(b); while a <> b do if a > b then a := a - b else b := b - a; writeln('NOD = ', a); end.
Вариант 5 Алгоритм Евклида с делением
Пусть a и b — целые числа, а r — остаток от деления a на b. Тогда НОД(a, b) = НОД(b, r). Эта формула также позволяет свести вычисление наибольшего общего делителя одной пары чисел к вычислению наибольшего обшего делителя другой пары чисел.
var a, b: integer; begin write('a = '); readln(a); write('b = '); readln(b); while (a <> 0) and (b <> 0) do if a >= b then a := a mod b else b := b mod a; write(a + b) end.
Вариант № 6
Program test2(input,output); Const N = 5; Var С: array[1..5] of integer; A,B:integer; function HOК (A, В:integer):integer; begin HOK:=A*B/ HOD(A,B); end; function НОD(А, В:integer):integer; var X,Y:integer; begin X:= A; Y: = В; 1:IF X = Y THEN HOD:=X; IF X > Y THEN begin X:= X – Y;goto 1; end; IF Y > X THEN begin Y:= Y – X;goto 1; end; end; Begin FOR i= 1 ТО N READ (C[i]); A:= С ([l]) FOR i = 1 TO N–1 begin B:=С[i + 1]; A:= HOK(A,B); end; writeln ("HOK="; A); end.
Вариант 7
Program N_O_D (Input, Output); Var A, B: LongInt; NOD : LongInt; Begin WriteLn ('PASCAL: Нахождение Н.О.Д. двух заданных чисел.'); Writeln ('Введите числа, для которых ищется НОД:'); Write('Первое число: ');ReadLn (A); Write('Второе число: ');ReadLn (B); If (A < B)ThenNOD := A Else NOD := B; While Not( (A mod NOD = 0) and (B mod NOD = 0) ) do NOD := NOD - 1; WriteLn ('НОД = ',NOD); ReadLn; End.
Program N_O_D (Input, Output); Var A, B: LongInt; NOK, NOD : LongInt; Begin WriteLn ('PASCAL: Нахождение Н.О.К. двух заданных чисел.'); WriteLn ('Введите числа, для которых ищется НОК:'); Write ('Первое число: ');ReadLn (A); Write ('Второе число: ');ReadLn (B); If (A < B)ThenNOD := A Else NOD := B; While Not ( (A Mod NOD = 0) And (B Mod NOD = 0) ) Do NOD := NOD - 1; A := A Div NOD; B := B Div NOD; NOK := A * B * NOD; WriteLn ('НОК = ', NOK); ReadLn; End.
При программировании на любом языке необходимо знать основные алгоритмы. Они являются как бы «азбукой» для программиста. Сегодня я хочу рассказать про основные алгоритмы в таком языке программирования, как Паскаль.
1. Первый алгоритм, про который я расскажу — это факториал натурального числа Pascal. Факториалом числа (!n) является произведение натуральных чисел от 1 до этого числа включительно. Например, 5!=1*2*3*4*5.
Наша задача — написать программу Pascal, которая находит факториал числа.
Сначала переменной f (сокр. Factorial) присваиваем значение, равное единице, т.к 0! = 1, 1!=1.
Далее идет цикл с параметром от 2 до заданного числа, в котором переменная f умножается на следующее значение после единицы с увеличением на 1 после каждого круга.
Программа нахождения факториала на языке Паскаль:
var
f: longint;
n, i: integer;
Begin
write('n = '); readln(n);
f := 1;
For i:=2 to n do
f := f * i;
writeln(n,'! = ', f);
End.
2. Второй алгоритм, который необходимо знать — нахождение НОК двух чисел. НОК — наименьшее общее кратное, то есть минимальное число, которое одновременно делится на оба числа.
В паскаль это реализуется достаточно просто:
var a,b,c:integer; //Описание переменных
begin //Начало программы
readln(a,b); //Считывание а и б
c:=a*b; //Перемножение
repeat //Цикл с постусловием
if a>b then a:=a-b else b:=b-a;
until a=b; //Цикл до тех пор, пока а не равно б
c:= c div a; //Делим c на a нацело и получаем нок
writeln('НОК=', c); //Выводим значение
end.//Конец программы
Скачать: nok.pas
3. Также нужно знать и про НОД двух чисел. НОД — наименьший общий делитель, т. е. Минимальное число, которое нацело делит два и более чисел.
Код нахождения НОД в паскаль:
var a,b,c: integer; //Описание переменных
begin //Начало программы
writeln('Введите a,b: '); //Диалог с пользователем
read(a,b); //Чистывание чисел
while b<>0 do //Вход в цикл while, пока b не равно 0
begin
c := a mod b; //Присваивание с остатка деления a/b
a := b;
b := c;
end;
writeln('НОД = ',a); //Вывод делителя
end.//Конец программы
Скачать: nod.pas
На сегодня все, во второй части расскажу про возведение числа в степень, а также про нахождение минимального и максимального в массиве.
Дата: 2013-10-04 13:18:03 Просмотров: 45324
Теги: Паскаль урок уроки Pascal основные алгоритмы
Перейти к содержимому
Формулировка. Даны два натуральных числа. Найти их наименьшее общее кратное.
Примечание: наименьшим общим кратным двух чисел m и n называется наименьшее натуральное число, которое делится на m и n. Обозначение: НОК(m, n)
Решение. Из теории чисел известно, что НОК(m, n) связан с НОД(m, n) следующим образом:
Следовательно, для нахождения ответа нам нужно лишь использовать предыдущую задачу нахождения НОД двух чисел m иn:
while m <> n do begin
if m > n then begin
m := m — n
end
else begin
n := n — m
end
end;
Так как исходные переменные будут испорчены в процессе работы алгоритма Евклида, нам нужно вычислить их произведение до входа в описанный выше цикл и присвоить это произведение переменной prod (от англ. product – «произведение»):
prod := m * n;
После этого нам остается вывести на экран результат арифметического выражения в правой части нашей формулы. В качестве самого НОД будет использоваться переменная m:
writeln(prod div m);
Кстати, деление в формуле будет целочисленным (через div) именно потому, что если два числа делятся на некоторое число, то и их произведение также делится на него.
Код:
- program LeastCommonMult;
- var
- m, n, prod: word;
- begin
- readln(m, n);
- prod := m * n;
- while m <> n do begin
- if m > n then begin
- m := m — n
- end
- else begin
- n := n — m
- end
- end;
- writeln(prod div m)
- end.
Программа для НОК и НОД на Паскале
Здесь приведен код программы на языке Паскаль. Программа вычисляет НОД и НОК с использованием алгоритма Евклида.
Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Приведем пример: для чисел 70 и 105 наибольший общий делитель будет равен 35. НОД существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Наименьшее общее кратное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n. Например, для 3 и 5, НОК равен 15, а для 2 и 4 НОК равен 4.
program nodnok; var a,b:longint; function NOD(x,y:longint):longint; begin if x<>0 then NOD:= NOD(y mod x,x) else NOD:= y; end; function NOK(x,y:longint):longint; begin NOK:= (x div NOD(x,y)) * y; end; Begin Write('Введите a и b: '); Readln(a,b); Writeln('НОД ',a,' и ',b,' = ', NOD(a,b)); Writeln('НОК ',a,' и ',b,' = ', NOK(a,b)); Readln; End.