Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)
Re[2]: Еще задачка
От:
Аноним
Дата:
26.08.02 05:19
Оценка:
Здравствуйте Nikto, Вы писали:
N>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)
Здравствуйте Аноним, Вы писали:
А>Здравствуйте Nikto, Вы писали:
N>>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)
А>На север, однако.
Здравствуйте Nikto, Вы писали:
N>Здравствуйте Аноним, Вы писали:
А>>Здравствуйте Nikto, Вы писали:
N>>>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)
А>>На север, однако.
N>А точнее?
На северном магнитном полюсе, если идти по компасу.
Здравствуйте Boroda, Вы писали:
B>Здравствуйте Nikto, Вы писали:
N>>Здравствуйте Аноним, Вы писали:
А>>>Здравствуйте Nikto, Вы писали:
N>>>>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)
А>>>На север, однако.
N>>А точнее?
B>На северном магнитном полюсе, если идти по компасу.
А если не по компасу? Допустим ты знаешь в каждой точке куда нужно сделать шаг чтобы шагнуть на северо-восток...
З.Ы.: Про компас, кстати, ничего сказано не было...
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте KonstantinA, Вы писали:
fAX>>>1. Есть 27 шариков. fAX>>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.) fAX>>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".
fAX>>>Удачи.
fAX>Теперь по теме. К сожалению ( :shuffle: ), явной ошибки я пока обнаружить не смог. У меня есть некоторые соображения, но об этом после. Вы не могли бы пояснить Теорему 2 (и, если можно, поменять индексы, а то "1" и "l" очень похожи, отчего плохо воспринимаются. Спасибо.
fAX>ЗЫ. Я всё же думаю, что знаю, что и где не так, но хочу дождаться Вашего ответа на этот пост. fAX>ЗЗЫ. Я сейчас лихорадочно вспоминаю решение как самый сильный аргумент :)
fAX>fAX
KA>>Пронумеруем шарики от 1 до 27. KA>>Определение (n,sign) --- конфигурация, где шарик n неправильный и тяжелее, если sign == +1, и легче, если sign == -1. KA>>Определение Алгоритм --- следующая последовательность действий KA>>(шаг 0). выбираем 0 < a <= 13, ( k_1, ..., k_a ) и ( p_1, ..., p_a ), где все k_i, p_j попарно различны и лежат в интервале [1,27]. KA>>(шаг 1). Кладем на весы по а шариков ( k_1, ..., k_a ) и ( p_1, ..., p_a ), смотрим результат pвзвешивания KA>>(шаг 2). KA>>a) Если шаг 1 выполнялся меньше 3 раз, то по итогам предыдущих результатов взвешивания выбираем a, ( k_1, ..., k_a ) и ( p_1, ..., p_a ). Идем на (шаг 1). KA>>a) Если шаг 1 выполнялся 3 раза, то выход.
KA>>Определение Результат работы алгоритма на конфигурации (n,sign) --- это те конфигурации (a_1,sign_1)...(a_k,sign_k), для которых результаты всех взвешиваний в процессе работы такие же как и для (n,sign). Обозначение A(n,sign) = (a_1,sign_1) + ... + (a_2, sign_2). KA>>Утверждение A(n_1,sign_1) == A(n_2,sign_2) либо A(n_1,sign_2) не пересекает A(n_2,sign_2). KA>>Определение Множество эквивалентности для A --- те конфигурации (a_1,sign_1),..., (a_k, sign_k), для которых A(a_1,sign_1) == ... == A(a_k, sign_k) и для любого (a,sign) не из этого множества A(a_i,sign_i) != A(a,sign)
KA>>Теорема 1 Для любого алгоритма A число множеств эквивалентности не превосходит 27 KA>>Доказательство KA>>Результатов взвешивания 3 * 3 * 3 = 27, а одному результату взвешиваний соответствует не более одного множества эквивалентности.
KA>>Обозначение (n,*) = (n,+) + (n,-) KA>>Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*). KA>>Определение Пусть A решает задачу нахождения неправильного шарика, тогда n число KA>>--- типа 1 для алгоритма A, если A(n,sign) == (n,sign) для любого sign (обозначим такие числа A1) KA>>--- типа 2 для алгоритма A, если A(n,sign) == (n,*) (обозначим такие числа A2) KA>>Замечание Каждое число от 1 до 27 является либо числом типа 1, либо числом типа 2 для данного алгоритма, решающего задачу нахождения шарика.
KA>>Теорема 2 Пусть A решает задачу нахождения неправильного шарика, тогда A1 не пусто. KA>>Доказательство KA>>k1 из шага 0 лежит в А1, т.к. мы знаем результаты взвешивания на первом шаге, поэтому A(k1,sign)=(k1,sign)
Пояснение
При фиксированном алгоритме у нас на первом шаге фиксированы a (k_1,...,k_a) и (p_1,...p_a). Рассмотрим конфигурацию (k_1,sign). Тогда A(k_1,sign)=(k_1,sign) или A(k_1,sign)=(k_1,*). Докажем, что второй вариант невозможен. Действительно для конфигураций (k_1,+) и (k_1,-) мы имеем разные результаты взвешивания на первом шаге, поэтому A(k_1,+) != A(k_1,-). Следовательно A(k_1,sign)=(k_1,sign).
То же верно в отношении k_2,..., k_a, p_1,..., p_a (выбранные на первом шаге).
KA>>Теорема 3 Пусть А --- алгоритм решающий задачу нахождения неправильного шарика, тогда каждое множество эквивалентности для A это KA>>либо {(n,+), если n из A1}, KA>>либо {(n,-), если n из A1}, KA>>либо {(n,*), если n из A2}. KA>>Поэтому количество множеств эквивалентности = 27 + количество чисел типа A1.
KA>>Скомбинируем теорему 1, теорему 2, теорему 3 и все :shuffle:
N>А если не по компасу? Допустим ты знаешь в каждой точке куда нужно сделать шаг чтобы шагнуть на северо-восток...
N>З.Ы.: Про компас, кстати, ничего сказано не было...
Тогда на северный полюс.(где ось земли)
З.Ы.
А как же без компаса на север-то ходить?
Заблудишься.
Здравствуйте Boroda, Вы писали:
B>Здравствуйте Nikto, Вы писали:
N>>А если не по компасу? Допустим ты знаешь в каждой точке куда нужно сделать шаг чтобы шагнуть на северо-восток...
N>>З.Ы.: Про компас, кстати, ничего сказано не было...
B>Тогда на северный полюс.(где ось земли)
Тогда правильно . Если б еще доказательство... Но мне оно не интересно .
B>З.Ы. B>А как же без компаса на север-то ходить? B>Заблудишься.
Здравствуйте fAX, Вы писали:
fAX>Кстати, на задачу с диском так и не было удовлетворительного ответа. Равно, как и на задачу с разбойниками от KonstantinA.
fAX>Нехорошо...
Насчет диска все довольно просто.
Имеется два возможных сочетания среди 4-х переключателей.
1). Два переключателя в одном положении, два в другом.
2). Три переключателя в одном положении, один в другом.
Алгоритм.
1. Переключить два выключателя, находящиеся напротив друг друга.
2. Переключить два выключателя, находящиеся рядом.
3. Переключить два выключателя, находящиеся напротив друг друга.
Очевидно, что проделав эти шаги мы однозначно добъемся того, чтоб загорелась лампочка если первоначальное состояние выключателей удовлетворяло условию (1).
А в случае, если первоначально состояние выключателей удовлетворяло условию (2), то после трех шагов, соотношение так и останется 3:1. Тогда прдолжаем.
4. Переключаем 3 выклюмателя.
Соотношение стало 2:2.
После чего повторяем 1,2,3 шаги.
PS. Если для того чтоб загорелась лампочка нужно не просто, чтоб все выключатели были в одинаковом положении, а именно в каком-то определенном, то после каждого шага алгоритма можно переключать 4-ре выключателя.
Здравствуйте fAX, Вы писали:
fAX>Кстати, на задачу с диском так и не было удовлетворительного ответа. Равно, как и на задачу с разбойниками от KonstantinA.
fAX>Нехорошо... :shuffle: :shuffle: :shuffle: :(
Здравствуйте KonstantinA, Вы писали:
KA>>Возможно работает все правильно, но это далеко не оптимально. KA>>Уточню задачу: KA>>найти оптимальный алгоритм по затратам времени и памяти (сколько чего тратить на усмотрение решающего). Более оптимальное решение есть!
KA>Да кстати совсем не обязательно находить эту последовательность...
Думал, думал ...
Вот до чего додумался:
Как-то так изменяем данную последовательность, что длина самой длинной подпоследовательности не меняется — подойдет, анпример, любая монотонная функция, примененая к каждому члену последовательности.
А дальше ничего не придумал
Я хотя бы в правильном направлении мыслю?
Здравствуйте KonstantinA, Вы писали:
KA>Имеется последовательность x_1, ..., x_n. KA>Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.
KA>Задача: KA>По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.
Довольно простая задача на динамическое программирование.
Здравствуйте Rumata, Вы писали:
R>Здравствуйте KonstantinA, Вы писали:
KA>>>Возможно работает все правильно, но это далеко не оптимально. KA>>>Уточню задачу: KA>>>найти оптимальный алгоритм по затратам времени и памяти (сколько чего тратить на усмотрение решающего). Более оптимальное решение есть!
KA>>Да кстати совсем не обязательно находить эту последовательность...
R>Думал, думал ...
R>Вот до чего додумался: R>Как-то так изменяем данную последовательность, что длина самой длинной подпоследовательности не меняется — подойдет, анпример, любая монотонная функция, примененая к каждому члену последовательности.
R>А дальше ничего не придумал :crash: R>Я хотя бы в правильном направлении мыслю? :???:
Не знаю, что это может дать, но к известному мне решению это не имеет никакого отношения... :(
Re[2]: Еще задачка
От:
Аноним
Дата:
26.08.02 11:31
Оценка:
Здравствуйте Nikto, Вы писали:
N>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)
На мой вгляд — на Сверней полюс(или бесконечно близко к нему).
Sam from Il.
Здравствуйте achp, Вы писали:
A>Здравствуйте KonstantinA, Вы писали:
KA>>Имеется последовательность x_1, ..., x_n. KA>>Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.
KA>>Задача: KA>>По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.
A>Довольно простая задача на динамическое программирование. A> :))
Здравствуйте Rumata, Вы писали:
R>Здравствуйте achp, Вы писали:
A>>Довольно простая задача на динамическое программирование. A>> :))
R>По словам "динамическое программирование" ее решение ищется влет: R>http://algolist.manual.ru/olimp/rec_sol.php#a20
R>Вот только я так и не понял, какой из вариантов решения имел в виду KonstantinA
Здравствуйте KonstantinA, Вы писали:
KA>Здравствуйте fAX, Вы писали:
fAX>>Кстати, на задачу с диском так и не было удовлетворительного ответа. Равно, как и на задачу с разбойниками от KonstantinA.
fAX>>Нехорошо...
KA>По поводу диска чем не нравиться cool site
Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
KA>Здравствуйте fAX, Вы писали:
fAX>>Здравствуйте KonstantinA, Вы писали:
fAX>>>>1. Есть 27 шариков. fAX>>>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.) fAX>>>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".
fAX>>>>Удачи.
fAX>>Теперь по теме. К сожалению ( ), явной ошибки я пока обнаружить не смог. У меня есть некоторые соображения, но об этом после. Вы не могли бы пояснить Теорему 2 (и, если можно, поменять индексы, а то "1" и "l" очень похожи, отчего плохо воспринимаются. Спасибо.
fAX>>ЗЫ. Я всё же думаю, что знаю, что и где не так, но хочу дождаться Вашего ответа на этот пост. fAX>>ЗЗЫ. Я сейчас лихорадочно вспоминаю решение как самый сильный аргумент
fAX>>fAX
KA>>>Пронумеруем шарики от 1 до 27. KA>>>Определение (n,sign) --- конфигурация, где шарик n неправильный и тяжелее, если sign == +1, и легче, если sign == -1. KA>>>Определение Алгоритм --- следующая последовательность действий KA>>>(шаг 0). выбираем 0 < a <= 13, ( k_1, ..., k_a ) и ( p_1, ..., p_a ), где все k_i, p_j попарно различны и лежат в интервале [1,27]. KA>>>(шаг 1). Кладем на весы по а шариков ( k_1, ..., k_a ) и ( p_1, ..., p_a ), смотрим результат pвзвешивания KA>>>(шаг 2). KA>>>a) Если шаг 1 выполнялся меньше 3 раз, то по итогам предыдущих результатов взвешивания выбираем a, ( k_1, ..., k_a ) и ( p_1, ..., p_a ). Идем на (шаг 1). KA>>>a) Если шаг 1 выполнялся 3 раза, то выход.
KA>>>Определение Результат работы алгоритма на конфигурации (n,sign) --- это те конфигурации (a_1,sign_1)...(a_k,sign_k), для которых результаты всех взвешиваний в процессе работы такие же как и для (n,sign). Обозначение A(n,sign) = (a_1,sign_1) + ... + (a_2, sign_2). KA>>>Утверждение A(n_1,sign_1) == A(n_2,sign_2) либо A(n_1,sign_2) не пересекает A(n_2,sign_2). KA>>>Определение Множество эквивалентности для A --- те конфигурации (a_1,sign_1),..., (a_k, sign_k), для которых A(a_1,sign_1) == ... == A(a_k, sign_k) и для любого (a,sign) не из этого множества A(a_i,sign_i) != A(a,sign)
KA>>>Теорема 1 Для любого алгоритма A число множеств эквивалентности не превосходит 27 KA>>>Доказательство KA>>>Результатов взвешивания 3 * 3 * 3 = 27, а одному результату взвешиваний соответствует не более одного множества эквивалентности.
KA>>>Обозначение (n,*) = (n,+) + (n,-) KA>>>Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*). KA>>>Определение Пусть A решает задачу нахождения неправильного шарика, тогда n число KA>>>--- типа 1 для алгоритма A, если A(n,sign) == (n,sign) для любого sign (обозначим такие числа A1) KA>>>--- типа 2 для алгоритма A, если A(n,sign) == (n,*) (обозначим такие числа A2) KA>>>Замечание Каждое число от 1 до 27 является либо числом типа 1, либо числом типа 2 для данного алгоритма, решающего задачу нахождения шарика.
KA>>>Теорема 2 Пусть A решает задачу нахождения неправильного шарика, тогда A1 не пусто. KA>>>Доказательство KA>>>k1 из шага 0 лежит в А1, т.к. мы знаем результаты взвешивания на первом шаге, поэтому A(k1,sign)=(k1,sign) KA>Пояснение KA>При фиксированном алгоритме у нас на первом шаге фиксированы a (k_1,...,k_a) и (p_1,...p_a). Рассмотрим конфигурацию (k_1,sign). Тогда A(k_1,sign)=(k_1,sign) или A(k_1,sign)=(k_1,*). Докажем, что второй вариант невозможен. Действительно для конфигураций (k_1,+) и (k_1,-) мы имеем разные результаты взвешивания на первом шаге, поэтому A(k_1,+) != A(k_1,-). Следовательно A(k_1,sign)=(k_1,sign). KA>То же верно в отношении k_2,..., k_a, p_1,..., p_a (выбранные на первом шаге).
KA>>>Теорема 3 Пусть А --- алгоритм решающий задачу нахождения неправильного шарика, тогда каждое множество эквивалентности для A это KA>>>либо {(n,+), если n из A1}, KA>>>либо {(n,-), если n из A1}, KA>>>либо {(n,*), если n из A2}. KA>>>Поэтому количество множеств эквивалентности = 27 + количество чисел типа A1.
KA>>>Скомбинируем теорему 1, теорему 2, теорему 3 и все
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
. Если б еще доказательство... Но мне оно не интересно 
. 
