|
|
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
mayton iOracleDev Обозначим стартовый вагон буковкой A, выключим в нем свет и пойдем по ходу поезда, идем пока свет в вагонах горит, дошли до вагона с выключенным светом, обозначим его буковкой B, включаем в нем свет и идем обратно в A, если в A горит свет, значит мы обошли все вагоны, если свет в A выключен, то включаем его и возвращаемся в вагон B, выключаем в вагоне B свет, назначаем вагон B вагоном A и далее повторяем описанную процедуру, до тех пор пока не обнаружим в A свет. Если будет дан поезд с 1000 вагонами где свет включен в четных вагонах и выключен в нечётных (worst case) данный алгоритм КМК все таки получаем квадратичную сложность. Под элементарной операцией я подразумеваю движение в любую сторону и действия со светом. Если я прав - то состав с 2000 вагонами приведет к увеличению количества операций не в два а в большую величину. Увеличение в два раза увеличит операции в два раза. Тут я пример обхода давал 22060734 PS Худший случай - свет везде потушен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2020, 07:56 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Твой пример с указателями? Дима в поезде нет указателей. Чтобы проверить инверсию света в первом вагоне тебе надо в этот первый вагон физически добежать. Тоесть вернуться обратно сделав N шагов алгоритма. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2020, 11:05 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
mayton Твой пример с указателями? Дима в поезде нет указателей. Чтобы проверить инверсию света в первом вагоне тебе надо в этот первый вагон физически добежать. Тоесть вернуться обратно сделав N шагов алгоритма. фишка в том, что в режиме "обратного хода" он проходит через каждый вагон ровно один раз, никакой вагон не посещается дважды ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2020, 11:21 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
mayton, просто возьми бумагу и ручку, и проверь описанный алгоритм для двух-трех случаев. Все вопросы отпадут ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2020, 11:26 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
mayton Твой пример с указателями? Дима в поезде нет указателей. Хоть как называй: указатели, смещения и т.д. и т.п. Александр попросил назвать указателем, я назвал. На работу алгоритма это никак не влияет. mayton Чтобы проверить инверсию света в первом вагоне тебе надо в этот первый вагон физически добежать. Тоесть вернуться обратно сделав N шагов алгоритма. Верно, так и происходит. Прочитай внимательно тот мой пост. Суть алгоритма в том что нет постоянного первого вагона, на каждой итерации другой вагон становиться первым. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2020, 12:40 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 так и не понял, где число 42... Если не ошибся, то умножение на 2 или на 3 переводит любое число в разные классы. В то же время классы не пересекаются согласно формуле: X1= {2^3a * 3^3b}, здесь оба вычета по модулю 3 равны, X2= {2^3c+(1 2 0) * 3^3d+(0 1 2)} , здесь его вычет соответственно (1 2 0) и (0 1 2) X3= {2^3e+(0 1 2) * 3^3f+(1 2 0)}, аналогично , где a b c d e f >=0 (1 2 0) это как бы в векторном виде. По этой классификации 42= 2*3 *(7). Вычеты показателей степени равны, значит Х1, вместе с 1. 2= 2^1 * 3^0, класс Х2 3= 2^0 * 3^1, класс Х3 4= 2^2 * 3^0, класс Х3 6= 2^1 * 3^1, класс Х1 12= 2^2 * 3^1, класс Х2 18= 2^1 * 3^2, класс Х3 и т.д. Как-то так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2020, 19:22 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Добавлю: классная задачка, никогда таких не решал. Здесь в одной куче сразу циклы, вычеты и простые числа. З.Ы. об обобщениях не думал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2020, 19:29 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
exp98, Да, всё верно, здесь именно про вычеты и т.д.) Но интересна эта задача именно в общем виде. Идею можно разглядеть, если решить не для 3, а например для 6 или даже лучше для 10. Тогда и появляется вишенка на торте - вопрос о том, можно ли это сделать для любого количества классов. Я пока не понял. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2020, 21:30 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Пока мне кажется, что это зависит от возможности разложить К*К комбинаций вычетов на К циклов с какими-то св-вами. Может "не всё так просто" , та самая клюквочка скажется, не знаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 28.01.2020, 22:10 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
exp98 X1= {2^3a * 3^3b}, здесь оба вычета по модулю 3 равны, X2= {2^3c+(1 2 0) * 3^3d+(0 1 2)} , здесь его вычет соответственно (1 2 0) и (0 1 2) X3= {2^3e+(0 1 2) * 3^3f+(1 2 0)}, аналогично , где a b c d e f >=0 (1 2 0) это как бы в векторном виде. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2020, 12:20 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Ну наверное так и есть. Тут возникла мысль, она же и вопрос на обобщение задачи. Нужно было разбить натуральные числа на 3 непересекающихся класса, а обобщение: разбить на К классов, так? Вы пишете, что общий алгоритм не вырисовывается, хотя для каждого К вроде получается эд хок? Вчера я пораскидал мозги на пробу для 10, сегодня весь день на ходу что-то крутилось в голове. Поток сознания получился вроде того: Если в разложении М отсутствуют все множители из формулировки (*2 *3 *4 ... *К), а любое такое число и мн-во их будем называть А. Класс Х1 будет (предварительно) содержать А. Причём Х1 <> А. Остальные классы назовём Х2 Х3 Х4 ... Есть К классов (ящиков) Х1 Х2 Х3 Х4 ... Хк Есть К-1 множителей (*1) *2 *3 *4 ... *К Для каждого М есть вектор из К произведений (м*1 м*2 м*3 м*4 ... м*К). В т.ч, к примеру, если м1= А*3 , то вектор произведений будет 3*(А*1 А*2 А*3 А*4 ... А*К). Умножение эквивалентно прибавлению 1 в одной координате вектора степеней (a b c d e f g ...). Надо чтобы добавление 1 переводило число в другой класс, и чтобы так было в любом классе. .......... у нас К координат, значит д.б. К значений (e+i). И мы знаем, что a=вычеты по модулю 2 (a=V(2)), b=V(3), c=V(4) ... Так приходим к вектору вычетов и к циклам по вычетам. Вроде К "шестерёнок" на одной оси. Но в каждой к-те своя длина цикла. А если множитель= 7, а классов 10? 7 вычетов нехватает для 10 классов, и 10 не делится на 7 оборотов. А если множитель= 4, то имеем (2^a 3^b 2^2c) ....... Как-то надо использовать НОК(). Так вот предложение есть. Если вдруг ещё нет описания обобщённого решения, если трудно это сделать ручками, может быть программно формировать формулу для каждого К? Причём формировать формулу в текстовом виде (примерно как для К=3 или в виде массивов). Может программа даст опору для формулировки формулы. Я потому имею ввиду текстовую форму, что поначалу не оставляет надежда, что метод для К=3 можно обобщить. Но это пока надежда (искать в инете лень). Голосуйте либо кидайте тухлыми томатами (помидоры нынче отменили). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2020, 21:48 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
exp98 Нужно было разбить натуральные числа на 3 непересекающихся класса, а обобщение: разбить на К классов, так? числа m, 2m, 3m, ..., K*m должны попадали в разные классы, для любого m надо просто обобщить формулу 22068507 Если К=6, то для числа m = (2 a * 3 b * 5 c * X) номер класса получается (1*a + 3*b + 5*с) mod 6 вот в этих числах - в данном случае (1, 3, 5), но для других К будут другие наборы - вся собака и зарыта. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.01.2020, 22:48 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Возился с К=4. В сравнении с 3 тут 2^x покрывает все 4^у. У меня менее красивый метод: все комбинации остатков. Получились след. комбинации наборов остатков (слева единственный столб для 3, справа перестановки для 2 при соответств. 3-вычете). вычеты"3" "2":х1 х2 х3 х40 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2 Для К=5 метод аналогичный, только матрица уже 3Д, и 2-остатки должны быть в комбинации с матрицей "для-3" х "для-5" Что-то похожее для 6. Но есть особенность, *6=2*3 даёт одновременное прибавление по 1 в двух позициях. Поэтому нельзя, чтобы в одной строке матрицы для "2" х "3" стояли однаковые остатки. Похожим способ и далее. Только размерность растёт и метод дальше не получается наглядным. Поэтому и предлагал программку составить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 03.02.2020, 16:52 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
exp98 Возился с К=4. В сравнении с 3 тут 2^x покрывает все 4^у. У меня менее красивый метод: все комбинации остатков. Получились след. комбинации наборов остатков (слева единственный столб для 3, справа перестановки для 2 при соответств. 3-вычете). вычеты"3" "2":х1 х2 х3 х40 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2 здесь каждая дополнительное умножение на 2 добавляет 1 к номеру группы, а умножение на 3 добавляет 3. Умножение на 4 добавляет 2, и таким образом, ничего не накладывается друг на друга. exp98 Что-то похожее для 6. Но есть особенность, *6=2*3 даёт одновременное прибавление по 1 в двух позициях. Поэтому нельзя, чтобы в одной строке матрицы для "2" х "3" стояли однаковые остатки. и когда составляем формулу, надо так подобрать коэффициенты, чтобы эти комбинации не пересекались. Главный вопрос - всегда ли это возможно. например, для 10: (1*a + 4*b + 6*с + 9*d) mod 10, где a, b, c, d - степени при 2, 3, 5, 7, а числа 1,4,6,9 - коэффициенты. для небольших N коэффициенты всегда легко подбираются. Для больших подобрать трудно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.02.2020, 12:31 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 .... как раз это получается по формуле (a+3b) mod 3, в той схеме, которую я приводил ... Для больших подобрать трудно. И для 4 у меня вышло, что (a+3b)mod 4 это ещё одно решение (как и a+7b, a+11b ...) остаток 3, и в рез-те комбинации 00 22 и 11 33 разнеслись в 2 класса А как в моём посте, так это (a+5b)mod 4 остаток 1. И в нём все 00 22 11 33 в одном классе. Что-то не так? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.02.2020, 23:01 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, ещё я вот что хотел спросить. Год назад читал РАН, Дискретная мат-ка, 2004 г, Системы образующих для групп с заданными св-вами. Там про использование сплетения групп и полугрупп, чтобы получать заранее заданные св-ва. Читал, читал, разобрался на <20%. Вдруг наведёт на общее решение. А вообще же одн и тот же алгоритм не бобязан существовать для всей "массовой проблемы". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 04.02.2020, 23:30 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Нашёл, что линейная комбинация необязательна. Ещё есть резерв - показатель степени. Напр К=4 вычеты "3"| "2":х1 х2 х3 х40| 0 1 2 31| 1 2 3 02| 0 1 2 33| 1 2 3 0 формула (b + (a + (b+1)mod 2)) mod 4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 05.02.2020, 20:01 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
exp98 формула (b + (a + (b+1)mod 2)) mod 4 Код: javascript 1. 2. 3. можно легко проверить, что практически для каждой пары (а, b) будут повторы среди f(a,b), f(a+1,b), f(a+2,b), f(a,b+1), а должны быть уникальными. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.02.2020, 13:04 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Эх, всё спутал, сделал как хотел. формула: b+ (a+ 2* (b mod 2)) mod 4 Проверка (по вертикали a=const, по горизонтали b=const): Код: sql 1. 2. 3. 4. 5. Соответствует моей матричной записи: Код: sql 1. 2. 3. 4. 5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.02.2020, 20:34 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
exp98 b+ (a+ 2* (b mod 2)) mod 4 а последние две формулы одинаковы, потому что в кольце вычетов по модулю 4, добавить 3 или вычесть 1 - без разницы итого, от линейной комбинации никуда не ушли. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.02.2020, 21:01 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, Надо же, равенства не проверял, я на бумажке, а на ней изначальные матрицы разнились. Посмотрю ... А вот по поводу 10. Где я ошибаюсь? По поводу формулы для 10: (1*a + 4*b + 6*с + 9*d) mod 10 Написал формализацию задачи, если формула линейная вида k2*a + k3*b + k5*c + k7*d. множители 2 3 5 7 показатели степени a b c d коэф-ты в линейной формуле к2 к3 к5 к7. Общее ограничение: все ki>0 Ограничения на принадлежность одному классу наращиваются с ростом порядка задачи аналогично такому: (k2+k3), (k2+k5) <>0 mod 10, 2*k2, 3*k2, 2*k3 <>0 mod 10. Остатки для линейной формулы с положительными коэф-тами {ki} и с шагом, к-рый соответствует умножению на ki= j ( т.е.цифре при +rj) Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. ... здесь убрал свой вопрос, кажется допёр ... Это ещё не проверял: (a + b + с + d) mod 10. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.02.2020, 22:01 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
exp98 Общее ограничение: все ki>0 Ограничения на принадлежность одному классу наращиваются с ростом порядка задачи аналогично такому: (k2+k3), (k2+k5) <>0 mod 10, 2*k2, 3*k2, 2*k3 <>0 mod 10. общее ограничение можно сделать так 0 < ki <10 потому что в итоге всё равно будет mod 10 вот 9 значений, которые символизируют умножение на 2...10: k2, k3, 2*k2, k5, (k2+k3), k7, 3*k2, 2*k3, (k2+k5) эти значения должны давать разные остатки от деления на 10, причем все остатки больше 0, то есть всего 9 вариантов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 06.02.2020, 23:45 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
проверил программно (a + b + с + d) mod 10 но вдруг ошибся, первый раз ведь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 07.02.2020, 21:50 |
|
||
|
Относительно простые задачки
|
|||
|---|---|---|---|
|
#18+
Соколинский Борис Долго объяснять, я запрограммировал оба варианта Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Думается, SearchUni можно оптимизировать. Как понимаю, суть алгоритма состоит в превращении последовательности всех битов в 1 за исключением единственного 0. При нахождении очередного нуля алгоритм пытается найти следующий и заканчивает свою работу если доходит до стартового нуля. Суть оптимизации: нет смысла возвращаться назад, если расстояние между нулями меньше, чем уже заполненное единицами расстояние. Пример: пройдено 5 битов (установлены в 1), шестой бит нулевой (стартовая точка). Если восьмой бит оказывается нулём, то, он точно не может быть шестым битом=стартовой точкой. Следовательно, нет смысла в проверке на хвост (или голову). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 08.02.2020, 23:12 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=39923650&tid=1339678]: |
0ms |
get settings: |
11ms |
get forum list: |
15ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
161ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
65ms |
get tp. blocked users: |
2ms |
| others: | 245ms |
| total: | 520ms |
| 0 / 0 |
