nh-

алгоритм O(N): вспомогательные функции/переменные: boolean random(); // функция, возвращающая случайное значение true/false const int keyLen = 16; // длина ключа boolean key[keyLen]; // массив для ключа int i; // вспомогательный счетчик вспомогательная функция для установки ключа после установки мы не возвращаемся, а находимся в вагоне, следующем после конца ключа void setKeyNoReturn() { for (i=0; i < keyLen; i++) { setState(random()); // устанавливаем случайный ключ key[i] = getState(); // запоминаем ключ goNext(); } } вспомогательная функция проверки совпадения с ключом после проверки возвращаемся в исходный вагон boolean compareKey() { boolean retval = false; // возвращаемое значение // проверка совпадения с ключом for (i=0; i < keyLen; i++) { if (getState() != key[i]) break; goNext(); } // результат проверки if (i == keyLen) retval = true; // возвращаемся в исходный вагон for (; i > 0; i--) { goPrev(); } return retval; } вспомогательная функция для проверки того, что длина цепочки больше, чем длина ключа возвращает длину цепочки, если она меньше keyLen, или keyLen в противном случае int getLengthIfLessThanKeyLen() { counter = 1; for (i=0; i < keyLen; i++) { if (checkLength(counter)) break; counter++; } return counter; } сам алгоритм int countLengthN() { counter = getLengthIfLessThanKeyLen(); if (counter > 0) return counter; setKeyNoReturn(); while (true) { if (compareKey()) { if (checkLength(counter)) return counter; } goNext(); counter++; } } сложность алгоритма получается что-то вроде const1*keyLen*N+const2 очевидные модификации алгоритма: - const2 определяется тем, насколько нам "повезло с ключом", поэтому если нам сильно не повезло (compareKey() часто возвращает true), то можно добавить установку нового ключа и запуск алгоритма заново - кроме того, применяя другие, более оптимальные алгоритмы поиска подстроки в строке (а именно это мы и делаем в цикле compareKey()->goNext()), можно добиться сложности порядка const3*(N+keyLen)+const4 - если вагонов может "ну ооочень много", то нужно позаменять везде типы данных с integer/int на соответствующие объекты (а-ля BigInteger) - функцию getLengthIfLessThanKeyLen() тоже можно оптимизировать, но это вряд ли поможет http://forum.academ.org/html/emoticons/smile.gif

формально: вагон нас интересует только с точки зрения того, горит в нём свет или нет, поэтому сопоставим каждому вагону состояние: true - если свет горит, false - иначе типы данных будем обозначать int - для целочисленных переменных boolean - для булевых переменных функции: boolean getState() // получить состояние текущего вагона void setState(boolean st) // установить состояние текущего вагона void goNext(), goPrev() // перейти к след./пред. вагону дополнительные функции для удобства: void switchState() // изменить состояние текущего вагона на противоположное = setState(!getState()) void goNextN(int n), goPrevN(int n) // перейти к след./пред. вагону n раз, goNextN(n) = goNext()*n переменные: int counter=0 // счётчик вагонов вспомогательная функция, проверяющая, является ли длина цепочки равной testLength: boolean checkLength(int testLength) { boolean state; // вспомогательная переменная state = getState(); goNextN(testLength); switchState(); goPrevN(testLength); if (state != getState()) return true; else return false; } итак, простейший алгоритм O(N^2): int countLengthN2() { counter = 1; while (!checkLength(counter)) counter++; return counter; }

QUOTE 5. Ручки, карандаша и бумажки с собой - нету.это ещё что за условие? очевидно, что вообще без памяти эта задача не решается. нужно или ставить чёткое ограничение на память, или говорить так, как было сказано: QUOTE (kostik)договоримся, что размер памяти неограничен алгоритм сейчас напишу

QUOTE как узнать, то же это место, или нет?очень просто - допустим, мы подозреваем, что вагоны A и B являются одним и тем же вагоном запоминаем состояние света в вагоне A, переходим в вагон B, щёлкаем там выключателем, возвращаемся в вагон A - если состояние света изменилось, то A=B, иначе - нет. p.s. я не отрицал, что нужно иногда двигаться в двух направлениях, просто это "иногда" настолько редко, что результат всё равно получится O(N) p.p.s. получается такой "метод метки с обратной проверкой" http://forum.academ.org/html/emoticons/smile.gif

имелось в виду то, что было сказано http://forum.academ.org/html/emoticons/smile.gif два бита памяти, кроме счётчика - то есть человечек, бегающий по вагонам, может запоминать сколько вагонов он уже насчитал и ещё запоминать одно состояние вкл./выкл. хотя я наврал... для самого простого алгоритма всё-таки минимум 2 бита понадобится - нужно ещё помнить, в какую сторону мы бежали ;) а что касается более быстрых алгоритмов - я не стал шибко вдаваться в то, что написал Mafia - как-то уж сильно сложно :Х мне кажется, что можно проще и за O(N) а именно - ставим k-битную случайную метку на k подряд идущих вагонов, после чего идём в одном направлении, пока не встретим эту метку. если встретили - проверяем, что это то же самое место и узнаём таким образом длину. если это оказалось не то же самое место - идём дальше ("ложное срабатывание"). если число "ложных срабатываний" слишком велико - нам не повезло с меткой, меняем её. в результате - O(N), поскольку алгоритм линейный, и проверка "ложности срабатывания" тоже даёт O(N), а она будет выполняться очень редко.

с 1 битом памяти (кроме счётчика, конечно) решается за O(N^2) беготни по вагонам http://forum.academ.org/html/emoticons/smile.gif с 2 битами - в два раза быстрее ;)

Мне вот тут интересно стало, неужели год работы - это вообще за стаж не считается? В "серъёзных" компаниях отбирают только людей, которые работали от 3х лет и больше? А где же тогда люди работают первые три года? Где придётся? http://forum.academ.org/html/emoticons/sad.gif

QUOTE Вопрос в том, есть ли алгоритм построения графа быстрее чем за O(n^3) операций?А зачем нужен полный граф? Он и в память может не влезть http://forum.academ.org/html/emoticons/smile.gif Насколько я понимаю, алгоритм поиска кратчайшего пути даст не лучше, чем O(N^2) в худшем случае. Проверить видимость можно не быстрее, чем O(N), значит, в итоге получим решение не лучше, чем O(N^3).. Вроде так. Тогда моё решение хорошее ;)

я делал так 1. fdisk /dev/sda - создал две партиции, первая 2 мега, вторая - всё остальное 2. mkfs /dev/sda1 mkfs -t vfat /dev/sda2 3. скинул на первую партицию файлы из /boot/grub/ 4. /bin/grub > root (hd1,0) > setup (hd1,0) ну и поправил настройки граба как надо потом положил что нужно было загрузить на вторую партицию и оно грузилось, но почему-то только на таких же компах http://forum.academ.org/html/emoticons/sad.gif при желании на первую партицию можно закатать мини-линукс, например, один из тех, которые на дискетку влазят http://forum.academ.org/html/emoticons/smile.gif

ну а точный ответ такой Binomial[480,99]= 56022099933742134542905898577582110805929050272389790\ 1281458809527214479570631168198385673295159633481600 считается, например, по треугольнику Паскаля, вот только до 480ой строчки ручками считать долго придётся http://forum.academ.org/html/emoticons/smile.gif

Я же добавил в граф начальную и конечную вершины => если отрезок, соединяющий нач. и кон. вершины, является решением, то он будет найден "пометка о прямой видимости" Формально нужен ещё один граф (полный), определяющий, видно ли из i-ой вершины j-ую (т.е. существует отрезок, соединяющий вершину i с вершиной j и не пересекающийся с исходными отрезками). А вот если бы я писал реализацию алгоритма, то никаких дополнительных структур я бы не добавлял, а просто считал бы, что расстояние между двумя точками, не находящимся в прямой видимости, равно 1e100 http://forum.academ.org/html/emoticons/smile.gif Поэтому я так написал, думал понятно будет :Х

Аргументацию в студию! http://forum.academ.org/html/emoticons/smile.gif Чем плохо моё решение Строим граф на вершинах отрезков + начальная и конечная точки, значениями на рёбрах являются расстояния между соотв. точками или пометка об отсутствии прямой видимости. Тогда решением задачи будет путь минимальной длины в таком графе. С учётом проверки видимости получаем O(N^3). Что не так?

Динамическое программирование вполне соотносится с условием задачи, т.к. простой перебор даст что-нибудь вроде O(N!) по числу вершин N => при достаточно больших N программа будет считать ну оооочень долго http://forum.academ.org/html/emoticons/smile.gif Поэтому правильное решение - применять алгоритмы динамического программирования, например, в этом случае по-моему подойдёт алгоритм Дейкстры O(N^2). Что-то слишком простая задачка... Или O(N^2) не хватает? ;)

остаётся только вопрос, откуда взялось таинственное число 4... почему не 1 и 2, 1 и 3, 1 и 5, 2 и 3, и другие комбинации?

f(2x) = 2f(x)+f(x)^2 f(2x)-2f(x) = f(x)^2 >= 0 f(2x) >= 2f(x) Значит а) f(x)=const (решения, ясно дело, 0 и -1) б) Пусть f(x) <> const Тогда f(x)->0 при x->(-infinity) устремляем в исходной формуле x->(-infinity), а y = const 0 = 0+f(y)+0*f(y) => f(y) = 0 для любого y => противоречие Значит существуют только два решения 0 и -1 QUOTE Всё гораздо прощеА как проще?

Физически поверхностная/свободная энергия - это, действительно, термодинамика. Можно посмотреть в книжке. Если интересует на пальцах - то проще в интернете найти. Например, первая ссылка в гугле А адсорбция - это уже более специализированная вещь, в таких терминах химики мыслят, а не физики ;)

Я не помню, что конкретно, но Иванов перечислял, что там потребуется, и там были не совсем тривиальные вещи.

Докторскую на прилипании пузыриков к шоколаду... ынтиресно... Может вы за "открытие" поверхностной энергии (силы поверхностного натяжения) ещё нобелевку давать будете? =) QUOTE ("SloNIK")во вторых ясно, что слишком большие кусочки тоже не будут всплывать.Да, не будут, и вы уже написали, почему - отношение площади к массе уменьшается. Налипает меньше пузыриков на единицу массы и утянуть не могут. QUOTE ("SloNIK")ну а в третьих, если выделяется газ, то надо как-то термодинамику сюда приплестиhttp://forum.academ.org/html/emoticons/blink.gif Это ещё зачем? Ну выделяется и выделяется, что мы хотим получить из термодинамики? QUOTE ("Dagaz")надо добавить что всплывают по ссылке на закон Архимеда В)Чьорт побьери, забыл =) Модератор: правило 4 раздела "Задачник": QUOTE 4. В форуме "Задачник" любое намеренное искажение орфографии считается агрессивным орфоартом (тем самым противоречащим правилу 10). считать классику орфоартом - это уже слишком

Ну а какое более подробное объяснение требуется? Прилипают пузырьки, тянут вверх, когда пузырьков достаточно налипло - всплывает. Что неясно-то? http://forum.academ.org/html/emoticons/blink.gif

QUOTE На вашей картинке видно, что Мн-во прилежащих клеток не связно, и виной тому - граница доски.То есть как это не связно? http://forum.academ.org/html/emoticons/blink.gif Прилежащие клетки обозначены красным кружком в центре. И множество этих клеток К-связно.. Или я что-то не понял? Если вы имеете в виду зелёные клетки - то это клетки, доступные ладье, идущей слева. Действительно, в пределах поля это множество несвязно. Поэтому я его и расширил, дорисовав слева ряд клеток. С учётом этих клеток множество вроде Л-связно http://forum.academ.org/html/emoticons/unsure.gif. QUOTE А почему нам так не решать? Стартовать с края и искать компоненту, выходящую на второй край...Непонянто как-то.. Допустим, что мы не нашли такую компоненту ни снизу вверх, ни слева направо. Неясно, откуда должно взяться противоречие. Опять же надо рассматривать границы множеств и прилегающие клетки?

Ух ты интересно, где я накосячил в доказательстве невозможности решения http://forum.academ.org/html/emoticons/smile.gif

Ага, у нас такая задачка была от Иванова. Не знаю, может он её каждому курсу даёт.. Кстати, утверждалось, что для решения этой задачки надо нехилый матаппарат привлекать, поэтому собсна за неё автомат и давали.

На плоскости тоже есть решение, если не ограничиваться точечными домами Вот, например, первое, что пришло в голову. Серыми линиями показаны расстояния по 50м, под расстоянием между двумя домами естественно понимается расстояние между двумя ближайшими точками этих домов http://forum.academ.org/html/emoticons/smile.gif Зелёные - "честные" дома, синий - "читерский" дом, красный - уже неважно где находится А для точечных домов я придумал доказательство про невозможность решения на плоскости, вот только уж больно оно длинное. Кто-нибудь знает доказательство "в несколько строк"?

QUOTE Вы имеете в виду ограниченые множества на неограниченной доске?В принципе - да, но в данном случае, наверное, удобнее сразу рассуждать про ограниченную доску. QUOTE Еще - хотелось бы увидеть определение К-односвязности.В принципе, можно и без него обойтись, доказав и используя только вторую часть предложенной теоремы. А вообще, насколько я знаю, односвязность есть возможность стянуть любой замкнутый контур в точку. Только вот как это делается в дискретном множестве я не очень понимаю :Х QUOTE А вообще, приносите бумажки на теннис, обсудим.К сожалению, проблемы с коленкой, врач попугал меня операцией и отправил на томографию, так что пока что не знаю насчет тенниса http://forum.academ.org/html/emoticons/sad.gif QUOTE Кстати, все знают игру "Лайнз". Там шарики бегают по незанятым клеткам, если есть ладейный путь. Значит, программа его всегда находит. Может, и нам поискать алгоритм прохождения?Ну там-то всё ясно http://forum.academ.org/html/emoticons/smile.gif Используется стандартный алгоритм поиска (в ширину/в глубину) кратчайшего пути в графе: исходно мы имеем множество из одной клетки на которой стоит шарик, затем на каждом шаге добавляем в этом множество ближайшие связные незанятые клетки, в итоге получаем все клетки, доступные из исходной (т.е. компоненту связности). QUOTE Без картинок плохо воспринимается.Приаттачил иллюстрацию. Жирная линия показывает границу доски, всё что за границей - дорисовано для удобства. Жёлтым обозначены исходно закрашенные клетки. Зелёным - Л-связное множество клеток, доступных ладье, идущей слева. Красными точками показано множество Л-прилежащих клеток к указанному Л-связному множеству. Это множество - К-связно, что и утверждается в теореме.

На мой взгляд, доказательство удобно построить на следующей теореме: Пусть имеется К-односвязное множество клеток. Тогда множество К-прилежащих к этому множеству клеток будет Л-связным. И наоборот, множество Л-прилежащих клеток к Л-односвязному множеству будет К-связным. Я называю клетку X К-прилежащей к множеству А, если X не принадлежит А, и существует такая клетка Y из А, что множество {X, Y} К-связно. Аналогично для Л-прилежащих клеток. Если доказать эту теорему, то дальше вроде всё понятно - строим множество клеток, доступных королю, идущему с верхнего края доски (кстати удобно дорисовать ещё один ряд клеток сверху/снизу доски, и считать, что они доступны для короля). Это множество К-связно по построению. Дополняем его до К-односвязного множества, можно применять теорему. Ну и тут есть два варианта: 1. Если в этом множестве есть клетка, принадлежащая нижнему ряду доски, то из связности следует, что существует путь для короля. 2. Иначе К-прилежащие клетки образуют Л-связное множество, и существует путь для ладьи (здесь получается не очень строго, возможно, надо немного модифицировать теорему)