2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Массивы, обработка последовательности, рекурсивные алгоритмы
Сообщение19.11.2009, 08:55 
Здравствуйте! Помогите решить задачи на паскале, очень надо, а то я ваще не шарю. Заранее очень благодарен

1.(Массивы) - Дан массив размера N. Найти номера двух ближайших чисел из этого массива.


2.(обработка последовательнльсти) - Дан набор ненулевых целых чисел; признак его завершения — число 0. Вывести сумму всех положительных четных чисел из данного набора. Если требуемые числа в наборе отсутствуют, то вывести 0.


3.(Простейшие рекурсивные алгоритмы) - Описать рекурсивную функцию FibRec(N) целого типа, вычисляющую N-е число Фибоначчи F(N) по формуле: F(1) = F(2) = 1, F(k) = F(k–2) + F(k–1), k = 3, 4, ... . С помощью этой функции найти пять чисел Фибоначчи с указанными номерами и вывести эти числа вместе с количеством рекурсивных вызовов функции FibRec, потребовавшихся для их нахождения.

 
 
 
 Re: Массивы, обработка последовательности, рекурсивные алгоритмы
Сообщение19.11.2009, 09:53 
Не, тут так нельзя (здесь почитайте). Предложите сначала свое решение.

 
 
 
 Re: Массивы, обработка последовательности, рекурсивные алгоритмы
Сообщение19.11.2009, 13:03 
Вот ядро третьей задачи -- а уж окружайте служебными строчками её самостоятельно.

Используется синтаксис Pascal
var  nRec: integer;

function FibRec(n: integer): integer;
begin
  if n<=2
    then FibRec:=1                      {Начальные значения}
    else begin
      inc(nRec, 2);                 {Увеличиваем счётчик рекурсий}
      FibRec:=FibRec(n-1)+FibRec(n-2);  {Рекурсивные вызовы}
    end;
end;


Счётчик рекурсий перед каждым вызовом надо, конечно, обнулять.

Я надеюсь, что составители задачи предложили ввести этот счётчик для того, чтобы продемонстрировать: это -- хороший пример задачи, в которой применение рекурсии неадекватно.

А вот любопытная задачка вдогонку: написать явную формулу для числа рекурсивных вызовов в зависимости от $n$.

 
 
 
 Re: Массивы, обработка последовательности, рекурсивные алгоритмы
Сообщение19.11.2009, 13:31 
ewert в сообщении #263453 писал(а):
А вот любопытная задачка вдогонку: написать явную формулу для числа рекурсивных вызовов в зависимости от $n$.

$F_n -1$

 
 
 
 Re: Массивы, обработка последовательности, рекурсивные алгоритмы
Сообщение19.11.2009, 14:08 
а почему?

(кстати, вдвое больше -- внутри каждого вызова два рекурсивных)

 
 
 
 Re: Массивы, обработка последовательности, рекурсивные алгоритмы
Сообщение19.11.2009, 17:02 
ewert
Спасибо, ща буду разбиратся...

 
 
 
 Re: Массивы, обработка последовательности, рекурсивные алгоритмы
Сообщение19.11.2009, 20:07 
Когда будете разбираться, призадумайтесь вот над чем. В любой рекурсивной процедуре необходим пункт, отслеживающий, не вышли ли мы на дно рекурсии -- тогда из процедуры следует выходить немедленно. В той программке роль такого пункта играет первая ветка оператора "if".

 
 
 
 Re: Массивы, обработка последовательности, рекурсивные алгоритмы
Сообщение19.11.2009, 21:25 
Вроде получилось:
program fib;
Const N=5;
var i, kol :integer;

Function Fib(n:integer):integer;
begin
if (n=1) or (n=2) then Fib:=1
else begin
Fib :=Fib(n-1) + Fib(n-2);

end;
kol:=kol+1;
end;

BEGIN

for i:= 1 to N do begin
kol :=0;
read(i);
Write(i, ' chislo Fibonachi ' , Fib(i));
writeln(' Kolichestvovo vizovov' , kol);
end;
END.

 
 
 
 Re: Массивы, обработка последовательности, рекурсивные алгоритмы
Сообщение19.11.2009, 21:36 
X-FactoR в сообщении #263624 писал(а):
else begin
Fib :=Fib(n-1) + Fib(n-2);
end;
kol:=kol+1;
end;

Вот это не годится. Рекурсивными-то будут только вызовы из второй ветки, у Вас же -- якобы в обеих будут какие-то вызовы.

Это во-первых. А во-вторых, программы (уверен, Вы это знаете) принято снабжать в приличном обществе приличествующими отступами. Для этого достаточно печатать их не в основном тексте, а внутри тега [ code ].

----------------------------------------------
да, кстати, и ещё один технический момент. Вы, я вижу, творчески переработали мою функцию, что само по себе замечательно. Однако же: если мой вариант выдавал хоть какой результат при всех $n\leqslant2$ (при $n\leqslant0$, естественно, бессмысленный, но хоть какой-то определённый), то в Вашем варианте при $n\leqslant0$ он будет выдавать просто некий случайный мусор. Совершенно не поддающийся интерпретации. Что не есть хорошо.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group