Форум » Динамическое программирование » 5011 23 задача » Ответить

5011 23 задача

KEVINBEIKAN: Мне кажется, что в условии имели в виду программы в 8 командами. Если так считать, то ответ 28 получится.

Ответов - 9

Фирсов М.: Если у Вас будет 8 команд, то 9 должна повторить первую, чтобы войти в цикл, а это всего один возможный случай. 28 * 1 = 28. Например у Вас начальное число 1, (4 3 2 1) - первый цикл; (4 3 2 1) - второй цикл. Использовалось 8 команд, чтобы начать 3-й цикл, необходимо придти в 4 девятой командой.

yflzu@mail.ru: Я тоже считаю, что 9-я команда лишняя. В Вашем примере начальное число 1 и Вы его получили восьмой командой. Девятая команда даёт второе число, а не начальное.

Поляков: yflzu@mail.ru пишет: Я тоже считаю, что 9-я команда лишняя. В Вашем примере начальное число 1 и Вы его получили восьмой командой. Девятая команда даёт второе число, а не начальное. В условии сказано: "при выполнении которой исполнитель на каком-то этапе вновь получает начальное число.".


yflzu@mail.ru: Спасибо, теперь всё встало на свои места. На каком-то это не обязательно, что на последнем.

Anna967: Все равно не понятен ответ. К этим 28 программам можно дописать любую команду в качестве девятой команды программы (программа по определению все равно останется циклической) - уже 56 программ. А еще есть программы, где цикл завершится после 4-й команды... Не понимаю, почему 28 является правильным ответом.

Фирсов М.: Программа на каком-то этапе возвращается в исходное число, после чего повторяются результаты команд. Вы можете лего заметить то, что для цикла в программе на одно увеличение на 3 должно быть 3 уменьшения на один. Из этого следует, что кол-во команд в цикле программы(не в самой программы), кратно 4. Цикл из 4 команд. 1 2 2 2. Любая перестановка команд. Цикл из 8 команд. 1 1 2 2 2 2 2 2. Любая перестановка команд. Если цикл состоит из 4 команд, то после него цикл должен быть таким же, как и этот. Например, (1 2 2 2) (1 2 2 2). Далее видно, что это возможный случай будет в себя включать всегда включать возможная перестановка цикла из 8 команд. По формуле перестановки с повторениями (8!)/( (8-2)! * (2!) ) = 8 * 7 / 2 = 4 * 7 = 28. 9 командой нельзя взять любую команду, она должна совпадать с 1. Если первая 1, последняя 1. Если 2, то 2. Следовательно, всего один возможный случай 9 команды у каждого случая 28 * 1 = 28. Вы можете придти к этому ответу при помощи программы: [pre2]#формирование возможных маршрутов С = 5 #вместо 5 можно взять любое число a = [ [ С ] ]; k = 9 for _ in range(k): b = [] for i in a: b.append(i + [ i[ -1 ] + 3 ]) b.append(i + [ i[ -1 ] - 1 ]) a = b #ways будет принимать возможные циклические программы, где С встречается более 1 раза. ways = [ ]; for way in a: if way.count(С) >= 2: ways.append(way) #Подсчет подходящих программ. Вывод их количества. cnt = 0 for way in ways: for i in range(2, len(way)): if way[ i: ] == way[ :len(way[ i: ]) ]: cnt += 1; break print(cnt)[/pre2]

Anna967: В условии сказано: Будем называть циклической программу, при выполнении которой исполнитель на каком-то этапе вновь получает начальное число. Например, циклической является программа следующих преобразований: 1  4  3  2  1. Почему Фирсов М. пишет: 9 командой нельзя взять любую команду, она должна совпадать с 1. ?

Поляков: Условие уточнено: Будем называть циклической программу, при выполнении которой исполнитель на каком-то этапе вновь получает начальное число и далее последовательность команд повторяется.

Anna967: О, спасибо!!



полная версия страницы