Форум программистов, компьютерный форум, киберфорум
Наши страницы
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
HitGirl
7 / 7 / 1
Регистрация: 08.10.2015
Сообщений: 264
1

Алгоритм поиска наименьшего и наибольшего множителей двух чисел

14.07.2018, 11:38. Просмотров 419. Ответов 12

Здравствуйте!
В книге Г.Шилдта есть метод для поиска наименьшего и наибольшего общего множителя двух чисел:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public bool HasComFactor(int x, int y,out int least,out int gratest)
    {
        int i;
        int max = x < y ? x : y;
        bool first = true;
        least = 1;
        gratest = 1;
 
        for (i = 2; i <= max / 2 + 1; ++i)
            if (((y % i) == 0) & ((x % i) == 0))
            {
                if (first)
                {
                    least = i;
                    first = false;
                }
                gratest = i;
            }
 
        if (least != 1)
            return true;
        else
            return false;
    }
Подскажите, пожалуйста, почему в качестве условия в цикле for используется выражение i <= max / 2 + 1, а не i<=max/2?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.07.2018, 11:38
Ответы с готовыми решениями:

Алгоритм поиска элементов, встречающихся только однажды в двух массивах
Всем привет, у меня такая проблема, помогите, нужно чтобы из двух массивов выводило. Элементы,...

Перевод с Pascal на C#: определение наибольшего общего делителя двух натуральных чисел
Здравствуйте, очень нужно перевести задачи из паскаля в C#. Тут задачи и ссылки на задачи на...

Написать программу вычисления наибольшего общего делителя двух целых чисел
1. Написать программу вычисления наибольшего общего делителя двух целых чисел. Наибольший общий...

Используя функцию поиска наибольшего (наименьшего) из двух чисел, вычислить выражение
используя функцию поиска наибольшего(наименьшего) из двух чисел составить программу вычисления...

Вычислить выражение, используя процедуру поиска наибольшего (наименьшего) из двух чисел
Тут нужно составить программу вычисления выражения используя: 1)процедуру поиска...

12
amr-now
Эксперт JS
1700 / 996 / 445
Регистрация: 14.06.2018
Сообщений: 2,493
14.07.2018, 12:02 2
Определение. Наибольшим общим делителем чисел a и b называется наибольшее число, на которое a и b делятся без остатка.
НОД он еще с советских времён назывался.

Правильно так:
C#
1
2
        for (i = 2; i <= max / 2; ++i)
            if (((y % i) == 0) && ((x % i) == 0))
0
theSUPPAFILA
0 / 0 / 0
Регистрация: 18.11.2015
Сообщений: 8
14.07.2018, 12:33 3
Цитата Сообщение от HitGirl Посмотреть сообщение
for (i = 2; i <= max / 2 + 1; ++i)
По-моему дело в "++i". Если бы было "i++" то цикл бы был с i<max/2. Камнями не кидайтесь)
0
amr-now
Эксперт JS
1700 / 996 / 445
Регистрация: 14.06.2018
Сообщений: 2,493
14.07.2018, 12:44 4
theSUPPAFILA, нет. Третья часть в круглых скобках у for предназначена для одной произвольной инструкции после выполненной итерации for.

Рекомендую разобраться в следующей конструкции для регулярного выражения:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
        /// <summary>
        /// Создайте регэксп, который ищет все числа без экспоненты, в том числе и с десятичной точкой, в том числе и отрицательные.
        /// -1.5, 0, 2, -123.4
        /// </summary>
        private static void JavaScript05_04()
        {
            var s = @"-1.5 0 2 -123.4.";
            var regex = new Regex(@"-?\d+(\.\d+)?");
 
            for (Match match = regex.Match(s); match.Success; match = match.NextMatch())
            {
                Console.WriteLine(match.Value);
            }
        }
Кстати, здесь очень хорошие примеры, которые рекомендую всем повторить на C#:
https://learn.javascript.ru/regexp-quantifiers
1
14.07.2018, 12:44
theSUPPAFILA
0 / 0 / 0
Регистрация: 18.11.2015
Сообщений: 8
14.07.2018, 13:03 5
Нет, ну третья часть у цикла я понимаю с какой целью там. Просто в случае преинкремента сначала происходит увеличение, а затем его использование.

Добавлено через 1 минуту
amr-now, Нет, ну третья часть у цикла я понимаю с какой целью там. Просто в случае преинкремента сначала происходит увеличение, а затем его использование.
0
amr-now
Эксперт JS
1700 / 996 / 445
Регистрация: 14.06.2018
Сообщений: 2,493
14.07.2018, 14:08 6
theSUPPAFILA, в третьей части в круглых скобках у for в инструкциях ++i и i++ значение никем не используется. i увеличивается и всё.
0
HitGirl
7 / 7 / 1
Регистрация: 08.10.2015
Сообщений: 264
14.07.2018, 15:01  [ТС] 7
Цитата Сообщение от amr-now Посмотреть сообщение
Наибольшим общим делителем чисел
Здесь не НОД ищется, а множители. Например: наибольший множитель 15 и 30: 5, наименьший - 3;
У Шилдта также был такой пример:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
public int LeastComFactor(int a, int b)
    {
        int max; 
 
        if (IsPrime(a) || (IsPrime(b))) return 1;
 
        max = a < b ? a : b;
 
        for (int i = 2; i <= max / 2; ++i)
            if (((a % i) == 0) && ((b % i) == 0)) return i;
 
        return 1;
    }
Но тут метод ищет только наименьший общий множитель двух чисел.
Вопрос состоит в том, почему изменилось условие в цикле?
0
amr-now
Эксперт JS
1700 / 996 / 445
Регистрация: 14.06.2018
Сообщений: 2,493
14.07.2018, 16:31 8
HitGirl, опечатка скорее всего.

Добавлено через 40 минут
Убивает наповал:
C#
1
2
        int max; 
        max = a < b ? a : b;
Если здесь max, то я инопланетный рептилоид.
0
IamRain
1423 / 1266 / 399
Регистрация: 02.08.2011
Сообщений: 3,752
14.07.2018, 20:06 9
Цитата Сообщение от amr-now Посмотреть сообщение
Если здесь max, то я инопланетный рептилоид.
Видимо, так и есть. Подразумевается, что максимальный общий множитель не может быть больше меньшего из двух чисел.

Добавлено через 8 минут
Цитата Сообщение от HitGirl Посмотреть сообщение
i <= max / 2 + 1, а не i<=max/2?
Видимо, человек, который писал, импульсивно решил (не подумав), что если меньшее число нечетное, то надо брать верхнюю границу больше половины этого числа, хотя само число max уже точно не будет делиться на это max/2 + 1.
На самом деле, тут не совсем корректное условие идет, может быть так, что большее из двух чисел делится без остатка на меньшее - нужно в первую очередь проверить этот вариант. А потом уже использовать деление пополам max/2.
0
amr-now
Эксперт JS
1700 / 996 / 445
Регистрация: 14.06.2018
Сообщений: 2,493
14.07.2018, 20:18 10
IamRain, ещё поражает, что Google и Яндекс не знают о существовании термина "Наибольший общий множитель".

Память о НОД и вводящее в заблуждение имя переменной max как раз и заставили думать о НОД )) (max по смыслу относится к НОД.)
0
HitGirl
7 / 7 / 1
Регистрация: 08.10.2015
Сообщений: 264
14.07.2018, 20:42  [ТС] 11
Разница между условие i<=max+1 и i<=max возникает, если одно число чётное, а второе равно 2. При первом варианте (i<=max+1) общий множитель 2 (наименьший и наибольший одновременно), а во втором случае нет общих множителей.В первом варианте (i<=max+1),при x=15 и y=30 (а также в других парах чисел, когда оба числа больше двух и одно делится на другое без остатка), наибольший множитель равен 5, а не 15, возникает противоречие (в этом случае само число не является множителем, в отличие от случая когда одно число чётное, а другое равно 2). Для того чтобы утверждать какой вариант правильный, нужно определение понятия "наибольший и наименьший общий множитель двух чисел", но этот термин быстро не ищется, возможно, его нет в интернете.
0
IamRain
1423 / 1266 / 399
Регистрация: 02.08.2011
Сообщений: 3,752
15.07.2018, 07:00 12
Цитата Сообщение от HitGirl Посмотреть сообщение
Разница между условие i<=max+1 и i<=max возникает, если одно число чётное, а второе равно 2.
Это как раз тот случай,
Цитата Сообщение от IamRain Посмотреть сообщение
может быть так, что большее из двух чисел делится без остатка на меньшее - нужно в первую очередь проверить этот вариант.
Не надо городить костылей с условиями.
Цитата Сообщение от HitGirl Посмотреть сообщение
наибольший множитель равен 5, а не 15
Наибольший общий множитель как раз-таки равен 15.
0
amr-now
Эксперт JS
1700 / 996 / 445
Регистрация: 14.06.2018
Сообщений: 2,493
15.07.2018, 10:34 13
IamRain, для 15 и 30 число 15 будет как раз НОД. Именно НОД.
Но здесь поиск множителя для произвольного натурального числа с условием - множитель строго не равен 1, и множитель строго не равен самому числу.

Вопрос на засыпку - как быть с простыми числами? У них множители принципиально отсутствуют - return false.

Добавлено через 26 минут
Причем не брать в качестве множителя само число - явно дополнительно принудительно выставленное условие.
Обычно множителем является само число для самого себя. То есть у простого числа множители - 1 и оно само.
https://ru.wikihow.com/разложить-число-на-множители
0
15.07.2018, 10:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.07.2018, 10:34

Используя процедуру поиска наибольшего ( наименьшего ) из двух чисел, составить программу вычисления выражения
используя процедуру поиска наибольшего ( наименьшего ) из двух чисел, составить программу...

Используя процедуру поиска наибольшего (наименьшего) из двух чисел, составить программу вычисления выражения
Используя процедуру поиска наибольшего(наименьшего) из 2-х чисел, составить программу вычисления...

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


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

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

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