Построить алгоритм Маркова, который ищет НОД (Алгоритм Евклида)

@andron773 · Регистрация: 06.11.2015

Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в чем, надо построить алгорифм Маркова, который ищет наибольший общий делитель (алгоритм Евклида). Заранее спасибо!

@Shamil1 · 09.11.2015, 13:58

Для вычисления разности двух чисел нужно из обоих чисел вычитать 1, пока меньшее не станет равным нулю.
Вход: два числа. Выход: разность.
5-2: 5-2 => 4-1 => 4-0 => 4

Для вычисления остатка от деления нужно вычитать из делимого делитель, пока делимое не станет равным нулю. Получившееся число нужно вычесть из делимого.
7%3: 7-3 => 4-3 => 1-3 => 0-2 => 3-2 => 1
Так как вычитаемое число теряется, нужно хранить его в другом месте и копировать перед каждым вычитанием.

Для вычисления НОД нужно вычислять остаток от деления одного числа на другое, пока остаток не станет равным нулю. Перед каждым вычислением остатка нужно менять числа местами: делитель на место делимого, остаток на место делителя (делимое теряется в процессе вычисления остатка).

@andron773 · 13.11.2015, 03:37 **[ТС]**

Что-то я туплю, но я так и не понял как реализовать Евклида в алгоритме Маркова...

@~~IrineK~~ · 13.11.2015, 03:59

В вики есть два примера.
У вас должно получиться нечто похожее, но по поводу НОД.

@Shamil1 · 13.11.2015, 09:51

Сообщение от andron773

Что-то я туплю, но я так и не понял как реализовать Евклида в алгоритме Маркова...

Я перечислил три этапа вычислений. Какой из них вызывает у Вас затруднения?

@andron773 · 13.11.2015, 18:14 **[ТС]**

Сообщение от Shamil1

Я перечислил три этапа вычислений. Какой из них вызывает у Вас затруднения?

Ну просто ты перечислил остаток и т. д. А мне надо НОД, что бы искало наибольший общий делитель, т. к. это делается в Евклида

@Shamil1 · 14.11.2015, 18:18

Результатом третьего этапа вычислений и будет НОД.

Вод для примера:

C#

int gcd(int a, int b)
{
    while (b != 0)
        b = a % (a = b);
    return a;
}

Добавлено через 2 часа 11 минут
Для НОМ можно упростить алгоритм Евклида: вычитаем из большего числа меньшее до тех пор, пока они не будут равны.
Пусть два числа данны в виде "aaaaaaaaaabbbbb".
Вычитание реализуется заменами:
cb->bc //перемещаем "c" в конец слова (после "b")
ab->c //сокращаем, но запоминаем, сколько мы сократили
В результате получим "aaaaacccc" или "bbbbbccc" или "ccccc".
В первых двух случаях нам надо переименовать к виду "aaaaaaaaaabbbbb" и повторить. В третьем случае переименовываем в "aaaaa" и останавливаемся.
Для переименования добавляем символ "*". Во втором случае заменяем его на "%", а в третьем - на "!".
*a->%a
*b->%b
*c->!c
Переименование 1/2:
%a->a%
%b->a%
%c->b%
%->
Переименование 3:
!c->c!
!->.

Вот всё вместе:

Код

//Определение варианта:
*a->%a
*b->%b
*c->!c
//Переименование:
%a->a%
%b->a%
%c->b%
%->
!c->a!
!->. // СТОП
// вычитание
cb->bc 
ab->c
// символ для переименования
->*

@andron773 · 15.11.2015, 19:38 **[ТС]**

Понял, огромное спасибо. Нереально помог!)

@Inerciya · 17.05.2017, 15:30

А как реализовать НОД для унарной системы счисления? Для такого задания: Постройте нормальный алгоритм, который находит наибольший общий делитель двух чисел, представленных в унарной системе. Числа разделены *
Например, для 1111*11 ответ 11

@Sindbad_M · 17.05.2017, 15:44

Сообщение от Inerciya

чисел, представленных в унарной системе. Числа разделены *

переименовать единички в "а" и "b" можно так:
*1 --> b*
* -->
1 --> a
Задача сведена к предыдущей?

@Inerciya · 17.05.2017, 16:50

Если под сведена Вы имеете в виду, что я должна получить в итоге, то в общем да, в конце нужно оставить НОД. Но я этот алгоритм Маркова вообще не поняла... точнее принцип работы ясен, но эту задачу воплотить не могу

Добавлено через 57 минут
У меня уже почти все готово, осталось c перевести обратно в 1. Вот с этим пока проблема

@Shamil1 · 17.05.2017, 16:52

Сообщение от Inerciya

Например, для 1111*11 ответ 11

Вычитание реализуется заменами:
c1->1c //перемещаем "c" в конец слова (после "1")
1*1->c //сокращаем, но запоминаем, сколько мы сократили
В результате получим "11111*cccc" или "*11111ccc" или "ccccc".
В первых двух случаях нам надо переименовать к виду "111111*1111" и повторить. В третьем случае переименовываем в "11111" и останавливаемся.

@Sindbad_M · 17.05.2017, 16:53

___

@Inerciya · 17.05.2017, 16:55

1->a
*a->%a
*b->%b
*c->!c
%a->a%
%b->a%
%c->b%
%->
!c->a!
!->.
cb->bc
ab->c
->*

Может есть идеи, как НОД обратно в единицы перевести?

@Sindbad_M · 17.05.2017, 16:57

Сообщение от Shamil1

1*1->c //сокращаем, но запоминаем, сколько мы сократили

может
1*1 --> *c
?

@Inerciya · 17.05.2017, 16:58

1->a
*a->%a
*b->%b
*c->!c
%a->a%
%b->a%
%c->b%
%->
!c->a!
!->.
cb->bc
ab->c
->*

Может есть идеи, как НОД обратно в единицы перевести?

@Shamil1 · 17.05.2017, 17:11

Сообщение от Sindbad_M

может
1*1 --> *c
?

Да.

@Inerciya · 17.05.2017, 17:18

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

@Sindbad_M · 17.05.2017, 17:43

___

@Inerciya · 17.05.2017, 17:45

В конце, кстати, получается НОД не в "с" выдает, а в "а". То есть для 11*11 НОД аа
аа обратно перевести не получается, может все-таки кто-нибудь знает? А то совсем беда прям(

@Sindbad_M 411 / 347 / 107 Регистрация: 23.05.2016 Сообщений: 1,431
	17.05.2017, 15:44	10
	Сообщение от Inerciya чисел, представленных в унарной системе. Числа разделены * переименовать единички в "а" и "b" можно так: 1 --> b * --> 1 --> a Задача сведена к предыдущей? 1

@Shamil1 Модератор 2976 / 2123 / 451 Регистрация: 26.03.2015 Сообщений: 8,274
	17.05.2017, 16:52	12
	Сообщение от Inerciya Например, для 111111 ответ 11 Вычитание реализуется заменами: c1->1c //перемещаем "c" в конец слова (после "1") 11->c //сокращаем, но запоминаем, сколько мы сократили В результате получим "11111cccc" или "11111ccc" или "ccccc". В первых двух случаях нам надо переименовать к виду "111111*1111" и повторить. В третьем случае переименовываем в "11111" и останавливаемся. 1

@andron773 0 / 0 / 0 Регистрация: 06.11.2015 Сообщений: 5
		1
	Построить алгоритм Маркова, который ищет НОД (Алгоритм Евклида) 09.11.2015, 06:30. Показов 6448. Ответов 27 Метки нет (Все метки) Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в чем, надо построить алгорифм Маркова, который ищет наибольший общий делитель (алгоритм Евклида). Заранее спасибо! 0

@Shamil1 Модератор 2976 / 2123 / 451 Регистрация: 26.03.2015 Сообщений: 8,274
	09.11.2015, 13:58	2
	Для вычисления разности двух чисел нужно из обоих чисел вычитать 1, пока меньшее не станет равным нулю. Вход: два числа. Выход: разность. 5-2: 5-2 => 4-1 => 4-0 => 4 Для вычисления остатка от деления нужно вычитать из делимого делитель, пока делимое не станет равным нулю. Получившееся число нужно вычесть из делимого. 7%3: 7-3 => 4-3 => 1-3 => 0-2 => 3-2 => 1 Так как вычитаемое число теряется, нужно хранить его в другом месте и копировать перед каждым вычитанием. Для вычисления НОД нужно вычислять остаток от деления одного числа на другое, пока остаток не станет равным нулю. Перед каждым вычислением остатка нужно менять числа местами: делитель на место делимого, остаток на место делителя (делимое теряется в процессе вычисления остатка). 0

@andron773 0 / 0 / 0 Регистрация: 06.11.2015 Сообщений: 5
	13.11.2015, 03:37 [ТС]	3
	Что-то я туплю, но я так и не понял как реализовать Евклида в алгоритме Маркова... 0

@~~IrineK~~ Заблокирован
	13.11.2015, 03:59	4
	В вики есть два примера. У вас должно получиться нечто похожее, но по поводу НОД. 0

@Shamil1 Модератор 2976 / 2123 / 451 Регистрация: 26.03.2015 Сообщений: 8,274
	13.11.2015, 09:51	5
	Сообщение от andron773 Что-то я туплю, но я так и не понял как реализовать Евклида в алгоритме Маркова... Я перечислил три этапа вычислений. Какой из них вызывает у Вас затруднения? 0

@andron773 0 / 0 / 0 Регистрация: 06.11.2015 Сообщений: 5
	13.11.2015, 18:14 [ТС]	6
	Сообщение от Shamil1 Я перечислил три этапа вычислений. Какой из них вызывает у Вас затруднения? Ну просто ты перечислил остаток и т. д. А мне надо НОД, что бы искало наибольший общий делитель, т. к. это делается в Евклида 0

@andron773 0 / 0 / 0 Регистрация: 06.11.2015 Сообщений: 5
	15.11.2015, 19:38 [ТС]	8
	Понял, огромное спасибо. Нереально помог!) 0

@Inerciya 0 / 0 / 0 Регистрация: 17.05.2017 Сообщений: 11
	17.05.2017, 15:30	9
	А как реализовать НОД для унарной системы счисления? Для такого задания: Постройте нормальный алгоритм, который находит наибольший общий делитель двух чисел, представленных в унарной системе. Числа разделены * Например, для 1111*11 ответ 11 0

@Inerciya 0 / 0 / 0 Регистрация: 17.05.2017 Сообщений: 11
	17.05.2017, 16:50	11
	Если под сведена Вы имеете в виду, что я должна получить в итоге, то в общем да, в конце нужно оставить НОД. Но я этот алгоритм Маркова вообще не поняла... точнее принцип работы ясен, но эту задачу воплотить не могу Добавлено через 57 минут У меня уже почти все готово, осталось c перевести обратно в 1. Вот с этим пока проблема 0

@Sindbad_M 411 / 347 / 107 Регистрация: 23.05.2016 Сообщений: 1,431
	17.05.2017, 16:53	13
	___ 0

Опции темы

@Inerciya 0 / 0 / 0 Регистрация: 17.05.2017 Сообщений: 11
	17.05.2017, 16:55	14
	1->a a->%a b->%b c->!c %a->a% %b->a% %c->b% %-> !c->a! !->. cb->bc ab->c -> Может есть идеи, как НОД обратно в единицы перевести? 0

@Sindbad_M 411 / 347 / 107 Регистрация: 23.05.2016 Сообщений: 1,431
	17.05.2017, 16:57	15
	Сообщение от Shamil1 11->c //сокращаем, но запоминаем, сколько мы сократили может 11 --> *c ? 2

@Inerciya 0 / 0 / 0 Регистрация: 17.05.2017 Сообщений: 11
	17.05.2017, 16:58	16
	1->a a->%a b->%b c->!c %a->a% %b->a% %c->b% %-> !c->a! !->. cb->bc ab->c -> Может есть идеи, как НОД обратно в единицы перевести? 0

@Shamil1 Модератор 2976 / 2123 / 451 Регистрация: 26.03.2015 Сообщений: 8,274
	17.05.2017, 17:11	17
	Сообщение от Sindbad_M может 11 --> c ? Да. 0

@Inerciya 0 / 0 / 0 Регистрация: 17.05.2017 Сообщений: 11
	17.05.2017, 17:18	18
	Последний алгоритм, который я случайно два раза отправила, уже отлично работает, в нем только надо ответ перевести обратно в единички. 0

@Sindbad_M 411 / 347 / 107 Регистрация: 23.05.2016 Сообщений: 1,431
	17.05.2017, 17:43	19
	___ 0

@Inerciya 0 / 0 / 0 Регистрация: 17.05.2017 Сообщений: 11
	17.05.2017, 17:45	20
	В конце, кстати, получается НОД не в "с" выдает, а в "а". То есть для 11*11 НОД аа аа обратно перевести не получается, может все-таки кто-нибудь знает? А то совсем беда прям( 0