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

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
м Категоризация по запросу на w:ВП:РДБ
Нет описания правки
Строка 9: Строка 9:
Рассмотрим следующую таблицу:
Рассмотрим следующую таблицу:


[[Изображение:pascal.png]]
[[Файл:pascal.png]]


То, что нарисовано справа, называется ''треугольником Паскаля'' &mdash; в <i>n</i>-й строчке
То, что нарисовано справа, называется ''треугольником Паскаля'' — в ''n''-й строчке этого треугольника находятся коэффициенты для разложения <math>(a+b)^n\,\!</math>.
этого треугольника находятся коэффициенты для разложения <math>(a+b)^n\,\!</math>.


Число номер <math>k+1</math> в <i>n</i>-й строчке называется биномиальным коэффициентом <math>C_n^k\,\!</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> &mdash; это
Эти числа возникают в задаче о числе сочетаний: <math>C_n^k\,\!</math> — это число способов выбрать ''k'' элементов из ''n'' различных. Например, число байт, в которых ровно 3 единицы — это число <math>C_8^3\,\!</math> — число способов выбрать три бита, в которых будут стоять единицы, из восьми бит байта.
число способов выбрать ''k'' элементов из ''n'' различных. Например,
чиcло байт, в которых ровно 3 единицы &mdash; это число <math>C_8^3\,\!</math> &mdash;
число способов выбрать три бита, в которых будут стоять единицы,
из воcьми бит байта.




Строка 36: Строка 31:


Рассмотрим две программы, которые решают следующие задачи:
Рассмотрим две программы, которые решают следующие задачи:
# Запрограммировать функцию <math>C(n,k) = C_n^k\,\!</math>.
# Запрограммировать функцию <math>C(n,k) = C_n^k\,\!</math>.
# Вывести на экран <i>n</i> строчек треугольника Паскаля.
# Вывести на экран ''n'' строчек треугольника Паскаля.




Строка 57: Строка 52:
</source>
</source>


* Сколько раз вызовется функция C(., .) при вычислении С(n, k)?
* Сколько раз вызовется функция 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>


* Докажите, что указанный алгоритм вычисления <i>n</i>-й строчки треугольника Паскаля
* Докажите, что указанный алгоритм вычисления ''n''-й строчки треугольника Паскаля
работает быстрее, чем алгоритм вычисления <math>C_n^k\,\!</math> из предыдущей программы, а именно
работает быстрее, чем алгоритм вычисления <math>C_n^k\,\!</math> из предыдущей программы, а именно
время работы пропорционально <math>n^2\,\!</math>.
время работы пропорционально <math>n^2\,\!</math>.
* Начиная с какого <i>n</i> самое большое число из <i>n</i>-й строчки треугольника Паскаля не умещается в тип <tt>long</tt>?
* Начиная с какого ''n'' самое большое число из ''n''-й строчки треугольника Паскаля не умещается в тип <tt>long</tt>?
[[Категория:Язык Си в примерах|Треугольник Паскаля]]
[[Категория:Язык Си в примерах|Треугольник Паскаля]]

Версия от 01:14, 6 декабря 2009

Язык Си в примерах


  1. Компиляция программ
  2. Простейшая программа «Hello World»
  3. Учимся складывать
  4. Максимум
  5. Таблица умножения
  6. ASCII-коды символов
  7. Верхний регистр
  8. Скобочки
  9. Факториал
  10. Степень числа
  11. Треугольник Паскаля
  12. Корень уравнения
  13. Система счисления
  14. Сортировка
  15. Библиотека complex
  16. Сортировка на основе qsort
  17. RPN-калькулятор
  18. RPN-калькулятор на Bison
  19. Простая грамматика
  20. Задача «Расчёт сопротивления схемы»
  21. Простая реализация конечного автомата
  22. Использование аргументов командной строки
  23. Чтение и печать без использования stdio
  24. Декодирование звукозаписи в формате ADX
  25. Другие примеры

Всем известны простые формулы

А как находить коэффициенты в разложении ?

Рассмотрим следующую таблицу:

То, что нарисовано справа, называется треугольником Паскаля — в n-й строчке этого треугольника находятся коэффициенты для разложения .

Число номер в n-й строчке называется биномиальным коэффициентом .

Например,

Стороны треугольника Паскаля состоят из единичек. Каждое число внутри треугольника Паскаля равно сумме двух чисел, стоящих над ним справа и слева в предыдущей строчке:

Эти числа возникают в задаче о числе сочетаний:  — это число способов выбрать k элементов из n различных. Например, число байт, в которых ровно 3 единицы — это число  — число способов выбрать три бита, в которых будут стоять единицы, из восьми бит байта.


Докажите, что


Рассмотрим две программы, которые решают следующие задачи:

  1. Запрограммировать функцию .
  2. Вывести на экран 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?