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

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

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

Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в чем, надо построить алгорифм Маркова, который ищет наибольший общий делитель (алгоритм Евклида). Заранее спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.11.2015, 06:30
Ответы с готовыми решениями:

Построить алгоритм Евклида для нахождения НОД чисел
Заданы два натуральных числа a, b. Построить алгоритм Евклида для нахождения НОД этих чисел....

Построить алгоритм Маркова. Вместо символа, который находится на четном месте вставить символ *, остальные буквы
Добрый день, уже второй день не могу разобраться как реализовать алгоритм Маркова. Задание такое:...

НОД . Рекурсивный алгоритм Евклида
1. Даны два натуральных числа X и Y. Найти их наибольший общий делитель, используя рекурсивный...

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

27
Модератор
2645 / 1820 / 403
Регистрация: 26.03.2015
Сообщений: 6,754
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
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 5
13.11.2015, 03:37  [ТС] 3
Что-то я туплю, но я так и не понял как реализовать Евклида в алгоритме Маркова...
0
Заблокирован
13.11.2015, 03:59 4
В вики есть два примера.
У вас должно получиться нечто похожее, но по поводу НОД.
0
Модератор
2645 / 1820 / 403
Регистрация: 26.03.2015
Сообщений: 6,754
13.11.2015, 09:51 5
Цитата Сообщение от andron773 Посмотреть сообщение
Что-то я туплю, но я так и не понял как реализовать Евклида в алгоритме Маркова...
Я перечислил три этапа вычислений. Какой из них вызывает у Вас затруднения?
0
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 5
13.11.2015, 18:14  [ТС] 6
Цитата Сообщение от Shamil1 Посмотреть сообщение
Я перечислил три этапа вычислений. Какой из них вызывает у Вас затруднения?
Ну просто ты перечислил остаток и т. д. А мне надо НОД, что бы искало наибольший общий делитель, т. к. это делается в Евклида
0
Модератор
2645 / 1820 / 403
Регистрация: 26.03.2015
Сообщений: 6,754
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
0 / 0 / 0
Регистрация: 06.11.2015
Сообщений: 5
15.11.2015, 19:38  [ТС] 8
Понял, огромное спасибо. Нереально помог!)
0
0 / 0 / 0
Регистрация: 17.05.2017
Сообщений: 11
17.05.2017, 15:30 9
А как реализовать НОД для унарной системы счисления? Для такого задания: Постройте нормальный алгоритм, который находит наибольший общий делитель двух чисел, представленных в унарной системе. Числа разделены *
Например, для 1111*11 ответ 11
0
264 / 234 / 68
Регистрация: 23.05.2016
Сообщений: 945
17.05.2017, 15:44 10
Цитата Сообщение от Inerciya Посмотреть сообщение
чисел, представленных в унарной системе. Числа разделены *
переименовать единички в "а" и "b" можно так:
*1 --> b*
* -->
1 --> a
Задача сведена к предыдущей?
1
0 / 0 / 0
Регистрация: 17.05.2017
Сообщений: 11
17.05.2017, 16:50 11
Если под сведена Вы имеете в виду, что я должна получить в итоге, то в общем да, в конце нужно оставить НОД. Но я этот алгоритм Маркова вообще не поняла... точнее принцип работы ясен, но эту задачу воплотить не могу

Добавлено через 57 минут
У меня уже почти все готово, осталось c перевести обратно в 1. Вот с этим пока проблема
0
Модератор
2645 / 1820 / 403
Регистрация: 26.03.2015
Сообщений: 6,754
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
264 / 234 / 68
Регистрация: 23.05.2016
Сообщений: 945
17.05.2017, 16:53 13
___
0
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
264 / 234 / 68
Регистрация: 23.05.2016
Сообщений: 945
17.05.2017, 16:57 15
Цитата Сообщение от Shamil1 Посмотреть сообщение
1*1->c //сокращаем, но запоминаем, сколько мы сократили
может
1*1 --> *c
?
2
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
Модератор
2645 / 1820 / 403
Регистрация: 26.03.2015
Сообщений: 6,754
17.05.2017, 17:11 17
Цитата Сообщение от Sindbad_M Посмотреть сообщение
может
1*1 --> *c
?
Да.
0
0 / 0 / 0
Регистрация: 17.05.2017
Сообщений: 11
17.05.2017, 17:18 18
Последний алгоритм, который я случайно два раза отправила, уже отлично работает, в нем только надо ответ перевести обратно в единички.
0
264 / 234 / 68
Регистрация: 23.05.2016
Сообщений: 945
17.05.2017, 17:43 19
___
0
0 / 0 / 0
Регистрация: 17.05.2017
Сообщений: 11
17.05.2017, 17:45 20
В конце, кстати, получается НОД не в "с" выдает, а в "а". То есть для 11*11 НОД аа
аа обратно перевести не получается, может все-таки кто-нибудь знает? А то совсем беда прям(
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.05.2017, 17:45

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

НОД двух чисел алгоритм Евклида
Найти найбольший общий делитель двух чисел по алгоритму Евклида. Использовать рекурсию.

Алгоритм Евклида для нахождения НОД
Уважаемые форумчане, никак не получается написать алгоритм Евклида, возможно не хватает знаний,...

Самый быстрый алгоритм Евклида вычисления НОД
Заинтересовал вопрос о различных реализациях алгоритма Евклида для неотрицательных целых чисел....

Найти НОД 2-х многочленов, используя алгоритм Евклида
Алгоритм основан на том факте, что для любых двух многочленов от одного переменного, f(x) и g(x),...

Найти НОД многочленов, применив алгоритм Евклида
Найти НОД многочленов Ф(х) и Джи(Х) алгоритма Евклиды f(x)=x^5+x^4-3x^3+9x^2 g(x)=x^4+2x^3-8 ...


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

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

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