Несколько интересных задач с решениями
В этом разделе будут размещаться достаточно сложные и интересные задачи выполненные моими учениками. Не могу сказать, что каждое из этих решений образец совершенства. Я выбираю решения содержащие в себе какую-то авторскую изюминку, идею. Некоторые задачи появились в этой коллекции в силу того, что они вообще интересны, как иллюстрация базового метода решения задач. Раздел будет очень большим. За почти 20 лет работы школы появилось много интересных решений, а идея их размещения без купюр и моих улучшений возникла недавно.
Задача1. Калькулятор алгебраических выражений. Пусть выражение задано строкой символов, содержащей арифметические операции, имена функций, скобки, числа. Как его вычислить? Наше решение содержит не вполне тривиальную идею, того, как это можно сделать. По сути предлагаемое здесь решение это небольшой алгебраический компилятор, создающий вычислительную структуру быстрого счета.
Задача 2. Расстановка ферзей. Классическая задача, часто используемая в учебниках по программированию. Необходимо расставить восемь ферзей на шахматной доске так, чтобы никакие два не угрожали друг другу.
Задача 3. Восстановление многочлена. Многочлен степени N - это важный алгебраический объект. Существует теорема утверждающая, что для каждого многочлена корни определяются однозначно. А это означает, что имея корни, можно вычислить и коэффициенты многочлена. На вопрос как это сделать и отвечает наше решение.
Задача 4. Гвозди и рейка. В длинную деревянную рейку вбили М гвоздей больше 2 но меньше 20. Гвозди объединяются в пары веревочками так, чтобы выполнились следующие условия:
Написать программу, которая определяет пары гвоздей, связанных веревочками, с учетом описанных выше обязательных условий.
Задача 5. Игра монетки. Есть набор столбиков монет различной высоты, расположенных на одной линии. Игроки по очереди забирают себе столбики с одного края линии. Игрок не может не брать столбиков и не может взять их больше, чем взял его противник предыдущим ходом. (то есть если один взял 3 столбика, то другой вслед за ним может взять 1, 2 или 3 по своему усмотрению – а первый затем – не больше чем взял второй, и так далее). В начале игры вводится максимальное количество столбиков для взятия первым ходом. Цель – взять себе в сумме больше монет, чем противник, к моменту, когда столбики кончатся.
Задача 6. Черные пятна на белой шкуре. Есть белая шкура и на ней некоторое количество черных пятен. Требуется найти наибольшее черное пятно (его площадь). Задача интересна тем, что необходимо придумать, как языковыми данными представить белую шкуру и черные пятна на ней. Самый простой вариант - это представить шкуру числовой матрицей, а пятно вполне определенными числами, например единицами или нулями.
Задача 7. Наименьшее невыбранное число. Из миллиарда чисел выбирается 10 миллионов случайным образом. Необходимо найти первое невыбранное. Проблема заключается в том, что выбранные числа хранятся в файле. Файловые операции работают очень медленно, поэтому применять алгоритмы сортировки к выбранным числам нельзя.
Задача 8. Поиск пути к бензоколонке. Некий автомобилист пытается в городе найти путь к бензоколонке. Он находится в определённой точке, и располагает картой города, на которой отмечена единственная бензоколонка. На улицах города, как и полагается, установлены знаки, соблюдать которые водитель в принципе обязан. Но наш водитель имеет возможность нарушить некоторое количество правил. Кроме того, его автомобиль имеет некоторое количество топлива, которого возможно более чем достаточно, но может быть и не очень много. Необходимо найти путь, на котором водитель уложится в существующее количество топлива и минимальное количество раз нарушит правила дорожного движения. Экономить топливо не обязательно. Карта города представляет собой граф, для построения которого обязательно использовать указатели.
Задача 9. Поиск наидлиннейшего пути рубки. На шахматной доске размером 8x8 клеток расставлено несколько белых и одна черная шашки. Найти наидлиннейший путь рубки черной по правилам игры в шашки. Программа несколько длинновата в силу того, что автор результат реализовал графически.
Задача 10. Путник в тумане. На поле квадратной формы находится некоторое количество препятствий прямоугольной формы. Путник начиная путь из точки А должен придти в точку Б, идя в глубоком тумане. Никакой карты позволяющей сориентироваться в пространстве у него нет. Нет и возможности привязаться как-то к координатам. Есть правда компас всегда показывающий на пункт Б, поэтому в отсутствии препятствий, даже глубокий туман ему не помешал бы, но они есть и их форма неизвестна. Ситуация усугубляется тем, что у путника большие проблемы с памятью и вообще интеллектом. Он может помнить только пару чисел и умеет выполнять простые арифметические операции и не более того. Реализация должна прорисовать путь на графическом представлении поля с препятствиями. Описание алгоритма, вы можете посмотреть в моем курсе, а ниже только текст программы на Turbo-Pascal. Эта реализация должна работать и на Free Pascal
Задача 11. Расстановка букв. В квадрате, состоящем из 16 клеток, расставить 4 буквы так чтобы в каждом столбце, каждой строке и каждой большой диагонали находилась только одна буква. Построить все возможные решения.
Задача 12. Реализация минимакса. Дано двоичное дерево оценок. Реализовать метод минимакса. Что такое минимакс, можно почитать в моем курсе. Впрочем это довольно часто используемый метод принятия решений, поэтому о нем можно много где почитать.
Задача 13. Составить выражение. Дано целое число М. Вставить между некоторыми цифрами 1, 2, 3, 4, 5, 6, 7, 8, 9, записанными именно в таком порядке, знаки "+" или "-" так, чтобы значением получившегося выражения было это число.
Задача 14. Построение сетки соревнований. Для соревнований по рукопашному бою требуется построить дерево боев так, чтобы бойцы, вышедшие в финал, провели либо равное количество боев, либо количество должно отличаться не более чем на один.
Задача 15. Ханойская башня. Еще одна классическая задача имеющая много решений. Её условие тоже общеизвестно.
Задача 16. Удаление скобок. Дано арифметическое выражение. Удалить из него все скобки не влияющие на порядок вычислений.
Задача 17. Вычисление площадей криволинейных фигур. Имеются ввиду фигуры ограниченные кривыми представлющими собой алгебраический многочлен. Для таких фигур нет стандартных формул расчета площадей, поэтому они вычисляются посредством операции интегрирования или с помощью приближения интегральными суммами. (автор решения - Камилла Хисамова, г. Казань)