Задачка мне очень понравилась, прилагаю решение на C#, консольное приложение
Объяснение:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Археологи_строители
{ class Program
{
static void Main(string[] args)
//Объявляем и задаем переменные "M" и "N", а так же переменную для результата
int M,N=new int();
int MyResult = 0;
Console.WriteLine("Ведите Текущее количество ступенек и Сколько их должно быть:");
M = int.Parse(Console.ReadLine());
N = int.Parse(Console.ReadLine());
// Создаем массив для хранения данных о ступенях. M-Количество ступенек, Цифра - для колонок длины и высоты
int[,] mass = new int[M,2];
// Запись значений в массив
for (int x = 0; x < M; x++){
for (int y = 0; y < 2; y++){
if (y==0){ //Чисто для юзерфрендли отображения
Console.Write($"Введите значение Длины для ступеньки №{x + 1}= ");} else{
Console.Write($"Введите значение Высоты для ступеньки №{x + 1}= ");}
mass[x, y] = Convert.ToInt32(Console.ReadLine());}
Console.WriteLine();}
/* Как оказалось, самый простой определить какую же ступеньку надо "поднимать"-
* это вычислить площадь гипотетически "заполняемого" пространства над ступенькой и взять
* наименьшее значение.
*
* Итак, допустим если у нас 5 ступенек, то нам нам необходимо записать 4 значения
* (в рамках лестницы) площади заполняемых ступенек.
* Перемножаем Длину ступеньки N на высоту ступеньки N+1, M-1 раз и сохраняем в массив
*/
int M2 = M; //Дублируем изначальное число ступенек для контроля цикла
for (int z = 0; z <M2-N; z++)
int[] acreage = new int[M - 1];
for (int x = 0; x < M - 1; x++)
for (int y = 0; y < 2; y++)
acreage[x] = mass[x, 0] * mass[x + 1, 1];
}
/*
* И так у нас есть все значения гипотетически заполняемой ступеньки.
* Ищем минимальное значение площади
int minAcreage = acreage[0];
for (int i = 0; i < M - 1; i++)
if (minAcreage > acreage[i])
minAcreage = acreage[i];
MyResult = MyResult+minAcreage; //Плюсуем данное значение в переменную результата
// У нас есть минимальная площадь. Найдем номер данной ступеньки
int IndexAcreage = Array.IndexOf(acreage, minAcreage);
//"Достроим нужную нам ступеньку и запишем обновленные данные во временный массив"
int[,] tempMass = new int[M - 1, 2]; //Он на размер меньше, т.к. и "полных" ступенек у нас стало меньше
//Ступеньки до IndexAcreage мы просто переписываем во временный массив
if (x < IndexAcreage)
tempMass[x, y] = mass[x, y];
//2 ступеньки от IndexAcreage мы превращаем в одну (застраивая их блоками)
else if (x == IndexAcreage)
tempMass[x, y] = mass[x, y] + mass[x + 1, y];
/* и после IndexAcreage мы та же копируем, но со сдвигом вправо, т.к. полноценных
* ступенек стало меньше
else if (x > IndexAcreage)
tempMass[x, y] = mass[x + 1, y];
M = M - 1; //Поскольку ступенек теперь меньше, то и их фактическое число необходимо уменьшить
for (int x = 0; x < M + 1; x++)
mass[x, y] = 0;
//переписываем данные в основной массив и запускаем следющую интерацию цикла
for (int x = 0; x < M; x++)
mass[x, y] = tempMass[x, y];
Console.WriteLine($"Минимально необходимое число блоков: {MyResult}");
Console.ReadKey(true);
#include <cstdlib>#include <string>#include <iostream>#include "field.h"using namespace std;
int main(int argc, char** argv, char** env){ srand(time(0)); vector< vector< string > > S; S.resize(2); S[0].push_back("Vremena_goda"); S[1].push_back("Zima"); S[1].push_back("Vesna"); S[1].push_back("Leto"); S[1].push_back("Osen");
Field A(S, Field().clGreen, Field().clLightblue); cout << A << std::endl; return 0;}
#ifndef FIELD_H_INCLUDED#define FIELD_H_INCLUDED
#include <vector>#include <iterator>#include <algorithm>#include <string>#include <sstream>class Field{public: enum ConsoleColor { clBlack, clRed, clGreen, clYellow, clBlue, clPurple, clLightblue, clWhite };private: size_t field_width, field_height; std::vector< std::vector< std::string > > Data; std::vector< size_t > column_width; ConsoleColor color_border, color_font; std::string get_format_color_string(std::string S, ConsoleColor color) { std::stringstream result; result << "\x1b[1;" << color + 30 << "m" << S << "\x1b[0m"; return result.str(); } std::string str_mul(std::string s, size_t num) { std::string result = ""; for(size_t i = 0; i < num; i++) result += s; return result; }public: Field() {}; Field(std::vector< std::vector< std::string > > D, ConsoleColor color_border, ConsoleColor color_font) : Data(D), color_border(color_border), color_font(color_font) { field_height = Data.size(); field_width = 0; for(size_t i = 0; i < field_height; i++) field_width = std::max(field_width, Data[i].size()); for(size_t i = 0; i < field_height; i++) while(Data[i].size() < field_width) Data[i].push_back(""); column_width.assign(field_width, 0); for(size_t i = 0; i < field_height; i++) for(size_t j = 0; j < field_width; j++) column_width[j] = std::max(column_width[j], Data[i][j].length()); } void logs() { std::cout << "field_height: " << field_height << std::endl; std::cout << "field_widht: " << field_width << std::endl; } friend std::ostream& operator <<(std::ostream& output_stream, Field & field) { /* std::cout << field.field_width << " " << field.field_height << std::endl; for(size_t i = 0; i < field.Data.size(); i++) { for(size_t j = 0; j < field.Data[i].size(); j++) std::cout << field.Data[i][j] << " "; std::cout << std::endl; } */
output_stream << field.get_format_color_string(" ┌", field.color_border); for(size_t i = 0; i < field.field_width - 1; i++) { output_stream << field.get_format_color_string(field.str_mul("─", field.column_width[i] + 2), field.color_border); output_stream << field.get_format_color_string("┬", field.color_border); } output_stream << field.get_format_color_string(field.str_mul("─", field.column_width[field.field_width - 1] + 2), field.color_border); output_stream << field.get_format_color_string("┐\n ", field.color_border);
for(size_t i = 0; i < field.field_height; i++) { output_stream << field.get_format_color_string("│", field.color_border); for(size_t j = 0; j < field.field_width; j++) { std::stringstream ss; ss << field.str_mul(" ", field.column_width[j] - field.Data[i][j].size() + 1) << (field.Data[i][j] != "" ? field.Data[i][j] : ""); output_stream << field.get_format_color_string(ss.str(), field.color_font); output_stream << field.get_format_color_string(" │", field.color_border); } output_stream << "\n "; if(i != field.field_height - 1) { output_stream << field.get_format_color_string("├", field.color_border); for(size_t j = 0; j < field.field_width - 1; j++) { output_stream << field.get_format_color_string(field.str_mul("─", field.column_width[j] + 2), field.color_border); output_stream << field.get_format_color_string("┼", field.color_border); } output_stream << field.get_format_color_string(field.str_mul("─", field.column_width[field.field_width - 1] + 2), field.color_border); output_stream << field.get_format_color_string("┤", field.color_border); } else { output_stream << field.get_format_color_string("└", field.color_border); for(size_t j = 0; j < field.field_width - 1; j++) { output_stream << field.get_format_color_string(field.str_mul("─", field.column_width[j] + 2), field.color_border); output_stream << field.get_format_color_string("┴", field.color_border); } output_stream << field.get_format_color_string(field.str_mul("─", field.column_width[field.field_width - 1] + 2), field.color_border); output_stream << field.get_format_color_string("┘\n", field.color_border); } output_stream << "\n "; } return output_stream;
}};
#endif // FIELD_H_INCLUDED
Задачка мне очень понравилась, прилагаю решение на C#, консольное приложение
Объяснение:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Археологи_строители
{ class Program
{
static void Main(string[] args)
{
//Объявляем и задаем переменные "M" и "N", а так же переменную для результата
int M,N=new int();
int MyResult = 0;
Console.WriteLine("Ведите Текущее количество ступенек и Сколько их должно быть:");
M = int.Parse(Console.ReadLine());
N = int.Parse(Console.ReadLine());
// Создаем массив для хранения данных о ступенях. M-Количество ступенек, Цифра - для колонок длины и высоты
int[,] mass = new int[M,2];
// Запись значений в массив
for (int x = 0; x < M; x++){
for (int y = 0; y < 2; y++){
if (y==0){ //Чисто для юзерфрендли отображения
Console.Write($"Введите значение Длины для ступеньки №{x + 1}= ");} else{
Console.Write($"Введите значение Высоты для ступеньки №{x + 1}= ");}
mass[x, y] = Convert.ToInt32(Console.ReadLine());}
Console.WriteLine();}
/* Как оказалось, самый простой определить какую же ступеньку надо "поднимать"-
* это вычислить площадь гипотетически "заполняемого" пространства над ступенькой и взять
* наименьшее значение.
*
* Итак, допустим если у нас 5 ступенек, то нам нам необходимо записать 4 значения
* (в рамках лестницы) площади заполняемых ступенек.
*
* Перемножаем Длину ступеньки N на высоту ступеньки N+1, M-1 раз и сохраняем в массив
*/
int M2 = M; //Дублируем изначальное число ступенек для контроля цикла
for (int z = 0; z <M2-N; z++)
{
int[] acreage = new int[M - 1];
for (int x = 0; x < M - 1; x++)
{
for (int y = 0; y < 2; y++)
{
acreage[x] = mass[x, 0] * mass[x + 1, 1];
}
}
/*
* И так у нас есть все значения гипотетически заполняемой ступеньки.
* Ищем минимальное значение площади
*/
int minAcreage = acreage[0];
for (int i = 0; i < M - 1; i++)
{
if (minAcreage > acreage[i])
{
minAcreage = acreage[i];
}
}
MyResult = MyResult+minAcreage; //Плюсуем данное значение в переменную результата
// У нас есть минимальная площадь. Найдем номер данной ступеньки
int IndexAcreage = Array.IndexOf(acreage, minAcreage);
//"Достроим нужную нам ступеньку и запишем обновленные данные во временный массив"
int[,] tempMass = new int[M - 1, 2]; //Он на размер меньше, т.к. и "полных" ступенек у нас стало меньше
for (int x = 0; x < M - 1; x++)
{
for (int y = 0; y < 2; y++)
{
//Ступеньки до IndexAcreage мы просто переписываем во временный массив
if (x < IndexAcreage)
{
tempMass[x, y] = mass[x, y];
}
//2 ступеньки от IndexAcreage мы превращаем в одну (застраивая их блоками)
else if (x == IndexAcreage)
{
tempMass[x, y] = mass[x, y] + mass[x + 1, y];
}
/* и после IndexAcreage мы та же копируем, но со сдвигом вправо, т.к. полноценных
* ступенек стало меньше
*/
else if (x > IndexAcreage)
{
tempMass[x, y] = mass[x + 1, y];
}
}
}
M = M - 1; //Поскольку ступенек теперь меньше, то и их фактическое число необходимо уменьшить
for (int x = 0; x < M + 1; x++)
{
for (int y = 0; y < 2; y++)
{
mass[x, y] = 0;
}
}
//переписываем данные в основной массив и запускаем следющую интерацию цикла
for (int x = 0; x < M; x++)
{
for (int y = 0; y < 2; y++)
{
mass[x, y] = tempMass[x, y];
}
}
}
Console.WriteLine($"Минимально необходимое число блоков: {MyResult}");
Console.ReadKey(true);
}
}
}