Jumping of a frog

Authors

  • Pavel Töpfer Faculty of Mathematics and Physics, Charles University, Prague

Abstract

The article from the series dedicated to problems of Mathematical Olympiad – category P (programming) describes a practical competition task from the home round of the 2015/16 school year. Our task is to find the longest sequence of jumps of a frog from the start stone to the target one. Jumps during this trip must be always shorter and shorter. We show three different solutions. The simplest version is based on the examination of all possible sequences, a better solution uses dynamic programming techniques and the best one additionally uses a pre-calculation, which means a sorting of all possible jumps according to their length in advance.

Published

2016-11-01

How to Cite

Töpfer, P. (2016). Jumping of a frog. MATHEMATICS–PHYSICS–INFORMATICS, 25(5), 376–383. Retrieved from https://mfi.upol.cz/index.php/mfi/article/view/299

Issue

Section

Informatics