RECURS (Методичка С++), страница 3
Описание файла
Файл "RECURS" внутри архива находится в папке "METODY". Документ из архива "Методичка С++", который расположен в категории "". Всё это находится в предмете "информатика" из 2 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "информатика" в общих файлах.
Онлайн просмотр документа "RECURS"
Текст 3 страницы из документа "RECURS"
begin for i:=1 to m do write(pole[i]:2);writeln; end
else
for i:=1 to m do
begin
pole[n]:=i;
if new_r(n,pole) then ferz(n+1,m,pole);
end;
end;
begin writeln('Введите размер доски:');
readln(m);
k:=0;
ferz(1,m,pole);
end.
Процедура new_r используется для проверки уже сгенерированной комбинации (уровень n соответствует попытке установить n-го ферзя). Процедура ferz рекурсивна. На каждом уровне она может породить до m рекурсивных вызовов (в соответствии c деревом генерации вариантов). Однако общее количество рассматриваемых вариантов резко уменьшается, что можно наглядно видеть по таблице 1.
Таблица 1.
Размер доски | Всего вариантов | Рассмотрено вариантов | Количество решений |
4*4 | 256 | 17 | 2 |
5*5 | 3125 | 54 | 10 |
6*6 | 46656 | 153 | 4 |
7*7 | 823543 | 552 | 40 |
8*8 | 16777216 | 2057 | 92 |
Выводы.
-
Рекурсию следует использовать тогда, когда рекурсивный алгоритм значительно проще нерекурсивного.
-
При использовании рекурсии следует обязательно проверять наличие и правильность условия выхода из рекурсии.
-
Не следует забывать о необходимости оценки размера фрейма активации и соотношения этой оценки с размером стека (с учетов развертывания рекурсии).