Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.65/51: Рейтинг темы: голосов - 51, средняя оценка - 4.65
0 / 0 / 0
Регистрация: 20.01.2010
Сообщений: 31

Написать модифицированный вариант алгоритма Евклида

30.01.2010, 00:23. Показов 10404. Ответов 21
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
1. Написать модифицированный вариант алгоритма Евклида (отыска-ния НОД – наибольшего общего делителя), используя соотношения: НОД(а, b) = НОД(a mod b, b), при a >= b;
НОД(а, b) = НОД(а, b mod a), при a <= b.
Вычислить НОД для нескольких пар чисел и построить график по введенным значениям a и b.
2. Дана матрица A=[aij], размером n*n, где , i = 1, 2, ... n и 0<=aij<1. Написать программу последовательного умножения матрицы саму на себя. Процесс закончить, когда все элементы двух последовательных матриц будут отличаться друг от друга меньше, чем на 10-4. Результаты выдать.
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
30.01.2010, 00:23
Ответы с готовыми решениями:

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

Написать модифицированный вариант алгоритма Евклида
Написать модифицированный вариант алгоритма Евклида, использующий соотношения НОД (a, b) = НОД (a mod b, b) при a &gt;= b, НОД (a, b) = НОД...

Написать вариант алгоритма Евклида, использующий соотношения НОД
Здравствуйте! Задача состоит в том, чтобы &quot;Написать вариант алгоритма Евклида, использующий соотношения НОД(2a, 2b) = 2•НОД(a,b), НОД(2a,b)...

21
 Аватар для Eugeniy
3132 / 1325 / 156
Регистрация: 19.12.2009
Сообщений: 1,808
30.01.2010, 00:28
Первая задача
https://www.cyberforum.ru/pasc... 75652.html
2
175 / 172 / 40
Регистрация: 14.11.2009
Сообщений: 507
30.01.2010, 00:30
1
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function NOD (x,y:longint):longint;
begin
if x<>0 then Nod:=Nod(x mod y,x)
else Nod:=y;
end;
 
var
a,b,c,d:longint;
begin
readln(a,b,c,d);
writeln('NOD (',a,',',b,',',c,',',d,') = ',NOD(a,NOD(b,NOD(c,d))));
 
readln
end.
2
Мат в 32 хода
 Аватар для nikkka
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
30.01.2010, 07:30
milagros2307, А что значит 10-4?

...друг от друга меньше, чем на 10-4
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
30.01.2010, 07:39
nikkka,
abs(An[i,j]-A(n-1)[i,j])<0.0001;
0
Мат в 32 хода
 Аватар для nikkka
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
30.01.2010, 07:44
[b]A(n-1)[i,j]
А это что?
Надо писать не 10-4 а 10^(-4)
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
30.01.2010, 09:30
Лучший ответ Сообщение было отмечено как решение

Решение

Что-то не нравится условие второй задачи, такое ощущение, что заданного результата, по крайней мере в Паскале не достичь. Написал программу, вроде верно, но работает только по самому минимуму, при n=2 и точности 0,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
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
uses crt;
const max=20;
      e=0.1;{0.0001}
type matr=array[1..max,1..max] of extended;
procedure Vvod(var mt:matr;var x:byte);{создание исходной матрицы}
var i,j:byte;
begin
repeat
write('Введите размер матрицы до ',max,' =');
readln(x);
until x in [1..20];
for i:=1 to x do
for j:=1 to x do
mt[i,j]:=random;
end;
procedure Vyvod(var mt:matr;x:byte;c:string);{вывод матриц на экран}
var i,j:byte;
begin
writeln(c);
for i:=1 to x do
 begin
  for j:=1 to x do
  write(mt[i,j]:8:5);
  writeln;
 end;
end;
 
procedure UmnMt(m1,m2:matr;var m3:matr;x:byte);{умножение матриц}
var k,j,i:byte;
begin
for k:=1 to x do
for j:=1 to x do
   begin
     m3[k,j]:=0;
     for i:=1 to x do
     m3[k,j]:=m3[k,j]+m1[k,i]*m2[i,j];
   end;
end;
 
procedure Razn(m1,m2:matr;var m3:matr;x:byte);{разность матриц}
var i,j:byte;
begin
for i:=1 to x do
for j:=1 to x do
m3[i,j]:=m1[i,j]-m2[i,j];
end;
 
function Prov(mt:matr;x:byte):boolean;{проверка достигнутой точности}
var i,j:byte;
begin
Prov:=true;
for i:=1 to x do
for j:=1 to x do
if abs(mt[i,j])>=e then
 begin
  Prov:=false;
  break;
 end;
end;
var a,b,an,r:matr;
    n,i,j:byte;
begin
clrscr;
Vvod(a,n);
Vyvod(a,n,'Исходная матрица:');
randomize;
b:=a;{запомним исходную матрицу}
repeat
UmnMt(a,b,an,n);{умножаем}
Razn(an,a,r,n);{смотрим матрицу разности}
if Prov(r,n) then break{если точность достигнута, выходим из цикла}
else a:=an;{иначе умножаем новую маирицу}
until Prov(r,n);
Vyvod(a,n,'Матрица A(n-1):');{выводим предпоследнюю}
Vyvod(an,n,'Матрица An:');{выводим последнюю}
Vyvod(r,n,'Достигнутая точность:');{матрица последних разностей}
readln
end.
Добавлено через 8 минут
Еще такой крамольный вариант, может не матрицу умножать саму на себя, т.е. возводить ее в степень, а просто элементы матрицы умножать, т.е. не матрицу возводить в степень, а ее элементы?
Тогда должно работать.

Добавлено через 10 минут
Вот этот крамольный вариант, здесь все работает.
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
uses crt;
const max=20;
      e=0.0001;
type matr=array[1..max,1..max] of extended;
procedure Vvod(var mt:matr;var x:byte);{создание исходной матрицы}
var i,j:byte;
begin
repeat
write('Введите размер матрицы до ',max,' =');
readln(x);
until x in [1..20];
for i:=1 to x do
for j:=1 to x do
mt[i,j]:=random;
end;
procedure Vyvod(var mt:matr;x:byte;c:string);{вывод матриц на экран}
var i,j:byte;
begin
writeln(c);
for i:=1 to x do
 begin
  for j:=1 to x do
  write(abs(mt[i,j]):11:7);
  writeln;
 end;
end;
 
procedure UmnMt(m1,m2:matr;var m3:matr;x:byte);{умножение элементов матриц}
var i,j:byte;
begin
for i:=1 to x do
for j:=1 to x do
m3[i,j]:=m1[i,j]*m2[i,j];
end;
 
procedure Razn(m1,m2:matr;var m3:matr;x:byte);{разность матриц}
var i,j:byte;
begin
for i:=1 to x do
for j:=1 to x do
m3[i,j]:=m1[i,j]-m2[i,j];
end;
 
function Prov(mt:matr;x:byte):boolean;{проверка достигнутой точности}
var i,j:byte;
begin
Prov:=true;
for i:=1 to x do
for j:=1 to x do
if abs(mt[i,j])>=e then
 begin
  Prov:=false;
  break;
 end;
end;
var a,b,an,r:matr;
    n,i,j:byte;
begin
clrscr;
Vvod(a,n);
Vyvod(a,n,'Исходная матрица:');
randomize;
b:=a;{запомним исходную матрицу}
repeat
UmnMt(a,b,an,n);{перемножаем элементы}
Razn(an,a,r,n);{смотрим матрицу разности}
if Prov(r,n) then break{если точность достигнута, выходим из цикла}
else a:=an;{иначе умножаем новую матрицу}
until Prov(r,n);
Vyvod(a,n,'Матрица A(n-1):');{выводим предпоследнюю}
Vyvod(an,n,'Матрица An:');{выводим последнюю}
Vyvod(r,n,'Достигнутая точность:');{матрица последних разностей}
readln
end.
4
Мат в 32 хода
 Аватар для nikkka
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
30.01.2010, 14:48
Цитата Сообщение от milagros2307 Посмотреть сообщение
отличаться друг от друга меньше, чем на 10-4
Не ДРУГ ОТ ДРУГА МЕНЬШЕ, а ДРУГ ОТ ДРУГА НЕ МЕНЬШЕ!
Ато так фигня какая то!

Добавлено через 21 минуту
Вот ещё один способ решения:
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
const n=2;
label exit;
var
a    : array[1..n, 1..n] of longint;
i,k  : integer;
m    : real;
iff  : boolean;
begin
exit:
writeln('Enter the array, one by one, pressing ENTER: ');
iff:=false;
for i:=1 to n do begin
for k:=1 to n do begin
readln(a[i,k]);
if (a[i,k]=1) or (a[i,k]<1) then begin writeln('The array cant consist of 1! (Press ENTER)'); readln; goto exit; end;
end;
end;
writeln('Enter the number to stop: ');
readln(m);
repeat
iff:=true;
for i:=1 to n do begin
for k:=1 to n do begin
if sqr(a[i,k])-a[i,k]<m then iff:=false;
a[i,k]:=sqr(a[i,k]);
end;
end;
until iff=true;
for i:=1 to n do begin
for k:=1 to n do begin
if k=n then begin write(a[i,k]); writeln; end
       else begin
       if a[i,k]<10 then write(a[i,k],'     ');
       if (a[i,k]<100) and (a[i,k]>=10) then write(a[i,k],'    ');
       if (a[i,k]>=100) and (a[i,k]<1000) then write(a[i,k],'   ');
       if (a[i,k]>=1000) and (a[i,k]<10000) then write(a[i,k],'  ');             {}{}{}{}{}{}
       if (a[i,k]>10000) and (a[i,k]<100000) then write(a[i,k],' ');
            end;
end;
end;
readln;
end.
1
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
30.01.2010, 14:51
Цитата Сообщение от nikkka Посмотреть сообщение
a * *: array[1..n, 1..n] of longint;
Это Вы о чем здесь? Если про умножение матрицы, то там по условию вещественные числа от 0 до1.
0
Мат в 32 хода
 Аватар для nikkka
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
30.01.2010, 15:10
Вы о чем здесь?
Я просто беру и возвожу все елементы матрицы в квадрат присваивая их самим себе (без вспомогательных матриц). Проделываю это пока не обнаружу что уже после очередного возведения в квадрат a[i,k] больше чем его корень на какую то заданную величину m. Разве не это нужно?
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
30.01.2010, 15:39
nikkka, Нужно умножать числа из интервала от (0;1) пока все они не станут меньше 0.0001
1
Мат в 32 хода
 Аватар для nikkka
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
30.01.2010, 16:29
А, то есть надо умножать все элементы матрицы на заданное число, пока они все не станут меньше 0.0001?
Но ведь это просто!
Зачем столько процедур и подпрограмм?! :O

Добавлено через 3 минуты
Цитата Сообщение от milagros2307 Посмотреть сообщение
Написать программу последовательного умножения матрицы саму на себя
Но ведь тут сказанно что матрица умножается сама на себя, то есть возводится в квадрат! Чего то я не понял...
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
30.01.2010, 16:36
nikkka, Да врубитесь Вы в текст программы. По условию нужно умножать матрицу саму на себя, но так программу выкидывает, так как точность 0,0001 не может быть достигнута. Я подумал, что может быть неверно написано условие и не матрицу нужно умножать(возводить в степень), а только ее элементы возводить в степень, тогда они довольно быстро станут меньше 0,0001.
Если вообще не понимаете, то и не лезьте, тем более не нужно критики, немного чему-то научитесь прежде.
0
Мат в 32 хода
 Аватар для nikkka
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
30.01.2010, 16:48
Puporev, вообще-то надо было написать программу автора а не "ту-что-вы-подумали". А если программу "выкидывает" то надо об этом сообщить, а не переделывать на свой лад.
Если вообще не понимаете, то и не лезьте, тем более не нужно критики, немного чему-то научитесь прежде.
А я и не знал что надо учится переделывать программы...
А критика - это моё мнение.
Думаете так легко перепутать "умножение на саму себя" и "умножение на число"? Такая ошибка - не опечатка. Тем более, автор бы поправил её, если бы посчитал нужным.
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
30.01.2010, 16:57
nikkka, Если бы Вы разули свои глаза, то заметили бы, что я написал 2 варианта программы, один точно по приведенному условию, но, полагая что условие ошибочное, написал еще один вариант.
И нечего тут рявкать.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
31.01.2010, 13:10
Если строго следовать условию задачи то вторая задача очень странная.

Начальная матрица имеет элементы <1.
Значит в худшем случае после умножения матрицы на саму себя элементы будут <n.
При следующем умножении элементы уже будут <n^2.
В этом случае никакой сходимости точно не будет.

Допустим элементы <1/n.
Тогда после возведения матрицы в квадрат новые элементы будут <(1/n)*(1/n)*n == 1/n
В этом случае можно надеяться что возможна какая-то сходимость.

Добавлено через 2 минуты
А, то есть надо умножать все элементы матрицы на заданное число, пока они все не станут меньше 0.0001?
Рекомендую прочитать внимательно условие задачи - оно находится в посте #1.
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
31.01.2010, 13:26
odip, Согласен что условие "умножать матрицу саму на себя" и ждать сходимости, это абсурд. После каждого умножения элементы будут расти, а не уменьшаться, так как при умножении матриц идет суммирование элементов. Поэтому и предположил, что нужно не матрицу в степень возводить, а ее элементы, тогда задача будет корректной.
0
Мат в 32 хода
 Аватар для nikkka
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
31.01.2010, 13:31
Ну вообще то если 0<a[i,j]<1 то при возведении в квадрат оно уменьшится...
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
31.01.2010, 13:32
nikkka, Вы вообще различаете понятия умножение матрицы на матрицу и умножение иатрицы на скаляр?
0
Мат в 32 хода
 Аватар для nikkka
237 / 172 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
31.01.2010, 21:32
Числа то, всё равно меньше 0

Добавлено через 7 часов 47 минут
Я знаю как матрицй умножать на матрицу. Строка на столбец. Но если все элементы меньше 1, то какой элемент на какой бы мы не умножали, всё равно будет получатся меньше и меньше. Так что матрице вполне можно возводить в квадрат, уменьшая тем самым элементы...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
31.01.2010, 21:32
Помогаю со студенческими работами здесь

Написать программу, которая использует модифицированный алгоритм Евклида
написать программу, которая использует модифицированный алгоритм Евклида: нужно заменять большее число на остаток от деления большего на...

написать программу, которая использует модифицированный алгоритм Евклида
написать программу, которая использует модифицированный алгоритм Евклида: нужно заменять большее число на остаток от деления большего на...

Модифицированный алгоритм Евклида
2.Напишите программу, использующую модифицированный алгоритм Евклида: нужно заменять большее число на остаток от деления большего на...

Написать демонстрационный вариант алгоритма - сортировка обменом
Написать демонстрационный вариант алгоритма (сортровка обменом), в котором сортируемый массив изображается в виде столбчатой диаграммы:...

Вычисление НОД с помощью бинарного алгоритма и алгоритма Евклида.
Решил заняться программированием, друг посоветовал язык C# и дал задачу: Сделать алгоритм для вычисления НОД с помощью бинарного...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru