Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

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


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


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



Или более научным языком:

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


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



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


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



Разрезание плоскости 3 линиями


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


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


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


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


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


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



Количество областей, которое пересекает линия на плоскости


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


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



Количество областей, которое пересекает линия на плоскости


Ln - Количество областей, когда на плоскости n линий; Ln-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();
        }
    }
}

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



Преобразование формулы в задаче о разрезании пиццы


Справа от L0 сумма арифметической прогрессии с первым индексом "1", приращением "1" и количеством элементов n. Преобразовав данную сумму по формуле арифметической прогрессии и учтя L0=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, правильный ответ получается всегда за одну строчку!


Результат работы программы:

Результат решения задачи о разрезании пиццы

Если сделать 10000 разрезов:

Результат решения задачи о разрезании пиццы 2







15-06-2019 в 20:44:47





Похожая статья:

Бинарный поиск

Сегодня мы разберём алгоритм бинарного поиска...

Категория: Алгоритмы  Подкатегория: Задачи
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



ОГЭ задание 1
Алгоритм Евклида





Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy