Задача.
Для заданных [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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <ctime> using namespace std; int main() { unsigned int start_time1,start_time2,start_time3,search_time1,search_time2,search_time3; int i,y,u,m,n,h,j,x; long long c3=0; cin>>m; cin>>n; double k=m,c2=1,c1; long long D[m+3][n+1]; double b=m-n, q=n, w=m, z=b; if(m>n && n>=1) { start_time1 = clock(); for(i=1;i<n;i++) {q=q*i;} for(y=1;y<m;y++) {w=w*y;} for(u=1;u<b;u++) {z=z*u;} c1=w/(q*z); cout<<"По первой формуле равно:"<<c1<<" "<<endl; search_time1 = clock() - start_time1; start_time2 = clock(); for(i=n;i>=1;i--) { c2*=(k-i+1)/i; } cout<<"По второй формуле равно:"<<c2<<" "<<endl; search_time2 = clock() - start_time2; start_time3 = clock(); for(y=1;y<=m;y++) // Для каждой строки. { D[y][1]=y; D[y][y]=1; for(x=2;x<=n && x<y;x++) { D[y][x]=D[y-1][x-1]+D[y-1][x]; } } c3=D[m][n]; cout<<"По третьей формyле равно:"<<c3<<" "<<endl; search_time3 = clock() - start_time3; } else if(m<n) { cout<<"invalid"; } cout<<"Первая формула сработала за:(в милисек)"<<((double)search_time1/CLOCKS_PER_SEC)*1000<<endl; cout<<"Вторая формула сработала за:(в милисек)"<<(double)search_time2/CLOCKS_PER_SEC*1000<<endl; cout<<"Третья формула сработала за:(в милисек)"<<(double)search_time3/CLOCKS_PER_SEC*1000<<endl; if(search_time1<search_time2 && search_time1<search_time3) { cout<<"Первая формула выполняется быстрее."<<endl; } else if(search_time2<search_time1 && search_time2<search_time3) { cout<<"Вторая формула выполняется быстрее."<<endl; } else if(search_time3<search_time2 && search_time3<search_time1) { cout<<"Третья формула выполняется быстрее."<<endl; } return 0; } |
Ход решения:
1.С помощью цикла [latex]for[/latex] и функции [latex]clock[/latex] я нахожу число сочетаний и время вычислений.
Чтобы посчитать время вычислений по второй рекуррентной формуле я воспользовался Треугольником Паскаля.
Треугольник Паскаля хранится в двумерном массиве и заполняется по указанной в условии формуле начиная с верхнего левого угла.
2.Вывожу число сочетаний
3.С помощью условного оператора [latex]if[/latex] я сравниваю время вычислений.
Ссылка на код
Рекуррентная формула — это выражение некоторого члена определенной последовательности через предыдущие. Предыдущий член тоже можно выразить по рекуррентной формуле и т.д. пока не дойдете до конечного случая (С_1_m=m для первой формулы, C_m_m во втором).
m,n — целые
в первой формуле — используются целые числа
во второй формуле — использовать вещественные
в третьей формуле 0- целые числа
третью формулу можно реализовать в лоб через рекурсию (функция) либо через динамическое программирование (нужен двухмерный массив).
В третьей формуле дописать условие C_0_m=1 и реализовать в двойном цикле вычисление по формуле с сохранением в массиве.
Исправлено (в очном режиме) и засчитано, 10 баллов.