Задача «Бином Ньютона». Пример решения

 Бином Ньютона

Постановка задачи. Записать  разложение бинома Ньютона (1+x)ⁿ по степеням x. Коэффициент  при   x^k обозначается  C_n,k , читается «биномиальный коэффициент из n по k» (или «число сочетаний из n по k»:
(1+x)ⁿ = C_n,0x⁰ + C_n,1x¹ + C_n,2x² +… + C_n,nxⁿ
для натуральных степеней n.

Вариант решения. Выясняем, как вычисляются  C_n,k , и составляем программу. Формула для вычисления C_n,k:
C_n,k = n!/(k!)(n-k)!) =  (n-k+1)·…·(n-1)·n/k!
где  n! – факториал от  n, см., например, предыдущую задачу.

Обсуждение. Из школьного курса алгебры вы знаете, что:
(x+1)²=1+2x+x²
(x+1)³=1+3x+3x²+x³
т.е. мы имеем уже два теста для n=2,3.

Реализация. Придерживаясь принципа проектирования «сверху-вниз», объявим в классе Program два метода:
static string бином(int n)
static int bk(int n, int k)
Второй метод будет вычислять C_n,k , а первый – возвращать строку, биномиальное разложение. В функции Main() останется ввод n и вызов результата.

using System;
namespace БиномНьютона
{
   class Program
   {
      static void Main(string[] args)
      {
         Console.Write("Степень бинома - ");
         int n = Convert.ToInt32(Console.ReadLine());
         Console.WriteLine(бином(n));
         Console.ReadKey();
      }
 // разложение бинома по степеням х
      static string бином(int n)
      {
         string s="1 + ";
         for (int k = 1; k <= n; k++)
         s = s+ bk(n, k).ToString() + "x^" + k.ToString() + " + ";
         string s1=s.Remove(s.Length - 3);
         s= "(1+x)^"+n.ToString()+ " = "+ s1;
         return s;
      }
 // биномиальный коэффициент
      static int bk(int n, int k)
      {
         long t = 1;
         for (int i = n - k + 1; i <= n; i++)
            t = t * i;
         for (int i = 2; i <= k; i++)
            t = t / i;
         return (int)t;
      }
   }
}

Пример работы программы:

Тестирование дает правильный результат для n = 0,1,2,…,19,20. Для n>20 в методе bk( ) происходит переполнение в первом цикле (хотя заметьте, что локальная переменная t объявлена типом Int64), коэффициенты разложения становятся отрицательными, чего не может быть исходя из смысла задачи.

Придумайте, как расширить область допустимых значений n.

Следующая задача имеет отношение к задачам защиты информации и состоит в нахождении наибольшего общего делителя.