Научно-образовательный IT-форум при КНИТУ-КАИ

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.



[+] C++ Рекурсия и Стеки

Сообщений 1 страница 5 из 5

1

Народ, аврал, не могу написать 2 программки...
1) Для одномерного массива рекурсивно вызвать функцию отдельно для первой трети массива и для остальной части массива и сотворить с ними математическую операцию типа суммы элементов: X3=x1*x1+x1*x1+x2*x2+x3*x3

2) Изменить исходный стек, удалив повторяющиеся несколько раз подряд элементы, и вычислить сумму оставшихся. (Изменять, перекладывая в дополнительный, затем вернуть обратно).

Прижало до завтрашнего 8:00... Хочу разобраться и понять, но не могу написать согласно требованиям, ибо в первой нет рекурсии, только цикл, а со второй даже нормально стек вызвать не получается.  HELP!!!

2

2.
Pseudocode
S-stack;
A = S[N-1]; //store the last element
B = 0;
call f(S[0..N-2],A,B) //call the function with 0..N-2 stack elements 

function f(S, A, B){
   if(S is empty) return B; //return the value in accumulator, guard.
   
   if(S[-1] == A) //if the last element in the stack equals to the value, stored in A.
         { f(S[0..N-2], S[N-1], B)}
       else
         {f(S[0..N-2], S[N-1], B+S[-1])}
}

Отредактировано ar (2013-10-03 00:10:05)

3

Низкий поклон. :)

4

Harry NightMare написал(а):

ибо в первой нет рекурсии, только цикл

Все, что может быть записано в виде цикла, может быть тоже представлено в рекурсивной форме. Единственная разница, это, то, что программы в форме записи в виде цикла имеют состояние. В любой момент можно остановить программу и получить промежуточный результат. В рекурсивной форме, из программы не может быть прочитан промежуточный результат (он просто еще не известен). Это называется referential transparency. Это свойство рекурсивной формы является наиважнейшим в функциональном программировании и позволяет избежать многих проблем, связанных с конкурренцией.
Вообще, любая вычислимая функция рекурсивна.
Для построения рекурсивной формы надо подумать о двух вещах:
1. Условие остановки алгоритма
2. Каждый последующий вызов функции должен приближать эту остановку.
В нашем случае 1. это пустой стек. 2. каждый вызов функции вызывается с меньшим стеком.

5

landwatersun написал(а):

Низкий поклон. :)

Спасибо)