Форум » Обработка числовых последовательностей » Задача 27-19(81) Алгоритм решения » Ответить
Задача 27-19(81) Алгоритм решения
dkonyashkin: Здравствуйте! Объясните пожалуйста алгоритм решения данной задачи. Имеется набор данных, состоящий из целых чисел. Необходимо определить максимальное произведение подпоследовательности, состоящей из одного или более смежных элементов. Я просто не понимаю что делает программа. Что хранят переменные dp_min и dp_max? [pre2] Fin = open("27.txt") N = int( Fin.readline() ) x = int( Fin.readline() ) dp_min = dp_max = ma = x for i in range(N-1): x = int( Fin.readline() ) t = min( dp_min*x, min(dp_max*x, x) ) dp_max = max(dp_min*x, max(dp_max*x, x)) dp_min = t ma = max(ma, dp_max) # print(x, ma) print( ma ) Fin.close()[/pre2] Заранее спасибо.
Ответов - 4
dkonyashkin: Еще раз здравствуйте! Я не халявщик, я разобраться хочу. Вот мой вариант программы: def chet(a,b): c=0 for i in range (a,b): if masz==1: c=c+1 return(c%2) def prom(n1,n2): if chet(n1,n2)==0: mm=1 for i in range(n1,n2): mm=mm*masf else: min1=0 minp=0 flag=n1+1 while flag!=0: if masz[flag-1]==1: min1=flag-1 flag=-1 flag=flag+1 flag=n2 while flag!=0: if masz[flag-1]==1: minp=flag-2 flag=1 flag=flag-1 mm1=1 mm2=1 for i in range (minp): mm1=mm1*masf for i in range(min1+1,N): mm2=mm2*masf mm=max(mm1,mm2) return(mm) Fin = open("27-19b.txt") N = int( Fin.readline() ) print(N) masf=[] #Содержит значения текстового файла masz=[0]*N #Содержит информацию о отрицательных числах mas0=[0]*N #Содержит информацию о числе 0 for i in range(N): x=(int( Fin.readline() )) masf.append(x) if x<0: masz=1 elif x==0: mas0=1 print(masf,masz,mas0) Fin.close() print() #Вариант когда 0 отсутствует и количество отрицателных чисел четное if max(mas0)==0 and sum(masz)%2==0: mm=prom(0,N) #Вариант когда 0 отсутствует и количество отрицательных чисел нечетное elif max(mas0)==0 and sum(masz)%2==1: mm=prom(0,N) #Вариант когда есть хотя бы 1 элемент равный 0 else: nn=0 mm=0 mmt=0 for i in range(N): if mas0==1: mmt=prom(nn,i) nn=i+1 if mm<mmt: mm=mmt print(mm) Вот вариант программы, предложенный одним из учеников: f = open('numbers.txt', 'r') N = int(f.readline()) nums = ''.join(f.readlines()) nums = nums.split('0\n') minusAmount = [] result = [] for i in range(len(nums)): minusAmount.append(nums.count('-')) nums = nums.split('\n') for i in range(len(nums)): if minusAmount % 2 == 0: m = 1 for k in nums: m *= int(k) result.append(m) else: m1 = 1 m2 = 1 c = 0 for k in nums: if int(k) < 0: c += 1 if c < minusAmount: m1 *= int(k) if c > 1: m2 *= int(k) result.append(m1) result.append(m2) print(max(result)) Я просто не понимаю алгоритм предложенного решения. Помогите пожалуйста разобраться. Спасибо
Поляков: dkonyashkin пишет: Я просто не понимаю алгоритм предложенного решения. Помогите пожалуйста разобраться. Комментарии автора есть в разборе задачи 90 в этом файле. Здесь префикс "dp_" означает динамическое программирование. dp_max - это максимальное произведение, которое может быть накоплено к текущему моменту, dp_min - минимальное произведение.
Nikola_Invicta_753: #ЗАДАЧА 19 n = int(f.readline()) x = int(f.readline()) dp_min = dp_max = mx = x for i in range(1,n): x = int(f.readline()) if x > 0: dp_max = max(dp_max*x,x) dp_min = min(dp_min*x,x) elif x < 0: time = dp_max dp_max = max(dp_min*x,x) dp_min= min(time*x,x) else: #ВВОДИТСЯ НУЛЕВОЕ ЗНАЧЕНИЕ dp_max = dp_min = 1 mx = max(mx,dp_max) print(mx)
yflzu@mail.ru: N - количество чисел, в программе не используется, но считывать надо x - очередное число последовательности p - произведение всех чисел пока не встретится ноль, после нуля начинаем копить опять с 1 p0 - первое встретившееся отрицательное произведение ma - искомое максимальное значение [pre2] f = open('....') N = int( f.readline() ) p0 = p = ma = 1 for i in f: x = int(i) if x==0: p0 = p = 1 else: p*=x if p<0 and p0==1: p0=p ma=max(ma,p,p//p0) print(ma)[/pre2]
полная версия страницы