Язык Си в примерах/Треугольник Паскаля: различия между версиями
Нет описания правки |
правки |
||
Строка 24: | Строка 24: | ||
Эти числа возникают в задаче о числе сочетаний: <math>C_n^k\,\!</math> — это |
Эти числа возникают в задаче о числе сочетаний: <math>C_n^k\,\!</math> — это |
||
число способов |
число способов выбрать ''k'' элементов из ''n'' различных. Например, |
||
чиcло байт, в которых ровно 3 единицы — это число <math>C_8^3\,\!</math> — |
чиcло байт, в которых ровно 3 единицы — это число <math>C_8^3\,\!</math> — |
||
число способов выбрать три бита, в которых будут стоять единицы, |
число способов выбрать три бита, в которых будут стоять единицы, |
||
Строка 64: | Строка 64: | ||
<source lang="c"> |
<source lang="c"> |
||
/* |
/* |
||
Вычисление треугольника Паскаля. |
Вычисление <i>n</i>-й строки треугольника Паскаля. |
||
*/ |
*/ |
||
#include <stdio.h> |
#include <stdio.h> |
Версия от 10:23, 5 июля 2008
- Компиляция программ
- Простейшая программа «Hello World»
- Учимся складывать
- Максимум
- Таблица умножения
- ASCII-коды символов
- Верхний регистр
- Скобочки
- Факториал
- Степень числа
- Треугольник Паскаля
- Корень уравнения
- Система счисления
- Сортировка
- Библиотека complex
- Сортировка на основе qsort
- RPN-калькулятор
- RPN-калькулятор на Bison
- Простая грамматика
- Задача «Расчёт сопротивления схемы»
- Простая реализация конечного автомата
- Использование аргументов командной строки
- Чтение и печать без использования stdio
- Декодирование звукозаписи в формате ADX
- Другие примеры
Всем известны простые формулы
А как находить коэффициенты в разложении ?
Рассмотрим следующую таблицу:
То, что нарисовано справа, называется треугольником Паскаля — в n-й строчке этого треугольника находятся коэффициенты для разложения .
Число номер в n-й строчке называется биномиальным коэффициентом .
Например,
Стороны треугольника Паскаля состоят из единичек. Каждое число внутри треугольника Паскаля равно сумме двух чисел, стоящих над ним справа и слева в предыдущей строчке:
Эти числа возникают в задаче о числе сочетаний: — это число способов выбрать k элементов из n различных. Например, чиcло байт, в которых ровно 3 единицы — это число — число способов выбрать три бита, в которых будут стоять единицы, из воcьми бит байта.
Докажите, что
Рассмотрим две программы, которые решают следующие задачи:
- Запрограммировать функцию .
- Вывести на экран 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)?
- Докажите, что время вычисления по приведенному алгоритму пропорционально .
- Оцените ассимптотику , а именно, напишите программу, которая вычисляет для и нарисуте график
от .
/*
Вычисление <i>n</i>-й строки треугольника Паскаля.
*/
#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?