	Персональная страничка Диканева Тараса Викторовича

Главная \ Преподавательское \ Программирование для начинающих

Выбор среды программирования

1. Линейные программы: арифметические операторы, стандартные функции и ввод/вывод в текстовом режиме

2. Логические выражения и условный оператор

3. Цикл с параметром (for)

4. Вычисления с помощью рекуррентных соотношений

5. Вложенные циклы

6. Задачи на перебор вариантов

7. Переменные-флаги

8. Переменная - счетчик событий

9. Циклы while и repeat

10. Массивы

11. Процедуры и функции

12. Двумерные массивы

13. Графика в Паскале

14. Символы, строки, текстовые файлы

15. Записи

16. Указатели

4. Вычисления с помощью рекуррентных соотношений

Предыдущий раздел:

4.1. Рекуррентные соотношения: основные понятия

Следующий раздел:

4.3. Многомерные рекуррентные соотношения

4.2. Задачи на составление рекуррентных соотношений

1) Придумайте рекуррентное соотношение, задающее следующие числовые последовательности:

а) 1, 2, 3, 4, …

б) 0, 5, 10, 15, …

в) 1, 1, 1, 1, …

г) 1, -1, 1, -1, …

д) 1, -2, 3, -4, 5, -6, …

е) 2, 4, 8, 16, …

ж) 2, 4, 16, 256, …

з) 0, 1, 2, 3, 0, 1, 2, 3, 0, …

и) 1!, 3!, 5!, 7!, …

2) Придумайте рекуррентные соотношения для вычисления последовательностей следующего вида:

а) $1,~a,~a^2,~a^3,~a^4,~\ldots$

б) $1,~\frac{\displaystyle a}{\displaystyle 1!},~\frac{\displaystyle a^2}{\displaystyle 2!},~\frac{\displaystyle a^3}{\displaystyle 3!},~\ldots$

в) $1,~1+a,~1+a+a^2,~1+a+a^2+a^3,~\ldots$

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

а) $a^{m+1}$

б) $2a^m$

в) $(a-1)^m$

г) $\frac{\displaystyle a^m}{\displaystyle (a-1)^{m+1}}$

д) $(2m-1)!$

е) $1+a+a^2+\ldots+a^k$

ж) $1+a^2+a^4+\ldots+a^{2k}$

з) $1-a+a^2-a^3+\ldots-a^{2m-1}$

и) $1+x+\frac{\displaystyle x^2}{\displaystyle 2!}+\frac{\displaystyle a^3}{\displaystyle 3!}+\ldots+\frac{\displaystyle x^m}{\displaystyle m!}$

к) $x-\frac{\displaystyle x^3}{\displaystyle 3!}+\frac{\displaystyle x^5}{\displaystyle 5!}-\ldots+(-1)^{m-1}\frac{\displaystyle x^{2m-1}}{\displaystyle (2m-1)!}$

4) Составьте рекуррентные соотношения для приведенных ниже величин.
Указание: как видно, данные формулы основаны на повторении одной или нескольких операций. Рекуррентное соотношение должно содержать их однократное выполнение.

а) Золотое сечение

$1+\frac{\displaystyle 1}{\displaystyle 1+\frac{\displaystyle 1}{\displaystyle 1+\frac{\displaystyle 1}{\displaystyle 1+ \ldots}}}$

Если вычисления продолжать до бесконечности, то результат сойдется к числу называемому «Золотое сечение» (оно же золотая пропорция, гармоническое деление и число Фидия). Данное число было известно еще до нашей эры (его открытие приписывают Пифагору), а само название было дано Леонардо да Винчи. Считается, что объекты, в которых присутствуют пропорции, равные этому числу, воспринимаются как красивые.

б)	$\sqrt{2}= 1+\frac{\displaystyle 1}{\displaystyle 2+\frac{\displaystyle 1}{\displaystyle 2+\frac{\displaystyle 1}{\displaystyle 2+\ldots }}}$
в)	$\sqrt{2+ \sqrt{4+ \sqrt{6+\ldots+\sqrt{98} }}}$

Следующий раздел:

4.3. Многомерные рекуррентные соотношения

Предыдущий раздел:

4.1. Рекуррентные соотношения: основные понятия

Добавить комментарий

35 комментариев

	Константин	11.12.2011 в 03:42
2) реккурентное соотношение x5+1 = x5 +5 ?

	Taras	11.12.2011 в 03:56
Кажется, ты правильно все понимаешь. Правильно написать это можно, например, так: x(n+1) = x(n) + 5

	Аноним	23.08.2012 в 15:11
А какой ответ должен получаться в 4в?

	Taras	23.08.2012 в 19:33
Ответы я предпочитаю не давать. Если у вас уже есть вариант, могу подтвердить или опровергнуть его правильность.

	Аноним	26.08.2012 в 14:17
Ну получилось 10.4069918… Похоже на правду, нет?

	Taras	26.08.2012 в 14:33
У меня 2.15847687231104… получается. А рекуррентное соотношение какое?

	Аноним	26.08.2012 в 18:55
Всё, совпало, я наоборот сделал, от 98 до 2, теперь такой же ответ, спасибо.

Аноним

26.08.2012 в 19:03

Программу оформил вот так, можно как-то проще или лучше?

program xdg;
var
  x:real;
  y,i:integer;
begin
  readln(x);
  y:=100;
  for i:=1 to 49 do
  begin
    y:=y-2;
    x:=sqrt(y+x);
  end;
  writeln(x);
end.

	Аноним	26.08.2012 в 19:04
Блин, все пробелы в начале строк съело.

	Taras	26.08.2012 в 19:20
Нет, проще, думаю, уже нельзя. Только readln в начале не очень понятно зачем.

	Аноним	26.08.2012 в 19:22
О, я думал оно так не будет работать. Спасибо большое.

Taras

26.08.2012 в 19:30

Начальное значение x нужно задать, но можно было написать просто

  x := 0;

В принципе x в начале и так равен 0, но задать его явно это требование хорошего стиля.

	Аноним	27.08.2012 в 02:14
То есть если не присваивать переменной никакого значения, то она автоматически будет равна нулю, так? Хороший стиль — это хорошо, учту.

Taras

27.08.2012 в 19:47

Да, так. Но:

1) Позже в разделе «11. Процедуры и функции» появятся локальные переменные, для которых это не верно.

2) Это верно для PascalABC. Но в других языках это часто бывает не так.

3) Типична ситуация, когда решая сложную задачу, программист выделяет в ней простые подзадачи, решает их, а потом из получившихся кусков собирает решение всей задачи. И вот он протестировал каждый из кусков — все работает. Собрал вместе — хрен. А потому что во время тестирования какая-то переменная была равна 0, а когда этот кусок вставили в середину программы, она уже не 0.

В общем, полагаться на ноль по умолчанию — не хорошо.

	Аноним	30.08.2012 в 20:42
Спасибо большое, всё доступно объяснили, буду помнить.

	Аноним	08.12.2012 в 20:34
Здравствуйте. Не могли бы вы написать как найти рек куренные соотношения к заданию 4 а и 4б

	Taras	08.12.2012 в 20:43
Попробуйте выделить повторяющиеся действия. Они и должны присутствовать в рекуррентном соотношении. Еще можно обратить внимание на подобие — если часть выражения подобна целому, то можно взять ее за $x_n$ и подумать как вычислить по ней целое выражение $x_{n+1}$ .

	Аноним	08.12.2012 в 21:06
Вы не могли бы написать какое именно будет рекуррентное соотношения. Так как у меня сложнее задание и мне надо по подобию составить. Саму суть понимаю, но именно дробь не получается

	Taras	09.12.2012 в 22:36
К сожалению, не могу. Моя принципиальная позиция — не давать ответов. Я считаю, что для обучающегося это как минимум бесполезно.

	Дмитрий	24.01.2013 в 14:42
Тарас Викторович, допускается ли использование условных операторов? К примеру 1)-з?

	Taras	24.01.2013 в 15:51
Вообще-то все задачи здесь можно решить без условных операторов. Если можешь решить 1з с помощью if’а — это хорошо. Но стоит подумать как это сделать без него.

	Дмитрий	29.01.2013 в 17:51
Во 2 задании первоначальное значение равно «1». Можно ведь не составлять функцию, где первое значение «1», а просто написать вначале writeln(‘1’)?

	Taras	29.01.2013 в 20:42
Ну, да, пример такой… курьезный что ли. Толку от подобной последовательности, понятно, немного. Но для общего развития полезно прикинуть, какие рекуррентные соотношения могут порождать такую последовательность.

	Дмитрий	05.02.2013 в 18:48
В задании 3-к возможно вычисление нечетных факториалов введением условия if i mod 2=0 then continue; но факториал будет вычисляться не полностью. К примеру (5!=135, а не 5!=12345). Если есть другой способ вычисления нечетных факториалов, подскажите, пожалуйста.

	Taras	05.02.2013 в 21:34
Я думаю, что поднапрягшись, ты сам догадаешься, как добиться нужного результата. В общем, я в тебя верю!

Аноним

19.04.2014 в 01:40

Тарас,подскажите,теориетически — все понятно, а в практике-сложнее, как в ступоре каком то, пока разогреюсь, подумаю..
первая задача «а» этой темы,верно я мыслю или все таки нет,этого от меня хотят?

var
i: integer;
begin
for i := 1 to 20 do

writeln(i);
end.

Аноним

19.04.2014 в 02:45

1) Придумайте рекуррентное соотношение, задающее следующие числовые последовательности:

б) 0, 5, 10, 15, …

var
x,i,y:integer;
begin
writeln(0);
for i:= 1 to 30 do begin
x := x+1;
if x mod 5=0 then
writeln( x );
end;
end.

правильно или нет?

	Денис	21.04.2014 в 02:06
задание 1е не могу выполнить( var x,y:real; i:integer; begin for i:= 2 to 20 do begin y := (1+(i-1)(i-1)/(i-1)); x := (y+1); x:= (((x+y)2)-6)*2; writeln ( x ); end; end. 2 и 4 не использует и все, понимаю,что код составил не так,но что не так,не понимаю.

	Роман	19.02.2015 в 17:08
Я, наверное что-то не понял. Но для получения ряда в задании 1е у меня вышел такой код: var z,x,y:integer; begin writeln(‘введите y ‘); readln(y); z:=1; for x:=1 to y do begin z:=2*z; writeln(z); end; end.

АленА

05.03.2015 в 22:48

4_в писали, что проще нельзя, а мне кажется, что так еще проще:

program chetvertaja_v;
var
i:integer;
p:real;
begin
p:=sqrt(98);
for i:= 48 downto 1 do
p:=sqrt(p+(2*i));
writeln (p);
end.

Ответ: 2.15847687231104

АленА

05.03.2015 в 22:52

Роман, у меня 1_е похоже, но, можно вывести через запятую, чтоб совсем идеально:

program pervaja_e;
var
x,i,n: integer;
begin
writeln(‘введите количество чисел ряда, которые нужно вывести’);
readln(x);
n:=1;
for i:= 1 to x do
begin
n:=n*2;
write (n,’, ‘);
end;
end.

АленА

05.03.2015 в 23:05

Роман, в условии нужно придумать рекуррентное соотношение.
1_е будет так:

program pervaja_e;
var
x,i: integer;
n: real;
function f(m:integer): real;
begin
f:=exp(ln(2)*m);
end;
begin
n:=0;
for i:= 1 to 4 do
begin
n:=f(i);
write (n,’, ‘);
end;
write (‘…’);
end.

АленА

06.03.2015 в 00:47

2_б еще таким соотношением вывести можно:

program pervaja_b;
var
x, i, n: integer;
function f(m:integer): integer;
begin
f:=m*5;
end;
begin
writeln(‘введите количество чисел ряда, которые нужно вывести’);
readln(x);
n:=0;
for i:= 0 to x-1 do
begin
n:=f(i);
write (n,’, ‘);
end;
write (‘…’);
end.

АленА

06.03.2015 в 00:50

4 а, б, в — решила без реккурентного соотношения, например:

program chetvertaja_a;
var
i:integer;
p:real;
begin
p:=0;
for i:= 1 to 100 do
p:=1+1/p;
writeln (p);
end.
Ответ: Золотое сечение = 1.618…

Или так и надо было?

Taras

06.03.2015 в 18:54

p:=1+1/p; — значение p на каждом шаге определяется по его предыдущему значению. Это и есть рекуррентное соотношение.

$p_{n+1}=1 + \frac{\displaystyle 1}{\displaystyle p_n}$

Персональная страничка Диканева Тараса Викторовича

4. Вычисления с помощью рекуррентных соотношений

4.2. Задачи на составление рекуррентных соотношений

35 комментариев

Добавить комментарий

Персональная страничка
Диканева Тараса
Викторовича