-1

Суть задачи: пришедшему на собеседование в новую IT компанию соискателю предстояло пройти следующее испытание - перед ним длинная лестница, чтобы наступить на каждую ступеньку, нужно потратить определенное количество магических очков. На следующий этап собеседования пройдут лишь те, кто потратил наименьшее количество очков при прохождении по лестнице. Соискатель может перемещаться вперед, либо на следующую ступеньку, либо через одну. В файле - схема лестницы, представляющая последовательность чисел - количество забираемых очков на каждой из ступенек.

Исходный код:

import numpy as np
import matplotlib.pyplot  as plt
from numpy import loadtxt
import pandas as pd
import json

#требуемое кол-во волшебных очков
magic_points=0
#максимальное кол-во очков
max_points=0

y = pd.read_json("D:\\SData.txt").iloc[:, 0]

#количество шагов/итераций
iter = 0;
#print(y)
for i in y:
    #max_points+=y[i]
    if (y[i] <= y[i+1]):
        magic_points+=y[i]
        iter=iter+1
        print("Тек: ", magic_points, "Итерация: ", iter)
    else:
        magic_points+=y[i+1]
        iter=iter+1
        print("Тек: ", magic_points, "Итерация: ", iter)

print("Финальный ответ: ", magic_points)

В ответе должно быть указано количество магических очков, которые необходимо затратить соискателю. Ожидаемый результат должен быть явно менее 20000, а при выполнении программа выдает ответ около 28000.

Что я делаю не так, и как получить верный результат при подсчёте очков?

Содержимое файла.

2 ответа 2

2

Можно создать вспомогательный столбец (стоимость следующей ступеньки):

df = pd.read_json("D:\\SData.txt").rename(columns={0:"this"})

df["next"] = df["this"].shift(fill_value=np.inf)

выбрать минимум и просуммировать:

res = df.min(axis=1).sum()
0

Начнем с того, что логика вашего алгоритма неверна.

Ваш цикл (for i in y:) - это последовательный перебор всех ступенек. Однако, если вы сделали шаг на одну ступень, то действительно, следующий цикл должен предполагать, что вы сдвинулись по файлу на одну запись. А вот если вы переступили через ступеньку, то вы должны оказаться не i+1 (что и делает ваш цикл), а на i+2 ступеньке (то самое перемещение через ступеньку). Это у вас никак не учтено.

Кроме того, предположим, что у вас где-то в файле есть примерно такая подпоследовательность: 13,14,13,2,7. Ваш алгоритм найдет последовательность 13,13,2. Оптимальный алгоритм должен найти 14,2. Т.е. шагов должно оказаться не три, а два, а накопленная сумма при достижении ступеньки "2" - 16, а не 27. Для этого алгоритм должен смотреть не просто пару следующих ступенек, а на каждом шаге "заглядывать" хотя-бы еще на две ступеньки вперед.

В целом - задача на умение составлять более-менее нетривиальные алгоритмы. Дерзайте.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.