Белка на дереве

и задачки для интервью.
Forum rules
User avatar
KirAleks
Уже с Приветом
Posts: 210
Joined: 25 Apr 2001 09:01
Location: Kaluga->Minsk->SFBA

Белка на дереве

Post by KirAleks »

Есть бесконечно большой двухмерный лес в котором растут бесконечно высокие деревья. На одном дереве сидит белка .
Задача: предложить алгоритм поиска белки за конечное время.
Top
vaduz
Уже с Приветом
Posts: 27652
Joined: 15 Jul 2002 17:05
Location: MD

Re: Белка на дереве

Post by vaduz »

Ответ типа из "Физики шутят" подойдет?
Top
vaduz
Уже с Приветом
Posts: 27652
Joined: 15 Jul 2002 17:05
Location: MD

Re: Белка на дереве

Post by vaduz »

Что-то нет реакции...

Ну ладно, может так сойдет:
- обзываем кусок тот участок дерева, который можем проверить за единицу времени
- нумеруем деревья
- на первом шаге проверяем первый кусок дерева #1
- на втором шаге проверяем второй кусок дерева #1 и первый кусок дерева #2
- на третьем шаге проверяем третий кусок дерева #1, затем второй кусок дерева #2 и потом первый кусок дерева #3
- и так далее...

Поскольку координаты белки конечны, то ее можно найти за конечное время...
Top
User avatar
Polar Cossack
Уже с Приветом
Posts: 56371
Joined: 22 Nov 2002 02:05
Location: С-Пб, NH

Re: Белка на дереве

Post by Polar Cossack »

vaduz wrote:Поскольку координаты белки конечны, то ее можно найти за конечное время...
В бесконечном пространстве? Методом перебора? Попробуйте тогда отсортировать очень большой массив с постоянно добавляемыми элементами. Для большей развлекухи представим, что каждый новый элемент меньше элемента с номером текущего последнего, деленным на 10 (с округлением).
"Я хотел бы устроиться в вашу мусарню… Я хочу ходить с волыной и шмалять в людей." "Триод и Диод"
Top
User avatar
KirAleks
Уже с Приветом
Posts: 210
Joined: 25 Apr 2001 09:01
Location: Kaluga->Minsk->SFBA

Re: Белка на дереве

Post by KirAleks »

Polar Cossack wrote:
vaduz wrote:Поскольку координаты белки конечны, то ее можно найти за конечное время...
В бесконечном пространстве? Методом перебора? Попробуйте тогда отсортировать очень большой массив с постоянно добавляемыми элементами. Для большей развлекухи представим, что каждый новый элемент меньше элемента с номером текущего последнего, деленным на 10 (с округлением).

Чето не пойму какое отношение имеет сортировка массива к поиску элемента. Вопрос об эффективности алгоритма поиска не стоял.
Top
User avatar
KirAleks
Уже с Приветом
Posts: 210
Joined: 25 Apr 2001 09:01
Location: Kaluga->Minsk->SFBA

Re: Белка на дереве

Post by KirAleks »

vaduz wrote:Что-то нет реакции...

Ну ладно, может так сойдет:
- обзываем кусок тот участок дерева, который можем проверить за единицу времени
- нумеруем деревья
- на первом шаге проверяем первый кусок дерева #1
- на втором шаге проверяем второй кусок дерева #1 и первый кусок дерева #2
- на третьем шаге проверяем третий кусок дерева #1, затем второй кусок дерева #2 и потом первый кусок дерева #3
- и так далее...

Поскольку координаты белки конечны, то ее можно найти за конечное время...



поздравляю. :appl:
Приведенное Вами решение является одним из нескольких верных решений.
Правда оно не эффективно.

Кто может предложить более быстрый алгоритм ?
Top
User avatar
Rios
Уже с Приветом
Posts: 163
Joined: 26 Apr 2006 10:33
Location: YRV -> MSC -> NYC -> MD -> SFBA

Re: Белка на дереве

Post by Rios »

все просто, даже искать не надо, по условиям задачи белка сидит в двумерном бесконечном лесу на одном из бесконечно высоких деревьев. :D

А если серьезно, вам с какой точностью надо найти ответ?
Last edited by Rios on 26 Nov 2008 21:56, edited 1 time in total.
“The only way to get something to turn up when you need it is to need it to turn up.” (c) Terry Pratchett
Top
User avatar
Flash-04
Уже с Приветом
Posts: 63377
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Re: Белка на дереве

Post by Flash-04 »

KirAleks wrote:Задача: предложить алгоритм поиска белки за конечное время.

любой способ перебора, кроме того что пытается просканировать всё выбранное дерево целиком (оно по условию бесконечное), найдет белку за конечное время :pain1:
Not everyone believes what I believe but my beliefs do not require them to.
Top
User avatar
Rios
Уже с Приветом
Posts: 163
Joined: 26 Apr 2006 10:33
Location: YRV -> MSC -> NYC -> MD -> SFBA

Re: Белка на дереве

Post by Rios »

Flash-04 wrote:
KirAleks wrote:Задача: предложить алгоритм поиска белки за конечное время.

любой способ перебора, кроме того что пытается просканировать всё выбранное дерево целиком (оно по условию бесконечное), найдет белку за конечное время :pain1:


Ну лес-то, он тоже по условию бесконечно большой.
“The only way to get something to turn up when you need it is to need it to turn up.” (c) Terry Pratchett
Top
User avatar
Flash-04
Уже с Приветом
Posts: 63377
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Re: Белка на дереве

Post by Flash-04 »

Rios wrote:Ну лес-то, он тоже по условию бесконечно большой.

ну и что? ключ в том что если алгоритм будет сканировать одно дерево чтобы найти там белку и белки там нет, то потребуется бесконечно большое время чтобы закончить поиск.
Not everyone believes what I believe but my beliefs do not require them to.
Top
User avatar
Rios
Уже с Приветом
Posts: 163
Joined: 26 Apr 2006 10:33
Location: YRV -> MSC -> NYC -> MD -> SFBA

Re: Белка на дереве

Post by Rios »

Flash-04 wrote:
Rios wrote:Ну лес-то, он тоже по условию бесконечно большой.

ну и что? ключ в том что если алгоритм будет сканировать одно дерево чтобы найти там белку и белки там нет, то потребуется бесконечно большое время чтобы закончить поиск.


Если алгоритм сканирует конечный кусок леса за конечное время, то существует большая вероятнотсть того, что белка находится в непросканированном куске леса, на любом шаге алгоритма.

Исходя из этого для того, чтобы гарантировано найти белку в бесконечном пространстве за конечное время нужно будет постуливать существование алгоритма проверки бесконечного куска леса за конечное время. В этом, и, очень похоже, что только в этом случае белку можно будет найти за конечное время.

Иными словами, если взять бесконечное множество (лес) и разбить его на конечное число подмножеств и постулировать что есть алгорим проверки такого подмножества за конечное время, - задача разрешима. Иначе пока не вижу.
“The only way to get something to turn up when you need it is to need it to turn up.” (c) Terry Pratchett
Top
User avatar
Rios
Уже с Приветом
Posts: 163
Joined: 26 Apr 2006 10:33
Location: YRV -> MSC -> NYC -> MD -> SFBA

Re: Белка на дереве

Post by Rios »

vaduz wrote:...

Поскольку координаты белки конечны, то ее можно найти за конечное время...


Такого типа алгоритм займет конечное время только в том случае если при N->бесконечности, время затрачиваемое на проверку -> 0. Если время необходимое не проверку ограничено снизу константой C>0, - поиск займет бесконечное количество времени.
“The only way to get something to turn up when you need it is to need it to turn up.” (c) Terry Pratchett
Top
User avatar
Rios
Уже с Приветом
Posts: 163
Joined: 26 Apr 2006 10:33
Location: YRV -> MSC -> NYC -> MD -> SFBA

Re: Белка на дереве

Post by Rios »

upd: причем стремится к нулю так что сумма стремится к константе.
upd2: понятное дело что для каждого конкретного случая затраченое время будет некое M, под конечностью этого M я понимаю что для любого местонахождения белки в лесу M<некой заранее заданной константы P.
“The only way to get something to turn up when you need it is to need it to turn up.” (c) Terry Pratchett
Top
User avatar
Flash-04
Уже с Приветом
Posts: 63377
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Re: Белка на дереве

Post by Flash-04 »

тут кажущийся парадокс. для упрощения рассмотрим алгоритм поиска на числовой оси натуральных чисел выбранного числа посредством их перебора начинаяя с 1. Имеем следующее:
1. нет верхнего предела для времени поиска т.к. натуральных чисел бесконечно много
2. тем не менее время поиска заданного числа - конечно, причем для любого числа
Not everyone believes what I believe but my beliefs do not require them to.
Top
User avatar
Rios
Уже с Приветом
Posts: 163
Joined: 26 Apr 2006 10:33
Location: YRV -> MSC -> NYC -> MD -> SFBA

Re: Белка на дереве

Post by Rios »

Flash-04 wrote:тут кажущийся парадокс. для упрощения рассмотрим алгоритм поиска на числовой оси натуральных чисел выбранного числа посредством их перебора начинаяя с 1.
Имеем следующее:
1. нет верхнего предела для времени поиска т.к. натуральных чисел бесконечно много
2. тем не менее время поиска заданного числа - конечно, причем для любого числа


Ну это не столько парадокс, сколько то, как мы понимаем конечное время необходимое для нахождения... понятное дело что для любого V(x,y,z) существует такое количество шагов N (конкретное число) при котором мы найдем белку. Но это самое N в общем случае не ограничено сверху.

Ну вобщем да.. я понял где засада в момент когда писал свой предыдущий пост

P.S а почему смайлы такие дурные?
“The only way to get something to turn up when you need it is to need it to turn up.” (c) Terry Pratchett
Top
Y+A=LOVE
Уже с Приветом
Posts: 467
Joined: 01 Feb 2005 19:21
Location: 666

Re: Белка на дереве

Post by Y+A=LOVE »

Намудрили тут канадские лесорубы... А бензопилой пользоваться можно?
Top
User avatar
Polar Cossack
Уже с Приветом
Posts: 56371
Joined: 22 Nov 2002 02:05
Location: С-Пб, NH

Re: Белка на дереве

Post by Polar Cossack »

Y+A=LOVE wrote:Намудрили тут канадские лесорубы... А бензопилой пользоваться можно?
Патч-коды для бесконечного бензина есть? :?
"Я хотел бы устроиться в вашу мусарню… Я хочу ходить с волыной и шмалять в людей." "Триод и Диод"
Top
User avatar
KP580BE51
Уже с Приветом
Posts: 15007
Joined: 14 Jun 2005 11:50
Location: Ukraine

Re: Белка на дереве

Post by KP580BE51 »

KirAleks wrote:Есть бесконечно большой двухмерный лес в котором растут бесконечно высокие деревья. На одном дереве сидит белка .
Задача: предложить алгоритм поиска белки за конечное время.

Логично предположить что если белка будет сидеть слишком низко, то она сдохнет от азотного отравления. А если слишком высоко, то кислородного голодания. :umnik1:
Top
User avatar
Polar Cossack
Уже с Приветом
Posts: 56371
Joined: 22 Nov 2002 02:05
Location: С-Пб, NH

Re: Белка на дереве

Post by Polar Cossack »

Я понял, что меня смущало: не приведен алгоритм перебора.
Если провести окружность и перебрать деревья, центр которых находится внутри (и на окружности), затем переходим на концентричееское кольцо заданной "ширины", например, добавив тот же радиус. Поиск конечен.
Два замечания.
1. Как прикладник, замечу, что время выполнения вам не понравится.
2. Как математик, замечу, что условие некорректно. Нет ограничения на перемещения белки. Тогда задача в общем виде не имееет конечного решения.
"Я хотел бы устроиться в вашу мусарню… Я хочу ходить с волыной и шмалять в людей." "Триод и Диод"
Top
User avatar
Flash-04
Уже с Приветом
Posts: 63377
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Re: Белка на дереве

Post by Flash-04 »

Polar Cossack wrote:1. Как прикладник, замечу, что время выполнения вам не понравится.

ну а как вы хотели? :pain1:
2. Как математик, замечу, что условие некорректно. Нет ограничения на перемещения белки. Тогда задача в общем виде не имееет конечного решения.


На одном дереве сидит белка
Not everyone believes what I believe but my beliefs do not require them to.
Top
User avatar
KP580BE51
Уже с Приветом
Posts: 15007
Joined: 14 Jun 2005 11:50
Location: Ukraine

Re: Белка на дереве

Post by KP580BE51 »

Flash-04 wrote:На одном дереве сидит белка

Это ничего не меняет. За бесконечное время, конечная белка наверняка сдохнет, свалится вниз, долетит до слоев где плотность воздуха будет равна плотности тушки, и будет бесконечно долго плавать по бесконечным течениям бесконечного леса. :umnik1:
Last edited by KP580BE51 on 27 Nov 2008 16:01, edited 1 time in total.
Top
User avatar
Flash-04
Уже с Приветом
Posts: 63377
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Re: Белка на дереве

Post by Flash-04 »

KP580BE51 wrote:За бесконечное время, конечная белка наверняка сдохнет и будет бесконечно долго падать вниз. :umnik1:

а вот и нет, время как раз - конечное 8) но даже если сдохнет, то все что изменится - координата белки на дереве (станет 0) :mrgreen:
Not everyone believes what I believe but my beliefs do not require them to.
Top
User avatar
KP580BE51
Уже с Приветом
Posts: 15007
Joined: 14 Jun 2005 11:50
Location: Ukraine

Re: Белка на дереве

Post by KP580BE51 »

Flash-04 wrote:
KP580BE51 wrote:За бесконечное время, конечная белка наверняка сдохнет и будет бесконечно долго падать вниз. :umnik1:

а вот и нет, время как раз - конечное 8) но даже если сдохнет, то все что изменится - координата белки на дереве (станет 0) :mrgreen:

А вот и нет. Требуется -то найти белку. Не указано что нужно найти живую белку. И не сказано, водятся ли бесконечном лесу падальщики. Хотя, не понятно, имеет ли решения задача, поедания трупа белки, в бесконечном лесу, за бесконечное время, бесконечным кол-вом падальщиков. Но если допустить, что кол-во падальщиков, конечно, то в бесконечном лесу они белку точно не найдут.
Top
User avatar
Flash-04
Уже с Приветом
Posts: 63377
Joined: 03 Nov 2004 05:31
Location: RU -> Toronto, ON

Re: Белка на дереве

Post by Flash-04 »

KP580BE51 wrote:Но если допустить, что кол-во падальщиков, конечно, то в бесконечном лесу они белку точно не найдут.

вух! :) теперь белка (точнее её труп) в безопасности
Not everyone believes what I believe but my beliefs do not require them to.
Top
vaduz
Уже с Приветом
Posts: 27652
Joined: 15 Jul 2002 17:05
Location: MD

Re: Белка на дереве

Post by vaduz »

Flash-04 wrote:
KP580BE51 wrote:Но если допустить, что кол-во падальщиков, конечно, то в бесконечном лесу они белку точно не найдут.

вух! :) теперь белка (точнее её труп) в безопасности


Ну да! А зачем же, по-вашему, мы ищем белку? :food:
Top

Return to “Головоломки”