Задачка мне очень понравилась, прилагаю решение на 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);
}
}
}
1) 255₁₀ = 11111111₂
2) 255₁₀ = 377₈
3) 255₁₀ = FF₁₆
4) 397₁₀ = 110001101₂
5) 397₁₀ = 615₈
6) 397₁₀ = 18D₁₆
Объяснение:
1) 255₁₀ = 11111111₂
255 / 2 = 127 + остаток 1
127 / 2 = 63 + остаток 1
63 / 2 = 31 + остаток 1
31 / 2 = 15 + остаток 1
15 / 2 = 7 + остаток 1
7 / 2 = 3 + остаток 1
3 / 2 = 1 + остаток 1
1 / 2 = 0 + остаток 1
записываем остатки снизу вверх
11111111₂ = 1 * 2⁰ + 1 * 2¹ + 1 * 2² + 1 * 2³ + 1 * 2⁴ + 1 * 2⁵ + 1 * 2⁶ + 1 * 2⁷ = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255₁₀
2) 255₁₀ = 377₈
255 / 8 = 31 + остаток 7
31 / 8 = 3 + остаток 7
3 / 8 = 0 + остаток 3
записываем остатки снизу вверх
377₈ = 7 * 8⁰ + 7 * 8¹ + 3 * 8² = 7 + 56 + 192 = 255₁₀
3) 255₁₀ = FF₁₆
255 / 16 = 15 + остаток 15
15 / 16 = 0 + остаток 15
записываем остатки снизу вверх
FF₁₆ = F * 16⁰ + F * 16¹ = 15 + 240 = 255₁₀
4) 397₁₀ = 110001101₂
397 / 2 = 198 + остаток 1
198 / 2 = 99 + остаток 0
99 / 2 = 49 + остаток 1
49 / 2 = 24 + остаток 1
24 / 2 = 12 + остаток 0
12 / 2 = 6 + остаток 0
6 / 2 = 3 + остаток 0
3 / 2 = 1 + остаток 1
1 / 2 = 0 + остаток 1
записываем остатки снизу вверх
110001101₂ = 1 * 2⁰ + 0 * 2¹ + 1 * 2² + 1 * 2³ + 0 * 2⁴ + 0 * 2⁵ + 0 * 2⁶ + 1 * 2⁷ + 1 * 2⁸ = 1 + 4 + 8 + 128 + 256 = 397₁₀
5) 397₁₀ = 615₈
397 / 8 = 49 + остаток 5
49 / 8 = 6 + остаток 1
6 / 8 = 0 + остаток 6
записываем остатки снизу вверх
615₈ = 5 * 8⁰ + 1 * 8¹ + 6 * 8² = 5 + 8 + 384 = 397₁₀
6) 397₁₀ = 18D₁₆
397 / 16 = 24 + остаток 13
24 / 16 = 1 + остаток 8
1 / 16 = 0 + остаток 1
записываем остатки снизу вверх
18D₁₆ = D * 16⁰ + 8 * 16¹ + 1 * 16² = 13 + 128 + 256 = 397₁₀
По комментариям в коде думаю должно быть все понято . Код в прикрепе