заменить два числа на одно число, которое находится между двумя в заданном массиве?

Question

Проблема заключается в том, что у нас есть массив A из N длина и случайное число X.

Выберите любые два числа говорят, а, Ъ из массива А и заменить их обоих одним числом сказать, Y такое, что в < = y < = b.

После операций N-1 в массиве осталось только один номер. Проверьте, можем ли мы получить этот номер или нет?

Я думаю, что это рекурсивная проблема, но я не могу подойти? расскажите, как подойти.

Answer 1

Скажем, массив a1, a2, .., a в отсортированном порядке. Таким образом, минимум равен a1 и max;

you may choose a1,a2 and replace with a1. 
Then after choose a1, a3(as a2 is gone now) and replace by a1. 
. 
Similarly you may choose a1, an-1 {a2 to an-2 is gone now} and replace by a1. 

Now you are left with 2 number a1 and an. So a1<=x<=an, ans is yes otherwise two. 

Это жадный подход, поэтому для этого требуется доказательство. Что я ухожу от вас.

Только побочный эффект: рекурсия и итерация имеют одинаковую математическую силу. Просто они имеют различную визуализацию.