Разбор олимпиадной задачи — Пицца
Программирование › Технология и методы программирования › Алгоритмы и структуры данных › Разбор олимпиадных задач › Динамическое программирование › Разбор олимпиадной задачи — Пицца
В этой теме 0 ответов, 1 участник, последнее обновление Васильев Владимир Сергеевич 2 года/лет, 1 месяц назад.
- АвторСообщения
- 02.01.2017 в 09:05 #3391@admin
Условие задачи взято с сайта acmp.ru:
Пицца – любимое лакомство Васи, он постоянно покупает и с удовольствием употребляет различные сорта этого великолепного блюда. Однажды, в очередной раз, разрезая круглую пиццу на несколько частей, Вася задумался: на какое максимальное количество частей можно разрезать пиццу за
N
прямых разрезов?Помогите Васе решить эту задачу, определив максимальное число не обязательно равных кусков, которые может получить Вася, разрезая пиццу таким образом.
Входные данные
Входной файлINPUT.TXT
содержит натуральное число N – число прямых разрезов пиццы (N <= 1000
).Выходные данные
В выходной файлOUTPUT.TXT
выведите ответ на задачу.Примеры:
table class=main cellpadding=2 cellspacing=1>
№ INPUT.TXT OUTPUT.TXT 1 2 4 2 3 7 Разбор решения задачи
Опытным путем определено, что при одном разрезе пиццы максимальное число кусков равно двум, при двух разрезах –
4
, при трех разрезах –7
, при четырех разрезах –11
(смотри рисунок). Для получения максимального числа кусков пиццы, делая новый разрез, необходимо что бы он проходил через каждый предыдущий.Под динамическим программированием понимают сведение задачи к подзадачам. Первым делом для решения задачи заполняются известные значения. В данном примере взяты число кусков при одном и двух разрезах (
array [1] = 2; array [2] = 4;
). Так, например, при еслиN
равно1
или2
, то в выходной файл записывается уже ранее известное (присвоенное) значение элемента, иначе, например, еслиN = 5
, то (с помощью циклаfor
) находим первое неизвестное значениеarray [3]
, затем следующееarray [4]
, и т.д., пока не дойдем до нужного. Неизвестные значения находятся по формуле — сумма значения предыдущего элемента и порядкового номера текущего элемента. Формула получена опытным путем. Описанный алгоритм можно изобразить в виде блок-схемы:
Исходный код реализации алгоритма на языке C#:
using System; using System.IO; namespace Lab2 { class Program { static void Main(string[] args) { var file = File.ReadAllText("input.txt"); var n = Convert.ToInt32(file); var array = new int[n+1]; array[1] = 2; array[2] = 4; if (n == 1 || n == 2) { File.WriteAllText("output.txt", array[n].ToString()); } else { for (int i = 3; i < n+1; i++) { array[i] = array[i - 1] + i; } File.WriteAllText("output.txt", array[n].ToString()); } } } }
- АвторСообщения
Для ответа в этой теме необходимо авторизоваться.