Вопрос интервью, который застал меня врасплох.
В. Рассмотрим бесконечное квадратное поле, в котором вы стоите в начале системы координат. Поле заполняется некоторыми деревьями, на которые у вас аллергия, такими, что деревья имеют размер точки и размещаются в целочисленных координатах tree(x,y), где x,y ∈ >набор I.Вы должны уйти с поля по прямой линии, не касаясь ни одного дерева.
Ответ:При первом взгляде на проблему кажется совершенно невозможным уйти от поля, поскольку это бесконечно большое поле, и чутье подсказывает, что любая линия, которую следует продолжать до бесконечности, уйдет. и прикоснуться к какому-нибудь дереву (уклон из реального мира), а если и есть такая линия, то их должно быть очень мало. Но, как всегда говорят, собрать некоторые данные.
Сначала рассмотрим случаи, когда линия из начала координат касается (проходит) дерева. Координаты любого дерева T равны X,Y . Уравнение линии имеет вид y=mx+c, где m — градиент линии.
m =(Y-0)/(X-0) i.e m =Y/X
но мы знаем, что Y и X ∈ I , AHAмы решили эту проблему, вы видите, что градиент представляет собой отношение целых чисел, которые также взаимно просты (вы не можете достичь любых x, y, которые являются не взаимно просты, так как вы остановитесь на первом встречном дереве на этой линии) друг с другом, что удовлетворяет условию рациональных чисел. Таким образом, мы просто устанавливаем градиент нашей линии от начала координат как иррациональное «нет», поскольку он никогда не будет проходить через любые целочисленные координаты.
Получается, что линий, позволяющих сбежать, бесконечно больше, чем тех, которые удерживают нас в ловушке поля.
