🗊Презентация Greedy algorithm

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find a best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps. For example, a greedy strategy for the traveling salesman problem (which is of a high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city." This heuristic does not intend to find a best solution, but it terminates in a reasonable number of steps; finding an optimal solution to such a complex problem typically requires unreasonably many steps.

1. Consider a method of cutting a rectangle with whole lengths of sides into the least number of squares. Cut the square with the largest side from the rectangle, and repeat this operation with the remaining part of the rectangle the necessary number of times. Show that this method does not always allow cutting into the smallest number of squares. 2. The cells of the copybook paper are painted in a checkerboard pattern. Draw the largest circle of radius, which lies entirely on the white fields, and explain the answer. 3. There are five pieces of chain: 3, 4, 5, 6 and 7 rings. Is it possible to make one chain of them by cutting and connecting only three rings? 4. Is it true that for each point inside the convex quadrilateral the sum of the distances from it to the vertices is less than the perimeter?

5. One tetrahedron lies inside the other. Can the sum of the lengths of the edges of the inner tetrahedron be greater than the sum of the lengths of the edges of the outer tetrahedron? 6. Is it possible to cut an isosceles right triangle into isosceles right triangles, among which there is no equal? 7. Over the chain of lakes flew a flock of birds. On each lake, half the birds and another half of the bird were landing, and the rest flew on. All the birds sat on seven lakes. How many birds were? 8. The first term of the sequence is equal , each following is equal to the sum of digits of the previous one. Find the tenth term in the sequence.

9. Are there three natural numbers, the sum of which is equal to 201, and the product is equal to 30030? 9. Are there three natural numbers, the sum of which is equal to 201, and the product is equal to 30030? 10. At the vertices and center of a regular octagon, arrange the numbers from 1 to 9 (each one at a time) so that the sum of the numbers along all the big diagonals is the same. What values ​​can take a number in the center? 11. How many five-digit numbers exist in which all digits are different and go (from left to right) in descending order? 12. How many five-digit numbers exist that all numbers are different and go (from left to right) in ascending order?