Кузнечики
От: A13x США  
Дата: 20.12.19 08:18
Оценка:
Встретился с задачей, показавшейся вначале простой, которой хочется поделиться:

По узлам односвязного списка зацикленного с какого-то узла и начиная с головы этого списка прыгают два кузнечика. Для ясности пронумеруем узлы этого списка, что узел 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)?
Отредактировано 20.12.2019 8:21 A13x . Предыдущая версия .
Re: Кузнечики
От: kov_serg Россия  
Дата: 20.12.19 23:27
Оценка: 6 (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
Re[2]: Кузнечики
От: Somescout  
Дата: 21.12.19 13:18
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>J2=2*J1

Почему?
ARI ARI ARI... Arrivederci!
Re[3]: Кузнечики
От: kov_serg Россия  
Дата: 21.12.19 13:21
Оценка:
Здравствуйте, Somescout, Вы писали:

S>Здравствуйте, kov_serg, Вы писали:


_>>J2=2*J1

S>Почему?
Потому что второй прыгает в два раза чаще.
Re[4]: Кузнечики
От: Somescout  
Дата: 21.12.19 13:44
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>>>J2=2*J1

S>>Почему?
_>Потому что второй прыгает в два раза чаще.
M=9, L=4 => J1 = 5, J2 = 9
Хотя вы правы, для решения задачи данных недостаточно.
ARI ARI ARI... Arrivederci!
Re: Кузнечики
От: rg45 СССР  
Дата: 23.12.19 16:13
Оценка:
Здравствуйте, 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 встеча будет происходить в разных точках, вот и все.
--
Завтра сегодня будет вчера
Re: Кузнечики
От: StatujaLeha на правах ИМХО
Дата: 23.12.19 19:07
Оценка:
Здравствуйте, 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. Что будет, если первый кузнечик прыгнул, а потом второй кузнечик после первого прыжка встретил первого кузнечика?
Re[2]: Кузнечики
От: A13x США  
Дата: 27.12.19 22:39
Оценка:
Здравствуйте, 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

Все верно! Я потратил пару дней, так как загодя считал, что это возможно и схожий результат как приведено выше счел ошибкой. Лишь построив контрпример понял, что ошибался.
Re[3]: Кузнечики
От: Erop Россия  
Дата: 05.03.20 10:44
Оценка:
Здравствуйте, 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)

Печатает
1: 0->1; 2->3->4
2: 1->2; 4->1->2
(2, 6)
1: 0->1; 2->3->2
2: 1->2; 2->3->2
(2, 6)
!!!Ups: (2, 6): (1, 4), (2, 3)!!!
!!!Ups: (2, 6): (2, 5), (2, 3)!!!
!!!Ups: (3, 8): (2, 6), (1, 5)!!!
!!!Ups: (4, 10): (2, 7), (1, 6)!!!
!!!Ups: (5, 12): (2, 8), (1, 7)!!!
!!!Ups: (6, 14): (2, 9), (1, 8)!!!


А если чутка допилить, то...
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]))}" )

(2, 6): ((1, 4), (2, 3), (2, 5))
(3, 7): ((3, 4), (3, 6))
(3, 8): ((1, 5), (2, 6), (3, 7))
(4, 10): ((1, 6), (2, 7), (3, 5), (3, 8), (4, 5), (4, 6), (4, 9))
(5, 11): ((5, 6), (5, 7), (5, 10))
(5, 12): ((1, 7), (2, 8), (3, 9), (4, 10))
(6, 14): ((1, 8), (2, 9), (3, 10), (4, 7), (5, 8), (6, 7), (6, 9))
(7, 15): ((7, 8), (7, 10))
(7, 16): ((1, 9), (2, 10), (6, 8), (7, 9))
(8, 18): ((1, 10), (5, 9), (6, 10), (8, 9))
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re: Кузнечики
От: Erop Россия  
Дата: 06.03.20 08:06
Оценка:
Здравствуйте, A13x, Вы писали:

A>Встретился с задачей, показавшейся вначале простой, которой хочется поделиться:


А не откроешь, зачем это было нужно? Откуда взялась задача?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.