Форум программистов, компьютерный форум, киберфорум
Наши страницы
Java SE (J2SE)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
jewerly
0 / 0 / 0
Регистрация: 07.10.2017
Сообщений: 3
1

Решение сравнений первой степени методом Эйлера и алгоритмом Евклида

07.10.2017, 20:12. Просмотров 886. Ответов 4
Метки c++ (Все метки)

Помогите написать программу для решения сравнений методом Эйлера и алгоритмом Евклида. Уже неделю сижу и не могу понять сами методы, а программу написать так уж тем более не получится. Если кто-то сможет, то напишите комментарии к коду, хотелось бы разобраться от и до.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.10.2017, 20:12
Ответы с готовыми решениями:

Системы из 2х сравнений первой степени
ну сравнения первой степени понятно например 141x=156(mod171) все делится на...

Решение дифференциального уравнения методом Эйлера и методом Рунге-кутта 4 порядка
Помогите пожалуйста решить уравнение y''-4y'+5y=2x2ex , методом Эйлера и...

Решение дифференциального уравнения методом Эйлера и методом Рунге-кутта
Помогите пожалуйста решить уравнение у' = 1 + х sin y, y(π) = 2π , методом...

Решение дифференциальных уравнений четвертого порядка методом Эйлера и методом Рунге-Кутта
Форумчане прошу помочь решить уравнение f :=y+y'*x+y''+y'''*x методами...

Решение методом Эйлера
Подскажите правильный ли алгоритм к задаче? Почему не правильно задана функция...

4
ArtemFM
246 / 228 / 164
Регистрация: 10.09.2015
Сообщений: 850
08.10.2017, 12:12 2
Поясни задачу. Я универ закончил лет 10 назад...

Написать 2 разных метода (1. метод Эйлера; 2. алгоритм Евклида)? Просто я посмотрел в википедии о этих алгоритмах и мало нашёл взаимосвязи между ними. Но сам принцип этих методов понятен... Поставь более точнее задачу с подробностями, как и что должно быть...
0
jewerly
0 / 0 / 0
Регистрация: 07.10.2017
Сообщений: 3
08.10.2017, 22:08  [ТС] 3
Решить сравнение. Т.е имеется вот такой пример сравнения 10x≡12 (mod14). 10 -это a, 12 -b, 14 - m. a, b, m вводить с клавиатуры. Необходимо написать программу(две программы), которые будут решать эти сравнения разными методами(Эйлера и Евклида). Заранее спасибо
0
ArtemFM
246 / 228 / 164
Регистрация: 10.09.2015
Сообщений: 850
09.10.2017, 09:00 4
Так они не могут существовать без друг друга по сути при решении
10x≡12 (mod14)
(10,14) ищем с помощью метода Евклида НОД
затем решаем методом Эйлера с расширенным алгоритмом Евклида

Задача, конечно, жесть. Я так пока до конца и не понял метод Эйлера... Но почитаю

Добавлено через 5 часов 11 минут
Вот решение. Оно работает по методу Эйлера с использованием алгоритма Евклида для поиска НОД..
Тут он в консоль выведет полное решение от начала до конца. В принципе это можно убрать, что уменьшит код.
Сделал для тебя для видимости, чтоб понял, как решать иные уравнения...

Java
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
public class SimpleAlgorithm {
    public static final String LS = System.lineSeparator();
 
    public static void main(String[] args) {
        System.out.println(methodEiler(25, 15, 17));
 
    }
 
    public static String methodEiler(int a, int b, int m) {
        String formula = String.format("%sx = %s(mod %s)", a, b, m);
        String tab = String.format("%3s", "");
        StringBuilder sb = new StringBuilder(String.format("Formula:%s%3s%s%s", LS, "", formula, LS));
        sb.append("Решение:").append(LS);
        String mod = String.format("(mod %s)", m);
        int countSolution = algorithmEvklid(a, m); //получаем общий делитель и кол-во решений уравнения
        if (countSolution != 0 && b % countSolution == 0) { //если b не делится на делитель, то решений нет
            sb.append(String.format("%sформула имеет %s решени%s.%s",
                    tab, countSolution, countSolution > 1 ? "я" : "е", LS));
            a = getNumberLessMod(a, m); //возвращаем число меньше mod отнимая mod от числа
            b = getNumberLessMod(b, m); // --//--
            if (countSolution != 1) { //если делитель не равен 1, то можем всё уравнение поделить на делитель
                a /= countSolution; //делим a на делитель
                b /= countSolution; //делим b на делитель
                m /= countSolution; //делим m на делитель
            }
            formula = String.format("%sx = %s(mod %s)", a, b, m);
            sb.append(tab).append("формула после сокращений имеет вид: ").append(formula).append(LS);
            int fx = functionEiler(m); //решаем функцию Эйлера
            sb.append(String.format("%sрешаем функцию Эвклида f(%s): %s%s", tab, m, fx, LS));
            sb.append(tab).append(formula).append(" = ").append(String.format("%s * %s^%s", b, a, --fx)).append(" = ").append(LS);
            while (fx > 1) { //пока степень больше 1 заходим в цикл
                if (fx % 2 != 0) { //если степень нечётная, то однимаем от неё 1 и умножаем b на a; Пример 15 * 8^15 = 15*8 * 8^14 = 120 * 8^14
                    b *= a;
                    fx--;
                    sb.append(String.format("%s%s * %s^%s", tab, b, a, fx)).append(" = ");
                }
                a = (int) Math.pow(a, 2); //возводим a в степень 2
                fx /= 2; //а общую степень делим на 2. Пример: 120 * (8^2)^7 = 120 * (64)^7
                sb.append(String.format("%s%s * %s^%s", tab, b, a, fx)).append(" = ");
                a = getNumberLessMod(a, m); //отнимаем от a mod. Пример: 120 * (64-17-17-17)^7 = 120 * (13)^7
                b = getNumberLessMod(b, m); //отнимаем от b mod. Пример: 120-17-17-17-17-17-17-17 * 13^7 = 1 * 13^7
                sb.append(String.format("%s%s * %s^%s", tab, b, a, fx)).append(" = ").append(LS);
                //зайдём в цикл по новой, т.к. степень 7 > 1 и так да тех пор, пока стерень не останется 1
            }
            int c = getNumberLessMod(a * b, m); //первое решение. перемножаем a на b и отнимаем mod
            sb.append(tab).append(c).append(LS);
            sb.append("Ответ:").append(LS);
            for (int i = 0; i < countSolution; i++) { //Выодит все решения по формуле x = 5*k + b(mod m) где k - это кол-во решений от 0
                                                      //к примеру если решений 3, то k = 0, 1, 2; если 5 решение: k = 0, 1, 2, 3, 4
                c += 5 * i;
                sb.append(tab).append("x = ").append(c).append(mod).append(LS);
            }
        } else {
            sb.append(tab).append("решений нет");
        }
        return sb.append(LS).toString();
    }
 
    /**
     * Если модуль числа number больше mod, то
     * если number отрицательное, прибавляем к нему mod до тех пор, пока модуль number не меньше mod
     * если number положительное, то отнимаем от него mod --//--
     *
     * @param number - число number;
     * @param mod - mod;
     * @return - возвращаем число меньше mod
     */
    public static int getNumberLessMod(int number, int mod) {
        while (Math.abs(number) > mod) {
            if (number < 0) {
                number += mod;
            } else {
                number -= mod;
            }
        }
        return number;
    }
 
    /**
     * Метод ищет общий делитель для 2-х чисел (НОД) по алгоритму Евклида.
     * А также НОД является кол-во решений сравнений степени.
     *
     * @param a - первое число;
     * @param b - второе число;
     * @return общий делители или 0, если оба числа равны 0;
     */
    public static int algorithmEvklid(int a, int b) {
        int d = 0;
        while (b != 0 && a != 0) {
            if (a > b) {
                a %= b;
            } else {
                b %= a;
            }
            d = a + b;
        }
        return d;
    }
 
    /**
     * Метод решает функцию Эвклида. Находит кол-во взаимно простых чисел с x до x не включая.
     * Взаимно простые числа - это числа, у которых общий делитель 1.
     * Используем алгоритм Евклида. Если вернёться из него не 1, то значит число не взаимно простые.
     *
     * @param x - число x;
     * @return кол-во взаимно простых чисел до x не включая x;
     */
    public static int functionEiler(int x) {
        int countPrimeNumber = 0;
        if (x > 0) {
            for (int i = 1; i < x; i++) {
                if (algorithmEvklid(i, x) == 1) {
                    countPrimeNumber++;
                }
            }
        }
        return countPrimeNumber;
    }
}
Добавлено через 25 минут
Забыл сделать ввод данных с клавиатура, да и поправил недочёты в объяснениях. Вот изменённый код

Java
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import java.util.Scanner;
 
public class SimpleAlgorithm {
    public static final String LS = System.lineSeparator();
 
    public static void main(String[] args) {
        System.out.println("Формула имеет вид: ax = b(mod m)");
        int a = readConsole("Введите параметр a");
        int b = readConsole("Введите параметр b");
        int m = readConsole("Введите параметр m");
        System.out.println(methodEiler(a, b, m));
 
    }
 
    public static String methodEiler(int a, int b, int m) {
        String formula = String.format("%sx = %s(mod %s)", a, b, m);
        String tab = String.format("%3s", "");
        StringBuilder sb = new StringBuilder(String.format("Formula:%s%3s%s%s", LS, "", formula, LS));
        sb.append("Решение:").append(LS);
        String mod = String.format("(mod %s)", m);
        int countSolution = algorithmEvklid(a, m); //получаем общий делитель и кол-во решений уравнения
        if (countSolution != 0 && b % countSolution == 0) { //если b не делится на делитель, то решений нет
            sb.append(String.format("%sформула имеет %s решени%s.%s",
                    tab, countSolution, countSolution > 1 ? "я" : "е", LS));
            a = getNumberLessMod(a, m); //возвращаем число меньше mod отнимая mod от числа
            b = getNumberLessMod(b, m); // --//--
            if (countSolution != 1) { //если делитель не равен 1, то можем всё уравнение поделить на делитель
                a /= countSolution; //делим a на делитель
                b /= countSolution; //делим b на делитель
                m /= countSolution; //делим m на делитель
            }
            formula = String.format("%sx = %s(mod %s)", a, b, m);
            sb.append(tab).append("формула после сокращений имеет вид: ").append(formula).append(LS);
            int fx = functionEiler(m); //решаем функцию Эйлера
            sb.append(String.format("%sрешаем функцию Эвклида f(%s): %s%s", tab, m, fx, LS));
            sb.append(tab).append(formula).append(" = ").append(String.format("%s * %s^%s", b, a, --fx)).append(" = ").append(LS);
            while (fx > 1) { //пока степень больше 1 заходим в цикл
                if (fx % 2 != 0) { //если степень нечётная, то однимаем от неё 1 и умножаем b на a; Пример 15 * 8^15 = 15*8 * 8^14 = 120 * 8^14
                    b *= a;
                    fx--;
                    sb.append(String.format("%s%s * %s^%s", tab, b, a, fx)).append(" = ");
                }
                a = (int) Math.pow(a, 2); //возводим a в степень 2
                fx /= 2; //а общую степень делим на 2. Пример: 120 * (8^2)^7 = 120 * (64)^7
                sb.append(String.format("%s * %s^%s", b, a, fx)).append(" = ");
                a = getNumberLessMod(a, m); //отнимаем от a mod. Пример: 120 * (64-17-17-17)^7 = 120 * (13)^7
                b = getNumberLessMod(b, m); //отнимаем от b mod. Пример: 120-17-17-17-17-17-17-17 * 13^7 = 1 * 13^7
                sb.append(String.format("%s * %s^%s", b, a, fx)).append(" = ").append(LS);
                //зайдём в цикл по новой, т.к. степень 7 > 1 и так да тех пор, пока стерень не останется 1
            }
            int c = getNumberLessMod(a * b, m); //первое решение. перемножаем a на b и отнимаем mod
            sb.append(tab).append(c).append(LS);
            sb.append("Ответ:").append(LS);
            for (int i = 0; i < countSolution; i++) { //Выодит все решения по формуле x = 5*k + b(mod m) где k - это кол-во решений от 0
                                                      //к примеру если решений 3, то k = 0, 1, 2; если 5 решение: k = 0, 1, 2, 3, 4
                c += 5 * i;
                sb.append(tab).append("x = ").append(c).append(mod).append(LS);
            }
        } else {
            sb.append(tab).append("решений нет");
        }
        return sb.append(LS).toString();
    }
 
    /**
     * Если модуль числа number больше mod, то
     * если number отрицательное, прибавляем к нему mod до тех пор, пока модуль number не меньше mod
     * если number положительное, то отнимаем от него mod --//--
     *
     * @param number - число number;
     * @param mod - mod;
     * @return - возвращаем число меньше mod
     */
    public static int getNumberLessMod(int number, int mod) {
        while (Math.abs(number) > mod) {
            if (number < 0) {
                number += mod;
            } else {
                number -= mod;
            }
        }
        return number;
    }
 
    /**
     * Метод ищет общий делитель для 2-х чисел (НОД) по алгоритму Евклида.
     * А также НОД является кол-во решений сравнений степени.
     *
     * @param a - первое число;
     * @param b - второе число;
     * @return общий делители или 0, если оба числа равны 0;
     */
    public static int algorithmEvklid(int a, int b) {
        int d = 0;
        while (b != 0 && a != 0) {
            if (a > b) {
                a %= b;
            } else {
                b %= a;
            }
            d = a + b;
        }
        return d;
    }
 
    /**
     * Метод решает функцию Эйлера. Находит кол-во взаимно простых чисел с 1 до x - 1.
     * Взаимно простые числа - это числа, у которых общий делитель 1.
     * Используем алгоритм Евклида. Если вернёться из него не 1, то значит число не взаимно простые.
     *
     * @param x - число x;
     * @return кол-во взаимно простых чисел до x не включая x;
     */
    public static int functionEiler(int x) {
        int countPrimeNumber = 0;
        if (x > 0) {
            for (int i = 1; i < x; i++) {
                if (algorithmEvklid(i, x) == 1) {
                    countPrimeNumber++;
                }
            }
        }
        return countPrimeNumber;
    }
 
    public static int readConsole(String answer) {
        Scanner read = new Scanner(System.in);
        boolean value = false;
        int result = 0;
        while (!value) {
            System.out.printf("%s: ", answer);
            try {
                result = Integer.valueOf(read.next());
                value = true;
            } catch (NumberFormatException e) {
                System.out.println("The value is not number. Try again.");
            }
        }
        return result;
    }
}
Добавлено через 2 часа 0 минут
Упссс... Там кое где ошибочка

поправь код со строки 54 по 58:
Java
1
2
3
4
5
for (int i = 0; i < countSolution; i++) { //Выодит все решения по формуле x = m*k + c(mod m) где k - это кол-во решений от 0
                                                      //к примеру если решений 3, то k = 0, 1, 2; если 5 решение: k = 0, 1, 2, 3, 4
                c += 5 * i;
                sb.append(tab).append("x = ").append(c).append(mod).append(LS);
            }
на вот этот:
Java
1
2
3
4
for (int i = 0; i < countSolution; i++) { //Выодит все решения по формуле x = m*k + c(mod m) где k - это кол-во решений от 0
                                                      //к примеру если решений 3, то k = 0, 1, 2; если 5 решение: k = 0, 1, 2, 3, 4
                sb.append(tab).append("x = ").append(m * i + c).append(mod).append(LS);
            }
1
jewerly
0 / 0 / 0
Регистрация: 07.10.2017
Сообщений: 3
09.10.2017, 19:00  [ТС] 5
Спасибо вам. Очень помогли)
0
09.10.2017, 19:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.10.2017, 19:00

Решение уравнения методом Эйлера
прошу помочь написать решение задач в Pascal 1) решить уравнение Y’x –sin(x)...

Решение уравнения методом Эйлера
Доброго времени суток всем!!! Помогите реализовать программу на С#. Заряд (q)...

Решение уравнения методом Эйлера
1.Разработать приложение на Visual Basic 6 для решения указанной задачи:...


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

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

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