IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> алгоритм евклида
сообщение
Сообщение #1


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


условие в прикрепленном файле.
вот то что сделал, дальше что делать не врубаюсь
uses crt;
function nod(a, b:longint):longint;
begin
if (a=0) or (b=0) then if a=0 then nod:=b
else nod:=a
else if a >= b then nod:=nod(a mod b,b)
else nod:=nod(a,b mod a);
end;
var f,g,i:integer;
ff,aa:array[1..1000] of integer;
begin
clrscr;
read(f,g);
ff[1]:=f;
ff[2]:=g;
i:=2;
while ff[i] mod ff[i-1]>0 do
begin
inc(i);
ff[i]:=ff[i-1] mod ff[i-2];
aa[i]:=ff[i-1] div ff[i-2];
end;
readkey;
end.



Сообщение отредактировано: Feagor -


Эскизы прикрепленных изображений
Прикрепленное изображение

--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 559
Пол: Мужской
Реальное имя: Бруно

Репутация: -  10  +


Тут материал с пояснением.


--------------------
Цитата
Imagination is more important than knowledge.
Albert Einstein
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


2 Tan - посмотри внимательно задание, и посмотри пожалуста, что у меня сделано! на той ссылке лежит разъянению функции, которая считает нод!
 function nod(a, b:longint):longint;
begin
if (a=0) or (b=0) then if a=0 then nod:=b
else nod:=a
else if a >= b then nod:=nod(a mod b,b)
else nod:=nod(a,b mod a);
end;

она у меня написана, проблема в том что вообще делать дальше?!


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Профи
****

Группа: Пользователи
Сообщений: 559
Пол: Мужской
Реальное имя: Бруно

Репутация: -  10  +


Алгоритм Евклида - это поиск наибольшего общего делителя двух целых чисел, что и сделано в приведённой мной ссылке. Не вижу проблемы.


--------------------
Цитата
Imagination is more important than knowledge.
Albert Einstein
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Tan, имеется ввиду расширенный алгоритм Эвклида. Посмотри объяснение, присоединенное к первому посту.

Feagor, тебе нужно кроме f и a еще считать коэффициенты p и s такие, что для любого i:

f[0] * s[i] + f[1] * p[i] = f[i].

Как это сделать, написано в том объяснении.

Ответом будет пара (s[n], p[n]).



 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


2 Michael_Rybak в каком объяснении?я туплю?=)
а с вариантом Б) и В) что делать?

Сообщение отредактировано: Feagor -


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


б) - сократи уравнение на нод и подумай что дальше делать

в) - делай то что там сказано. вычисляй не s[i] и p[i] а только s[i].
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


спасип, буду разбиратся! понял на счет объяснения, туплю!!!

Сообщение отредактировано: Feagor -


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


после десятикратного прочтения объяснения, до сих пор не могу понять как искать u и v...


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


u=s[n]
v=p[n]
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


а n- это последний член? или как?


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


по материалам algolist.manual.ru решил сделать вот так:
uses crt;
procedure nod(a, b:longint; var d,x,y:longint);
var q,r,x1,x2,y1,y2:longint;
begin
if b=0 then
begin
d:=a;
x:=1;
y:=0;
end
else
begin
x2:=1;x1:=0;y2:=0;x1:=1;
while b>0 do
begin
q:=a div b;
r:=a-q*b;
x:=x2-q*x1;
y:=y2-q*y1;
a:=b;b:=r;x2:=x1;x1:=x;y2:=y1;y1:=y;
end;
end;
d:=a; x:=x2;y:=y2;
end;
var a,b,d,x,y:longint;
begin
clrscr;
Write('Input f,g');
Read(a,b);
nod(a,b,d,x,y);
writeln(d,' ',x,' ',y);
readkey;
end.


заработало!!! остались б и в

Сообщение отредактировано: Feagor -


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


работает неправильно на каком тесте?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


2 Michael_Rybak попровил свои кривые ручки - заработало, помоги с написанием б


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


про б я тебе уже сказал что делать.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


ну вот смотри, берем уравнение fu+gv=nod(f,g) делим его на нод fu/nod(f,g)+fg/nod(f,g)=1 выносим за скобку u и g u*(f/nod(f,g))+v*(g/nod(f,g))=1, тогда m=1; k=f/nod(f,g); l=g/nod(f,g) Я правильно тебя понял так делать?

Добавлено через 1 мин.
тольков объяснении кажись что-то другое написано


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Не совсем так.

Тебе нужно вычислить не m, k и l - они тебе даны! А вычислить нужно х и у.

Берешь уравнение kx + ly = m, и делишь его на нод(x, y).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


Цитата
Берешь уравнение kx + ly = m, и делишь его на нод(x, y).
может не нод(x,y), а нод(k,l)?


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ой smile.gif Да, конечно.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


ыыыыщщщщщщыыыы
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Иван

Репутация: -  0  +


вот что получилось:
uses crt;
procedure nod(a, b:longint; var d,x,y:longint);
var q,r,x1,x2,y1,y2:longint;
begin
if b=0 then
begin
d:=a;
x:=1;
y:=0;
end
else
begin
x2:=1;x1:=0;y2:=0;y1:=1;
while b>0 do
begin
q:=a div b;
r:=a-q*b;
x:=x2-q*x1;
y:=y2-q*y1;
a:=b;b:=r;x2:=x1;x1:=x;y2:=y1;y1:=y;
end;
end;
d:=a; x:=x2;y:=y2;
end;
var a,b,d,x,y,k,l,m:longint;
xx,yy:real;
begin
clrscr;
Writeln('Input f,g');
Read(a,b);
nod(a,b,d,x,y);
writeln(d,' ',x,' ',y);
writeln('Input k,l,m');
read(k,l,m);
nod(abs(k),abs(l),d,x,y);
xx:=x*m/d;
yy:=y*m/d;
writeln(trunc(xx),' ',trunc(yy));
readkey;
end.


Вроде работает, Michael_Rybak +1 за великое знание cool.gif lol.gif

Сообщение отредактировано: Feagor -


--------------------
Никогда не задавайте вопрос, если не уверены, что хотите получить ответ...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 13:25
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name