• ,

level14.lesson08.bonus02

Не проходит тестирование. Находит вроде правильно. Помогите понять в чем моя ошибка, пожалуйста!
package com.javarush.test.level14.lesson08.bonus02;

/* НОД
Наибольший общий делитель (НОД).
Ввести с клавиатуры 2 целых положительных числа.
Вывести в консоль наибольший общий делитель.
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Solution
{
    static int NOD = 1;
    static ArrayList<Integer> list1 = new ArrayList<Integer>();
    static ArrayList<Integer> list2 = new ArrayList<Integer>();

    public static void main(String[] args) throws Exception
    {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String a = reader.readLine();
        String b = reader.readLine();
        getPrimeFactor(a, list1);
        getPrimeFactor(b, list2);

        for (Integer x : resList(list1, list2))
            NOD *= x;
        System.out.println(NOD);
        }

    public static int initList(ArrayList<Integer> list, String a){

        if (divisionBy2(a) != -1){
            list.add(2);
            return divisionBy2(a);
        }
        else if (divisionBy3(a) != -1){
            list.add(3);
            return divisionBy3(a);
        }
        else if (divisionBy5(a) != -1){
            list.add(5);
            return divisionBy5(a);
        }
        else if (divisionBy6(a) != -1){
            list.add(2);
            return divisionBy6(a);
        }
        else if (divisionBy9(a) != -1){
            list.add(9);
            return divisionBy9(a);
        }
        else list.add(SimpleDigit(a));
            return SimpleDigit(a);

    }
    public static void getPrimeFactor(String a, ArrayList<Integer> list){
        int buf = initList(list, a);
        while (buf != 1){
            buf = initList(list, Integer.toString(buf));
        }
    }
    static int divisionBy2(String a){
        int c = Integer.parseInt(a.substring(a.length() - 1, a.length()));
        if (c == 0 || c == 2 || c == 4 || c == 6 || c == 8)
            return Integer.parseInt(a) / 2;
        return -1;
    }
    static int divisionBy3(String a){
        int buf = 0;
        for (int i = a.length(); i > 0; i--)
            buf += Integer.parseInt(a.substring(i - 1, i));
        if (buf % 3 == 0)
            return Integer.parseInt(a) / 3;
        return -1;
    }
    static int divisionBy6(String a){
        int b = Integer.parseInt(a);
        if (b % 2 == 0 && b % 3 == 0)
            return b / 2;
        return -1;
    }
    static int divisionBy5(String a){
        if (Integer.parseInt(a.substring(a.length() - 1, a.length())) == 0 ||
                Integer.parseInt(a.substring(a.length() - 1, a.length())) == 5)
            return Integer.parseInt(a) / 5;
        return -1;
    }
    static int divisionBy9(String a){
        int buf = 0;
        for (int i = a.length(); i > 0; i--)
            buf += Integer.parseInt(a.substring(i - 1, i));
        if (buf % 9 == 0)
            return Integer.parseInt(a) / 9;
        return -1;
    }
    static int SimpleDigit(String a){
        return Integer.parseInt(a) / Integer.parseInt(a);
    }
    public static ArrayList<Integer> resList(ArrayList<Integer> list1, ArrayList<Integer> list2){
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (list1.size() > list2.size()){
            for (Iterator<Integer> i = list2.iterator(); i.hasNext(); ){
                Integer l2 = i.next();
                for (Iterator<Integer> j = list1.iterator(); j.hasNext(); ){
                    Integer l1 = j.next();
                    if (l2.equals(l1)){
                        result.add(l2);
                        break;
                    }
                }
            }
        }else if (list1.size() < list2.size()){
            for (Iterator<Integer> i = list1.iterator(); i.hasNext(); ){
                Integer l1 = i.next();
                for (Iterator<Integer> j = list2.iterator(); j.hasNext(); ){
                    Integer l2 = j.next();
                    if (l1.equals(l2)){
                        result.add(l1);
                        break;
                    }
                }
            }
        }else if (list1.size() == list2.size()){
            for (Iterator<Integer> i = list1.iterator(); i.hasNext(); ){
                Integer l1 = i.next();
                for (Iterator<Integer> j = list2.iterator(); j.hasNext(); ){
                    Integer l2 = j.next();
                    if (l1.equals(l2)){
                        result.add(l1);
                        list2.remove(l2);
                        break;
                    }
                }
            }
        }
        return result;
    }
}

67 комментариев

bfg
Это какой-то ад.

Просто выясни, какое из 2-х чисел меньшее, потом в цикле до этого меньшего значения проверяй, чтобы одновременно выполнялось (a % i == 0) && (b % i == 0), и заноси в какую-нибудь переменную текущее значение i.
Конечное значение этой переменной и будет ответом. Задача в 3 строчки.
lisoed
Тогда уж лучше так:
for (int i = 1; i <= a; i++) {
            if ((a % i == 0) && (b % (a / i) == 0)) {
                System.out.println(a/i);
                break;
            }
    

Быстрее найдется
Coder
  • Coder
  • 0
  • Комментарий отредактирован 2014-05-23 22:24:05 пользователем Coder
Такой алгоритм нахождения НОД:
— разложить все данные числа на простые множители;
— отметить одинаковые множители во всех разложениях;
— найти произведение отмеченных множителей, которое и есть наибольшим общим делителем этих чисел.
второй пункт не получается реализовать. Делаю с двумя листами

Твой вариант пробовал до этого, показалось скучно или что-то не получилось…

Нашел ошибку, теперь точно правильно выводит, но не проходит тестирование на сервере
package com.javarush.test.level14.lesson08.bonus02;

/* НОД
Наибольший общий делитель (НОД).
Ввести с клавиатуры 2 целых положительных числа.
Вывести в консоль наибольший общий делитель.
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Solution
{
    static int NOD = 1;
    static ArrayList<Integer> list1 = new ArrayList<Integer>();
    static ArrayList<Integer> list2 = new ArrayList<Integer>();

    public static void main(String[] args) throws Exception
    {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String a = reader.readLine();
        String b = reader.readLine();
        getPrimeFactor(a, list1);
        getPrimeFactor(b, list2);

        for (Integer x : resList(list1, list2))
            NOD *= x;
        System.out.println(NOD);
        }

    public static int initList(ArrayList<Integer> list, String a){

        if (divisionBy2(a) != -1){
            list.add(2);
            return divisionBy2(a);
        }
        else if (divisionBy3(a) != -1){
            list.add(3);
            return divisionBy3(a);
        }
        else if (divisionBy5(a) != -1){
            list.add(5);
            return divisionBy5(a);
        }
        else if (divisionBy6(a) != -1){
            list.add(2);
            return divisionBy6(a);
        }
        else if (divisionBy9(a) != -1){
            list.add(9);
            return divisionBy9(a);
        }
        else list.add(SimpleDigit(a));
            return SimpleDigit(a);

    }
    public static void getPrimeFactor(String a, ArrayList<Integer> list){
        int buf = initList(list, a);
        while (buf != 1){
            buf = initList(list, Integer.toString(buf));
        }
    }
    static int divisionBy2(String a){
        int c = Integer.parseInt(a.substring(a.length() - 1, a.length()));
        if (c == 0 || c == 2 || c == 4 || c == 6 || c == 8)
            return Integer.parseInt(a) / 2;
        return -1;
    }
    static int divisionBy3(String a){
        int buf = 0;
        for (int i = a.length(); i > 0; i--)
            buf += Integer.parseInt(a.substring(i - 1, i));
        if (buf % 3 == 0)
            return Integer.parseInt(a) / 3;
        return -1;
    }
    static int divisionBy6(String a){
        int b = Integer.parseInt(a);
        if (b % 2 == 0 && b % 3 == 0)
            return b / 2;
        return -1;
    }
    static int divisionBy5(String a){
        if (Integer.parseInt(a.substring(a.length() - 1, a.length())) == 0 ||
                Integer.parseInt(a.substring(a.length() - 1, a.length())) == 5)
            return Integer.parseInt(a) / 5;
        return -1;
    }
    static int divisionBy9(String a){
        int buf = 0;
        for (int i = a.length(); i > 0; i--)
            buf += Integer.parseInt(a.substring(i - 1, i));
        if (buf % 9 == 0)
            return Integer.parseInt(a) / 9;
        return -1;
    }
    static int SimpleDigit(String a){
        return Integer.parseInt(a) / Integer.parseInt(a);
    }
    public static ArrayList<Integer> resList(ArrayList<Integer> list1, ArrayList<Integer> list2){
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (list1.size() > list2.size()){
            for (Iterator<Integer> i = list2.iterator(); i.hasNext(); ){
                Integer l2 = i.next();
                for (Iterator<Integer> j = list1.iterator(); j.hasNext(); ){
                    Integer l1 = j.next();
                    if (l2.equals(l1)){
                        result.add(l2);
                        break;
                    }
                }
            }
        }else if (list1.size() < list2.size()){
            for (Iterator<Integer> i = list1.iterator(); i.hasNext(); ){
                Integer l1 = i.next();
                for (Iterator<Integer> j = list2.iterator(); j.hasNext(); ){
                    Integer l2 = j.next();
                    if (l1.equals(l2)){
                        result.add(l1);
                        break;
                    }
                }
            }
        }else if (list1.size() == list2.size()){
            for (Iterator<Integer> i = list1.iterator(); i.hasNext(); ){
                Integer l1 = i.next();
                for (Iterator<Integer> j = list2.iterator(); j.hasNext(); ){
                    Integer l2 = j.next();
                    if (l1.equals(l2)){
                        result.add(l1);
                        i.remove();
                        j.remove();
                        break;
                    }
                }
            }
        }
        return result;
    }
}
Anton_n
Ну если уж делать не по нормальному алгоритму (как bfg предложил), то проще пройтись циклом от 2 до меньшего из обоих чисел и в процессе найти максимум среди всех, на которые делятся оба числа. Пусть не 3, но хоть 5 строчек, а не 50 :)
Anton_n
А, собственно это bfg и предложил, попутал я :)

На самом деле есть стандартный быстрый алгоритм нахождения НОД — погуглите.
deft
по моему если ты введешь числа 13 и 17 у тебя работать прога не будет
wmmix
  • wmmix
  • 0
  • Комментарий отредактирован 2014-06-02 12:49:03 пользователем wmmix
Бинарный алгоритм вычисления НОД — очень быстро работает и легко реализуется. ИМХО, к тому же всегда полезно повторить работу с рекурсией.
Svejk
Блин, тоже решал по «школьному» алгоритму как автор) чуть покрасивше правда но все равно)
package com.javarush.test.level14.lesson08.bonus02;

/* НОД
Наибольший общий делитель (НОД).
Ввести с клавиатуры 2 целых положительных числа.
Вывести в консоль наибольший общий делитель.
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num1 = Integer.parseInt(br.readLine());
        int num2 = Integer.parseInt(br.readLine());
        System.out.println(getGcd(num1, num2));
    }
    public static ArrayList<Integer> getPrimes(int num) {
        int[] simpleNumbers = new int[] {2, 3, 5, 7, 11, 13, 17, 19};
        ArrayList<Integer> primes = new ArrayList<Integer>();
        while (num != 1) {
            for (int i = 0; i < simpleNumbers.length;) {
                if (num % simpleNumbers[i] == 0) {
                    num = num / simpleNumbers[i];
                    primes.add(simpleNumbers[i]);
                    i = 0;
                }
                else i++;
            }
        }
        return primes;
    }
    public static ArrayList<Integer> getCommonPrimes(ArrayList<Integer> list1, ArrayList<Integer> list2) {
        ArrayList<Integer> commonPrimes = new ArrayList<Integer>();
        for (Integer num1p : list1) {
            if (list2.indexOf(num1p) != -1) commonPrimes.add(num1p);
        }
        return commonPrimes;
    }
    public static int getArrayListElementsProduct(ArrayList<Integer> list) {
        int product = 1;
        for (Integer  num : list) {
            product = product * num;
        }
        return product;
    }
    public static int getGcd(int num1, int num2) {
        ArrayList<Integer> num1Primes = getPrimes(num1);
        ArrayList<Integer> num2Primes = getPrimes(num2);
        ArrayList<Integer> commonPrimes = getCommonPrimes(num1Primes, num2Primes);
        if (commonPrimes.isEmpty()) return 1;
        return getArrayListElementsProduct(commonPrimes);
    }
}


а по способу который подсказал bfg получилось 8 строк в main)
RomanZaglodin
  • RomanZaglodin
  • 0
  • Комментарий отредактирован 2014-07-15 23:51:08 пользователем RomanZaglodin
Не пойму, почему сервер не принимает программу? Работает отлично! Или надо ещё добавить проверку, что пользователь и правда вводит положительные целые числа (а не дробные или отрицательные)??

package com.javarush.test.level14.lesson08.bonus02;

/* НОД
Наибольший общий делитель (НОД).
Ввести с клавиатуры 2 целых положительных числа.
Вывести в консоль наибольший общий делитель.
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        System.out.print("Введите первое целое положительное число: ");
        int a = Integer.parseInt(reader.readLine());
        System.out.print("Введите второе целое положительное число: ");
        int b = Integer.parseInt(reader.readLine());

        System.out.print("Наибольший общий делитель: " + commonDivider(a, b));
    }

    private static int commonDivider (int a, int b)
    {
        int commonDivider = 1;

        for (int i = 1; i < (a < b ? a : b); i++)
        {
            if ( (a % i == 0) && (b % i == 0) )
                commonDivider = i;
        }
        return commonDivider;
    }
}
Sant9Iga
попробуй убрать принтлны текста, оставь только вывод НОДа
mrserfr
Просто вспомните это, тогда решается очень просто:
Наибольший общий делитель (НОД) двух данных чисел a и b — это наибольшее число, на которое оба числа a и b делятся без остатка.
EmperioAf
  • EmperioAf
  • 0
  • Комментарий отредактирован 2014-11-08 12:41:09 пользователем EmperioAf
Лол, а я 40 минут пытался найти Наибольшее Общее Частное двух чисел и неудомевал почему сервер не принимает. Спасибо за напоминание теории о НОД
Bestlis
public static void main(String[] args) throws Exception
{
BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

Integer n1 = Integer.parseInt(rd.readLine());
Integer n2 = Integer.parseInt(rd.readLine());

int min = 0;
min = (n1 > n2)? n2: n1;

int delitel = 1;

for (int i = 1; i <= min; i++)
{
if(n1 % i == 0 && n2 % i == 0)
{
delitel = i;
}
}

System.out.println(delitel);
}

И всё решение! Нафига огород городить!
isaenkovl
Ваше решение выдает 1 для 0 и для отрицательных чисел.
Можно еще сделать рекурсивно. Это 9 строчек в методе о всеми проверками…
Ну решение автора — это жесть. Извините конечно, но так нельзя над мозгом издеватся…
elimental
Условие: Ввести с клавиатуры 2 целых положительных числа.
stivo32
Странно конечно. Вернулся в изучению джавы после перерыва. Сначала сделал задачку через алгоритм Эвклида. Потом через (a % i == 0) && (b % i == 0). Все варианты считают правильно. Но задача не компилируется на сервере.
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int one = Integer.parseInt(reader.readLine());
        int two = Integer.parseInt(reader.readLine());
        System.out.print(nod(one, two));
    }

    private static int nod (int one, int two)
    {
        int nod = 1;

        for (int i = 1; i < (one < two ? one : two); i++)
        {
            if ( (one % i == 0) && (two % i == 0) )
                nod = i;
        }
        return nod;
    }
}
isaenkovl
А лучше сразу погуглить что такое Наибольший общий делитель)))
У Вас абсолютно неправильно считает. ошибка тут
i < (one < two ? one : two)
elimental
  • elimental
  • 0
  • Комментарий отредактирован 2014-11-19 18:47:31 пользователем elimental
Можно погуглить алгоритм Евклида.
eugentius
Зашел посмотреть как другие решили задачу ради интереса.
Код топикстартера поразил меня)
Задача решается алгоритмом Евклида за пару минут через while.
arthasfp
public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int first = Integer.parseInt(reader.readLine());
        int counter1 = 0;

            while (first > 0 && first%2 == 0)
            {

                first = first/2;
//            System.out.println(first);
                counter1++;
//            System.out.println(counter1);
            }

        int second = Integer.parseInt(reader.readLine());
        int counter2 = 0;

            while (second > 0 && second%2 == 0)
            {
                second = second/2;
//            System.out.println(second);
                counter2++;
//            System.out.println(counter2);
            }


        if (counter1 > 0 && counter2 > 0 && counter2 > counter1)
        {
            int NOD = ((counter1 - counter2)*(-1))*2;
            System.out.println(NOD);
        }
        else if (counter1 > 0 && counter2 > 0 && counter1 > counter2)
        {
            int NOD = ((counter2 - counter1)*(-1))*2;
            System.out.println(NOD);
        }
        else if (counter1 == 1 && counter2 == 1)
        {
            int NOD = 1;
            System.out.println(NOD);
        }


    }

}

Написал такой вариант. Проверил на 0 и минусовые. Но не засчитывает…
freeman_lex
Тоже зашел посмотреть, как другие решают… и сказать как решил я.
1. Определил не только меньшее, но и большее из двух чисел. Зачем? -->
2. Сразу проверяю деление большего на меньшее без остатка. (если да --> вывод на экран).
3. Если нет --> в цикле от меньшего/2 (делитель числа как мимимум в два раза меньше его) вниз нахожу первое число, удовлетворяющее известное условие --> вывод на екран.
Мне кажется, при таком алгоритме меньше вичислений и быстрее находится результат. Если нет, поправьте)
eger
Хотел плюсануть твой ответ, но мышка соскользнула, ссори((,
А я вот как решил, перед этим конечно проверив, какое из них большее:
for(int i = 0; i < b; i++)
{
if (a %(b — i) == 0 && b % (b — i) == 0)
{
delitel = b — i;
break;
}
freeman_lex
Во-первых, рабочий код выкладывать нельзя)
Во-вторых, і в диапазоне от 1 до b/2 это лишние вичисления — там ответа точно нет.
eger
Согласен, но я проверяю не деление на i, а деление на (b — i), таким образом при первом проходе цикла, вычисляется, является ли b делителем для а, и если это так, цикл завершается.
lisoed
Шаг 2 можно пропустить, если в 3-м шаге в цикле (i от 1 до наименьшего) «меньшее»/i. Только нужно проверку поставить («меньшее» % i == 0).
А так ты во втором шаге тоже самое делаешь, только ручками.
freeman_lex
Извините, но я не согласен)
В данном случае, идти «снизу» вообще не эффективно. Нам же нужно найти найбольшее… Значит быстрее идти сверху к решению.
lisoed
а мы и идем сверху. допустим числа 10 и 6.
первая итерация цикла 6/1 = 6
вторая итерация 6/2 = 3
третья 6/3 = 2
freeman_lex
Мы идем снизу — делим сначала на 1,..2,..3. А там решения точно не будет. Для еефктивного поиска решения делитель должен быть в цикле от меньшее/2 вниз.
lisoed
Извиняюсь, не расписал точнее, в цикле мы получаем именно делить, а уже потом его проверяем. Т.е. для моего примера
итерация 1: 6/1 = 6 => 10 % 6
итерация 2: 6/2 = 3 => 10 % 3
итерация 3: 6/3 = 2 => 10 % 2 — наш ответ. Решение за 3 итерации.
freeman_lex
  • freeman_lex
  • 0
  • Комментарий отредактирован 2015-02-06 12:25:23 пользователем freeman_lex
Прошу прощения, теперь я наконец-то начал понимать, что Вы хотели мне сказать)
profeg
я поражен решением предложенным автором. не делай так никогда пожалуйста, не увеличивай энтропию =))
2 строчки в рекурсивном варианте
eniqen
автор жжет!
while (b != 0)
            b = a % (a = b);
        return a;
вот и все
playua
*******************Алгоритм Евкліда*******************
public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int a,b;
        a = Integer.parseInt(reader.readLine());
        b = Integer.parseInt(reader.readLine());
        System.out.println(NOD(a, b));
    }

    public static int NOD(int a, int b)
    {
        int nod;
        while (true)
        {
            if ( a < b)
            {
                b = b - a;
                if (b == 0)
                {
                    nod = a;
                    break;
                }
            }
            else if (a > b)
            {
                a = a -b;
                if (a == 0)
                {
                    nod = b;
                    break;
                }
            }
        }
        return nod;
    }
}


що я пропустив? не хоче зупинятись програма після вводу двох чисел…
playua
Завтикав з умовами а > b та a < b, треба a >= b та a <= b.
ziby
а я прям по школьной математике… создал три списка, в первый внес делители одного числа, во второй — другого. в третий записал повторяющиеся числа из первых двух и вывел на консоль максимальное.

работу сервер принял, но что-то мне подсказывает, что решение чересчур трудозатратное.
Oberon
тоже сделал по алгоритму Эвклида, 10 строчек вышло со всеми проверками.
а автор топика конечно удивил,)) у меня бы терпения не хватило,
mirnyy1984
Мля!!! увидев предложенное решение bfg — решил пойти застрелиться))) Элементарщина! А я на множители раскладывал вводимые числа ну и т.д.… Народ, когда Вы видите решение той или иной задачи намного проще и короче чем свой вариант, не возникают ли мысли в голове, что как-то «хреновый» программист в итоге может получиться! ну или вообще не получиться))))
ps: тоже нарешал большой код… но проверку прошел с первого раза!
Naissur
А не дано было погуглить алгоритмы нахождения НОД и реализовать оный в три строчки вместо 100500?
Lexw
странно… в соседней ветке вы против поиска решений на других сайтах…
Naissur
Когда вы укажете мне, где именно я говорил, что нельзя искать информацию на других сайтах, я прислушаюсь.
Menelkir
  • Menelkir
  • 0
  • Комментарий отредактирован 2015-05-02 03:03:50 пользователем Menelkir
Друзья, я где-то туплю, но не понимаю где =/
Вариант 1:
<code>import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        int a, b, next;
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        a = Integer.parseInt(reader.readLine());
        b = Integer.parseInt(reader.readLine());

        if (b > a)
        {
            int temp = a;
            a = b;
            b = temp;
        }

        next = 1;
        while (next != 0)
        {
            next = a%b;
            a = b;
            b = next;
        }
        System.out.println(a);
    }</code>
Варианты 2 и 3 — через функцию:
<code>import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        int a, b, next;
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        a = Integer.parseInt(reader.readLine());
        b = Integer.parseInt(reader.readLine());

        if (b > a)
        {
            int temp = a;
            a = b;
            b = temp;
        }

      mcd(a, b);
}</code>
Итеративная mcd
<code>public static void mcd(int c, int d)
    {
        int next = 1;
        while (next != 0)
        {
            next = c%d;
            c = d;
            d = next;
        }
        System.out.println( с );
    }</code>
и рекурсивная
<code>public static void mcd(int c, int d)
    {

        int next = c%d;
        if (next != 0) mcd(d, next);

        if (next == 0) System.out.println(d);
    } </code>
При любом варианте в ide все работает и правильно, а на сервере не компилируется.
Menelkir
Немного обработал напильником.
В main добавил
System.out.println(mcd(a, b));

А варианты функции поменял на
public static int mcd(int c, int d)
    {
        while (d != 0)
        {
            int next = c%d;
            c = d;
            d = next;
        }
        return c;
    }

и
public static int mcd(int c, int d)
    {
        if (d == 0) return c;
        int next = c%d;
        return mcd(d, next);
    }


Но результат тот же самый.
durahok
  • durahok
  • 0
  • Комментарий отредактирован 2015-06-11 12:37:50 пользователем durahok
<code>
public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
       int  a = Integer.parseInt(reader.readLine());
       int b = Integer.parseInt(reader.readLine());
        while (true){
            if (a==b){
                System.out.println("НОД = "+a);
                break;
            }else
                if (a>b){
                    a=a-b;
                }
            else b=b-a;
        }
    }
}
</code>
Почему не проходит хотя находит все правильно
virtual2014
Могу добавить от себя, для решения задания использовал стандартный рекурсивный алгорим Эвклида:

public static int gcd (int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

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

В итоге для того чтобы сервер принял решение достаточно считать с клавиатуры 2 числа, проверить чтобы числа были положительные, выполнить процедуру поиска НОД и выдать результат в консоль.
Lansky
  • Lansky
  • 0
  • Комментарий отредактирован 2015-09-06 22:21:38 пользователем Lansky
решал через рекурсию
velobaduk
Решил только что через алгоритм Эвклида, который нагуглил в википедии. Реализация алгоритма занимает 6 строчек.
Taras88
Не нужно придумывать велосипед к этой задачи. Учитесь гуглить. Все уже давно написано и отрефакторино давно за вас
Donshinigami
С алгоритмом Евклида вообще все просто получается) не нужно заморачиваться) через один while(...) все делается)
alexpusher1
Если кому интересно
package com.javarush.test.level14.lesson08.bonus02;

/* НОД
Наибольший общий делитель (НОД).
Ввести с клавиатуры 2 целых положительных числа.
Вывести в консоль наибольший общий делитель.
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int a = Integer.parseInt(reader.readLine());
        int b = Integer.parseInt(reader.readLine());
        List<Integer> y = new ArrayList<Integer>(a);
        List<Integer> u = new ArrayList<Integer>(b);
        int qw =0;
        for(int s=1;s<=a;s++)
        {
            if((a % s)==0)
            {
                y.add(s);
            }
        }
        for(int f=1;f<=b;f++)
        {
            if((b % f)==0)
            {
                u.add(f);
            }
        }
        for(Integer aa : y)
        {
            for(Integer bb : u)
            {
                if(aa.equals(bb))
                {
                    qw = aa;
                }
            }
        }
        System.out.println(qw);

    }
}
SonicBIast
100% не нужны никакие листы! Никогда не пиши такие коды, а то на роботу не возьмут!
Используй логические операторы (не знаешь что это !? ОБЯЗАТЕЛЬНО ГУГЛИШЬ и УЧИШЬ !!!)
— в цикле считываешь два числа, потом проверка если они оба >= 1 break;
— создаешь NOD = 1;
— цикл for(количество итераций от 1 до <= от большего из двух чисел)
— внутри цикла for условие, если оба числа деляться по модулю на i, дальше подумай!!!
Удачи!
alexpusher1
а что плохого, что я использовал листы?
SonicBIast
во первых все можно сделать без них! когда ты начинаешь что то создавать (переменные, массивы, или коллекциии, или обьекты классов — не важно) ты тратишь ресурсы — память. на выделение памяти, операции, и освобождение памяти. Старайся писать более компактно и понятно. Не надо выдумывать велосипед, он уже придуман.
alexpusher1
вообщем вы правы, но мне было интересно реализовать это самому, без лишнего гугла.
а кроме как засунуть это в лист, перетряхнуть его и забрать результат, я ничего больше не придумал.
будем учиться дальше!!!
Спасибо :)
SonicBIast
  • SonicBIast
  • 0
  • Комментарий отредактирован 2015-12-21 19:36:20 пользователем SonicBIast
Я тебя понимаю, НО гугл это не лишняя веСЧь! Гугл очень полезен, так что ты почаще туда заглядывай! :) Все что тебе не понятно, просто ищи в инете и читай-читай!!!
Archie369
Решил задачу таким способом:
while(a != 0 && b != 0){
if (a > b)
a = a % b;
else
b = b % a;
nod = (a + b);
}

— В ветке увидел, что есть решение по такому же методу, но записанное несколько иначе:
while (b != 0)
b = a % (a = b);

— Вот не могу понять, как оно работает? Объясните пожалуйста «на пальцах», если не сложно!
Alejandro_Kolio
Друзья, может кому будет полезно. Я создал метод и через «sout» вывел его на консоль.
public static int gcd(int a, int b)
    {
        if(b == 0) return a;
        int x = a % b;
        return gcd(b, x);
    }

Почитайте про алгоритм Евклида. Полезная статья http://habrahabr.ru/sandbox/60131/
arrbitr
  • arrbitr
  • 0
  • Комментарий отредактирован 2016-01-19 17:22:47 пользователем arrbitr
вы совсем поехали тут, какие алгоритмы ?? решение 4 строчки))две остальные додумайте сами:
BigInteger literal2=scanner.nextBigInteger();
      System.out.println(literal1.gcd(literal2));
Ibeskov
Коню понятно, что через рекурсию решать проще, лучше и быстрее, но, если я не путаю, то рекурсия рассматривается на 34 занятии.
SonicBIast
  • SonicBIast
  • 0
  • Комментарий отредактирован 2016-03-08 08:51:16 пользователем SonicBIast
Вообще там где можно решить через рекурсию, там можно решить и через цикл! Но рекурсия сложнее для понимания!
Вот мне кажется, что рекурсию лучше использовать когда или не знаешь количество итераций или количество итераций разное (и большое)! Тут же цикл до наибольшего из двух чисел и один if, в котором
два числа делятся нацело одновременно, ВСЕ!
Kraagesh
while (true)
{
    if (a > b)
        a = a - b;
    else
        b = b - a;
    ...

И так циклить пока b не станет 0. НОД будет равен a.
Самое простейшее решение. Да, можно, конечно, если очень хочется, решить математически (нахождением степеней всех простых множителей и тд) но зачем?
А перебирать ВСЕ числа до наименьшего… Как-то совсем уже ресурсоемко, мне кажется. Так гораздо меньше вычислений.
Zobnin
Эффективными способами вычисления НОД двух чисел являются алгоритм Евклида и бинарный алгоритм.
Я использовал алгоритм Евклида Алгоритм Евклида
ikrockus
  • ikrockus
  • 0
  • Комментарий отредактирован 2016-09-27 22:48:33 пользователем ikrockus
Проверенно. Работает.
<code>public class Solution
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int a;
        int b;

        try
        {
            a = Integer.parseInt(reader.readLine());
            b = Integer.parseInt(reader.readLine());
        }
        catch (Exception e)
        {
            return;
        }

        int min = Math.min(a,b);

        for (int q = min; q >= 1; q--)
        {
            double aa = (double) a/q;
            double bb = (double) b/q;

            if (aa == (double)((int) aa) && bb == (double)((int) bb))
            {
                System.out.print(q);
                break;
            }


        }
    }


}
</code>
Xoxol
for(int i = 1; i <= (x<y?x:y); i++)
{
if (x%i==0 && y%i==0 )
cheshenko
  • cheshenko
  • 0
  • Комментарий отредактирован 2018-02-25 12:23:27 пользователем cheshenko
<code>
<img src="http://info.javarush.ru/uploads/images/01/31/32/2018/02/25/af9922c5d8.jpg"  alt="" />public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String x = reader.readLine();
        String y = reader.readLine();
        int a = Integer.parseInt(x);
        int b = Integer.parseInt(y);
        int NOD = 0;
        while (true){
            if (a >= b) {
                a = a - b;
                if (b%a == 0) {
                    NOD = a;
                    break;}
            }
            else{
                b = b - a;
                if (a%b == 0){
                    NOD = b;
                    break;}
            }
        }
        System.out.println(NOD);

    }
}
</code>
Ругается, в чем ошибка понять не могу…
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.