Climbing the stairs, the hare jumps either to the next step, or one, or two. In how many ways can he climb the step with the number K?

Everything seems to be clear ...

#include <iostream> using namespace std; int vr(int n) { if (n<3) return n; else if (n==3) return 4; else return vr(n-1)+vr(n-2)+vr(n-3); } int main() { int n; cin >> n; cout << vr(n); return 0; }

But when the program did not pass the time test on 32 steps, it finally reached me that such an algorithm generates an unmeasured number of repeated calculations, thereby wasting precious resources. I ask wise heads to suggest a true idea, how to reduce the amount of calculations beyond the clouds to the optimal number.

  • one
    The simplest option: Create an array of length n and cycle through it. A better option: since we use only the last 3 elements, it is enough to create an array of all three elements and walk through it several times. - HolyBlackCat
  • @HolyBlackCat Array with solutions for n = 1,2,3,4? - Max
  • one
    So where did the reference to recursion come from? This requirement of the problem condition is to solve it by recursion? - AnT
  • 3
    Please do not specify in the title of the question of PL. It is indicated in the tags - cpp questions

4 answers 4

Well, to begin with, if you want to limit yourself to int 's, then in principle you can leave the recursion as it is :) - anyway, the last value that fits in the int is obtained for 36.

But if you take unsigned long long , then, of course, you just can not leave everything. Of course, you can refuse recursion, but we are not looking for easy ways? :)

So if you definitely want to leave recursion - use this kind of dynamic programming, as memoization :)

 unsigned long long vr(unsigned int n) { // Размера массива 100 хватит за глаза, потому что // последний помещающийся в unsigned long long результат // получается при n == 73 static unsigned long long v[100] = {0}; if (n<3) return n; else if (n==3) return 4; else { if (v[n]) return v[n]; return v[n] = vr(n-1)+vr(n-2)+vr(n-3); } }

    This is the "Tribonacci Numbers"

     #include <iostream> int main() { unsigned K; std::cin >> K; unsigned long long n = 0; for (unsigned long long a = 0, b = 0, c = 1; K > 0; --K, a = b, b = c, c = n) n = a + b + c; std::cout << n << std::endl; }

    Or simply

     #include <cmath> #include <iostream> int main() { unsigned K; std::cin >> K; double tribo = 0x1.584c2ef9f4ab1p-2 * std::pow(0x1.d6db7f2d9c5c1p+0, K + 1); // ^^^ A ^^^ B // A = 0.336228116994941094225362954014332415157926090020459280443 // B = 1.839286755214161132551852564653286600424178746097592246778 std::cout << (unsigned long long) (tribo + 0.5) << std::endl; }

    Exact constants in the original formula are irrational. The accuracy of the decimal expansion given in the comments is sufficient to calculate the answer up to 208 terms in the sequence , provided that there is no loss of accuracy in performing the calculations. When using the double type (IEEE754 double precision), the discrepancy arises already on the 56th member of the sequence. When using the type long double (IEEE754 extended precision), the discrepancy will occur on the 67th member of the sequence.

    • one
      Two additions ... First, for the condition of the problem, you need to add 1 to the argument - because for step 1 there is already one way to climb on it (and not 0), and the second is that the second method will start lying on step 56 ... - Harry
    • one
      @Harry: No, neither the first nor the second option needs to be shifted to K — they correspond perfectly to K and the answers to K But for K = 1 I would say that the task is not defined at all, so it does not matter what the program gives out in this case. (And 0 for this reason is more appropriate than 1 ). As for the second method - the theoretical approach itself is, of course, accurate. The only question is the practical accuracy of the representation of constants and the accuracy of intermediate calculations. It is clear that the more accurately the floating type used is, the longer the formula will not “lie”. - AnT
    • one
      Here is your program - ideone.com/gqLjIY . We enter 1, we get 0. But the first step can be reached in one way - by stepping on it. We do not stand on the first step initially. It’s impossible for me to interpret this problem in a different way ... By the way, assuming that the first versions of the vehicle are being tested, then everything is as it is :) Your results differ from its results by a step shift. And the task, it turns out, is defined. You just did not solve the task of the vehicle, but your own - to get the numbers of the tribonacci ... - Harry
    • one
      As for the use of a floating point for integer calculations ... And, by the way, okay. You consider it correct to give an answer without indicating the limitations of its applicability - who am I to indicate to you? ... - Harry
    • one
      As for the second option - here you are carrying something incomprehensible about some kind of "using a floating point for integer calculations" (O_o) (???). No "integer calculations" is not here to mention. The closed form for the i-th member of the Fibonacci sequence and similar sequences is not something that is not integer, it is not even rational (!). I gave a reference - read, everything is written in detail. - AnT
     if (n<3) vr=n; else if (n==3) vr=4; else vr=(n-2)*3;
    • obviously, already for 4, the result is no longer true ... the general sequence formula here will be exponential and irrational, so it is problematic for direct calculation ... - Fat-Zer
    • one
      Interestingly, 3 people consider the linear formula the right answer? - Mikhailo
    • @Mikhailo: The last time on ruSO there has been a "foray" of some mysterious trolls and miners and trolls. This has always been the case, but now there’s some kind of surge. It is clear, of course, that these are not “organic” assessments)) - AnT

    Thanks https://ru.stackoverflow.com/users/215103/holyblackcat for the tip

      #include <iostream> using namespace std; int main() { long n; cin >> n; n++; long arr[n]; arr[1]=1; arr[2]=2; arr[3]=4; for (int i=4;i<n;i++) { arr[i]=arr[i-1]+arr[i-2]+arr[i-3]; } cout << arr[n-1]; return 0; }
    • If you write like this - cin >> n; n++; long arr[n]; cin >> n; n++; long arr[n]; - then this is no longer C ++ ... And the application of the array is unnecessary here - with each calculation you need only the last three values, you can not store all the others. - Harry