Помогите, пожалуйста с задачей.. Можно не полностью, а хотя бы алгоритм...
спасибо заранее
читать дальшеЭлементы массива вещественных чисел не убывают. Двоичным поиском найти позицию(индекс), где в этот массив можно вставить заданное число x с сохранением упорядоченности массива. Дан файл, в котором первое число-это х, второе-количество элементов, остальные-элементы.
Люди никогда не достигнут совершенства, пока будут оставаться людьми...
А в чём собственно говоря проблемы? Метод Дихотомии, принцип вложенных отрезков вам не знаком?
Алгоритм примерно такой: пусть l, r - левая и правая границы соответственно того промежутка массива, в котором мы ищем, тогда посмотрим в элемент с номером q = (l + r) / 2, тоесть в середину отрезка. Если этот элемент больше, чем тот, что мы ищём, значит нам нужно искать левее, тоесть сдвинуть правую границу r = q, иначе (q-ый элемент меньше, чем тот, что мы ищем) -- l = q. Теперь если получилось так, что мы нашли то, что надо - выдаём номер. Если попали в ситуацию, что l = r-1 и всё плохо (т.е. a[l] < x < a[r]) -- можно вставить в позицию r. Программируется ещё проще, но это мне уже лень.
-
-
17.12.2008 в 18:35Алгоритм примерно такой: пусть l, r - левая и правая границы соответственно того промежутка массива, в котором мы ищем, тогда посмотрим в элемент с номером q = (l + r) / 2, тоесть в середину отрезка. Если этот элемент больше, чем тот, что мы ищём, значит нам нужно искать левее, тоесть сдвинуть правую границу r = q, иначе (q-ый элемент меньше, чем тот, что мы ищем) -- l = q. Теперь если получилось так, что мы нашли то, что надо - выдаём номер. Если попали в ситуацию, что l = r-1 и всё плохо (т.е. a[l] < x < a[r]) -- можно вставить в позицию r. Программируется ещё проще, но это мне уже лень.