Язык Си в примерах/Треугольник Паскаля: различия между версиями
Содержимое удалено Содержимое добавлено
ISbot (обсуждение | вклад) м Замена <tt /> на <code />; избыточные <big /> и <font /> вокруг <source />; {{SUBPAGENAME}}; пробелы. |
Добавил 2 варианта реализации поиска Биномиального коэффициента, дополнение |
||
Строка 83:
время работы пропорционально <math>n^2\,\!</math>.
* Начиная с какого ''n'' самое большое число из ''n''-й строчки треугольника Паскаля не умещается в тип <code>long</code>?
Еще 1 вариант реализации вычисления Биномиального коэффициента из общей формулы <math>C_n^k\,\!</math> (без рекурсии):
<source lang="C">
/*
Вычисление биномиальных коэффициентов
*/
#include <stdio.h>
#include <assert.h>
int binomial(int row, int pos){
int koef=1;
int i;
for(i=pos+1;i<=row;i++)
koef=koef*i;
for(i=1;i<(row-pos+1);i++)
koef=koef/i;
return koef;
}
int main (void){
int row, pos;
int r
= scanf("%i%i",&row,&pos);
assert(r==2);
printf("%i",binomial(row,pos));
return 0;
}
</source>
Если посмотреть на Треугольник Паскаля, то можно заметить симметрию. Если исходить из нее и общей формулы <math>C_n^k\,\!</math>, то можно еще немного улучшить алгоритм (уменьшив число проходов) из кода выше сокращая числитель на больщий элемент знаменателя:
<source lang="C">
/*
Вычисление биномиальных коэффициентов
*/
#include <stdio.h>
#include <assert.h>
int binomial(int row, int pos){
int koef=1;
int i;
if(row-pos>pos) pos=row-pos;
for(i=pos+1;i<=row;i++)
koef=koef*i;
for(i=1;i<(row-pos+1);i++)
koef=koef/i;
return koef;
}
int main (void){
int row, pos;
int r
= scanf("%i%i",&row,&pos);
assert(r==2);
printf("%i",binomial(row,pos));
return 0;
}
</source>
[[Категория:Язык Си в примерах|{{SUBPAGENAME}}]]
| |||