lab4GP.cs - master - FavnGod/Lab4

lab4GP.cs
355 строк15 KB
FavnGod
upload files
18 дек 2025, 11:42
18 дек 2025, 11:42cb1182b
using System;
using System.Collections.Generic;
using System.Linq;

namespace ArrayTasks
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.OutputEncoding = System.Text.Encoding.UTF8;

            while (true)
            {
                Console.WriteLine("Введите длину массива (целое положительное число):");
                if (!int.TryParse(Console.ReadLine(), out int n) || n <= 0)
                {
                    Console.WriteLine("Ошибка ввода длины массива.\n");
                    continue;
                }

                int[] array = new int[n];
                Console.WriteLine("Введите элементы массива (целые числа) через пробел или по одному в строке:");
                string line = Console.ReadLine();
                string[] parts = line.Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);

                if (parts.Length == n)
                {
                    for (int i = 0; i < n; i++)
                        array[i] = int.Parse(parts[i]);
                }
                else
                {
                    Console.WriteLine("Введено не столько элементов, сколько задано длиной, введите по одному элементу:");
                    for (int i = 0; i < n; i++)
                    {
                        Console.Write($"array[{i}] = ");
                        array[i] = int.Parse(Console.ReadLine());
                    }
                }

                Console.WriteLine("\nВыберите задачу (1–11):");
                Console.WriteLine("1. Проверить, является ли массив возрастающей последовательностью");
                Console.WriteLine("2. Найти максимальную возрастающую подпоследовательность (подряд)");
                Console.WriteLine("3. Найти максимальную симметричную подпоследовательность (подряд)");
                Console.WriteLine("4. Найти максимальную возрастающую подпоследовательность (LIS, с вычеркиванием)");
                Console.WriteLine("5. Количество элементов, встречающихся один раз");
                Console.WriteLine("6. Элемент, встречающийся максимальное число раз");
                Console.WriteLine("7. Количество различных элементов массива");
                Console.WriteLine("8. Команда из 4 лучших (здесь массив – времена забега)");
                Console.WriteLine("9. Количество элементов первого массива, которые есть во втором");
                Console.WriteLine("10. Проверить, образуют ли элементы массива множество");
                Console.WriteLine("11. Проверить равенство двух множеств");
                Console.WriteLine("0. Выход");

                if (!int.TryParse(Console.ReadLine(), out int choice))
                {
                    Console.WriteLine("Некорректный выбор.\n");
                    continue;
                }

                if (choice == 0)
                    break;

                switch (choice)
                {
                    case 1:
                        Console.WriteLine($"Массив возрастающий: {Task1_IsAscending(array)}");
                        break;

                    case 2:
                        var res2 = Task2_MaxAscendingSubsequence(array);
                        Console.WriteLine($"Макс. возрастающая подпоследовательность (подряд): [{string.Join(", ", res2)}], длина = {res2.Length}");
                        break;

                    case 3:
                        var res3 = Task3_MaxSymmetricSubsequence(array);
                        Console.WriteLine($"Макс. симметричная подпоследовательность: [{string.Join(", ", res3)}], длина = {res3.Length}");
                        break;

                    case 4:
                        var res4 = Task4_LongestIncreasingSubsequence(array);
                        Console.WriteLine($"LIS: [{string.Join(", ", res4)}], длина = {res4.Length}");
                        break;

                    case 5:
                        Console.WriteLine($"Элементов, встречающихся один раз: {Task5_CountUniqueElements(array)}");
                        break;

                    case 6:
                        Console.WriteLine($"Элемент с максимальной частотой: {Task6_MostFrequentElement(array)}");
                        break;

                    case 7:
                        Console.WriteLine($"Количество различных элементов: {Task7_CountDistinctElements(array)}");
                        break;

                    case 8:
                        Console.WriteLine("Лучшие 4 результата (меньшее время – лучше):");
                        var best = Task8_SelectTopAthletes(array, 4);
                        Console.WriteLine($"[{string.Join(", ", best)}]");
                        break;

                    case 9:
                        Console.WriteLine("Введите длину второго массива:");
                        int m = int.Parse(Console.ReadLine());
                        int[] array2 = new int[m];
                        Console.WriteLine("Введите элементы второго массива через пробел или по одному в строке:");
                        string line2 = Console.ReadLine();
                        string[] parts2 = line2.Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
                        if (parts2.Length == m)
                        {
                            for (int i = 0; i < m; i++)
                                array2[i] = int.Parse(parts2[i]);
                        }
                        else
                        {
                            Console.WriteLine("Введено не столько элементов, сколько задано длиной, введите по одному элементу:");
                            for (int i = 0; i < m; i++)
                            {
                                Console.Write($"array2[{i}] = ");
                                array2[i] = int.Parse(Console.ReadLine());
                            }
                        }
                        Console.WriteLine($"Количество общих элементов: {Task9_CountCommonElements(array, array2)}");
                        break;

                    case 10:
                        Console.WriteLine($"Массив образует множество (все элементы уникальны): {Task10_IsSet(array)}");
                        break;

                    case 11:
                        Console.WriteLine("Введите длину второго массива:");
                        int k = int.Parse(Console.ReadLine());
                        int[] set2Arr = new int[k];
                        Console.WriteLine("Введите элементы второго массива через пробел или по одному в строке:");
                        string line3 = Console.ReadLine();
                        string[] parts3 = line3.Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
                        if (parts3.Length == k)
                        {
                            for (int i = 0; i < k; i++)
                                set2Arr[i] = int.Parse(parts3[i]);
                        }
                        else
                        {
                            Console.WriteLine("Введено не столько элементов, сколько задано длиной, введите по одному элементу:");
                            for (int i = 0; i < k; i++)
                            {
                                Console.Write($"set2[{i}] = ");
                                set2Arr[i] = int.Parse(Console.ReadLine());
                            }
                        }
                        Console.WriteLine($"Множества равны: {Task11_AreSetsEqual(array, set2Arr)}");
                        break;

                    default:
                        Console.WriteLine("Нет такой задачи.\n");
                        break;
                }

                Console.WriteLine("\nНажмите Enter, чтобы продолжить...");
                Console.ReadLine();
                Console.Clear();
            }
        }

        static bool Task1_IsAscending(int[] array)
        {
            if (array == null || array.Length <= 1)
                return true;

            for (int i = 1; i < array.Length; i++)
                if (array[i] <= array[i - 1])
                    return false;

            return true;
        }

        static int[] Task2_MaxAscendingSubsequence(int[] array)
        {
            if (array == null || array.Length == 0)
                return Array.Empty<int>();

            int maxLength = 1, maxStart = 0;
            int curLength = 1, curStart = 0;

            for (int i = 1; i < array.Length; i++)
            {
                if (array[i] > array[i - 1])
                    curLength++;
                else
                {
                    if (curLength > maxLength)
                    {
                        maxLength = curLength;
                        maxStart = curStart;
                    }
                    curLength = 1;
                    curStart = i;
                }
            }

            if (curLength > maxLength)
            {
                maxLength = curLength;
                maxStart = curStart;
            }

            int[] result = new int[maxLength];
            Array.Copy(array, maxStart, result, 0, maxLength);
            return result;
        }

        static int[] Task3_MaxSymmetricSubsequence(int[] array)
        {
            if (array == null || array.Length == 0)
                return Array.Empty<int>();

            int maxLength = 1, maxStart = 0;

            for (int i = 0; i < array.Length; i++)
                for (int j = i; j < array.Length; j++)
                    if (IsPalindrome(array, i, j))
                    {
                        int len = j - i + 1;
                        if (len > maxLength)
                        {
                            maxLength = len;
                            maxStart = i;
                        }
                    }

            int[] result = new int[maxLength];
            Array.Copy(array, maxStart, result, 0, maxLength);
            return result;
        }

        static bool IsPalindrome(int[] array, int l, int r)
        {
            while (l < r)
            {
                if (array[l] != array[r]) return false;
                l++; r--;
            }
            return true;
        }

        static int[] Task4_LongestIncreasingSubsequence(int[] array)
        {
            if (array == null || array.Length == 0)
                return Array.Empty<int>();

            int n = array.Length;
            int[] dp = new int[n];
            int[] parent = new int[n];

            for (int i = 0; i < n; i++)
            {
                dp[i] = 1;
                parent[i] = -1;
            }

            for (int i = 1; i < n; i++)
                for (int j = 0; j < i; j++)
                    if (array[j] < array[i] && dp[j] + 1 > dp[i])
                    {
                        dp[i] = dp[j] + 1;
                        parent[i] = j;
                    }

            int maxLen = dp.Max();
            int pos = Array.IndexOf(dp, maxLen);

            List<int> lis = new List<int>();
            while (pos != -1)
            {
                lis.Add(array[pos]);
                pos = parent[pos];
            }
            lis.Reverse();
            return lis.ToArray();
        }

        static int Task5_CountUniqueElements(int[] array)
        {
            if (array == null || array.Length == 0)
                return 0;

            Dictionary<int, int> freq = new Dictionary<int, int>();
            foreach (int x in array)
            {
                if (freq.ContainsKey(x)) freq[x]++;
                else freq[x] = 1;
            }

            return freq.Values.Count(v => v == 1);
        }

        static int Task6_MostFrequentElement(int[] array)
        {
            if (array == null || array.Length == 0)
                throw new ArgumentException("Массив пуст");

            Dictionary<int, int> freq = new Dictionary<int, int>();
            foreach (int x in array)
            {
                if (freq.ContainsKey(x)) freq[x]++;
                else freq[x] = 1;
            }

            return freq.OrderByDescending(p => p.Value).First().Key;
        }

        static int Task7_CountDistinctElements(int[] array)
        {
            if (array == null || array.Length == 0)
                return 0;

            return new HashSet<int>(array).Count;
        }

        static int[] Task8_SelectTopAthletes(int[] times, int teamSize)
        {
            if (times == null || times.Length == 0 || teamSize <= 0)
                return Array.Empty<int>();

            return times.OrderBy(t => t).Take(teamSize).ToArray();
        }

        static int Task9_CountCommonElements(int[] array1, int[] array2)
        {
            if (array1 == null || array2 == null)
                return 0;

            HashSet<int> set2 = new HashSet<int>(array2);
            return array1.Count(x => set2.Contains(x));
        }

        static bool Task10_IsSet(int[] array)
        {
            if (array == null) return false;
            return array.Length == new HashSet<int>(array).Count;
        }

        static bool Task11_AreSetsEqual(int[] array1, int[] array2)
        {
            if (array1 == null || array2 == null)
                return false;

            HashSet<int> s1 = new HashSet<int>(array1);
            HashSet<int> s2 = new HashSet<int>(array2);
            return s1.SetEquals(s2);
        }
    }
}