Using System class MainClass

• Название: Using System class MainClass
• Дата: 25.05.2023
• Размер: 200.58 Kb.
• Имя файла: matc#.docx
• Тип: Документы; #1158340

Задание 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;

}

}

}

Вывод: