НОД

  • 16
  • Недоступна
Продолжаем наши попытки войти в космическое пространство планеты Линейный Хаос. И вот ещё одно задание с приграничного собеседования для юных поступающих: найти наибольший общий делитель (или НОД) двух целых положительных чисел.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (584)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Kolya Kutylov
Уровень 26
24 июня, 16:02
Сразу попытался загуглить, что такое НОД и там же был найден алгоритм для его поиска. int gcd(int a, int b) { if (b == 0) { return a; } return gcd(b, a % b); } Честно говоря не знаю зачем городить такие ребусы как в правильном решении. Если можно сделать все красивее.
Игорь Чайка
Уровень 28, Вінниця, Ukraine
21 июня, 09:48
интересная задачка.
Станислав Венцковский
Уровень 26, Днепр, Ukraine
18 июня, 07:19
Решил простым циклом: 1) задаем цикл для i, где i = от 0 до максимального из двух введенных чисел 2) условие если можно оба введенных числа поделить на i = присваиваем его значение НОД и выводим ее Т.к. у нас проверка идет от 0 до большего числа, в переменную НОД сохранится самый большой общий делитель
[M210] Java Developer
10 июня, 14:31
Решил задачу за 2 минуты, но быдлокодом))))
int a = Integer.parseInt(r.readLine());
int b = Integer.parseInt(r.readLine());

        	int c = b;
        	while(true) {
	        	while(a % c != 0) {
	            	c--;
	            }
	        	while(b % c != 0) {
	            	c--;
	            }

	        	if(a % c == 0) {
	            	break;
	            }
        	}

            System.out.println(c);
Vadym Illarionov
Уровень 29, Харьков, Ukraine
6 июня, 12:05
Ужасно запутанное правильное решение, можно сделать код в 5 строк, и очень понятным
Сонмониус
Уровень 33, Харьков, Ukraine
30 мая, 08:47
Очень понравился вариант со стандартным решением. Пока не разобрал его, не знал что так можно. Я делал через цикл, где в качестве итератора выступает меньшее, и цикл каждую итерацию уменьшается на единицу, пока меньшее и большее не станут делится на итератор без остатка
Blynchik Работает в Pegas Touristik
30 мая, 06:33
Находим меньшее и большее, в цикле пока меньшее не равно нулю во временную переменную записываем остаток от деления большего на меньшее большее = меньшее меньшее = временное после цикла выводим большее
Anton
Уровень 22, Москва, Russian Federation
3 июня, 08:30
Зачем так усложнять простую задачу? Делается проще:
for (int i = 1; i < 10; i++) {
     div = min / i;
     if (max % (div) == 0) {
        System.out.println(div);
        break;
     }
}
Anton
Уровень 22, Москва, Russian Federation
3 июня, 08:36
Хотя нет, я не прав, хоть валидатор и принял мой вариант с 1 раза. Он учитывает не весь диапазон значений, нужно в цикле написать:
for (int i = 1; i <= min; i++)
Vadym Illarionov
Уровень 29, Харьков, Ukraine
6 июня, 12:07
ты все равно не прав
Anton
Уровень 22, Москва, Russian Federation
6 июня, 13:36
Да, ты прав, некорректно считает значение делителя из-за округления, не учел этого.😅 Поправил, вроде бы работает.
public static void main(String[] args) {
    int min = 99;
    int max = 100;
    double div;

    for (int i = 1; i <= min; i++) {
        div = (double) min / i;
        if (max % (div) == 0 && div % 1 == 0) {
            System.out.println((int)div); //1
            break;
        }
    }
}
Игорь Чайка
Уровень 28, Вінниця, Ukraine
21 июня, 09:45
я тоже через алгоритм Евклида сделал.:)
Kidchai
Уровень 21, Chicago, United States
26 мая, 23:27
еее, алгоритм!
MRamazanov System Engineer
18 мая, 13:07
Решил так: 1. Вводим 2 числа 2. Находим делители для 2 чисел и заносим их в список 3. Находим список делителей у которого длина меньше чем у второго 4. Через вложенный цикл проверяем пару делителей из обоих списков. Смысл такой, если элемент списка минимальной длины равен элементу второго(большего списка) то считаем найденной пару делителей и .д. Так как делители идут во возрастанию последняя найденная пара делителей и будет соответствовать НОД
Abdushukur
Уровень 24, Andijan, Uzbekistan
21 апреля, 04:34
for (int i = Math.min(num1, num2); i > 0; i--) {
//           если num1 и num2 делятся на i  без остаток прерываем цикл и выводим на экран i