Встретился с задачей, показавшейся вначале простой, которой хочется поделиться:
По узлам односвязного списка зацикленного с какого-то узла и начиная с головы этого списка прыгают два кузнечика. Для ясности пронумеруем узлы этого списка, что узел 0 — голова списка, узел 1 — следующий за головой, узел 2 — следующий за 1-м узлом и т.д.
1. На самом первом шаге первый кузнечик помещается в узел 0 и не делает прыжков.
2. На каждом следующем шаге первый кузнечик прыгает на непосредственно следующий узел.
3. Второй кузнечик "шустрее" первого и делает за шаг два последовательных прыжка, но всегда после того, как прыгает первый кузнечик. На самом первом шаге второй кузнечик успевает прыгнуть на узел 1 и затем на узел 2. Далее, например, на втором шаге первый кузнечик прыгает в узел 1, а второй прыгает в узел 3 и затем в узел 4, на 3-м шаге первый прыгает в узел 2, а второй — в узел 5 и затем в узел 6 и так далее.
4. Как было сказано вначале, список зациклен, таким образом, что если кузнечик прыгает на следующий узел с некоторого узла M он попадает на узел N встречавшийся ранее. Считаем, что 0 < N < M.
Когда второй кузнечик встречает первого кузнечика на некотором прыжке некоторого шага, процесс останавливается.
Можно ли назвать количество узлов для части списка до начала цикла, если известны:
1. Количество прыжков первого и второго кузнечика до остановки (допустим J1 и J2)?
2. Количество узлов L в части списка, составляющей цикл (очевидно L = M — N + 1)?
Здравствуйте, A13x, Вы писали:
A>Встретился с задачей, показавшейся вначале простой, которой хочется поделиться:
A>По узлам односвязного списка зацикленного с какого-то узла и начиная с головы этого списка прыгают два кузнечика. Для ясности пронумеруем узлы этого списка, что узел 0 — голова списка, узел 1 — следующий за головой, узел 2 — следующий за 1-м узлом и т.д.
A>1. На самом первом шаге первый кузнечик помещается в узел 0 и не делает прыжков. A>2. На каждом следующем шаге первый кузнечик прыгает на непосредственно следующий узел. A>3. Второй кузнечик "шустрее" первого и делает за шаг два последовательных прыжка, но всегда после того, как прыгает первый кузнечик. На самом первом шаге второй кузнечик успевает прыгнуть на узел 1 и затем на узел 2. Далее, например, на втором шаге первый кузнечик прыгает в узел 1, а второй прыгает в узел 3 и затем в узел 4, на 3-м шаге первый прыгает в узел 2, а второй — в узел 5 и затем в узел 6 и так далее. A>4. Как было сказано вначале, список зациклен, таким образом, что если кузнечик прыгает на следующий узел с некоторого узла M он попадает на узел N встречавшийся ранее. Считаем, что 0 < N < M.
A>Когда второй кузнечик встречает первого кузнечика на некотором прыжке некоторого шага, процесс останавливается.
A>Можно ли назвать количество узлов для части списка до начала цикла, если известны:
Нет. Две неизвестных, одна переменная. A>1. Количество прыжков первого и второго кузнечика до остановки (допустим J1 и J2)? A>2. Количество узлов L в части списка, составляющей цикл (очевидно L = M — N + 1)?
J2=2*J1
J1=(n1+2)*L if n0==0
J1=(n1+1)*L if n0!=0
где N=n1*L+n0, n0 и n1 целые числа >=0
Здравствуйте, kov_serg, Вы писали:
_>>>J2=2*J1 S>>Почему? _>Потому что второй прыгает в два раза чаще.
M=9, L=4 => J1 = 5, J2 = 9
Хотя вы правы, для решения задачи данных недостаточно.
Здравствуйте, A13x, Вы писали:
A>Можно ли назвать количество узлов для части списка до начала цикла, если известны: A>1. Количество прыжков первого и второго кузнечика до остановки (допустим J1 и J2)? A>2. Количество узлов L в части списка, составляющей цикл (очевидно L = M — N + 1)?
Нет, нельзя. Для любого набора входных данных, при которых задача имеет решение (L > 0; J1 = k*L; k — натуральное), искомая длина "хвостика", обозначим ее X, может быть любой в диапазоне [J1-L, J1]. Да-да, J1 кратно L — это необходимое условие встречи. А J2 = 2*J1, это очевидно. Простейший пример: L = 10, J1 = 10, J2 = 20. X может быть любым от 0 до 10. Просто при разных X встеча будет происходить в разных точках, вот и все.
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, A13x, Вы писали:
A>Встретился с задачей, показавшейся вначале простой, которой хочется поделиться:
A>По узлам односвязного списка зацикленного с какого-то узла и начиная с головы этого списка прыгают два кузнечика. Для ясности пронумеруем узлы этого списка, что узел 0 — голова списка, узел 1 — следующий за головой, узел 2 — следующий за 1-м узлом и т.д.
A>1. На самом первом шаге первый кузнечик помещается в узел 0 и не делает прыжков. A>2. На каждом следующем шаге первый кузнечик прыгает на непосредственно следующий узел. A>3. Второй кузнечик "шустрее" первого и делает за шаг два последовательных прыжка, но всегда после того, как прыгает первый кузнечик. На самом первом шаге второй кузнечик успевает прыгнуть на узел 1 и затем на узел 2. Далее, например, на втором шаге первый кузнечик прыгает в узел 1, а второй прыгает в узел 3 и затем в узел 4, на 3-м шаге первый прыгает в узел 2, а второй — в узел 5 и затем в узел 6 и так далее. A>4. Как было сказано вначале, список зациклен, таким образом, что если кузнечик прыгает на следующий узел с некоторого узла M он попадает на узел N встречавшийся ранее. Считаем, что 0 < N < M.
A>Когда второй кузнечик встречает первого кузнечика на некотором прыжке некоторого шага, процесс останавливается.
A>Можно ли назвать количество узлов для части списка до начала цикла, если известны: A>1. Количество прыжков первого и второго кузнечика до остановки (допустим J1 и J2)? A>2. Количество узлов L в части списка, составляющей цикл (очевидно L = M — N + 1)?
1. Я правильно понимаю, что после первого шага координата первого кузнечика будет 0, а второго — 2?
2. Что будет, если встреча произойдет после того, как прыгнет первый кузнечик?
3. Что будет, если первый кузнечик прыгнул, а потом второй кузнечик после первого прыжка встретил первого кузнечика?
Здравствуйте, kov_serg, Вы писали:
_>Здравствуйте, A13x, Вы писали:
A>>Встретился с задачей, показавшейся вначале простой, которой хочется поделиться:
A>>По узлам односвязного списка зацикленного с какого-то узла и начиная с головы этого списка прыгают два кузнечика. Для ясности пронумеруем узлы этого списка, что узел 0 — голова списка, узел 1 — следующий за головой, узел 2 — следующий за 1-м узлом и т.д.
A>>1. На самом первом шаге первый кузнечик помещается в узел 0 и не делает прыжков. A>>2. На каждом следующем шаге первый кузнечик прыгает на непосредственно следующий узел. A>>3. Второй кузнечик "шустрее" первого и делает за шаг два последовательных прыжка, но всегда после того, как прыгает первый кузнечик. На самом первом шаге второй кузнечик успевает прыгнуть на узел 1 и затем на узел 2. Далее, например, на втором шаге первый кузнечик прыгает в узел 1, а второй прыгает в узел 3 и затем в узел 4, на 3-м шаге первый прыгает в узел 2, а второй — в узел 5 и затем в узел 6 и так далее. A>>4. Как было сказано вначале, список зациклен, таким образом, что если кузнечик прыгает на следующий узел с некоторого узла M он попадает на узел N встречавшийся ранее. Считаем, что 0 < N < M.
A>>Когда второй кузнечик встречает первого кузнечика на некотором прыжке некоторого шага, процесс останавливается.
A>>Можно ли назвать количество узлов для части списка до начала цикла, если известны: _>Нет. Две неизвестных, одна переменная. A>>1. Количество прыжков первого и второго кузнечика до остановки (допустим J1 и J2)? A>>2. Количество узлов L в части списка, составляющей цикл (очевидно L = M — N + 1)? _>J2=2*J1 _>J1=(n1+2)*L if n0==0 _>J1=(n1+1)*L if n0!=0 _>где N=n1*L+n0, n0 и n1 целые числа >=0
Все верно! Я потратил пару дней, так как загодя считал, что это возможно и схожий результат как приведено выше счел ошибкой. Лишь построив контрпример понял, что ошибался.
Здравствуйте, A13x, Вы писали:
A>Все верно! Я потратил пару дней, так как загодя считал, что это возможно и схожий результат как приведено выше счел ошибкой. Лишь построив контрпример понял, что ошибался.
Да ты крут!!!
def correct_pos( pos, N, L ) :
"""
Возвращает правильный номер узла в зацикленном списке
"""return pos if pos <= N else (pos-N)%L + N
def play_the_game( N, M, dump_it=False ) :
"""
Возвращает J1 и J2 в момент встречи
"""
J1, pos1 = 0, 0
J2, pos2 = 2, 2
L = M - N + 1
while pos1 != pos2 :
J1 += 1
if dump_it :
print(end=f"{J1}: {pos1}->")
pos1 = correct_pos( pos1+1, N, L )
if dump_it :
print(end=f"{pos1}; {pos2}->")
J2 += 1
pos2 = correct_pos( pos2+1, N, L )
if pos1 != pos2 :
if dump_it :
print(end=f"{pos2}->")
J2 += 1
pos2 = correct_pos( pos2+1, N, L )
if dump_it :
print(f"{pos2}")
return J1, J2
print( play_the_game( 1, 4, True ) )
print( play_the_game( 2, 3, True ) )
cache = dict()
for m in range( 2, 10 ) :
for n in range( 1, m ) :
res = play_the_game( n, m )
if res in cache :
print( f"!!!Ups: {res}: {(n, m)}, {cache[res]}!!!")
break
cache[res] = (n, m)
def play_all_games( max_m ) :
cache = dict()
for m in range( 2, max_m+1 ) :
for n in range( 1, m ) :
res = play_the_game( n, m )
if res in cache :
cache[res].add( (n, m) )
else :
cache[res] = {(n, m)}
return cache
cache = play_all_games( 10 )
for res in sorted( cache ):
if len(cache[res]) > 1 :
print( f"{res}: {tuple(sorted(cache[res]))}" )
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, A13x, Вы писали:
A>Встретился с задачей, показавшейся вначале простой, которой хочется поделиться:
А не откроешь, зачем это было нужно? Откуда взялась задача?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
