Язык Си в примерах/Треугольник Паскаля: различия между версиями
Содержимое удалено Содержимое добавлено
м дополнение |
Переоформлены примеры кода (включая $ indent -gnu -br); использован шаблон {{BookCat}} (была: явная категория); удалены лишние пустые строки. |
||
Строка 23:
Эти числа возникают в задаче о числе сочетаний: <math>C_n^k\,\!</math> — это число способов выбрать ''k'' элементов из ''n'' различных. Например, число байт, в которых ровно 3 единицы — это число <math>C_8^3\,\!</math> — число способов выбрать три бита, в которых будут стоять единицы, из восьми бит байта.
Докажите, что
<math>C_n^1=n,\quad C_n^k+C_n^{k+1} = C_{n+1}^{k+1}, \quad C_n^k = \frac{n!}{k! (n-k)!}.\,\!</math>
Рассмотрим две программы, которые решают следующие задачи:
# Запрограммировать функцию <math>C(n,k) = C_n^k\,\!</math>.
# Вывести на экран ''n'' строчек треугольника Паскаля.
<source lang="c">
Вычисление биномиальных коэффициентов.
*/
long C(long n,long k) {▼
long
if(k == 0 || n == k) return 1;▼
{
}▼
return
printf ("%ld ", C(n, k));▼
return 0;▼
}▼
main ()
{
scanf ("%ld%ld", &n, &k);
</source>
Строка 58 ⟶ 61 :
<source lang="c">
▲ long c[N];
main () { long c[N];
long n, i, j; for
for
for
for
</source>
Строка 84 ⟶ 90 :
* Начиная с какого ''n'' самое большое число из ''n''-й строчки треугольника Паскаля не умещается в тип <code>long</code>?
Еще
▲Еще 1 вариант реализации вычисления Биномиального коэффициента из общей формулы <math>C_n^k\,\!</math> (без рекурсии):
<source lang="C">
Строка 91 ⟶ 96 :
Вычисление биномиальных коэффициентов
*/
#include <stdio.h>▼
#include <assert.h>
▲#include <stdio.h>
int koef=1;▼
{
▲ 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);
▲ int r
assert (r ==
printf ("%i", binomial (row, pos));▼
▲ printf("%i",binomial(row,pos));
return 0;
}
Строка 120 ⟶ 128 :
Вычисление биномиальных коэффициентов
*/
#include <stdio.h>▼
#include <assert.h>
▲#include <stdio.h>
int
int koef=1;▼
{
▲ 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);
▲ int r
assert (r ==
printf ("%i", binomial (row, pos));▼
▲ printf("%i",binomial(row,pos));
return 0;
}
Строка 146 ⟶ 158 :
Стоит учитывать, что в реализованных примерах нет защиты от дурака (переполнение значения переменной).
{{BookCat}}
| |||