ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.11.2023
Просмотров: 43
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Задание 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 GetPrimes(int n)
{
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;
}
}
}
Вывод:
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;
}
}
}
Вывод: