Вычисление суммы необычного ряда (6)

echs · Регистрация: 23.10.2013

Студворк — интернет-сервис помощи студентам

Надо вычислить сумму 100 слагаемых
f(1)^.07 + f(2)^.07 + ... + f(100)^.07
где f(i) - число Фибоначчи. Программа сосчитала и получила
число 800.0099. В качестве ответа можно записать 800.01

Вопросы
1. Как можно решить иначе?
2. Можно ли сократить вычисления? Ведь тут
числа Фибоначчи есть в каждом слагаемое.
3. Сложно ли понять программу? Что тут лишнее?

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
REM
REM  S = 800.0099
REM
 
DECLARE FUNCTION f! (n!, a!, b!)
 
CLS
CLEAR , , 20000
 
FOR n = 1 TO 100
   S = S + f(n, 1, 1) ^ .07
NEXT
 
PRINT S
END
 
FUNCTION f (n, a, b)
   IF n <= 2 THEN
      f = a
   ELSE
      f = f(n - 1, a + b, a)
   END IF
END FUNCTION

@volvo · 20.09.2016, 13:20

Можно ли сократить вычисления?

Можно. Убрав рекурсию, например:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
var 
  a, b, f : double;
  s : double;
begin
  a := 0; b := 1; s := 1;
  for var i := 1 to 99 do
  begin
    f := a + b; a := b; b := f;
    s := s + power(f, 0.07);
  end;
  writeln(s:0:3);
end.

@m-ch · 20.09.2016, 13:33

чем данная задача отличается от простого вычисления чисел Фибоначчи?

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
DIM i AS LONG, a AS DOUBLE, b AS DOUBLE, s AS DOUBLE
a = 1
s = a
FOR i = 2 TO 100
    a = a + b
    b = a - b
    s = s + a ^ 0.07
NEXT i
PRINT s

echs · 20.09.2016, 14:48 **[ТС]**

volvo
Спасибо!
volvo,
А вы уверены, что вычислений стало меньше?

m-ch,
Вы задали хороший вопрос. Но посмотрите на
рекурсивную функцию, это совсем не то, что я
обычно пишу. (Обычно - это один параметр).

@volvo · 20.09.2016, 14:57

А вы уверены, что вычислений стало меньше?

Конечно. Простая проверка, чтобы определить, сколько раз программа заходит в рекурсивную функцию:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var 
  count : integer := 0;
function f(n : integer; a, b : double) : double;
begin
  inc(count);
  if n <= 2 then result := a
  else result := f(n - 1, a+b, a);
end;
 
var s : double;
begin
  for var i := 1 to 100 do s := s + power(f(i, 1, 1), 0.07);
  writeln(s:0:3);
  writeln(count);
end.

Вывод программы:

Code
1
2
800.010
4951

Почти 5 тысяч раз. Еще вопросы остались?

echs · 20.09.2016, 15:26 **[ТС]**

volvo
Спасибо еще раз! И извините меня за то, что я
усомнился в вашей программе. Просто невероятно!!
Я был так уверен, что моя рекурсивная функция на
этот раз не даст сбоя и что разница если и будет, то
Невелика! СПАСИБО!
...
Вот уж никак не думал... и где это рекурсивная функция
успела "наследить"? (Наверное я сделал что-то не так?)
Или так? И лучше невозможно?

@m-ch · 20.09.2016, 17:36

Сообщение от echs

Но посмотрите на
рекурсивную функцию, это совсем не то, что я
обычно пишу.

Конечно данная реализация лучше, чем просто f(n)=f(n-1)+f(n-2), иначе f(100) мы бы просто не дождались.
Но если задача без рекурсий решается проще, зачем притягивать рекурсию "за уши"?

Если вычислять последовательно числа Фибоначчи и на каждой итерации производить с ними вычисления, то потребуется максиму 100 (99) итераций.
Если же каждый раз вычислять число Фибоначчи раскручивая рекурсиями с n-го числа до первого (ли с первого до n-го без рекурсий), то за 99 последовательных вычислений, число запусков рекурсий будет 1+2+3+...+98+99 = (1+99)/2*99 = 4950 запусков

echs · 20.09.2016, 17:46 **[ТС]**

m-ch
Я хочу разобраться основательно.
Если запоминать (в массив) каждое вычисленное
значение функции, то это будет лучше? Или есть
иные варианты? Наверняка эту функцию все-же
можно улучшить?

@m-ch · 20.09.2016, 18:07

можно функцию вычисления числа Фибоначчи реализовать без рекурсий:

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
FUNCTION f#(n AS LONG)
    DIM i AS LONG, a AS DOUBLE, b AS DOUBLE
    IF n < 1 THEN EXIT FUNCTION
    a = 1
    FOR i = 2 TO n
        a = a + b
        b = a - b
    NEXT i
    f = a
END FUNCTION

Добавлено через 5 минут

Сообщение от echs

Если запоминать (в массив) каждое вычисленное
значение функции, то это будет лучше?

Зачем тогда вообще рекурсия если будем использовать массив?

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
DIM i AS LONG, f(100) AS DOUBLE, s AS DOUBLE
f(1) = 1
s = 1
FOR i = 2 TO 100
    f(i) = f(i - 1) + f(i - 2)
    s = s + f(i) ^ 0.07
NEXT i
PRINT s

echs · 20.09.2016, 18:09 **[ТС]**

m-ch
СПАСИБО!!
...
А вот вопрос остался. Можно ли написать такую
рекурсивную программу, чтобы она не повторяла
свои вычисления? Ну например дать ей параметры,
которые будут все запоминать, как при обычном
вычислении этой функции?

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

Вычисление суммы необычного ряда (6)

Решение

Решение

Решение

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	20.09.2016, 14:48 [ТС]
	volvo Спасибо! volvo, А вы уверены, что вычислений стало меньше? m-ch, Вы задали хороший вопрос. Но посмотрите на рекурсивную функцию, это совсем не то, что я обычно пишу. (Обычно - это один параметр). 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	20.09.2016, 15:26 [ТС]
	volvo Спасибо еще раз! И извините меня за то, что я усомнился в вашей программе. Просто невероятно!! Я был так уверен, что моя рекурсивная функция на этот раз не даст сбоя и что разница если и будет, то Невелика! СПАСИБО! ... Вот уж никак не думал... и где это рекурсивная функция успела "наследить"? (Наверное я сделал что-то не так?) Или так? И лучше невозможно? 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	20.09.2016, 17:46 [ТС]
	m-ch Я хочу разобраться основательно. Если запоминать (в массив) каждое вычисленное значение функции, то это будет лучше? Или есть иные варианты? Наверняка эту функцию все-же можно улучшить? 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	20.09.2016, 18:09 [ТС]
	m-ch СПАСИБО!! ... А вот вопрос остался. Можно ли написать такую рекурсивную программу, чтобы она не повторяла свои вычисления? Ну например дать ей параметры, которые будут все запоминать, как при обычном вычислении этой функции? 0