Ваша задача похожа на fibonnaci :) Сначала я объясню вам ФИБОНАЧЧИ.
Р (1) = 1
Р (2) = 1
F (N) = F (N - 1) + F (N - 2), для каждого N> 2
Первые несколько числа Фибоначчи:
Р (1) = 1
F (2) = 1
F (3) = Р (2) + F (1) = 2
Р (4) = F (3) + F (2) = 3
F (5) = F (4) + F (3) = 5
...
Вы можете увидеть больше на: http://en.wikipedia.org/wiki/Fibonacci_number
Последовательность Фибоначчи чисел Фибоначчи определяется отношением рекуррентности. Последовательность Фибоначчи является рекурсивной последовательностью.
Каждый рекурсии должен иметь:
1) базовый вариант (ы)
2) рекуррентное соотношение
В случае Фибоначчи, базовые случаи: Р (1), который равен и F (2) который также равен . Отношение повторения - это отношение, которое «связывает» меньшие экземпляры одной и той же проблемы. В случае чисел Фибоначчи, если вы хотите знать F (N), вы должны знать F (N - 1) и F (N - 2), для всех N> 2, и это так. В случае Фибоначчи отношение повторения составляет F (N) = F (N - 1) + F (N - 2).
Вот код:
#include <cstdio>
#include <cstdlib>
using namespace std;
int f(int n) {
//printf("n = %d\n", n);
if(n == 1 || n == 2) // base case
return 1;
return f(n - 1) + f(n - 2); // recurrence relation
}
int main() {
int n; scanf("%d", &n);
printf("%d\n", f(n));
return 0;
}
Если удалить Printf, который комментировал вы увидите, что многие значения Фибоначчи вычисляются снова и снова, и, что очень неэффективно.Попробуйте запустить этот код для F (45), и вы увидите, почему он очень неэффективен.
Здесь динамическое программирование приходит. Как вы можете видеть, многие значения фибоначчи вычисляются снова и снова, и мы можем использовать memoization для сохранения их в таблице, и если они нам нужны, мы можем просто вернуть их из таблицы. Вот код:
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 50;
long long memo[N];
long long f(int n) {
if(memo[n] != -1) // if we already computed the value of f(N), then return that value
return memo[n];
return memo[n] = f(n - 1) + f(n - 2); // else compute the value, and save it into the table
}
int main() {
memset(memo, -1, sizeof(memo));
memo[1] = memo[2] = 1; // add answer for base case to the table
int n; scanf("%d", &n);
printf("%lld\n", f(n));
return 0;
}
И finnaly, ваш вопрос.
Как Фибоначчи, вы можете сохранить вычисленное значение h (N). Вот код:
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int N = 25;
int check, memo[N];
int f(int x) {
if(memo[x] != check) // if f(n) was already computed
return memo[x]; // return computed value
return memo[x] = f(x - 2) - f(x - 1) + 2; // else compte given value and add it to a table
}
int main() {
memset(memo, 63, sizeof(memo)); // very big number, if the value of h(n) is different then that very big number, then we know we have computed the value for h(n)
check = memo[0];
memo[1] = 2; // base case
memo[2] = 3; // base case
int n; scanf("%d", &n);
printf("%d\n", f(n));
return 0;
}
Это просто вариация на числах Фибоначчи, вы можете сделать это так же, как – harold