Рекурсивное добавление последовательности чисел

ProgramBox

Рекурсивное добавление последовательности чисел

Post author:admin
Запись опубликована:30 апреля, 2023
Post category:Вопросы по программированию

#c #algorithm #recursion #sequence #add

#c #алгоритм #рекурсия #последовательность #Добавить

Вопрос:

Привет, я пытаюсь освежить свой разум небольшой рекурсией. Я хочу добавить все числа от ‘start’ до ‘end’ включительно.

Т.е. если начало было 1, а конец был 5. Тогда ответ был бы 1 2 3 4 5 = 15

Пока у меня есть это

 int calc(int start, int end){
    if(start > end)
        return total;
    else{
        total = total   start;  
    return sum1(start  , end);
    }
}

Это не работает (я получаю ошибку seg). Что я делаю не так?

РЕДАКТИРОВАТЬ: Извините, я использую те же переменные в своем реальном коде, когда я писал это, я в конечном итоге ссылался на них как на начало / конец и забыл изменить весь код.

Ответ №1:

Что такое from и to переменные внутри вашей функции? Может быть, вы используете некоторые глобальные переменные вместо использования start и end , и именно поэтому у вас проблема? Также почему вы используете sum1 внутри calc функции вместо calc ?

Попробуйте это вместо:

 int calc(int start, int end){
    if(start > end)
        return 0;
    else
        return start   calc(start   1, end);
}

1. Спасибо 🙂 Ваш первый ответ, в котором есть (start ,end), вызвал ошибку сегментации, но start 1 сработал. почему это?

2. это должно было быть start. pre-increment, а не post-increment. start никогда не увеличивает значение, переданное в рекурсивную функцию, и приводит к бесконечному циклу. Отсюда ошибка сегментации.

3. @Splendor, @Sean Arnold, start не вызовет segfault, но это может привести к неверным результатам, поскольку компилятор волен оценивать start до или после start ранее в инструкции. Как правило, не следует одновременно изменять и использовать переменную в выражении.

4. @ikegami, запуск (после увеличения) вызовет ИСКЛЮЧЕНИЕ ПЕРЕПОЛНЕНИЯ СТЕКА. Я пробовал на своей машине. Переданное значение никогда не увеличивается и остается неизменным. Это приводит к бесконечным рекурсивным вызовам. Вы можете запустить с помощью start и проверить.

5. @Splendor, я знаю. Я никогда не говорил, start что это правильно. Я сказал, start что это неправильно. Вы сказали, start что это неправильно. Оба верны.

Ответ №2:

Для начала, вы не используете параметры своей функции (start, end), вместо этого вы используете (from, to). Я предполагаю, что from и to являются либо глобальными переменными, либо ваш код не будет компилироваться. Кроме того, где объявлено total?

Это должно работать лучше:

 int calc(int start, int end){
    if(start > end)
        return 0;
    else{
        return start   calc(start 1, end);
    }
}

1. Я думаю, вам нужно start в вашем рекурсивном вызове.

2. Должно быть start 1 , на самом деле. start неверно, потому что это могло быть оценено до start ранее в инструкции.

3. О, вы, ребята, правы, я подумал, что это выглядело забавно, я должен был это изменить.

Ответ №3:

Кстати, вот более эффективное решение:

 int calc(int from, int to)
{
    if (from == 0)
        return to * (to 1) / 2;
    else
        return calc(0, to) - calc(0, from);
}

Это даже рекурсивно! Ну, пока вы не упростите это еще больше до

 int calc(int from, int to)
{
    return ( to * (to 1) - from * (from 1) ) / 2;
}

Это потому, что f (n) = n … 3 2 1 = n (n 1)/2

1. Я думаю, что лучшее решение для этой проблемы предложено ikegami. Иногда вам не нужно принимать проблемы такими, какие они есть, и думать о разных способах вычисления одного и того же. То, что показал икегами, является простой реализацией алгоритма суммирования ряда до определенного числа. Это также работает довольно эффективно.

Ответ №4:

Это отлично работает для.

 int calc(int from, int to)
{
    if (from >= to) return to;
    return from   calc(from   1, to); 
}

1. from неверно, потому что оно могло быть вычислено до from ранее в инструкции. Так и должно быть from 1 .

2. это не из , а from. (предварительное увеличение)

3. то же самое относится к from . from неверно, потому что оно могло быть вычислено до или после from ранее в инструкции. Как правило, не следует одновременно изменять и использовать переменную в выражении.

4. @ikegami, я согласен 1 за ваши комментарии. Я исправил свой код. Спасибо.