Язык Си в примерах/Треугольник Паскаля: различия между версиями
Ashikbot (обсуждение | вклад) м Категоризация по запросу на w:ВП:РДБ |
Нет описания правки |
||
Строка 9: | Строка 9: | ||
Рассмотрим следующую таблицу: |
Рассмотрим следующую таблицу: |
||
[[ |
[[Файл:pascal.png]] |
||
То, что нарисовано справа, называется ''треугольником Паскаля'' |
То, что нарисовано справа, называется ''треугольником Паскаля'' — в ''n''-й строчке этого треугольника находятся коэффициенты для разложения <math>(a+b)^n\,\!</math>. |
||
этого треугольника находятся коэффициенты для разложения <math>(a+b)^n\,\!</math>. |
|||
Число номер <math>k+1</math> в |
Число номер <math>k+1</math> в ''n''-й строчке называется биномиальным коэффициентом <math>C_n^k\,\!</math>. |
||
Например, |
Например, |
||
<math>C_3^0 = 1, \quad C_5^2 = 10, \quad C_4^2 = 6.\,\!</math> |
<math>C_3^0 = 1, \quad C_5^2 = 10, \quad C_4^2 = 6.\,\!</math> |
||
Стороны |
Стороны треугольника Паскаля состоят из единичек. Каждое число внутри треугольника Паскаля равно сумме двух чисел, стоящих над ним справа и слева в предыдущей строчке: |
||
<math>C^{k+1}_{n+1} = C^{k+1}_{n}+C^k_{n}.</math> |
<math>C^{k+1}_{n+1} = C^{k+1}_{n}+C^k_{n}.</math> |
||
Эти числа возникают в задаче о числе сочетаний: <math>C_n^k\,\!</math> |
Эти числа возникают в задаче о числе сочетаний: <math>C_n^k\,\!</math> — это число способов выбрать ''k'' элементов из ''n'' различных. Например, число байт, в которых ровно 3 единицы — это число <math>C_8^3\,\!</math> — число способов выбрать три бита, в которых будут стоять единицы, из восьми бит байта. |
||
число способов выбрать ''k'' элементов из ''n'' различных. Например, |
|||
чиcло байт, в которых ровно 3 единицы — это число <math>C_8^3\,\!</math> — |
|||
число способов выбрать три бита, в которых будут стоять единицы, |
|||
из воcьми бит байта. |
|||
Строка 36: | Строка 31: | ||
Рассмотрим две программы, которые решают следующие задачи: |
Рассмотрим две программы, которые решают следующие задачи: |
||
# Запрограммировать функцию |
# Запрограммировать функцию <math>C(n,k) = C_n^k\,\!</math>. |
||
# Вывести на экран |
# Вывести на экран ''n'' строчек треугольника Паскаля. |
||
Строка 57: | Строка 52: | ||
</source> |
</source> |
||
* Сколько раз вызовется функция |
* Сколько раз вызовется функция C(., .) при вычислении С(n, k)? |
||
* Докажите, что время вычисления <math>C_n^k\,\!</math> по приведенному алгоритму пропорционально <math>C_n^k\,\!</math>. |
* Докажите, что время вычисления <math>C_n^k\,\!</math> по приведенному алгоритму пропорционально <math>C_n^k\,\!</math>. |
||
* Оцените ассимптотику <math>C_n^{n/2}\,\!</math>, а именно, напишите программу, которая вычисляет <math>\log C_n^{n/2}\,\!</math> для <math>n = 2, 4, ... , 40</math> и |
* Оцените ассимптотику <math>C_n^{n/2}\,\!</math>, а именно, напишите программу, которая вычисляет <math>\log C_n^{n/2}\,\!</math> для <math>n = 2, 4, ... , 40</math> и нарисуйте график |
||
<math>\log C_n^{n/2}\,\!</math> от <math>n</math>. |
<math>\log C_n^{n/2}\,\!</math> от <math>n</math>. |
||
Строка 83: | Строка 78: | ||
</source> |
</source> |
||
* Докажите, что указанный алгоритм вычисления |
* Докажите, что указанный алгоритм вычисления ''n''-й строчки треугольника Паскаля |
||
работает быстрее, чем алгоритм вычисления <math>C_n^k\,\!</math> из предыдущей программы, а именно |
работает быстрее, чем алгоритм вычисления <math>C_n^k\,\!</math> из предыдущей программы, а именно |
||
время работы пропорционально <math>n^2\,\!</math>. |
время работы пропорционально <math>n^2\,\!</math>. |
||
* Начиная с какого |
* Начиная с какого ''n'' самое большое число из ''n''-й строчки треугольника Паскаля не умещается в тип <tt>long</tt>? |
||
[[Категория:Язык Си в примерах|Треугольник Паскаля]] |
[[Категория:Язык Си в примерах|Треугольник Паскаля]] |
Версия от 01:14, 6 декабря 2009
- Компиляция программ
- Простейшая программа «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)?
- Докажите, что время вычисления по приведенному алгоритму пропорционально .
- Оцените ассимптотику , а именно, напишите программу, которая вычисляет для и нарисуйте график
от .
/*
Вычисление <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?