Случайный массив алгоритма двоичного поиска - PullRequest
0 голосов
/ 01 августа 2020

Я не понимаю, почему рекурсивная функция всегда дает мне нулевой результат, даже если я помещаю значения в массив. кажется, что size (a) == 0

recursive function binarySearch_R (a, value) result (bsresult)
real, intent(in) :: a(6), value
integer          :: bsresult, mid

mid = size(a)/2 + 1
if (size(a) == 0) then
    bsresult = 0        ! not found
else if (a(mid) > value) then
    bsresult= binarySearch_R(a(:mid-1), value)
else if (a(mid) < value) then
    bsresult = binarySearch_R(a(mid+1:), value)
    if (bsresult /= 0) then
        bsresult = mid + bsresult
    end if
else
    bsresult = mid      ! SUCCESS!!
end if
end function binarySearch_R

program hji
read*, a
read*, value
print*, binarySearch_R
end program hji

Ответы [ 2 ]

2 голосов
/ 01 августа 2020

Слишком долго для комментария, но не для ответа ( и для всех экспертов Fortran, читающих это, да, есть одно или два места, где я замалчиваю некоторые детали, потому что считаю, что они не важны на данном этапе ) ...

Способ написания кода не позволяет компилятору вам помочь. Что касается компилятора, то связь между функцией и программой отсутствует. Что касается программы, то a, поскольку вы не сообщили компилятору об обратном, считается реальным скалярным значением. a в программе - это не то же самое, что a в функции - нет связи между функцией и программой.

То же верно для value.

То же самое верно и для binarysearch_r - и если вы не верите, удалите определение функции из исходного кода и перекомпилируйте программу.

Итак, что вы должны сделать, чтобы исправить код?

Первый шаг: измените исходный код так, чтобы он выглядел следующим образом:

program hji
... program code goes here ...
contains
    recursive function binarySearch_R (a, value) result (bsresult)
    ... function code goes here ...
    end function binarySearch_R
end program hji

Этот первый шаг позволяет компилятору увидеть связь между программой и функцией.

Второй шаг: вставьте строку implicit none сразу после строки program hji. Этот второй шаг позволяет компилятору обнаруживать любые ошибки, которые вы делаете с типами (действительными или целыми, et c) и ранжированием (скаляр, массив, et c) объявляемых вами переменных.

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

print*, binarySearch_R

в программе придется изменить на

print*, binarySearch_R(a, value)
2 голосов
/ 01 августа 2020

Глава 1: Опасности неявной типизации

Первое, что я настоятельно рекомендую вам сделать, это включить строку

implicit none

после строки program. Это подавит неявную типизацию, а возникающие в результате ошибки дадут вам некоторую полезную информацию о том, что происходит.

Если бы вы это сделали, вы бы получили сообщение об ошибке:

$ gfortran -o binsearch binsearch.f90
binsearch.f90:23:12:

     read*, a
            1
Error: Symbol ‘a’ at (1) has no IMPLICIT type
binsearch.f90:27:25:

     print*,binarySearch_R
                     1
Error: Symbol ‘binarysearch_r’ at (1) has no IMPLICIT type
binsearch.f90:24:16:

     read*, value
            1
Error: Symbol ‘value’ at (1) has no IMPLICIT type

It не имеет значения, что a, value и binarySearch_R были определены в функции. Поскольку функция не является частью блока program, программа не знает, что это такое.

При активном неявном типировании она просто предполагала, что все три являются простыми real переменными. (Тип зависит от первой буквы имени переменной, от i до n это integer, все остальное - real)

Поскольку эта неявная типизация может так легко скрыть ошибки кодирования, это сильно, настоятельно рекомендуется всегда выключать его.

Это также означает, что мы должны объявить переменные a и value в программе:

program hji
    implicit none
    real :: a(6), value
    ...
end program hji

Глава 2 : Как ввести функцию в программу?

Так как программа получает доступ к функции? Есть четыре способа:

  1. Лучший способ: использовать модуль

     module mod_binsearch
         implicit none
     contains
         recursive function binarySearch_R (a, value) result (bsresult)
             ...
         end function binarySearch_R
     end module mod_binsearch
    
     program hji
         use mod_binsearch
         implicit none
         real :: a(6), value
         ...
     end program hji
    

    Обратите внимание, что оператор use должен стоять перед implicit none. Этот метод оставляет функцию отдельной, но вызываемой. Он автоматически проверяет правильность параметров (это то, к чему мы скоро вернемся).

  2. Имеет функцию, содержащуюся в программе.

    Между последняя строка кода программы и оператор end program, добавьте ключевое слово contains, за которым следует код функции (все от recursive function ... до end function ...).

    Это быстрый и -грязный метод. Вы должны быть осторожны с этим методом, так как функция автоматически получит доступ к программным переменным, если внутри функции не объявлена ​​новая переменная с таким именем.

  3. Сложный способ: Интерфейсы

    Создайте блок интерфейса в разделе объявления исходного кода вашей программы и повторите там информацию об интерфейсе.

    Это по-прежнему позволяет компилятору проверять, правильно ли вызывается функция, но она работает вам, чтобы убедиться, что этот интерфейсный блок правильный и соответствует фактической реализации.

  4. Действительно, действительно уродливый способ: объявить его как переменную, вызвать ее как функция.

    Пожалуйста, не делайте этого.

Глава 3: Вызов функции

Когда вы вызываете функцию, вы должны использовать круглые скобки и дайте ему все ожидаемые параметры. В вашем случае вам нужно ввести

print *, binarySearch_r(a, value)

Глава 4: Dynami c массивы в качестве фиктивных параметров

При последовательных рекурсивных вызовах функции массив становится все меньше и меньше. Но фиктивный параметр всегда одного размера (6). Это не только помешает вашему алгоритму, но также может привести к опасно неопределенному доступу к памяти.

К счастью, специально для intent(in) фиктивных параметров вы можете использовать динамические c массивы:

recursive function binarySearch_R(a, value)
    real, intent(in) :: a(:), value

Единственное двоеточие сообщает компилятору, что следует ожидать одномерный массив, но не его длину. Поскольку вы уже используете size(a), он должен работать автоматически.

...