Форум » Обработка числовых последовательностей » №4507 (27.78) ошибки в алгоритме » Ответить
№4507 (27.78) ошибки в алгоритме
beep: Здравствуйте! В алгоритме "27-78.py" есть ошибки: 1) Если самая длинная цепочка будет начинаться с первого члена последовательности и этот член будет кратен 73, то длина цепочки определится неверно. Связано это с тем, что в tailSum хранится i отсчитывающееся с единицы, а не нуля, а в начальных значениях занесен 0. Данные: [pre2] 3 73 2 73 [/pre2] Алгоритм выдаст ответ 4, хотя у нас всего 3 члена последовательности. 2) maxSum определяется неверно, потому что x слишком рано прибавляется к totalSum и в tailSum получается, что хранится сумма хвоста, которую нужно вычесть + первый член цепочки, для которой вычисляется сумма. Данные: [pre2] 8 145 2 1 2 6 28 10 67 [/pre2] Правильный ответ 3 (145 + 2 + 1 = 148, 148 / 37 = 4 и (145 + 1) / 73 = 2), алгоритм же выдаст 4 с максимальной суммой 105, что неправильно. Во-первых, максимальная сумма будет 111 (6 + 28 + 10 + 67), но алгоритм вычитает первый член цепочки и получается 105. Во-вторых, 148 больше 111, но поскольку алгоритм каждый раз вместе с tailSum вычитает первый член цепочки, получается что он сравнивает две суммы (148 - 145) и (111 - 6). На всякий случай сам алгоритм: [pre2] K, M = 37, 73 F = open("27.txt") N = int( F.readline() ) tailSum = [ [0] + [None]*(K-1) ] for i in range(M-1): tailSum.append( [None]*K ) tailLen = [[0]*K for i in range(M)] maxSum, minLen = 0, 0 totalSum = 0 r = 0 for i in range(1,N+1): x = int( F.readline() ) totalSum += x ri = x % M if tailSum[ri][r] == None: tailSum[ri][r] = totalSum tailLen[ri][r] = i r0 = (M - ri) % M r = totalSum % K if tailSum[r0][r] != None: curSum = totalSum - tailSum[r0][r] curLen = i - tailLen[r0][r] + 1 if curSum > maxSum or \ (curSum == maxSum and curLen < minLen): maxSum = curSum minLen = curLen F.close() print( minLen ) [/pre2]
Ответов - 1
Поляков: Спасибо за тщательный анализ и примеры. Решение исправлено.
полная версия страницы