enter image description here

The task:

Lay such routes from the bottom to the top of the numerical pyramid so that the sums of numbers that will be on each of them are 35, 45, 55, respectively.

How do I understand this pyramid to be implemented in the form of a binary tree, sort it, and then select the desired branch?

  • one
    Something offhand, except sorting out 2 ^ 6 = 64 options, is not invented ... There is no need for a tree: just choose the left path, say, 0, right - 1, that's all ... - Harry
  • @Harry pyramid needs to be implemented in the form of a binary tree - I do not see any restrictions on the movement "sideways", and even on self-intersection. So not 2 ^ 6, but a bit more. Well, in addition - from the top to the base is easier to build. - Akina
  • @Akina about the implementation in the tree format is just my guess, and not the condition of the task. - Hardc0re
  • Binary tree here probably will not work. Since it is not otherwise specified, then in 7 at level 4 (from above, considering the vertex as level 1), you can get from both 9 and 4 from level 3 (this is if you look in the opposite direction). Probably it is better to present the data in the form of a matrix (lower left triangle) and go from the top down - to the right - left (accumulating paths in the queue) until you reach the base with the desired result. It is clear that brute force (and an obvious shortfall) can be immediately discarded. - avp
  • one
    @ Hardc0re Please, specify the allowed movements ... - Harry

1 answer 1

Use any standard path finding algorithm. I would use brute force and simple recursion. Termination condition - the current amount is not less than the specified, the criterion of withdrawal - the equality of the current amount specified plus the current location - the base. Schematically:

proc findpath(currentway, currentplace, currentsum) if currentsum >= checksum then if currentplace.level=0 and currentsum=checksum then output currentway end if else for i=0 to 5 call findpath(currentway+currentplace, currentplace.moveto(i), currentsum+currentplace.weight) next i end if end proc
  • For convenience (and simplification) of the algorithm, the pyramid scheme should be transformed into a triangular matrix with a "framing contour" (i.e., the vertex has an index of 2.2), and a value not less than a specified amount should be assigned to the "non-existent elements". Then, when you exit the border, the current amount will immediately be exceeded and the recursion will be stopped without outputting the current path. - Akina