2
Рассмотрим следующий алгоритм min, который принимает списки x, y в качестве параметров и возвращает z-й наименьший элемент в объединении x и y. Предварительные условия: X и Y сортируют списки ints в порядке возрастания, и они не пересекаются.Как я могу доказать правильность следующего алгоритма?
Обратите внимание, что его псевдо-код, поэтому индексация начинается с 1 не 0.
Min(x,y,z):
if z = 1:
return(min(x[1]; y[1]))
if z = 2:
if x[1] < y[1]:
return(min(x[2],y[1]))
else:
return(min(x[1], y[2]))
q = Ceiling(z/2) //round up z/2
if x[q] < y[z-q + 1]:
return(Min(x[q:z], y[1:(z - q + 1)], (z-q +1)))
else:
return(Min(x[1:q], B[(z -q + 1):z], q))
Я могу доказать, что она заканчивается, потому что г сохраняет уменьшается на 2, а в конечном итоге прийти к одному из базовых случаев, но я не могу доказать частичную корректность.
Привет, я думал, что это было более подходящим для компьютерной науки? – user65065
Вы могли бы указать более подробно: что должен сделать алгоритм? Я понял, что вы хотите, чтобы k-й наименьший элемент среди элементов 'x' и' y', т. Е. 'Mix ([1,2], [3, 4], 1) = 1' (наименьший элемент) 'Mix ([1, 2], [3, 4], 2) = 2' (второй наименьший элемент) и т. Д. Правильно ли это? Если это так, я не думаю, что этот алгоритм работает правильно. Нет даже рекурсии. – chris
И, конечно, если нет рекурсии, окончание тривиально. Если бы у вас была рекурсия, ваш аргумент не гарантировал бы прекращения (предполагая, что вы действительно означали целые числа, а не натуральные числа), так как уменьшение отрицательного целого может продолжаться (теоретически) навсегда, не ударяя базовый случай. – chris