Мой алгоритм деления и покоя работает, но мой код не возвращает значение

Итак, я пытаюсь научиться правильно программировать, и я просматриваю книгу алгоритмов и данных. В рамках упражнения, чтобы научить читателя значению алгоритмов (прежде чем мы даже начнем их изучать), я решаю проблему выполнения кодирования, которая найдет k-е наименьшее целое число в списке int в O (N) времени. Я избегаю поиска ответа, потому что я хочу решить его самостоятельно для упражнений мозга. Во всяком случае, у меня есть код MOSTLY, работающий с по общему признанию неуклюжий алгоритм разделения и покорения.
Я не хочу ЛЮБОЙ помощи по самому алгоритму !! Я просто хочу знать, что я делаю неправильно в том смысле, что я могу распечатать вывод, но возврат его не работает.Мой алгоритм деления и покоя работает, но мой код не возвращает значение

alg_list = [7, 10, 18, 3, 8, 11, 9, 15, 0, 14, 12, 16, 6, 5, 2, 13, 17, 4, 1, 19] 

def kth_smallest(k, input_list): 
    N = len(input_list) 
    if N == k: 
    input_list.sort() 
    M = input_list[-1] 
    print M # used this to get some output to ensure the algorithm works at least 
    return M #this is where Im confused. Why no return? 
    else: 
    if N == 1: 
     M = input_list[0] 
     #print '2nd condition' 
     return M 
    elif N%2 == 0: 
     M = input_list[N/2] 
     #print '3rd condition' 
    else: 
     M = input_list[(N - 1)/2] 
     #print '4th' 
    list_small = [x for x in input_list if x < M] 
    list_large = [x for x in input_list if x > M] 
    if len(list_small) == k - 1: 
     #print '5th' 
     return M 
    elif len(list_small) > k - 1: 
     #print '6th' 
     kth_smallest(k, list_small) 
    elif (len(list_large) + len(list_small)) == (k - 1): 
     #print '7th' 
     return M 
    elif (len(list_large) + len(list_small)) == k: 
     #print '8th' 
     new_list = list_large + list_small 
     kth_smallest(k, new_list) 
    else: 
     #print '9th' 
     kth_smallest(k, list_large) 

kth_smallest(3, alg_list)

печать 3, но если я закомментируйте оператор печати, он не вернется 3. Что я делаю неправильно здесь с возвращением значения «M» ?? Опять же, я уверен, что моя дрянная попытка алгоритма плоха, но я нахожусь в самом начале книги, и это упражнение только для того, чтобы заставить читателя задуматься, поэтому я в порядке с этим сейчас плохо. Я просто хочу знать, что я делаю неправильно, возвращая значение. Я предполагаю что-то очень очевидное, что мне не хватает.

Спасибо!

источник

2014-02-05 JPKab

Там только несколько отраслей, в которых вы ничего возвращения , Дважды проверьте свои рекурсивные вызовы и проверьте, следует ли вам поставить 'return' перед любым из них. Я думаю, ты должен. – Makoto

Спасибо! это было очень полезно. Меня поражает, насколько глупым может быть мой мозг с такими тонкими деталями! – JPKab

Этот алгоритм не является «O (n)», кстати ... Все дело в том, чтобы избежать сортировки –

Внутри функции kth_smallest, добавить return слева от каждого звонка до kth_smallest.

Тогда, вне этой функции, изменения:

kth_smallest(3, alg_list)

To:

val = kth_smallest(3, alg_list) 
print val

Или просто:

print kth_smallest(3, alg_list)

источник

2014-02-05 20:37:04

Спасибо! Как я уже сказал выше, меня постоянно унижают, как глупо некоторые из моих оплошностей. Это действительно помогает иметь ресурс стольких блестящих людей здесь. – JPKab

Добро пожаловать :) –

Мой алгоритм деления и покоя работает, но мой код не возвращает значение

ответ

Смежные вопросы