Ctrl →

Adastraz · Июнь 4, 2013 20:34:27

Доброго времени суток!
Такая задачка:
Генерируется ряд чисел (сколько их - задает пользователь). Они ненулевые, кроме крайних. Они “0”. Пройтись надо так, чтобы сумма тех, на которые мы “наступили” была максимальной. Ходить можно на след и послеслед число.

import random
n = input(u'Введите число уровней: ')
numbers = [0]
while True:
    number = random.randint(-50, 50)
    numbers.append(number)
    if number == 0:
        continue
    if len(numbers) > n-2:
        break
numbers.append(0)
for i in numbers:
    print i

Далее нужно пройтись по массиву таким образом:
Допустим ряд таков: 0, 1, -2, 3, 4, -5, 0
x(1) = 0
x(2) = 1
x(3) = -1
x(4) = 4
x(5) = 8
Первые два числа статичны, они из массива, а с третьим мы работает. Смотрим на два предыдущих числа, анализируем суммы третьего числа с этими двумя предыдущими и выбираем. Какой случай будет больше x(1) + x(3) or x(2) + x(3) тот и выбираем и так далее.

Вопрос:
Как это все упаковать в цикл, чтобы на IndexError: list index out of range не ругался?

Отредактировано Adastraz (Июнь 4, 2013 20:34:40)

4kpt · Июнь 5, 2013 22:25:24

Adastraz
и так далее

Что далее? Что дальше сравнивается? Результат предыдущего сравнения и х(4) или опять х(1) и х(2) но уже с х(4)? Сумбурно, очень сумбурно.

Помогу с удовольствием, но напишите нормальные условия задачи. Если можно, с примером данных :)

Adastraz · Июнь 6, 2013 16:30:43

Согласен, что сумбурно

Ряд: 0, 1, -2, 3, 4 ,-5 ,0

Берем первые два числа (0, 1) и к ним поочередно прибавляем след. цифру (-2) и смотрим, куда нам выгоднее ее прибавить, чтобы в конце таких мелких задачек по ходу ряда, получить максимальную сумму. Динамическое программирование, полагаю. Важно, чтобы алгоритм был не жадным.

Итак, два числа:
1) 0
2) 1

Третье - 2. Выгоднее сделать:

1) 0
2) 1
3) 1 - 2 = -1
Так как ходить можно на число вперед и на послеслед. число, то 0 можно отбросить.

Получается так:

2) 1
3) -1

На очереди число 3. Выгоднее так:

2) 1
3) -2
4) 1 + 3 = 4

Число 2) отбрасываем по причине, которую я уже описал.

Ряд:
3) -2
4) 4

След. число - 4

3) -2
4) 4
5) 8

Число -5

4) 4
5) 8
6) 3

Число 0 в расчет не берем

Итого, если пройтись по данному ряду, ступая только на след и послеслед число, максимальную сумму, которую можно получить - 8

Надеюсь, понятно

4kpt · Июнь 7, 2013 00:56:33

Алгоритм ясен. Что должна выдавать программа? Максимальную сумму? Выбранные шаги? Индексы шагов, которые приводят к максиальной сумме? Можно это все, но не хочется писать лишний код :)

Отредактировано 4kpt (Июнь 7, 2013 01:22:38)

Adastraz · Июнь 7, 2013 12:24:25

Сумму

dimy44 · Июнь 7, 2013 14:27:26

t = [0, 1, -2, 3, 4, -5, 0]
end_index = len(t) - 2
for i in xrange(3, end_index+1):
    if i == end_index:
        m = max(m, t[i-1])
    else:
        m = max(t[i-1], t[i-2]) + t[i]
        t[i] = m
print(m)

так?

Adastraz · Июнь 7, 2013 19:36:13

dimy44

Спасибо. Почти так
Написал часть, чтобы кол-во цифр в ряду выбирал пользователь.
Проблема раз:
Попалось:
0
-28
9
36
10
0
45 - сумма

При использовании бумажки сумма - 55.

Проблема два:
Если ряд <= 5 - дает ошибку
NameError: name ‘m’ is not defined
Если > 5 - все ок

Код генерирования:

import random
n = input(u'Введите число уровней лестницы: ')
numbers = [0]
while True:
    number = random.randint(-50, 50)
    if number == 0:
        continue
    if len(numbers) > n-2:
        break
    numbers.append(number)
numbers.append(0)
for i in numbers:
    print i

dimy44 · Июнь 7, 2013 21:13:52

Тогда так

def foo(lst):
    lenght = len(lst)
    assert lenght >=  3
    if lenght == 3: return max((0, lst[1]))
    for i in xrange(lenght-3):
        m = max(lst[i], lst[i+1]) + lst[i+2]
        lst[i+2] = m
    return m
print(foo([0, -28, 9, 36, 10, 0]))

Adastraz · Июнь 8, 2013 00:52:28

Еще ближе

Но при кол-ве чисел = 4 считает через раз правильно

Введите число уровней лестницы: 4
0
21
7
0
28
>>> ================================ RESTART ================================
>>> 
Введите число уровней лестницы: 4
0
-41
-3
0
-3
>>> ================================ RESTART ================================
>>> 
Введите число уровней лестницы: 4
0
-24
-49
0
-49

dimy44 · Июнь 8, 2013 08:21:33

замените lenght-3 на lenght-2 в for i in …

Отредактировано dimy44 (Июнь 8, 2013 08:33:46)

Python-сообщество

Уведомления

#1 Июнь 4, 2013 20:34:27

Пройтись по массиву

#2 Июнь 5, 2013 22:25:24

Пройтись по массиву

#3 Июнь 6, 2013 16:30:43

Пройтись по массиву

#4 Июнь 7, 2013 00:56:33

Пройтись по массиву

#5 Июнь 7, 2013 12:24:25

Пройтись по массиву

#6 Июнь 7, 2013 14:27:26

Пройтись по массиву

#7 Июнь 7, 2013 19:36:13

Пройтись по массиву

#8 Июнь 7, 2013 21:13:52

Пройтись по массиву

#9 Июнь 8, 2013 00:52:28

Пройтись по массиву

#10 Июнь 8, 2013 08:21:33

Пройтись по массиву

Board footer