Доказать, что можно найти самый легкий и самый тяжелый из камней (одновременно), количество которых равно (2*n+1), с - C#

Узнай цену своей работы

Формулировка задачи:

Где ошибка??не могу понять почему не работает,при вводе весов камней не происходит последующее взвешивание
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace Rocks
{
    class Rocks
    {
        static public int GlobalMin { get; set; }   // Минимальный вес
        static public int GlobalMax { get; set; }   // Максимальный вес
        static public int Stages { get; set; }      // кол-во взвешиваний
        static public int N { get; set; }           // Задаваемое N
        static public int LastTmpMin { get; set; }  // Если список минимальных весов - нечетный, храним отдельно последний элемент
        static public int LastTmpMax { get; set; }  // По аналогии с предыдущим пунктом
        
        // Число камней
        static public int AmountOfRocks
        {
            get
            {
                return (2*N + 1);
            }
        }
 
        // Число взвешиваний
        static public int AmountOfWeighings
        {
            get
            {
                return (3*N);
            }
        }
 
        // Функция разбиения массива на пары
        static public List<List<int>> GetPairs(int[] weights)
        {
            var pairs = new List<List<int>>();              // Список пар
            var pair = new List<int>();                     // Пара
            // Если во входном массиве больше 2х элеентов и его длина - нечетная, обрезаем последний элемент
            var rightBorder = (weights.Length > 2 && weights.Length % 2 != 0) ? 1 : 0;
 
            // Если массив единичной длины, возвращаем список из 1 элемента
            if (weights.Length == 1)
            {
                pairs.Add(new List<int> {weights[weights.Length - 1]});
                return pairs;
            }
 
            // Формируем пары элементов
            for (var i = 0; i < weights.Length - rightBorder; i++)
            {
                pair.Add(weights[i]);
 
                if (i % 2 != 0)
                {
                    pairs.Add(pair);
                    pair = new List<int>();
                }
            }
 
            return pairs;
        }
 
        // Рекурсивная функция нахождения минимакса (при первом проходе 2й массив = null, т.к. еще не было разбиения на минимумы и максимумы)
        static void GetMinMax(List<List<int>> min, List<List<int>> max)
        {
            // Списки минимумов и максимумов во входных парах
            var arrayOfMax = new List<int>();
            var arrayOfMin = new List<int>();
 
            // В случае не первого прохода 
            if (max != null)
            {
                // Если входные данные содержат по 1 элементу (последнее сравнение)
                if (min[0].Count == 1 && max[0].Count == 1)
                {
                    // Случай с нечетным числом минимаксов
                    if (LastTmpMin != 0 && LastTmpMax != 0)
                    {
                        // Формируем пары оставшихся элементов с последними (ранее обрезанными)
                        var lastMin = new[] { min[0].ElementAt(0), LastTmpMin };
                        var lastMax = new[] { max[0].ElementAt(0), LastTmpMax };
 
                        var minPair = GetPairs(lastMin);
                        var maxPair = GetPairs(lastMax);
 
                        LastTmpMax = 0;
                        LastTmpMin = 0;
 
                        // Последнее сравнение для пределения минимального и максимального весов
                        GetMinMax(minPair, maxPair);
                    }
                    else
                    {
                        // Заносим наши минимумы и максимумы в глобальные переменные
                        GlobalMax = max[0].ElementAt(0);
                        GlobalMin = min[0].ElementAt(0);
                    }
 
                    return;
                }
            }
 
            // Стадии взвешиваний с формированием списка минимумов и максимумов
            for (var i = 0; i < min.Count; i++)
            {
                Stages++;
                arrayOfMin.Add(min[i].Min());
 
                // Не первый проход
                if (max != null)
                {
                    Console.WriteLine("Взвешивание {0}. Сравниваем {1} и {2}. Минимум = {3}.", Stages, min[i].ElementAt(0), min[i].ElementAt(1), min[i].Min());
                    arrayOfMax.Add(max[i].Max());
                    Stages++;
                    Console.WriteLine("Взвешивание {0}. Сравниваем {1} и {2}. Максимум = {3}.", Stages, max[i].ElementAt(0), max[i].ElementAt(1), max[i].Max());
                }
                else
                {
                    // При первом проходе массив единственный
                    arrayOfMax.Add(min[i].Max());
                    Console.WriteLine("Взвешивание {0}. Сравниваем {1} и {2}. Минимум = {3}, максимум = {4}.", Stages, min[i].ElementAt(0), min[i].ElementAt(1), min[i].Min(), min[i].Max());
                }
            }
 
            // Если при первом проходе определилось нечетное число минимаксов, запоминаем последние элементы в глобальные переменные
            if (max == null)
            {
                if (arrayOfMin.Count % 2 != 0 && arrayOfMin.Count > 2)
                {
                    LastTmpMin = arrayOfMin[arrayOfMin.Count - 1];
                    LastTmpMax = arrayOfMax[arrayOfMax.Count - 1];
                }
            }
 
            // Формируем пары минимаксов
            var minPairs = GetPairs(arrayOfMin.ToArray());
            var maxPairs = GetPairs(arrayOfMax.ToArray());
 
            // Рекурсивно вычисляем минимаксы от уже имеющихся
            GetMinMax(minPairs, maxPairs);
        }
 
        static void Main()
        {
            var n = 0;
 
            Console.Write("N = ");
            int.TryParse(Console.ReadLine(), out n);
            N = n;
            
            var weights = new int[AmountOfRocks];
 
            Console.WriteLine("Число камней = {0}", AmountOfRocks);
            Console.WriteLine("Число взвешиваний = {0}", AmountOfWeighings);
            Console.WriteLine();
 
            if (AmountOfWeighings > 0)
            {
                string[] splittedData;
 
                // Ввод данных осуществляется через пробел
                while (true)
                {
                    Console.Write("Введите веса камней: ");
                    var inputData = Console.ReadLine();
 
                    if (inputData != null)
                    {
                        splittedData = inputData.Split(' ');
 
                        if (splittedData.Length == AmountOfRocks)
                            break;
                    }
                }
 
                // Формируем массив весов
                for (var i = 0; i < AmountOfRocks; i++)
                {
                    int.TryParse(splittedData[i], out n);
                    weights[i] = n > 0 ? n : 1;
                }
 
                // Запоминаем последний элемент списка
                var lastElement = weights[weights.Length - 1];
                
                Console.WriteLine();
                // Первый проход: массив общий, посему второй параметр = null.
                // Предварительно разбиваем массив весов на пары.
                // В результате рекурсивного выполнения данной функции, мы получим глобальный минимакс без последних
                // двух итераций (когда происходит сравнение с последним элементом).
                GetMinMax(GetPairs(weights), null);
 
                // Подготовка последних двух взвешиваний: найденный ранее минимакс сравнивается с поледним элементом
                var lastMin = new[] { GlobalMin, lastElement };
                var lastMax = new[] { GlobalMax, lastElement };
 
                var minPair = GetPairs(lastMin);
                var maxPair = GetPairs(lastMax);
 
                GetMinMax(minPair, maxPair);
 
                Console.WriteLine();
                Console.WriteLine("Минимальный вес камня = {0}", GlobalMin);
                Console.WriteLine("Максимальный вес камня = {0}", GlobalMax);
                Console.WriteLine("Число взвешиваний = {0}", Stages);
            }
            else
                Console.WriteLine("Число взвешиваний должно быть величиной положительной!");
        }
    }
}

Решение задачи: «Доказать, что можно найти самый легкий и самый тяжелый из камней (одновременно), количество которых равно (2*n+1), с»

textual
Листинг программы
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace GetMinMax
{
    class Program
    {
        static int count=0;
        static void Main(string[] args)
        {
            int[] mas = new int[] { 1, 5, 8, 2, 4, 6, 9 };
            int min, max;
            GetMinMax(mas, 0, mas.Length - 1, out min, out max);
            Console.WriteLine("Минимальный элемент - {0}", min);
            Console.WriteLine("Максимальный элемент - {0}", max);
            Console.WriteLine("Количество взвешиваний - {0}", count);
            Console.Read();
        }
        static void GetMinMax(int[] mas, int startindex, int endindex, out int min, out int max)
        {
            //для трех камней чтоб не взвешивать камень сам с собой
            if ((endindex - startindex) == 2)
            {
                if (mas[startindex] > mas[endindex])
                {
                    if (mas[startindex] > mas[startindex+1])
                    {
                        min = mas[startindex + 1]; max = mas[startindex];
                    }
                    else
                    {
                        max = mas[startindex + 1]; min = mas[startindex];
                    }
                }
                else
                {
                    if (mas[endindex] > mas[startindex + 1])
                    {
                        min = mas[startindex + 1]; max = mas[endindex];
                    }
                    else
                    {
                        max = mas[startindex + 1]; min = mas[endindex];
                    }
                }
                count+=2;
                return;
            }
            //для двух камней
            if ((endindex - startindex ) == 1)
            {
                if (mas[startindex] > mas[endindex])
                {
                    min = mas[endindex]; max = mas[startindex];
                }
                else
                {
                    max = mas[endindex]; min = mas[startindex];
                }
                count++;
                return;
            }
            //если камней больше
            int s = startindex + (endindex - startindex) / 2;
            int min1, min2, max1, max2;
            GetMinMax(mas, startindex, s, out min1, out max1);
            GetMinMax(mas, s + 1, endindex, out min2, out max2);
            min = min1 < min2 ? min1 : min2;            
            max = max1 > max2 ? max1 : max2;
            count += 2;
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.889 из 5
Похожие ответы