Ю3.25

Задача.

Для заданных [latex]m[/latex] и [latex]n[/latex] вычислить число сочетаний [latex]C_m^n[/latex] непосредственно: [latex]C_m^n=\frac{m!}{n!(m-n)!}[/latex] и по рекуррентным формулам:

• [latex]C_m^n=\frac{m-n+1}{n}\cdot C_m^{n-1}, C_m^1=m;[/latex]

• [latex]C_m^n=C_{m-1}^{n-1}+C_{m-1}^n;C_m^1=m,C_m^m=1.[/latex]

Сравнить время вычислений(или число операций) по каждой формуле.

Тесты:

[latex]m[/latex] [latex]n[/latex] [latex]C_m^n[/latex] Комментарий
122 12  

По первой формуле равно: 1.29803e+16

По второй формуле равно: 1.29803e+16

По третьей формуле равно: 12980291311103116

Первая формула сработала за(в милисек):0.056

Вторая формула сработала за(в милисек):0.009

Третья формула сработала за(в милисек):0.021

 

Пройдено
14 5  

По первой формуле  равно: 2002

По второй формуле равно: 2002

По третьей формуле равно: 2002

Первая формула сработала за(в милисек):0.064

Вторая формула сработала за(в милисек): 0.009

Третья формула сработала за(в милисек):  0.012

Пройдено
16 7 По первой формуле  равно: 11440

По второй формуле равно: 11440

По третьей формуле равно: 11440

Первая формула сработала за(в милисек):0.067

Вторая формула сработала за(в милисек): 0.009

Третья формула сработала за(в милисек):  0.012

Пройдено

Код программы:

Ход решения:

1.С помощью цикла [latex]for[/latex] и функции [latex]clock[/latex] я нахожу число сочетаний и время вычислений.

Чтобы посчитать время вычислений по второй рекуррентной формуле я воспользовался Треугольником Паскаля.

Треугольник Паскаля хранится в двумерном массиве и заполняется по указанной в условии формуле начиная с верхнего левого угла.

2.Вывожу число сочетаний

3.С помощью условного оператора [latex]if[/latex] я сравниваю время вычислений.

Ссылка на код

 

 

Related Images:

2 thoughts on “Ю3.25

  1. Рекуррентная формула — это выражение некоторого члена определенной последовательности через предыдущие. Предыдущий член тоже можно выразить по рекуррентной формуле и т.д. пока не дойдете до конечного случая (С_1_m=m для первой формулы, C_m_m во втором).
    m,n — целые
    в первой формуле — используются целые числа
    во второй формуле — использовать вещественные
    в третьей формуле 0- целые числа

    третью формулу можно реализовать в лоб через рекурсию (функция) либо через динамическое программирование (нужен двухмерный массив).
    В третьей формуле дописать условие C_0_m=1 и реализовать в двойном цикле вычисление по формуле с сохранением в массиве.

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