Stairs

The little boy has a set of N cubes (5 ≤ N ≤ 500). From these cubes can be folded various stairs. Stairs have steps of different sizes, following in ascending order of this size (pay special attention to the fact that a staircase cannot have two identical steps). Each staircase must have at least two steps, and each step must consist of at least one cube. The figure shows examples of stairs for N = 11 and N = 5:

enter image description here

Find the number Q of different ladders that a little boy can build in exactly N cubes.

Initial data

Number n

Result

Q number

Example

raw data 212

result 995645335

You need to write a function

  • Anyway, the code on what will be written - Vanya Avchyan
  • five
    Knut, "The Art of Programming", vol. 4A, section 7.2.1.4, problem 21. This is your task ... - Harry
  • @Harry Thanks for the tip. I will study - Vanya Avchyan

2 answers 2

This is the sequence A111133

Implementation on VB :

Sub Calc() Dim n As Long, count(), i As Long n = 500 ReDim count(n) count(0) = 1 For i = 1 To n For j = n To i Step -1 count(j) = count(j) + count(j - i) Next j, i For i = 1 To n Debug.Print count(i) - 1; Next End Sub

Asymptotics through A000009:

 a(n) ~ exp(Pi*sqrt((n-1/24)/3)) / (4*3^(1/4)*(n-1/24)^(3/4)) * (1 + (Pi^2-27)/(24*Pi*sqrt(3*(n-1/24))) + (Pi^4-270*Pi^2-1215)/(3456*Pi^2*(n-1/24))) - 1

    The limit of 500 is quite a bit ... In fact, it is possible to solve with a much greater limit.

    The solution is the dynamics F[i][j] - the number of ways to assemble a ladder of j cubes with i last row. In fact, the whole matrix is ​​not needed here, it’s better to compress it into the list, but these are details.

    Base F[0][0] = 1

    Recalculation: go up the last row. Enumerate the value of the next row. We add there. Do not forget to check that the amount is not more than N

    The answer is the sum of the matrix by column.

    Difficulty if you write completely in the forehead, then the order of the cube (it will have time). If neatly a square or even n log n .

    • F [i] [j] is that the function accepts i, j? - Vanya Avchyan
    • Usually, if the square brackets mean a two-dimensional array. - pavel
    • In my letter F, they denote functions. At the level of abstraction, it is difficult to understand whether the solution is correct.
    • 7
      @VanyaAvchyan you for fools then people do not hold here. They help with problems when you have difficulties with your own realization of something. And so you just want to get a free code ready code, without putting effort. It does not happen. It happens more precisely, but this is for you on Freelance ....... especially in the question label алгоритм , and not YP - Alexey Shimansky
    • one
      @ Aleksey Shimansky There are any languages ​​in the label too. For fools, I don’t hold anyone. And there are other platforms for verbal disturbances. There’s Man either responding or not. - Vanya Avchyan