Викиучебник

Язык Си в примерах/Треугольник Паскаля: различия между версиями

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
мНет описания правки
мНет описания правки
Строка 1:
{{Содержание «Язык Си в примерах»}}
 
Всем известны простые формулы
* <math>(a+b)^2 = a^2 + 2ab + b^2</math>
* <math>(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3</math>
 
А как находить коэффициенты в разложении <math>(a+b)^n</math>?
 
Рассмотрим следующую таблицу:
 
[[Изображение:pascal.png]]
Строка 8 ⟶ 14 :
этого треугольника находятся коэффициенты для разложения <math>(a+b)^n\,\!</math>.
 
Число номер <math>k+1</math> в <i>n</i>-ойй строчке называется биномиальным коэффициентом <math>C''nC_n^k\,\!</math>.
Например,
<math>C''3C_3^0 = 1, \quad C''5C_5^2 = 10, \quad C''4C_4^2 = 6.\,\!</math>
 
Стороны треугольника Паскаля состоят из единичек. Каждое число внутри треугольника Паскаля равно сумме двух чисел, стоящих над ним справа и слева в предыдущей строчке:
 
<math>C^{k+1}_{n+1} = C^{k+1}_{n}+C^k_{n}.</math>
 
Эти числа возникают в задаче о числе сочетаний: <math>C''nC_n^k\,\!</math> &mdash; это
число способов быбрать ''k'' элементов из ''n'' различных. Например,
чиcло байт, в которых ровно 3 единицы &mdash; это число <math>C''8C_8^3\,\!</math> &mdash;
число способов выбрать три бита, в которых будут стоять единицы,
из возьмивоcьми бит байта.
 
Обратите внимание на то, что каждое число в треугольнике Паскаля равно сумме двух чисел
из предыдущей строчки, которые находятся над ним.
 
 
Докажите, что
<math>C''nC_n^1=n,\quad C''nC_n^k+C''n^{k+1} = C''C_{n+1}^{k+1}, \quad C''nC_n^k = \frac{n!}{k! (n-k!)}.\,\!</math>
 
 
Рассмотрим две программы, которыерешаюткоторые решают следующие задачи:
# Запрограммировать функцию <math>C(n,k) = C''nC_n^k\,\!</math>.
# Вывести на экран <i>n</i> строчек треугольника Паскаля.
 
 
Строка 36 ⟶ 44 :
*/
#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);
Строка 50 ⟶ 56 :
 
 
* Сколько раз вызовется функция C(., .) при вычислении С(n, k)?
* Докажите, что время вычисления <math>C''nC_n^k\,\!</math> по приведенному алгоритму пропорционально <math>C''nC_n^k\,\!</math>.
* Оцените ассимптотику <math>C''nC_n^{n/2}\,\!</math>, а именно, напишите программу, которая вычисляет <math>\log C''nC_n^{n/2}\,\!</math> для n=2, 4, ... , 40 и нарисуте график <math>\log C''nC_n^{n/2}\,\!</math> от n.
 
 
Строка 61 ⟶ 67 :
#define N 1000
long c[N];
int main () {
{
long n, i, j;
scanf ("%ld",&n);
Строка 76 ⟶ 81 :
 
 
*Докажите, что указанный алгоритм вычисления ''<i>n'' </i>-ойй строчки треугольника Паскаля
работает быстрее, чем алгоритм вычисления <math>C''n^k\,\!</math> из предыдущей программы, а именно
время работы пропорционально <math>n^2\,\!</math>.
*Начиная с какого ''n'' самое большой число из ''<i>n'' </i>-ойй строчки не умещается в тип <tt>long</tt>?
Источник — https://ru.wikibooks.org/wiki/Язык_Си_в_примерах/Треугольник_Паскаля