niman
|
*
|
|
|
|
Рег.: 05.12.2005
|
Сообщений: 3991
|
|
Рейтинг: 1460
|
|
|
ага. ошибся.
хвост можно сделать так:
перебираем все элементы цикла. Получаем на каждом шаге длину пути от первого элемента(хвоста) до каждого элемента цикла. Берем минимум иэ этих чисел.
|
|
abv
|
|
|
|
|
Рег.: 21.09.2007
|
Сообщений: 6924
|
|
Рейтинг: 6747
|
|
Re: Задачи с собеседований.
[re: abv]
05.03.2009 15:14
|
|
|
апд: проверил на других примерах... забавно они всегда ровно на 1 расходятся. в общем первый нужно пускать с начала списка. а второй - не с точки пересечения, а от следующего за ней элемента
|
|
|
abv
|
|
|
|
|
Рег.: 21.09.2007
|
Сообщений: 6924
|
|
Рейтинг: 6747
|
|
Re: Задачи с собеседований.
[re: niman]
05.03.2009 15:16
|
|
|
непонятно как считать длину от начала списка. ты тут то же самое предлагаешь. брать по модулю длины цикла нельзя, ибо длина цикла может быть меньше чем длина хвоста
|
|
|
Castaneda
|
Carpal Tunnel
|
|
|
|
Рег.: 30.11.2004
|
Сообщений: 4013
|
Из: Desierto de Sonora
|
Рейтинг: 2594
|
|
|
мне нигде - это задача из упомянутой тут книги
|
|
nelapsi
|
the wumbologist
|
|
|
|
Рег.: 10.11.2003
|
Сообщений: 10759
|
Из: Orbis Tertius
|
Рейтинг: 10650
|
|
Re: Задачи с собеседований.
[re: abv]
05.03.2009 15:18
|
|
|
ну там +-1 начинай с элемента след. за пересечением
|
Your touch will set me free |
|
DarkGray
|
Carpal Tunnel
|
|
|
|
Рег.: 30.09.2002
|
Сообщений: 31414
|
|
Рейтинг: 8951
|
|
Re: Задачи с собеседований.
[re: niman]
05.03.2009 15:18
|
|
|
Quote:
перебираем все элементы цикла. Получаем на каждом шаге длину пути от первого элемента(хвоста) до каждого элемента цикла. Берем минимум иэ этих чисел.
лучше тогда: для каждого элемента хвоста делаем круг по циклу, как только кольцевой итератор встретил хвостовой итератор - это и будет длина хвоста
|
|
xandr
|
|
|
|
|
Рег.: 26.11.2004
|
Сообщений: 6546
|
|
Рейтинг: 1779
|
|
Re: Задачи с собеседований.
[re: abv]
05.03.2009 15:18
|
|
|
такую хорошую тему засрали...
|
|
Castaneda
|
Carpal Tunnel
|
|
|
|
Рег.: 30.11.2004
|
Сообщений: 4013
|
Из: Desierto de Sonora
|
Рейтинг: 2594
|
|
Re: Задачи с собеседований.
[re: xandr]
05.03.2009 15:19
|
|
|
надо сделать тему обсуждаемой а вообще согласен, все эти разговоры и желание быть умнее кого-то - полный бред
|
|
nelapsi
|
the wumbologist
|
|
|
|
Рег.: 10.11.2003
|
Сообщений: 10759
|
Из: Orbis Tertius
|
Рейтинг: 10650
|
|
Re: Задачи с собеседований.
[re: abv]
05.03.2009 15:19
|
|
|
опередил я просто на бумажке рисовал что там куда попадает - так что +- 1
|
Your touch will set me free |
|
abv
|
|
|
|
|
Рег.: 21.09.2007
|
Сообщений: 6924
|
|
Рейтинг: 6747
|
|
|
В ответ на:
все эти разговоры и желание быть умнее кого-то
поржал. где ты это увидел?
|
|
|
abv
|
|
|
|
|
Рег.: 21.09.2007
|
Сообщений: 6924
|
|
Рейтинг: 6747
|
|
|
В ответ на:
лучше тогда: для каждого элемента хвоста делаем круг по циклу, как только кольцевой итератор встретил хвостовой итератор - это и будет длина хвоста
ага и получаем асимптотику н квадрат... в случае если длина цикла равна половине длине списка
|
|
|
nelapsi
|
the wumbologist
|
|
|
|
Рег.: 10.11.2003
|
Сообщений: 10759
|
Из: Orbis Tertius
|
Рейтинг: 10650
|
|
Re: Задачи с собеседований.
[re: nelapsi]
05.03.2009 15:21
|
|
|
была уже похожая тема ( и не одна) - там уже предлагали ее сделать обсуждаемой и прикрепить, но это не встретило понимания
|
Your touch will set me free |
|
nelapsi
|
the wumbologist
|
|
|
|
Рег.: 10.11.2003
|
Сообщений: 10759
|
Из: Orbis Tertius
|
Рейтинг: 10650
|
|
|
|
pelot
|
летчик
|
|
|
|
Рег.: 22.12.2004
|
Сообщений: 13954
|
|
Рейтинг: 3711
|
|
|
В ответ на:
желание быть умнее кого-то - полный бред
нормальное желание
|
_______...__Oooo._ ___.oooO___(___)_ ___(___)_____)_/_ ____\_(_____(_/_ _____\_)_
|
|
DarkGray
|
Carpal Tunnel
|
|
|
|
Рег.: 30.09.2002
|
Сообщений: 31414
|
|
Рейтинг: 8951
|
|
Re: Задачи с собеседований.
[re: abv]
05.03.2009 15:25
|
|
|
Quote:
апд: проверил на других примерах... забавно они всегда ровно на 1 расходятся. в общем первый нужно пускать с начала списка. а второй - не с точки пересечения, а от следующего за ней элемента
что-то мне, кажется, что ты какие-то красивые примеры подбирал, чтобы такое получилось.
что будет, если хвост - 0, а кольцо - 3, 4, 5, 6 и т.д.?
|
|
Castaneda
|
Carpal Tunnel
|
|
|
|
Рег.: 30.11.2004
|
Сообщений: 4013
|
Из: Desierto de Sonora
|
Рейтинг: 2594
|
|
Re: Задачи с собеседований.
[re: pelot]
05.03.2009 15:26
|
|
|
3 разных ответа: "где ты это увидел", "мелочь, а приятно", "это нормально" предлагаю создать отдельную ветку "кто тут самый умный"
|
|
DarkGray
|
Carpal Tunnel
|
|
|
|
Рег.: 30.09.2002
|
Сообщений: 31414
|
|
Рейтинг: 8951
|
|
Re: Задачи с собеседований.
[re: abv]
05.03.2009 15:27
|
|
|
Quote:
ага и получаем асимптотику н квадрат... в случае если длина цикла равна половине длине списка
да, будет tail*loop
для варианта наоборот, когда для каждого элемента цикла перебираем хвост - будет (tail+loop/2)*loop
|
|
abv
|
|
|
|
|
Рег.: 21.09.2007
|
Сообщений: 6924
|
|
Рейтинг: 6747
|
|
|
В ответ на:
что-то мне, кажется, что ты какие-то красивые примеры подбирал, чтобы такое получилось.
зря тебе так кажется. Я не на столько туп, чтобы не суметь это правильно протестить. странно, но работает. нулевые и единичные случаи я не тестил. вот разные независимые комбинации длины списка, хвоста и цикла - да
|
|
|
abv
|
|
|
|
|
Рег.: 21.09.2007
|
Сообщений: 6924
|
|
Рейтинг: 6747
|
|
|
В ответ на:
tail*loop
тебе не кажется, что задача должна иметь какое-то более интересное решение? ибо tail * loop как-то не сильно отличается от обычного решения в лоб за (tail + loop) * (tail + loop)
|
|
|
abv
|
|
|
|
|
Рег.: 21.09.2007
|
Сообщений: 6924
|
|
Рейтинг: 6747
|
|
Re: Задачи с собеседований.
[re: abv]
05.03.2009 15:33
|
|
|
вот вам еще задачка со вступительного собеседования в мфти: заходит абитуриент. ему профессор говорит: -Вон видите на окне ваза стеклянная стоит? -Ага. -Так у нее та сторона, которая стоит на солнце - холоднее, чем та, которая обращена к нам! Почему так? -Че реально? подходит, убеждается, охуевает. собеседование не проходит. а вы бы прошли?
да, задачка известная и многие ее знают. не обламывайте тех, кто не слышал
|
|
|