Даша: Спасибо:3
31-05-2023
Читать статью
Санечка: я ничего не учила) но буду надеятся что ..
30-05-2023
Мейнер Сяо: Удачи всем сегодня на экзамене ;)..
Добрый день! Сегодня разберём задачу о разрезании пиццы.
Задача: Сколько кусков пиццы можно получить, делая n прямолинейных разрезов ножом ?
Какое максимальное число Ln областей, на которые плоскость делится n прямыми ?
Решение: Рассмотрим самые простые случаи задачи.
Переменная L показывает количество областей, а маленький индекс количество линий. Разберём когда количество линий равно 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, правильный ответ получается всегда за одну строчку!