Danielos168

Teoria Algorytmów ĆW8 Zadania

Jan 17th, 2021
963
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Runtime.InteropServices;
  5. using System.Text;
  6. using System.Threading.Tasks;
  7.  
  8. namespace Kolokwium2_TeoriaAlgorytmów
  9. {
  10.     class Program
  11.     {
  12.         public static void hoteleTrasa(int[] trasa, int rr)
  13.         {
  14.             if (rr > 0)
  15.             {
  16.                 hoteleTrasa(trasa, trasa[rr]);
  17.             }
  18.  
  19.             Console.Write(rr + " ");
  20.         } //pomocnicza funkcja do zadania 2.
  21.         public static bool dict(char[] s, int p, int k)
  22.         {
  23.             string tmp = "";
  24.             for (int i = p; i <= k; i++)
  25.             {
  26.                  tmp = tmp + s.ElementAt(i);
  27.             }
  28.             string[] dictionary = {"jesteśmy", "najlepsi", "wśród", "najlepszych"};
  29.             return dictionary.Contains(tmp);
  30.  
  31.         } //pomocnicza funkcja do zadania 4(TU UZUPEŁNIĆ POPRAWNYMI SŁÓWKAMI)
  32.         static int lps(string seq)
  33.         {
  34.             int n = seq.Length;
  35.             int i, j, cl;
  36.             int[,] L = new int[n, n];
  37.  
  38.             for (i = 0; i < n; i++)
  39.                 L[i, i] = 1;
  40.             for (cl = 2; cl <= n; cl++)
  41.             {
  42.                 for (i = 0; i < n - cl + 1; i++)
  43.                 {
  44.                     j = i + cl - 1;
  45.  
  46.                     if (seq[i] == seq[j] &&
  47.                         cl == 2)
  48.                         L[i, j] = 2;
  49.                     else if (seq[i] == seq[j])
  50.                         L[i, j] = L[i + 1, j - 1] + 2;
  51.                     else
  52.                         L[i, j] =
  53.                             max(L[i, j - 1], L[i + 1, j]);
  54.                 }
  55.             }
  56.  
  57.             return L[0, n - 1];
  58.         } //pomocnicza funkcja do zadania 8 cz.1
  59.         static int max(int x, int y)
  60.         {
  61.             return (x > y) ? x : y;
  62.         } //pomocnicza funkcja do zadania 8 cz.2
  63.         static void Main(string[] args)
  64.         {
  65.             /*
  66.             int[] a = {-5,7,3,-10,12,-8,5,9};
  67.             Zadanie1(a);
  68.             */
  69.             /*
  70.             int[] b = {280,461,490,542,759,786,883};
  71.             Zadanie2(b);
  72.             */
  73.             /*
  74.             int[] m = {117, 181, 298, 396, 432, 454, 610, 627, 680, 774};
  75.             int[] p = {14, 20, 9, 19, 18, 11, 8, 14, 16, 5};
  76.             Zadanie3(m,p,130);
  77.             */
  78.             /*
  79.             string s = "najlepsiwśródnajlepszych"; //Tutaj musiałem zmienic wejściowego stringa(wśród zamiast z). program nie działa z
  80.                                                 //jednoznakowymi stringami jak "z / w / u"
  81.             char[] ss = s.ToCharArray();
  82.             Zadanie4(ss);
  83.             */
  84.             /*
  85.             string x = "DIODA";
  86.             string y = "DIPOL";
  87.             Zadanie5(x,y);
  88.             */
  89.             /*
  90.             string x = "1001010";
  91.             string y = "0101101";
  92.             char[] xx = x.ToCharArray();
  93.             char[] yy = y.ToCharArray();
  94.             Zadanie6(xx,yy);
  95.             */
  96.             /*
  97.             string s = "OldSite:GeeksforGeeks.org";
  98.             string d = "NewSite:GeeksQuiz.com";
  99.             char[] ss = s.ToCharArray();
  100.             char[] dd = d.ToCharArray();
  101.             Zadanie7(ss,dd,s.Length,d.Length);
  102.             */
  103.             /*
  104.             string seq = "kamilślimak";
  105.             Zadanie8(seq);
  106.             */
  107.         }
  108.         //Programowanie Dynamiczne Ćw8.
  109.         static void Zadanie1(int[] a) //podciąg spójny o mozliwie najwiekszej sumie (Kroki: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)
  110.         {
  111.             int size = a.Length;
  112.             int max_so_far = int.MinValue,
  113.                 max_ending_here = 0;
  114.             int s = 0;
  115.             int start = 0;
  116.             int end = 0;
  117.  
  118.             for (int i = 0; i < size; i++)
  119.             {
  120.                 max_ending_here = max_ending_here + a[i];
  121.  
  122.                 if (max_so_far < max_ending_here)
  123.                 {
  124.                     max_so_far = max_ending_here;
  125.                     start = s;
  126.                     end = i;
  127.                 }
  128.  
  129.                 if (max_ending_here < 0)
  130.                 {
  131.                     max_ending_here = 0;
  132.                     s = i + 1;
  133.                 }
  134.             }
  135.  
  136.             Console.Write("Najwiekszym podciągiem spójnym o najwiekszej sumie jest podciąg: ");
  137.             for (int i = start; i <= end; i++)
  138.             {
  139.                 Console.Write(a[i] + ",");
  140.             }
  141.             Console.Write(" o sumie: "+max_so_far);
  142.         }
  143.  
  144.         static void Zadanie2(int[] b) //Algorytm efektywnego wyznaczania ciągu hoteli w podrózy z karą
  145.         {
  146.             int[] kara = new int[b.Length];
  147.             int[] trasa = new int[b.Length];
  148.             kara[0] = 0;
  149.             kara[1] = (int) Math.Pow(200 - b[1], 2);
  150.             trasa[0] = trasa[1] = 0;
  151.  
  152.             for (int i = 2; i < b.Length; i++)
  153.             {
  154.                 kara[i] = -1000;
  155.                 trasa[i] = -1;
  156.             }
  157.  
  158.             for (int j = 2; j < b.Length; j++)
  159.             {
  160.                 for (int d = 0; d < j; d++)
  161.                 {
  162.                     int tmp = (int)(Math.Pow(200 - (b[j] - b[d]),2)+kara[d]);
  163.                     if (tmp < kara[j])
  164.                     {
  165.                         kara[j] = tmp;
  166.                         trasa[j] = d;
  167.                     }
  168.                     else if(kara[j] == -1000)
  169.                     {
  170.                         kara[j] = tmp;
  171.                         trasa[j] = d;
  172.                     }
  173.                 }
  174.             }
  175.  
  176.             for (int i = 1; i < b.Length; i++)
  177.             {
  178.                 Console.WriteLine("Hotel w odległości: " + b[i] + ", kara wynosi: " + kara[i] +
  179.                                   ". Optymalna trasa przez podane hotele to: ");
  180.                 hoteleTrasa(trasa,i);
  181.                 Console.WriteLine();
  182.             }
  183.            
  184.         }
  185.  
  186.         static void Zadanie3(int[] m, int[] p, int k) //Algorytm maksymalnego oczekiwanego całkowitego zysku
  187.         {
  188.             int[] P = new int[m.Length];
  189.             int temp = 0;
  190.             int mnoznik = 0;
  191.             for (int a = 1; a < m.Length; a++)
  192.             {
  193.  
  194.                 for (int b = 0; b <= a - 1; b++)
  195.                 {
  196.                     if (m[a] - m[b] < k)
  197.                     {
  198.                          mnoznik = 0;
  199.                     }
  200.                     else if (m[a] - m[b] >= k)
  201.                     {
  202.                          mnoznik = 1;
  203.                     }
  204.  
  205.                     temp = P[b] + (mnoznik * p[a]);
  206.  
  207.                     if (temp > P[a])
  208.                     {
  209.                         P[a] = temp;
  210.                     }
  211.                 }
  212.  
  213.                 if (P[a] < p[a])
  214.                 {
  215.                     P[a] = p[a];
  216.                 }
  217.             }
  218.  
  219.             Console.WriteLine("Przewidywany optymalny zysk to :"+P.Max());
  220.  
  221.         }
  222.  
  223.         static void Zadanie4(char[] s) //Algorytm wypisujący pojedyncze słowa ze złączonego zdania. Trzeba uzupełnic słownik u góry
  224.         {
  225.             int[] R = new int[s.Length];
  226.             for (int i = 0; i < s.Length; i++)
  227.             {
  228.                 R[i] = 0;
  229.                 for (int j = 0; j <= i - 1; j++)
  230.                 {
  231.                     if (dict(s, j, i) == true)
  232.                     {
  233.                         R[j] = 1;
  234.                     }
  235.                 }
  236.             }
  237.  
  238.             for (int i = 0; i < s.Length; i++)
  239.             {
  240.                 if (R[i] == 1)
  241.                 {
  242.                     Console.Write(" ");
  243.                 }
  244.  
  245.                 Console.Write(s[i]);
  246.             }
  247.         }
  248.  
  249.         static void Zadanie5(string source1, string source2)
  250.         {
  251.             var source1Length = source1.Length;
  252.             var source2Length = source2.Length;
  253.  
  254.             var matrix = new int[source1Length + 1, source2Length + 1];
  255.  
  256.             // First calculation, if one entry is empty return full length
  257.             if (source1Length == 0)
  258.                 Console.WriteLine(source2Length);
  259.  
  260.             if (source2Length == 0)
  261.                 Console.WriteLine(source1Length);
  262.  
  263.             // Initialization of matrix with row size source1Length and columns size source2Length
  264.             for (var i = 0; i <= source1Length; matrix[i, 0] = i++) { }
  265.             for (var j = 0; j <= source2Length; matrix[0, j] = j++) { }
  266.  
  267.             // Calculate rows and collumns distances
  268.             for (var i = 1; i <= source1Length; i++)
  269.             {
  270.                 for (var j = 1; j <= source2Length; j++)
  271.                 {
  272.                     var cost = (source2[j - 1] == source1[i - 1]) ? 0 : 1;
  273.  
  274.                     matrix[i, j] = Math.Min(
  275.                         Math.Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1),
  276.                         matrix[i - 1, j - 1] + cost);
  277.                 }
  278.             }
  279.             for (int i = 0; i < matrix.GetLength(0); i++)
  280.             {
  281.                 for (int j = 0; j < matrix.GetLength(1); j++)
  282.                 {
  283.                     Console.Write(matrix[i, j] + "\t");
  284.                 }
  285.                 Console.WriteLine();
  286.             }
  287.             Console.WriteLine("Odległość edycyjna wynosi: "+matrix[source1Length,source2Length]);
  288.         }
  289.  
  290.         static void Zadanie6(char[] X, char[] Y) //Najdłuższy wspólny podciąg taki jak w zadaniu6
  291.         {
  292.             int m = X.Length;
  293.             int n = Y.Length;
  294.             int[,] C = new int[m+1,n+1];
  295.             for (int i = 1; i <= m; i++)
  296.             {
  297.                 for (int j = 1; j <= n; j++)
  298.                 {
  299.                     if (X[i-1] == Y[j-1])
  300.                     {
  301.                         C[i, j] = C[i - 1, j - 1] + 1;
  302.                     }
  303.                     else if (C[i-1,j] >= C[i,j-1])
  304.                     {
  305.                         C[i, j] = C[i - 1, j];
  306.                     }
  307.                     else
  308.                     {
  309.                         C[i, j] = C[i, j - 1];
  310.                     }
  311.                 }
  312.             }
  313.  
  314.             for (int i = 0; i < C.GetLength(0); i++)
  315.             {
  316.                 for (int j = 0; j < C.GetLength(1); j++)
  317.                 {
  318.                     Console.Write(C[i, j] + "\t");
  319.                 }
  320.                 Console.WriteLine();
  321.             }
  322.         }
  323.  
  324.         static void Zadanie7(char[] X, char[] Y, int m, int n) //Algorytm znajdujący długość najdłuższego wspólnego podciągu tak jak w zad7
  325.         {
  326.             int[,] LCStuff = new int[m+1,n+1];
  327.             int result = 0;
  328.             for (int i = 0; i <= m; i++)
  329.             {
  330.                 for (int j = 0; j <= n; j++)
  331.                 {
  332.                     if (i == 0 || j == 0)
  333.                     {
  334.                         LCStuff[i, j] = 0;
  335.                     }
  336.                     else if(X[i-1] == Y[j-1])
  337.                     {
  338.                         LCStuff[i, j] = LCStuff[i - 1, j - 1] + 1;
  339.                         result = Math.Max(result, LCStuff[i, j]);
  340.                     }
  341.                     else
  342.                     {
  343.                         LCStuff[i, j] = 0;
  344.                     }
  345.                 }
  346.             }
  347.  
  348.             Console.WriteLine("Najdłuższym wspólny podciąg ma długość: "+result);
  349.         }
  350.  
  351.         static void Zadanie8(string seq) //Algorytm obliczania długości najdłuższego podciągu palindromicznego
  352.         {
  353.             int n = seq.Length;
  354.             Console.Write("Długość najdłuższego podciągu palidromicznego wynosi:  "+ lps(seq));
  355.         }
  356.     }
  357. }
  358.  
RAW Paste Data