Форум » Выполнение и анализ алгоритмов для исполнителей » Задание 12 Вариант 1 (№ 5727) (А. Рогов) » Ответить
Задание 12 Вариант 1 (№ 5727) (А. Рогов)
НадеждаТ: Совсем не понимаю, как решать подобные задачи. Цифры (1, 2, 3) расположены в произвольном порядке, их количество одинаково. Как нужно составлять исходную строку? По какому принципу ее потом менять? Не перебирать же все возможные комбинации? Пожалуйста, подскажите!!!
Ответов - 7
MrAndrewson: Здравствуйте. Необходимо проанализировать алгоритм. Рекомендую сделать следующее: возьмите разные входные строки, где цифры расположите по-разному. Посмотрите, что сделает с ними алгоритм.
НадеждаТ: Спасибо, я тоже так делаю. Но вдруг какую-то комбинацию не учту, а она как раз и повлияет на результат? Может есть какой-то другой подход к решению подобных задач?
MrAndrewson: Могу отметить следующий факт: во всех подобных заданиях открытого банка заданий ФИПИ начальное расположение числе в строке никогда не влияет на результат. Он всегда одинаковый. Это соответствует заявленному уровню сложности. На сайте К.Ю. Полякова есть задания, где от начального расположения символов строки результат будет меняться. Как готовиться к таким заданиям - это отдельный разговор. Могу лишь заверить, что в заданиях авторства А. Рогова, как и в заданиях ФИПИ, начальное расположение не влияет на результат.
Ольга Тузова: Здравствуйте. Мне показали (Сергей Мульганов) алгоритм, который можно применить для не очень длинных строк в заданиях, где порядок размещения символов имеет значение. С моими комментариями и небольшой модификацией он представлен ниже. Алгоритм основан на получении всевозможных перестановок и обработкой каждой из них. При этом используется не функция permutations, а shuffle, что значительно ускоряет построение множества перестановок. Но в первоначальном варианте количество элементов множества перестановок для N единиц и N двоек ограничивалось числом 2**N. Почему это так, я не могу понять и Сергей не смог мне объяснить. По моим представлениям, количество перестановок определяется классической формулой (2*N)!/(N!*N!) Это значительно больше, чем 2**N и программа работает дольше. Интересно, что ответ при этом не меняется. Для меня это осталось вопросом - можно рассматривать не все перестановки, только какую-то их часть? Задача [pre2] Дана программа для Редактора: НАЧАЛО ПОКА НЕ нашлось (00) ЕСЛИ нашлось (011) ТО заменить (011, 101) ИНАЧЕ заменить (01, 40) заменить (02, 20) заменить (0222, 1401) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ [/pre2] Известно, что исходная строка A содержала ровно два нуля – на первом и на последнем месте, а также поровну единиц и двоек. После выполнения данной программы получилась строка B, содержащая 6 единиц и 9 двоек. Какое наименьшее количество четвёрок может быть в строке B? Решение: [pre2] rom random import shuffle def fact(n): if n == 1: return 1 else: return n * fact(n-1) def get_set(n): # быстрое получение множества перестановок из n единиц и n двоек a = set() # Начинаем с пустого множества # определяем количество перестановок с повторением для этого n d_set = fact(2*n) / fact(n)**2 while len(a) < d_set: # формируем множество всех перестановок через shuffle line = list(n*"1"+n*"2") # Исходная строка (пока - список) # "Перемешиваем" данные в списке, случайная перестановка shuffle(line) # Преобразуем список в строку, добавляем нули line_new = "0" + "".join(line) + "0" # Добавляем строку в множество, повторений не будет a.add(line_new) return(a) ######################################### def alg(f): # заданный алгоритм while '00' not in f: if '011' in f: f = f.replace('011', '101') else: if '01' in f: f = f.replace('01', '40', 1) if '02' in f: f = f.replace('02', '20', 1) if '0222' in f: f = f.replace('0222', '1401', 1) return f ########## Находим первую строку с 6 единицами и 9 двойками ####### ########## Дальше число четвёрок разве что увеличивается ########## count = 0 got = 0 n = 7 # Выбираем, с какого n начнём поиск while got == 0: # пока не получили нужную строку a = get_set(n) # получаем множество перестановок for line in a: f = alg(line) # применяем к каждому элементу множества алгоритм if f.count('2') == 9 and f.count('1') == 6: count = len(line) - 9 - 6 - 2 # считаем количество четвёрок got = 1 # всё нашли! break n+=1 # Продолжаем поиск с новым n print(count, f, n-1, line) # подробный вывод для проверки [/pre2] Ответ в этой задаче - 3
MrAndrewson: Интересно, такой алгоритм генерации строк действительно куда быстрее. Сравнение двух алгоритмов [pre2]from random import shuffle from itertools import permutations from time import time def fact(n): if n == 1: return 1 else: return n * fact(n-1) def get_set_shuffle(n): # быстрое получение множества перестановок из n единиц и n двоек a = set() # Начинаем с пустого множества # определяем количество перестановок с повторением для этого n d_set = fact(2*n) / fact(n)**2 while len(a) < d_set: # формируем множество всех перестановок через shuffle line = list(n*"1"+n*"2") # Исходная строка (пока - список) # "Перемешиваем" данные в списке, случайная перестановка shuffle(line) # Преобразуем список в строку, добавляем нули line_new = "0" + "".join(line) + "0" # Добавляем строку в множество, повторений не будет a.add(line_new) return(a) def get_set_permutations(n): # получение множества перестановок из n единиц и n двоек a = set() # Начинаем с пустого множества # определяем количество перестановок с повторением для этого n for item in permutations('2' * n + '1' * n): a.add('0' + ''.join(item) + '0') return(a) start = time() print(len(get_set_shuffle(6))) print(time() - start) start = time() print(len(get_set_permutations(6))) print(time() - start) 924 0.04333138465881348 924 159.2287471294403[/pre2] По поводу 2**n - странно, возьмем даже пример. При n = 2: 0011 0101 0110 1001 1010 1100 - 6 вариантов. 2 ** 2 = 4 4! / (2! * 2!) = 6 (я считаю по формуле n! / (n1! * n2!), где n - общее количество, n1 и n2 - количество одинаковых)
1llumi: Представлю свой способ решения таких номеров, работает для небольших строк, где не нужна конкретная и единственная возможная расстановка цифр. [pre2] from random import * for n in range(1, 100): cnt = 0 while cnt != 1000: c = ["1"]*n + ["2"]*n + ["3"]*n shuffle(c) s = ''.join(c) cnt += 1 [/pre2]
Ж: [pre2] from random import * for n in range(17,100): s=list('1'*n+'2'*n+'3'*n) shuffle(s) s=''.join(s) while any(c in s for c in ['21','31','32']): if '21' in s: s=s.replace('21','12',1) if '31' in s: s = s.replace('31', '13', 1) if '32' in s: s = s.replace('32', '23', 1) if s[49]=='2': print(n*3); exit() [/pre2]
полная версия страницы