Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
yutochka123
0 / 0 / 0
Регистрация: 14.11.2014
Сообщений: 55
#1

Алгоритм Евклида - Pascal

30.09.2015, 20:49. Просмотров 886. Ответов 7
Метки нет (Все метки)

Даны натуральные взаимно простые числа n, p. Найдите m такое, что, во-первых, m<p, во-вторых, произведение чисел m и n при делении на p даёт остаток 1.
Помогите пожалуйста!!!
http://www.cyberforum.ru/pascal/thread136514.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.09.2015, 20:49
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм Евклида (Pascal):

НОК алгоритм Евклида
Определить НОК (наименьшее общее кратное) двух чисел, используя алгоритм...

Расширенный алгоритм Евклида
Не могу найти решение на Паскале задачи на расширенный алгоритм Евклида: Для...

Функции и Алгоритм Евклида
Помогите пожалуйста! Даны натуральные числа а и b, обозначающие соответственно...

Сокращение дроби (алгоритм Евклида)
Написать программу сокращения дроби p/q, где p и q натуральные числа (Алгоритм...

Наибольший общий делитель двух натуральных чисел A и B, используя алгоритм Евклида
помогите пожалуйста((( долго уже думаю над прогой.... вобщем задание......

7
ZX Spectrum-128
Модератор
Эксперт Pascal/Delphi
3858 / 2845 / 3631
Регистрация: 05.06.2014
Сообщений: 13,940
30.09.2015, 20:56 #2
yutochka123, внизу страницы "Похожие темы".
0
yutochka123
0 / 0 / 0
Регистрация: 14.11.2014
Сообщений: 55
30.09.2015, 21:05  [ТС] #3
Именно такой нет...
0
ФедосеевПавел
Модератор
3412 / 1909 / 815
Регистрация: 01.02.2015
Сообщений: 6,451
30.09.2015, 21:16 #4
Мне кажется, что задача сводится к Диофантовому уравнению
m*n+x*p=1
m, n - из условия,
m, x - найдётся по решению, вернее, там множество решений, нужно будет ограничить m<p.
0
Puporev
Модератор
54131 / 41764 / 28875
Регистрация: 18.05.2008
Сообщений: 98,293
30.09.2015, 21:57 #5
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function Evclid(x,y:integer):integer;
begin
repeat
if abs(x)>abs(y) then x:=x mod y
else y:=y mod x;
until (x=0) or (y=0);
Evclid:=abs(x+y);
end;
var n,p,m,i:integer;
begin
repeat
writeln('Введите 2 натуральны, взаимно простых числа');
readln(n,p);
until  Evclid(n,p)=1;
writeln('n=',n);
writeln('p=',p);
i:=1;
m:=0;
while (i<p)and(m=0) do
if i*n mod p=1 then m:=i
else inc(i);
if m=0 then write('Искомого числа нет')
else write('m=',m,' ',n,'*',m,'=',n*m,' mod ',p,'=1');
end.
Добавлено через 3 минуты
Цитата Сообщение от ФедосеевПавел Посмотреть сообщение
Мне кажется, что задача сводится к Диофантовому уравнению
Прочитал это и вспомнил про расширенный алгоритм Эвклида, наверное на него задача, как писал такую на форуме.

Добавлено через 4 минуты
Хотя там условие другое...
0
ФедосеевПавел
Модератор
3412 / 1909 / 815
Регистрация: 01.02.2015
Сообщений: 6,451
01.10.2015, 21:11 #6
И я думаю, что расширенный алгоритм Эвклида. За счёт двух условий НОД(n,p)=1 и (m*n) mod p = 1 формулы для решения линейного Диофантового уравнения слегка упростятся. А там или по формулам умножения/деления или перебором кратных чисел.

Добавлено через 21 час 46 минут
Решение задачи ТС из переделанной программы для решения диофантовых уравнений. Я не стал переименовывать переменные - оставлю это ТС. Смысл проги вот в чём:
1. Имеется уравнение вида
a*x+b*y=c
которое в переменных условия задачи выглядит
n*m+p*y=1
Т.е. имеем соответствие
a -> n
x -> m
b -> p
y -> y
Можно по всему тексту заменить названия переменных, но для автоматического переименования я выбрал слишком короткие названия, а вручную - лень.
2. Далее математика такая
g:=НОД(a, b) = 1 (по условию задачи)
По формуле
X0:=Xg*(c div g) = Xg*(1 div 1) = Xg
Y0:=Yg*(c div g) = Yg*(1 div 1) = Yg
Решение уравнения с заданными условиями
x:=X0 + b*k
y:=Y0 - a*k
Как мы помним, переменная x соответствует искомой m, которая в свою очередь меньше p ( -> b). Получим
m:=X0+b*k < p
m:=X0+b*k < b
k < (b-X0) div b
Мне сейчас трудно сообразить, возможна ли ситуация, когда (b-X0) нацело делится на b, что приведёт к m=p. Но предположим, что нет.
Тогда
k:=(b-X0) div b
И
m:=X0+b*k
Всё.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
{
Решение диофантового a*x+b*y=c уравнения в общем виде
 
Ограничение:
Коэффициенты a и b - только неотрицательные. Для отрицательных
нужно сделать ещё некоторые телодвижения, описанные в e-maxx.
}
program LinearDiophantineEquation;
 
  {Extended Euclidean algorithm}
  {
   на входе:
   a, b
   на выходе:
   НОД(a, b) = GCD(a, b)
   x, y - числа, такие, что a*x+b*y=GCD(a, b)
  }
  function ExtendedEuclideanAlgorithm(a, b: integer; var x, y: integer): integer;
  var
    x1, y1, d: integer;
  begin
    if (a = 0) then
    begin
      x := 0;
      y := 1;
      ExtendedEuclideanAlgorithm := b;
      Exit;
    end;
    d := ExtendedEuclideanAlgorithm(b mod a, a, x1, y1);
    x := y1 - (b div a) * x1;
    y := x1;
    ExtendedEuclideanAlgorithm := d;
  end;
 
var
  a, b, c: integer;
  Xg, Yg, g: integer;
  X0, Y0: integer;
  k: integer;
begin
  a := 10;
  b := 23;
  c := 1;
  {рассмотрим некоторые вырожденные случаи, доступные на данном этапе}
  {
   1. a=0, b=0, c=0 - бесконечное множество решений с произвольными x и y
   2. a=0, b=0, c<>0 - нет ни одного решения
   }
  if (a = 0) and (b = 0) then
  begin
    if (c = 0) then
      writeln('Бесконечное множество решений с любыми значениями x и y.')
    else
      writeln('Нет ни одного решения.');
    Exit;
  end;
  {нахождение НОД(a,b) и дополнительных переменных}
  g := ExtendedEuclideanAlgorithm(a, b, Xg, Yg);
  {на основе новых данных рассмотрим ещё один вырожденный случай
  3. c не делится на GCD(a, b) - нет ни одного решения
  }
  if (c mod g) <> 0 then
  begin
    writeln('Нет ни одного решения.');
    Exit;
  end;
  {нахождение одного решения}
  X0 := Xg * (c div g);
  Y0 := Yg * (c div g);
  {нахождение решения в общем виде}
  (*
  writeln('Решение диофантова уравнения ', a, 'x+', b, 'y=', c, ' в общем виде:');
  writeln('x=', X0, '+', (b div g), 'k');
  writeln('y=', Y0, '-', (a div g), 'k');
  *)
  {теперь подгонка к решению задачи на основе диофантового уравнения}
  k := (b - X0) div b;
  writeln('m=', X0 + b * k, '<', b);
end.
Добавлено через 6 минут
Предвидя вопросы о пояснении - приведу ссылки на мои источники вдохновения: e-maxx и Wikipedia.

Добавлено через 54 минуты
------------------------------------------------------------------------------------
Если посмотреть на результат, возвращаемый расширенным алгоритмом Эвклида, то с учётом взаимной простоты чисел n и p, то получим, что Ng*n+Pg*p=1, что является условием задачи. И принимая во внимание решения для диофантовых уравнений, получим
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
program task;
 
  {Extended Euclidean algorithm}
  {
   на входе:
   a, b
   на выходе:
   НОД(a, b) = GCD(a, b)
   x, y - числа, такие, что a*x+b*y=GCD(a, b)
  }
  function ExtendedEuclideanAlgorithm(a, b: integer; var x, y: integer): integer;
  var
    x1, y1, d: integer;
  begin
    if (a = 0) then
    begin
      x := 0;
      y := 1;
      ExtendedEuclideanAlgorithm := b;
      Exit;
    end;
    d := ExtendedEuclideanAlgorithm(b mod a, a, x1, y1);
    x := y1 - (b div a) * x1;
    y := x1;
    ExtendedEuclideanAlgorithm := d;
  end;
 
var
  Ng, Pg, g: integer;
  k: integer;
  m, n, p: integer;
begin
  n := 103;
  p := 23;
  {нахождение НОД(n,p) и дополнительных переменных}
  g := ExtendedEuclideanAlgorithm(n, p, Ng, Pg);
  {теперь подгонка к решению задачи на основе диофантового уравнения}
  k := (p - Ng) div p;
  if Ng + p * k >= p then
    Dec(k);
  m := Ng + p * k;
  writeln('m=', m, '<', p);
  writeln('m*n=', m * n, ' mod ', p, ' = ', (m * n) mod p);
end.
0
Puporev
Модератор
54131 / 41764 / 28875
Регистрация: 18.05.2008
Сообщений: 98,293
01.10.2015, 21:13 #7
А мне кажется и мой код решает задачу как она описана.
0
ФедосеевПавел
Модератор
3412 / 1909 / 815
Регистрация: 01.02.2015
Сообщений: 6,451
01.10.2015, 21:25 #8
Да, согласен на все 100%. Просто хотелось решить другим способом. Это даже не для ТС, а чтобы самому вспомнить математику. Даже видно изменение кода по мере чтения .
0
01.10.2015, 21:25
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.10.2015, 21:25
Привет! Вот еще темы с решениями:

Описать рекурсивную функцию NOD(A,B), находящую наибольший общий делитель двух чисел, используя алгоритм Евклида
Описать рекурсивную функцию NOD(A,B) целого типа, находящую наибольший общий...

Даны натуральные числа A и B. Найти их НОК, определив функцию для расчета НОД двух натуральных чисел, используя алгоритм Евклида
Даны натуральные числа A и B. Найти их наименьшее общее кратное, определив...

Найти НОД с помощью алгоритма Евклида
Написать пpогpаммы, включающие pекуpсивную и неpекуpсивную пpоцедуpы. 1....

Написать модифицированный вариант алгоритма Евклида
1. Написать модифицированный вариант алгоритма Евклида (отыска-ния НОД –...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru