Using System class MainClass
![]()
|
Задание 1 КОД: using System; class MainClass { public static void Main (string[] args) { int[,] a = new int[,] { { 36, 36, 47, 37, 44, 41, 58 }, { 28, 47, 43, 42, 49, 49, 60 }, { 23, 23, 36, 35, 39, 42, 56 }, { 17, 23, 23, 11, 23, 23, 23 }, { 23, 35, 34, 27, 48, 48, 62 }, { 23, 29, 25, 24, 25, 42, 56 }, { 23, 42, 47, 37, 41, 35, 80 } }; int n = a.GetLength(0); int m = a.GetLength(1); int[] u = new int[n]; int[] v = new int[m]; int[] p = new int[m]; int[] way = new int[m]; for (int i = 1; i < n; ++i) { p[0] = i; int j0 = 0; int[] minv = new int[m]; bool[] used = new bool[m]; for (int j = 1; j < m; ++j) { minv[j] = int.MaxValue; } do { used[j0] = true; int i0 = p[j0]; int delta = int.MaxValue; int j1 = 0; for (int j = 1; j < m; ++j) { if (!used[j]) { int cur = a[i0, j] - u[i0] - v[j]; if (cur < minv[j]) { minv[j] = cur; way[j] = j0; } if (minv[j] < delta) { delta = minv[j]; j1 = j; } } } for (int j = 0; j < m; ++j) { if (used[j]) { u[p[j]] += delta; v[j] -= delta; } else { minv[j] -= delta; } } j0 = j1; } while (p[j0] != 0); do { int j1 = way[j0]; p[j0] = p[j1]; j0 = j1; } while (j0 != 0); } int[] ans = new int[n]; for (int j = 1; j < m; ++j) { if (p[j] != 0) { ans[p[j] - 1] = j; } } int sum = 0; for (int i = 0; i < n; ++i) { int j = ans[i]; if (j >= 0) { sum += a[i, j]; } } Console.WriteLine("Optimal assignments:"); for (int i = 0; i < n; i++) { Console.WriteLine("Job " + (i + 1) + " assigned to worker " + (ans[i] + 1)); } Console.WriteLine("Total cost: " + sum); } } Вывод: ![]() Задание 2 КОД: using System; using System.Collections.Generic; using System.Linq; namespace FactoringAlgorithms { class Program { static void Main(string[] args) { int number = 123456789; // число, которое нужно разложить на множители Console.WriteLine($"Разложение числа {number} на множители:"); // Метод Ферма var fermatStart = DateTime.Now; // засекаем время начала работы метода Ферма var fermatFactors = FermatMethod(number); var fermatEnd = DateTime.Now; // засекаем время окончания работы метода Ферма Console.WriteLine($"Метод Ферма: {string.Join(" * ", fermatFactors)}, время выполнения: {(fermatEnd - fermatStart).TotalMilliseconds} мс"); // Метод Диксона var dixonStart = DateTime.Now; // засекаем время начала работы метода Диксона var dixonFactors = DixonMethod(number); var dixonEnd = DateTime.Now; // засекаем время окончания работы метода Диксона Console.WriteLine($"Метод Диксона: {string.Join(" * ", dixonFactors)}, время выполнения: {(dixonEnd - dixonStart).TotalMilliseconds} мс"); // Метод Ленстры var lenstraStart = DateTime.Now; // засекаем время начала работы метода Ленстры var lenstraFactors = LenstraMethod(number); var lenstraEnd = DateTime.Now; // засекаем время окончания работы метода Ленстры Console.WriteLine($"Метод Ленстры: {string.Join(" * ", lenstraFactors)}, время выполнения: {(lenstraEnd - lenstraStart).TotalMilliseconds} мс"); // Метод решета квадратичного var quadraticSieveStart = DateTime.Now; // засекаем время начала работы метода решета квадратичного var quadraticSieveFactors = QuadraticSieveMethod(number); var quadraticSieveEnd = DateTime.Now; // засекаем время окончания работы метода решета квадратичного Console.WriteLine($"Метод решета квадратичного: {string.Join(" * ", quadraticSieveFactors)}, время выполнения: {(quadraticSieveEnd - quadraticSieveStart).TotalMilliseconds} мс"); Console.ReadKey(); } // Метод Ферма static int[] FermatMethod(int n) { if (n <= 0) throw new ArgumentException("Число должно быть положительным"); if (n == 1) return new int[] { 1 }; if (n % 2 == 0) return new int[] { 2 }.Concat(FermatMethod(n / 2)).ToArray(); int a = (int)Math.Ceiling(Math.Sqrt(n)); int b = 0; int b2 = a * a - n; while (!IsSquare(b2)) { a++; b2 = a * a - n; } b = (int)Math.Sqrt(b2); return new int[] { a - b, a + b }; } // Метод Диксона static int[] DixonMethod(int n) { if (n <= 0) throw new ArgumentException("Число должно быть положительным"); if (n == 1) return new int[] { 1 }; int x = 2; int y = 2; int d = 1; int i = 1; while (d == 1) { x = (x * x + 1) % n; y = ((y * y + 1) % n * (y * y + 1) % n + 1) % n; d = Gcd(Math.Abs(x - y), n); i++; } return d == n ? new int[] { } : new int[] { d, n / d }; } // Метод Ленстры static int[] LenstraMethod(int n) { if (n <= 0) throw new ArgumentException("Число должно быть положительным"); if (n == 1) return new int[] { 1 }; int a = 2; int b = 2; int d = 1; var primes = GetPrimes(1000); int i = 0; while (d == 1) { a = (a * a + b) % n; b = (b * b + 1) % n; d = Gcd(Math.Abs(a - b), n); if (i == primes.Count - 1) { i = -1; primes = GetPrimes(primes.Last() * 2); } i++; } return d == n ? new int[] { } : new int[] { d, n / d }; } // Метод решета квадратичного static int[] QuadraticSieveMethod(int n) { if (n <= 0) throw new ArgumentException("Число должно быть положительным"); if (n == 1) return new int[] { 1 }; int maxFactorBase = (int)Math.Exp(Math.Sqrt(Math.Log(n) * Math.Log(Math.Log(n)))); var factorBase = GetPrimes(maxFactorBase).ToArray(); var sieve = new List foreach (int p in factorBase) { int exp = 0; while (n % p == 0) { n /= p; exp++; } if (exp > 0) sieve.Add(new int[] { p, exp }); } var primes = factorBase.Take(sieve.Count).ToArray(); var exponents = new int[sieve.Count]; var matrix = new List for (int i = 0; i < sieve.Count; i++) { exponents[i] = sieve[i][1]; var row = new List int k = 0; for (int j = 0; j < primes.Length && k < sieve[i][1]; j++) { int l = 0; while (sieve[i][0] % primes[j] == 0) { l++; sieve[i][0] /= primes[j]; } row.Add(l % 2); k += l; } matrix.Add(row.ToArray()); } var indices = GaussianElimination(matrix.ToArray()); int a = 1; for (int i = 0; i < indices.Length; i++) { if (indices[i]) a = (a * primes[i]) % n; } int b2 = a * a - n; while (!IsSquare(b2)) { a++; b2 = a * a - n; } int b = (int)Math.Sqrt(b2); return new int[] { a - b, a + b }; } // Проверка, является ли число квадратом целого числа static bool IsSquare(int n) { int sqrt = (int)Math.Sqrt(n); return sqrt * sqrt == n; } // Нахождение НОД двух чисел static int Gcd(int a, int b) { if (b == 0) return a; return Gcd(b, a % b); } // Получение списка простых чисел до заданного числа static List { var primes = new List for (int i = 2; i <= n; i++) { bool isPrime = true; for (int j = 2; j <= Math.Sqrt(i); j++) { if (i % j == 0) { isPrime = false; break; } } if (isPrime) primes.Add(i); } return primes; } // Решение системы линейных уравнений методом Гаусса static bool[] GaussianElimination(int[][] matrix) { int rows = matrix.Length; int cols = matrix[0].Length; bool[] result = new bool[cols]; for (int i = 0; i < cols; i++) { for (int j = i; j < rows; j++) { if (matrix[j][i] != 0) { int[] temp = matrix[j]; matrix[j] = matrix[i]; matrix[i] = temp; break; } } if (matrix[i][i] == 0) continue; for (int j = i + 1; j < rows; j++) { if (matrix[j][i] == 0) continue; for (int k = i; k < cols; k++) { matrix[j][k] = (matrix[j][k] * matrix[i][i] - matrix[i][k] * matrix[j][i]) / Gcd(matrix[i][i], matrix[j][i]); } } } for (int i = cols - 1; i >= 0; i--) { if (matrix[i][i] == 0) continue; int gcd = matrix[i][i]; for (int j = i - 1; j >= 0; j--) { if (matrix[j][i] == 0) continue; gcd = Gcd(gcd, matrix[j][i]); } result[i] = (gcd == matrix[i][i]); } return result; } } } Вывод: ![]() |