Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Рекурсия

Автор: sashkr 5.6.2008, 22:00

помогите пожалуйста с задачей на рекурсию

дан одномерный массив int и число int надо написать функцию boolean которая получает число(к массиву можно обращаться напрямую в классе) и возвращает true если в массиве есть числа сумма которых равна полученному числу,false если нет.

Автор: Platon 5.6.2008, 22:33

Можно попробовать бектрейс

Код


boolean[] visited;
int[] arr;
boolean sumExists(int need, int cur) {
    if (need == cur) return true;
    for (int i = 0; i < arr.length; i++) if (!visited[i]) {
        visited[i] = true;
        if (solve(i, cur + arr[i]))
            return true;
        visited[i] = false;
    }
    return false;
}

запускать надо sumExists(N, 0);

Автор: sashkr 5.6.2008, 22:37

спасибо,забыл написать что функция не может пользоваться циклами вообще

Добавлено @ 22:40
я что-то написал,но не совсем работает..

Код



public boolean cover(int amount)
    {
    
        return cover(0,amount);

    }
    
    private boolean cover(int i, int amount)
    {
        if(amount==0)
            return true;
            
        if(i==_arr.length-1)
            if((amount-_arr[i])==0) return true;
                else return false;
                
        if((amount-_arr[i])<0)
        {
            i++;
            return cover(i,amount);
        }
 
        if(cover(i+1,amount-_arr[i]))
        return true;
        else{i++;
            return cover(i,amount);
        }

Автор: Platon 5.6.2008, 23:07

Цитата(sashkr @ 5.6.2008, 23:37

)

я что-то написал,но не совсем работает..

Ага, и я что-то сказал, но не совсем объяснил.

Код


boolean cover(int[] arr, int i, int am) {
    if (am == 0) return true;
    if (am < 0) return false;
    if (i >= arr.length) return false;
    return cover(i + 1, am - arr[i]) || cover(i + 1, am);
}

Вспомнил старый добрый курс Lisp'а cover(new int[]{1,2,3}, 0, 4)

Добавлено через 5 минут и 10 секунд
Помню, на таких задачках денюшки только так рубил. Боятся люди рекурсии, непонятно почему?

Автор: sashkr 5.6.2008, 23:28

в массиве {5,22,13,5,7,-4} проблема с 31(22+13-4)..

с нулём можешь подсказать что делать,я вот тоже написал,вроде работает-правда не совсем понимаю как smile

)
но с нулём тоже проблема...

Код



public boolean cover(int amount)                     //функ для пользовотеля
    {
    
        return cover(_arr.length-1,amount);

    }
    
    private boolean cover(int i, int amount)
    {
        if(amount==0)
            return true;
            
        if(i<=0)
            if((amount-_arr[i])==0) return true;
                else return false;
                
        if((amount-_arr[i])<0)
        {
            i--;
            return cover(i,amount);
        }
        
        if(cover(i-1,amount-_arr[i]))
        return true;
        else{i--;
            return cover(i,amount);
        }
        
    }

Добавлено @ 23:28
кстати спасибо огромное за внимание и помощь!!!!!

Автор: Platon 6.6.2008, 04:15

Окэй, тогда в моей схеме убери ветку на проверку меньше нуля:

Код


boolean cover(int[] arr, int i, int am) {
    if (am == 0) return true;
    if (i >= arr.length) return false;
    return cover(arr, i + 1, am - arr[i]) || cover(arr, i + 1, am);
}

Добавлено @ 04:22

Цитата(sashkr @ 6.6.2008, 00:28

)

я вот тоже написал

Батенька, у вас черт ногу сломит. Очень "хитро накосячено", тяжко для понимания. Скорее всего твой преподаватель попутал курсы, обычно обучение мастерству рекурсий обучают на лиспе, но скорее всего он ждет от тебя моего решения. Моё решение, как раз стилизованно под лисповский подход, так что примите к сведению.

Автор: sashkr 6.6.2008, 16:41

Преогромное спасибо, smile

Автор: Platon 6.6.2008, 17:13

Помогли тебе, помоги другим!

Автор: Gaon 7.6.2008, 03:42

вы бы не могли объяснить как действует эта рекурсия?

Автор: Platon 7.6.2008, 09:07

Gaon, давайте я оставлю это на самостоятельное изучение. Уж в 3-х строчках кода разобраться, ну совсем, несложно.

Добавлено через 41 секунду
Сдается мне вы ребята с 1 учебного заведения?

Автор: Gaon 7.6.2008, 13:29

похоже что  с одного.

как я понял
  cover(arr, i + 1, am - arr[i]) вычитает из суммы числа с массива, а вот что дает
cover(arr, i + 1, am)  и как они относятся один к другому......

будем грызть дальше   smile

Автор: Platon 7.6.2008, 13:55

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

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

Автор: Gaon 7.6.2008, 18:57

допустим есть сумма 23 , и числа 2,13, 10.

из сумми вичитаетса 2, если остаток менше 23 и больше 0 вичитается 2 число и тд. до конца.

если остаток не поподает в этот промежуток, прыгаем на 2 число и тд.

Автор: Platon 7.6.2008, 19:34

хм, интересно а такая последовательность у тебя не пройдет: 23, {2, -13, 36} а по условию сказано, что в последовательности может быть отрицательное число, думай дальше.

Автор: Gaon 7.6.2008, 19:54

23,{2,-13,36}

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

помоему ты так и сделал