Язык Си в примерах/Треугольник Паскаля: различия между версиями
Нет описания правки |
оформление |
||
Строка 35: | Строка 35: | ||
<source lang="c"> |
<big><source lang="c"> |
||
/* |
/* |
||
Вычисление биномиальных коэффициентов. |
Вычисление биномиальных коэффициентов. |
||
Строка 50: | Строка 50: | ||
return 0; |
return 0; |
||
} |
} |
||
</source> |
</source></big> |
||
* Сколько раз вызовется функция C(., .) при вычислении С(n, k)? |
* Сколько раз вызовется функция C(., .) при вычислении С(n, k)? |
||
Строка 57: | Строка 57: | ||
<math>\log C_n^{n/2}\,\!</math> от <math>n</math>. |
<math>\log C_n^{n/2}\,\!</math> от <math>n</math>. |
||
<source lang="c"> |
<big><source lang="c"> |
||
/* |
/* |
||
Вычисление n-й строки треугольника Паскаля. |
Вычисление n-й строки треугольника Паскаля. |
||
Строка 77: | Строка 77: | ||
return 0; |
return 0; |
||
} |
} |
||
</source> |
</source></big> |
||
* Докажите, что указанный алгоритм вычисления ''n''-й строчки треугольника Паскаля |
* Докажите, что указанный алгоритм вычисления ''n''-й строчки треугольника Паскаля |
Версия от 11:20, 1 мая 2012
- Компиляция программ
- Простейшая программа «Hello World»
- Учимся складывать
- Максимум
- Таблица умножения
- ASCII-коды символов
- Верхний регистр
- Скобочки
- Факториал
- Степень числа
- Треугольник Паскаля
- Корень уравнения
- Система счисления
- Сортировка
- Библиотека complex
- Сортировка на основе qsort
- RPN-калькулятор
- RPN-калькулятор на Bison
- Простая грамматика
- Задача «Расчёт сопротивления схемы»
- Простая реализация конечного автомата
- Использование аргументов командной строки
- Чтение и печать без использования stdio
- Декодирование звукозаписи в формате ADX
- Другие примеры
Всем известны простые формулы
А как находить коэффициенты в разложении ?
Рассмотрим следующую таблицу:
То, что нарисовано справа, называется треугольником Паскаля — в n-й строчке этого треугольника находятся коэффициенты для разложения .
Число номер в n-й строчке называется биномиальным коэффициентом .
Например,
Стороны треугольника Паскаля состоят из единичек. Каждое число внутри треугольника Паскаля равно сумме двух чисел, стоящих над ним справа и слева в предыдущей строчке:
Эти числа возникают в задаче о числе сочетаний: — это число способов выбрать k элементов из n различных. Например, число байт, в которых ровно 3 единицы — это число — число способов выбрать три бита, в которых будут стоять единицы, из восьми бит байта.
Докажите, что
Рассмотрим две программы, которые решают следующие задачи:
- Запрограммировать функцию .
- Вывести на экран n строчек треугольника Паскаля.
/*
Вычисление биномиальных коэффициентов.
*/
#include <stdio.h>
long C(long n,long k) {
if(k == 0 || n == k) return 1;
return C(n - 1, k - 1) + C(n - 1, k);
}
int main() {
long n, k;
scanf ("%ld%ld", &n, &k);
printf ("%ld ", C(n, k));
return 0;
}
- Сколько раз вызовется функция C(., .) при вычислении С(n, k)?
- Докажите, что время вычисления по приведенному алгоритму пропорционально .
- Оцените ассимптотику , а именно, напишите программу, которая вычисляет для и нарисуйте график
от .
/*
Вычисление n-й строки треугольника Паскаля.
*/
#include <stdio.h>
#define N 1000
long c[N];
int main () {
long n, i, j;
scanf ("%ld",&n);
for(i = 1; i <= n; i++)
c[i] = 0;
c[0] = 1;
for(j = 1; j <= n; j++)
for(i = j; i >= 1; i--)
c[i] = c[i-1] + c[i];
for(i = 0; i <= n; i++)
printf ("%ld ", c[i]);
return 0;
}
- Докажите, что указанный алгоритм вычисления n-й строчки треугольника Паскаля
работает быстрее, чем алгоритм вычисления из предыдущей программы, а именно время работы пропорционально .
- Начиная с какого n самое большое число из n-й строчки треугольника Паскаля не умещается в тип long?