Форум » Обработка числовых последовательностей » Некорректный ответ в задаче №3922? » Ответить
Некорректный ответ в задаче №3922?
Arthur: Здравствуйте, задача, по-моему, имеет неверный ответ (в пункте А). Если отсортировать все числа, найти наиболее часто встречающуюся разность (поиск шага q арифм. прогрессии). То получается 2 значения - 3 и 13. Значит, нужно пытаться строить подмножества из данных шагов. Если устроить переборный алгоритм, т.к. в пункте А не так много чисел, мы получим последовательность из 3 чисел с помощью шага равного "3", а именно - 24, 27, 30 либо 17 20 23. А с помощью шага равного "13" можем получить самую длинную последовательность, а именно - 9, 22, 35, 48. Возможно я что-то не учёл, подскажите пожалуйста. Вот мой код: [pre2] f = open('27-62a.txt') n = int(f.readline()) counts = [int(f.readline()) for _ in range(n)] counts.sort() diffs = [] for i in range(len(counts) - 1): for j in range(i+1, len(counts)): if 1 <= abs(counts[ i] - counts[j]) <= 100: diffs += [abs(counts[ i] - counts[j])] max_k = 0 for i in diffs: max_k = max(max_k, diffs.count(i)) steps = [] for i in diffs: if diffs.count(i) == max_k: steps.append(i) check = {x: 1 for x in counts} max_k = 1 for i in steps: for j in range(len(counts)): k = 1 cs = counts[j] while cs + i in check: cs += i k += 1 max_k = max(k, max_k) k = 1 print(max_k) [/pre2]
Ответов - 3
Поляков: Arthur пишет: Возможно я что-то не учёл, подскажите пожалуйста 11, 17, 23, 29, 35.
Нечитайло: Здравствуйте. Вы что-то не учли. Вот мой код c похожим брутфорсом: [pre2] f = open('27-62a.txt') f.readline() numbers = sorted(set(map(int, f.read().split()))) print(numbers) maximal = [] for ia, a in enumerate(numbers): for ib, b in enumerate(numbers[ia+1:]): seria = [a, b] delta = b - a c = b + delta while c in numbers: seria += [c] c += delta if len(seria) > len(maximal): maximal = seria print(maximal) [/pre2] Вот его вывод: [pre2] [3, 8, 9, 11, 12, 17, 20, 22, 23, 24, 27, 29, 30, 35, 37, 40, 46, 48, 49, 50] [11, 17, 23, 29, 35] [/pre2] Как видите, там пять элементов. Ваш код не запускается, поскольку местный движок воспринимает ' [ i ] ' без пробелов как разметку курсивом и из текста его выкусывает. Даже если их обратно вписать, то это же можно короче и яснее. Думаю, что дело в ложном заключении вроде такого: "Если в длинных искомых последовательностях много одинаковых разностей, то наибольшему числу одинаковых разностей соответствует самая длинная последовательность". Ошибка в том, что одинаковые разности могут появляться и по другим причинам. Я готовлюсь к занятиям и сделал вариант этого кода с отладочной печатью и комментариями. Вдруг они и вам пригодятся? [pre2] #открываем файл #пропускаем первое число (ненужное нам количество элементов) f = open('27-62a.txt') f.readline() #читаем нужные числа, сортируем, любуемся #преобразование к списку необязательно, но оно гарантирует исключение дубликатов numbers = sorted(set(map(int, f.read().split()))) print(numbers) #есть вопросы? #раскомментируйте отладочный код #разберитесь с тестовым примером # numbers = [1,3,5,8,9,10,11,13,17] # print(numbers) # for ia, a in enumerate(numbers): # for b in numbers[ia+1:]: # print(a,b, b-a, end = ' ') # print() # # 1 3 2 1 5 4 1 8 7 1 9 8 1 10 9 1 11 10 1 13 12 1 17 16 # 3 5 2 3 8 5 3 9 6 3 10 7 3 11 8 3 13 10 3 17 14 # 5 8 3 5 9 4 5 10 5 5 11 6 5 13 8 5 17 12 # 8 9 1 8 10 2 8 11 3 8 13 5 8 17 9 # 9 10 1 9 11 2 9 13 4 9 17 8 # 10 11 1 10 13 3 10 17 7 # 11 13 2 11 17 6 # 13 17 4 #ниже блок с началом каждого кандидата #раскомментируйте и посмотрите в работе, #если есть вопросы к полному алгоритму # maximal = [] # for ia, a in enumerate(numbers): # for ib, b in enumerate(numbers[ia+1:]): # seria = [a, b] # delta = b - a # print(seria, delta) # print() maximal = [] for ia, a in enumerate(numbers): for ib, b in enumerate(numbers[ia+1:]): seria = [a, b] delta = b - a c = b + delta print(seria, '?', c, '?', delta, end = ' -- ') while c in numbers: seria += [c] c += delta print(seria) if len(seria) > len(maximal): maximal = seria print() print('----------------') print(maximal) [/pre2] И еще, почему бы вам не использовать стандартную библиотеку Питона? Например import collections избавляет от массы велосипедов в коде. Я переписал начало вашей программы яснее. [pre2] #этот модуль входит в стандартную библиотеку from collections import Counter #открываем файл #пропускаем первое число (ненужное нам количество элементов) f = open('27-62a.txt') f.readline() #читаем нужные числа, сортируем, любуемся counts = sorted(map(int, f.read().split())) print(counts) #комбинируем генератором каждое с каждым #вносим в список положительные разности #при помощи удобного словаря Counter получаем частоту их повторений diffs = Counter([a - b for a in counts for b in counts if a > b]) print(diffs) #смотрим на частоту повторений #3 и 13 встречаются чаще прочих (по восемь раз) print(diffs.most_common()) exit() [/pre2]
patnikk: брут файла А [pre2]### var a := |24, 50, 40, 9, 8, 11, 3, 20, 49, 35, 12, 29, 37, 48, 27, 23, 46, 22, 17, 30|; a.Sort; var mc := -1; for var i := 1 to a.Length do begin var c := 0; foreach var x in a.Cmb(i) do begin for var j := 2 to x.Length - 3 do if x[j + 2]-x[j+1] = x[j+1] -x[j] then c += 1 else begin if c > mc then mc := c; c := 0; end; end; end; print(mc); [/pre2] https://www.youtube.com/watch?v=C52hT-MJv9I
полная версия страницы