Пицца

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 9 мес., 2 нед. назад.

  • Автор
    Сообщения
  • #3391

    Условие задачи взято с сайта 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());
          }
        }
      }
    }

Для ответа в этой теме необходимо авторизоваться.