Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/10: Рейтинг темы: голосов - 10, средняя оценка - 5.00
andron773
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 5
1

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

09.11.2015, 06:30. Просмотров 1907. Ответов 27
Метки нет (Все метки)

Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в чем, надо построить алгорифм Маркова, который ищет наибольший общий делитель (алгоритм Евклида). Заранее спасибо!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2015, 06:30
Ответы с готовыми решениями:

Алгоритм Евклида
Написать вариант алгоритма Евклида, использующий соотношения НОД(2*a, 2*b) = 2*НОД(a,b)

алгоритм Евклида
не могу понять как алгоритм Евклида работает в программе для чего он нужен? как его работа...

Алгоритм Маркова
Здравствуйте! Подскажите, пожалуйста, как можно построить алгоритм Маркова для следующей задачи: ...

Алгоритм Маркова
Помогите сделать задачи: 1) Составить нормальный алгоритм Маркова вычисляющий функцию f(x)=4x+4;...

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

27
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,427
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
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,427
13.11.2015, 09:51 5
Цитата Сообщение от andron773 Посмотреть сообщение
Что-то я туплю, но я так и не понял как реализовать Евклида в алгоритме Маркова...
Я перечислил три этапа вычислений. Какой из них вызывает у Вас затруднения?
0
andron773
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 5
13.11.2015, 18:14  [ТС] 6
Цитата Сообщение от Shamil1 Посмотреть сообщение
Я перечислил три этапа вычислений. Какой из них вызывает у Вас затруднения?
Ну просто ты перечислил остаток и т. д. А мне надо НОД, что бы искало наибольший общий делитель, т. к. это делается в Евклида
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,427
14.11.2015, 18:18 7
Результатом третьего этапа вычислений и будет НОД.

Вод для примера:
C#
1
2
3
4
5
6
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
// символ для переименования
->*
2
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
Sindbad_M
119 / 119 / 36
Регистрация: 23.05.2016
Сообщений: 488
17.05.2017, 15:44 10
Цитата Сообщение от Inerciya Посмотреть сообщение
чисел, представленных в унарной системе. Числа разделены *
переименовать единички в "а" и "b" можно так:
*1 --> b*
* -->
1 --> a
Задача сведена к предыдущей?
1
Inerciya
0 / 0 / 0
Регистрация: 17.05.2017
Сообщений: 11
17.05.2017, 16:50 11
Если под сведена Вы имеете в виду, что я должна получить в итоге, то в общем да, в конце нужно оставить НОД. Но я этот алгоритм Маркова вообще не поняла... точнее принцип работы ясен, но эту задачу воплотить не могу

Добавлено через 57 минут
У меня уже почти все готово, осталось c перевести обратно в 1. Вот с этим пока проблема
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,427
17.05.2017, 16:52 12
Цитата Сообщение от Inerciya Посмотреть сообщение
Например, для 1111*11 ответ 11
Вычитание реализуется заменами:
c1->1c //перемещаем "c" в конец слова (после "1")
1*1->c //сокращаем, но запоминаем, сколько мы сократили
В результате получим "11111*cccc" или "*11111ccc" или "ccccc".
В первых двух случаях нам надо переименовать к виду "111111*1111" и повторить. В третьем случае переименовываем в "11111" и останавливаемся.
1
Sindbad_M
119 / 119 / 36
Регистрация: 23.05.2016
Сообщений: 488
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
119 / 119 / 36
Регистрация: 23.05.2016
Сообщений: 488
17.05.2017, 16:57 15
Цитата Сообщение от Shamil1 Посмотреть сообщение
1*1->c //сокращаем, но запоминаем, сколько мы сократили
может
1*1 --> *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
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,427
17.05.2017, 17:11 17
Цитата Сообщение от Sindbad_M Посмотреть сообщение
может
1*1 --> *c
?
Да.
0
Inerciya
0 / 0 / 0
Регистрация: 17.05.2017
Сообщений: 11
17.05.2017, 17:18 18
Последний алгоритм, который я случайно два раза отправила, уже отлично работает, в нем только надо ответ перевести обратно в единички.
0
Sindbad_M
119 / 119 / 36
Регистрация: 23.05.2016
Сообщений: 488
17.05.2017, 17:43 19
___
0
Inerciya
0 / 0 / 0
Регистрация: 17.05.2017
Сообщений: 11
17.05.2017, 17:45 20
В конце, кстати, получается НОД не в "с" выдает, а в "а". То есть для 11*11 НОД аа
аа обратно перевести не получается, может все-таки кто-нибудь знает? А то совсем беда прям(
0
17.05.2017, 17:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.05.2017, 17:45

Алгоритм Маркова
Вот система, для неё нужно написать алгоритм маркова. Не могу разобраться.

Алгоритм Маркова
Подсобите, господа, у нас есть унарный алфавит состоящий из | Нужно вывести пустое множество...

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


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

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

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