Програмирование, простая задача на рекурсию

Question

Програмирование, простая задача на рекурсию

Кирилл жижов Ученик (87), открыт 2 недели назад

Вовочке надо построить забор из досок длиной в 17 метров. На каждый метр забора может быть прибито не более одной доски. Важным условием является то, что на первом и последнем метре забора обязано быть по доске. При этом Вовочка может не пропускать, пропускать ровно 2 или 5 метра подряд (но не более), то есть на этих метрах он не прибивает доски. Необходимо помочь Вовочке посчитать - сколькими способами он сможет построить забор. Можно считать, что у него в распоряжении есть любое необходимое количество досок.

Answer 1

Вот вовочке делать нечего, я бы ему ремня всыпал

Answer 2

 #include<bits/stdc++.h> 
using namespace std; 
long long dp[20]; 
bool computed_arr[20]; 
long long f(int pos){ 
    if(pos ==16) return 1; 
    if(pos >16) return 0; 
    if(computed_arr[pos]) return dp[pos]; 
    computed_arr[pos]=true; 
    dp[pos]=f(pos+1)+f(pos+3)+f(pos+6); 
    return dp[pos]; 
} 
int main(){ 
    memset(computed_arr, 0, sizeof(computed_arr)); 
    cout<<f(0); 
}

Answer 3

Здесь нет задачи на рекурсию. Это задача на динамическое программирование.

 #include <iostream>
#include <map>

using namespace std;

int main() {
  map<int, int> t;
  t[1] = 1;
  for (int i = 2; i <= 17; ++i) { t[i] = t[i - 1] + t[i - 3] + t[i - 6]; }
  cout << t[17];
}