Задача о разрезании пиццы С#

Добрый день! Сегодня разберём задачу о разрезании пиццы.

Задача: Сколько кусков пиццы можно получить, делая n прямолинейных разрезов ножом ?

Какое максимальное число L_n областей, на которые плоскость делится n прямыми ?

Решение: Рассмотрим самые простые случаи задачи.

Переменная L показывает количество областей, а маленький индекс количество линий. Разберём когда количество линий равно 3.

Первое, что нужно заметить: Прирост новых областей равно количеству областей, через которые проходит новая линия. (1)

Действительно, мы третью линию провели через три области, и прирост новых областей составил тоже 3 области. Было 4, стало 7. Это происходит потому, что линия делит область на две части.

Чтобы вывести формулу для нашей задачи, необходимо узнать для новый линии под номер n: сколько максимально областей эта линия может пересечь.

Для того, чтобы количество кусков было максимальным - линии будем проводить не параллельно друг другу, так же, точки пересечения линий не должны совпадать.

Максимальное количество областей, которое может пересечь новая линия под номером n равно количеству пересечений этой линией старых линий, плюс один. (2)

К примеру, рассмотрим картинку:

Здесь, новая красная линия пересекает 8 старых линий. Тогда эта линия пересекает 8 + 1 = 9 областей.

Т.к. новая линия под номером n максимально может пересечь n-1 старых линий, то это означает, что новая линия может пересечь n-1 + 1 = n областей (Учитывая (2)). Следовательно, учитывая (1), прирост новых областей равно тоже n. На основании этого можно написать формулу:

L_n - Количество областей, когда на плоскости n линий; L_n-1 - количество областей, когда на плоскости n-1 линий; n-прирост новых областей, когда проводим линию под номер n.

Например, если мы проводим 3-ю линию, то прирост будет 3 новых области, 4 + 3 = 7 областей всего.

Исходя из выведенной формулы, можно написать программу на языке программирования C#. Формула получилось рекурсивной, поэтому будем использовать рекурсию.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace ConsoleApp23
{
    class Program
    {
        static void Main(string[] args)
        {
            int n;  // Количество линий.
    
            Console.WriteLine("Введите количесвто линий n: ");
            n = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine("Программа с помощью рекурсии");
            Console.WriteLine("Количество областей: " + CountArea(n));

            Console.ReadKey();
        }

        static int CountArea(int n)
        {
            if (n == 0) return 1;
            return (CountArea(n-1) + n);
        }
    }
}

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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace ConsoleApp25
{
    class Program
    {
        static void Main(string[] args)
        {
            int n,   // Количество линий.
                L,   // Результат.
                i; 

            Console.WriteLine("Введите количество линий n: ");
            n = Convert.ToInt32(Console.ReadLine());
             
            L = 1;

            for (i = 0; i <= n; i++)
            {
                L = L + i;
            }

            Console.WriteLine("Программа с помощью цикла");
            Console.WriteLine("Количество областей: " + L);

            Console.ReadKey();
        }
    }
}

Ещё, программу можно сделать намного эффективнее, если применить математические преобразования:

Справа от L₀ сумма арифметической прогрессии с первым индексом "1", приращением "1" и количеством элементов n. Преобразовав данную сумму по формуле арифметической прогрессии и учтя L₀=1 , получаем:

Напишем программу для данной формулы:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp24
{
    class Program
    {
        static void Main(string[] args)
        {
            int n;  // Количество линий.

            Console.WriteLine("Введите количество линий n: ");
            n = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine("C помощью арифметической прогрессии.");
            Console.WriteLine("Количество областей: " + (n*(n+1)/2 + 1));

            Console.ReadKey();
        }
    }
}

Теперь скорость программы не зависит от величины n, правильный ответ получается всегда за одну строчку!