Teoria Algorytmów ĆW8 Zadania

using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;
using System.Threading.Tasks;

namespace Kolokwium2_TeoriaAlgorytmów
{
    class Program
    {
        public static void hoteleTrasa(int[] trasa, int rr)
        {
            if (rr > 0)
            {
                hoteleTrasa(trasa, trasa[rr]);
            }

            Console.Write(rr + " ");
        } //pomocnicza funkcja do zadania 2.
        public static bool dict(char[] s, int p, int k)
        {
            string tmp = "";
            for (int i = p; i <= k; i++)
            {
                 tmp = tmp + s.ElementAt(i);
            }
            string[] dictionary = {"jesteśmy", "najlepsi", "wśród", "najlepszych"};
            return dictionary.Contains(tmp);

        } //pomocnicza funkcja do zadania 4(TU UZUPEŁNIĆ POPRAWNYMI SŁÓWKAMI)
        static int lps(string seq)
        {
            int n = seq.Length;
            int i, j, cl;
            int[,] L = new int[n, n];

            for (i = 0; i < n; i++)
                L[i, i] = 1;
            for (cl = 2; cl <= n; cl++)
            {
                for (i = 0; i < n - cl + 1; i++)
                {
                    j = i + cl - 1;

                    if (seq[i] == seq[j] &&
                        cl == 2)
                        L[i, j] = 2;
                    else if (seq[i] == seq[j])
                        L[i, j] = L[i + 1, j - 1] + 2;
                    else
                        L[i, j] =
                            max(L[i, j - 1], L[i + 1, j]);
                }
            }

            return L[0, n - 1];
        } //pomocnicza funkcja do zadania 8 cz.1
        static int max(int x, int y)
        {
            return (x > y) ? x : y;
        } //pomocnicza funkcja do zadania 8 cz.2
        static void Main(string[] args)
        {
            /*
            int[] a = {-5,7,3,-10,12,-8,5,9};
            Zadanie1(a);
            */
            /*
            int[] b = {280,461,490,542,759,786,883};
            Zadanie2(b);
            */
            /*
            int[] m = {117, 181, 298, 396, 432, 454, 610, 627, 680, 774};
            int[] p = {14, 20, 9, 19, 18, 11, 8, 14, 16, 5};
            Zadanie3(m,p,130);
            */
            /*
            string s = "najlepsiwśródnajlepszych"; //Tutaj musiałem zmienic wejściowego stringa(wśród zamiast z). program nie działa z
                                                //jednoznakowymi stringami jak "z / w / u"
            char[] ss = s.ToCharArray();
            Zadanie4(ss);
            */
            /*
            string x = "DIODA";
            string y = "DIPOL";
            Zadanie5(x,y);
            */
            /*
            string x = "1001010";
            string y = "0101101";
            char[] xx = x.ToCharArray();
            char[] yy = y.ToCharArray();
            Zadanie6(xx,yy);
            */
            /*
            string s = "OldSite:GeeksforGeeks.org";
            string d = "NewSite:GeeksQuiz.com";
            char[] ss = s.ToCharArray();
            char[] dd = d.ToCharArray();
            Zadanie7(ss,dd,s.Length,d.Length);
            */
            /*
            string seq = "kamilślimak";
            Zadanie8(seq);
            */
        }
        //Programowanie Dynamiczne Ćw8.
        static void Zadanie1(int[] a) //podciąg spójny o mozliwie najwiekszej sumie (Kroki: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)
        {
            int size = a.Length;
            int max_so_far = int.MinValue,
                max_ending_here = 0;
            int s = 0;
            int start = 0;
            int end = 0;

            for (int i = 0; i < size; i++)
            {
                max_ending_here = max_ending_here + a[i];

                if (max_so_far < max_ending_here)
                {
                    max_so_far = max_ending_here;
                    start = s;
                    end = i;
                }

                if (max_ending_here < 0)
                {
                    max_ending_here = 0;
                    s = i + 1;
                }
            }

            Console.Write("Najwiekszym podciągiem spójnym o najwiekszej sumie jest podciąg: ");
            for (int i = start; i <= end; i++)
            {
                Console.Write(a[i] + ",");
            }
            Console.Write(" o sumie: "+max_so_far);
        }

        static void Zadanie2(int[] b) //Algorytm efektywnego wyznaczania ciągu hoteli w podrózy z karą
        {
            int[] kara = new int[b.Length];
            int[] trasa = new int[b.Length];
            kara[0] = 0;
            kara[1] = (int) Math.Pow(200 - b[1], 2);
            trasa[0] = trasa[1] = 0;

            for (int i = 2; i < b.Length; i++)
            {
                kara[i] = -1000;
                trasa[i] = -1;
            }

            for (int j = 2; j < b.Length; j++)
            {
                for (int d = 0; d < j; d++)
                {
                    int tmp = (int)(Math.Pow(200 - (b[j] - b[d]),2)+kara[d]);
                    if (tmp < kara[j])
                    {
                        kara[j] = tmp;
                        trasa[j] = d;
                    }
                    else if(kara[j] == -1000)
                    {
                        kara[j] = tmp;
                        trasa[j] = d;
                    }
                }
            }

            for (int i = 1; i < b.Length; i++)
            {
                Console.WriteLine("Hotel w odległości: " + b[i] + ", kara wynosi: " + kara[i] +
                                  ". Optymalna trasa przez podane hotele to: ");
                hoteleTrasa(trasa,i);
                Console.WriteLine();
            }

        }

        static void Zadanie3(int[] m, int[] p, int k) //Algorytm maksymalnego oczekiwanego całkowitego zysku
        {
            int[] P = new int[m.Length];
            int temp = 0;
            int mnoznik = 0;
            for (int a = 1; a < m.Length; a++)
            {

                for (int b = 0; b <= a - 1; b++)
                {
                    if (m[a] - m[b] < k)
                    {
                         mnoznik = 0;
                    }
                    else if (m[a] - m[b] >= k)
                    {
                         mnoznik = 1;
                    }

                    temp = P[b] + (mnoznik * p[a]);

                    if (temp > P[a])
                    {
                        P[a] = temp;
                    }
                }

                if (P[a] < p[a])
                {
                    P[a] = p[a];
                }
            }

            Console.WriteLine("Przewidywany optymalny zysk to :"+P.Max());

        }

        static void Zadanie4(char[] s) //Algorytm wypisujący pojedyncze słowa ze złączonego zdania. Trzeba uzupełnic słownik u góry
        {
            int[] R = new int[s.Length];
            for (int i = 0; i < s.Length; i++)
            {
                R[i] = 0;
                for (int j = 0; j <= i - 1; j++)
                {
                    if (dict(s, j, i) == true)
                    {
                        R[j] = 1;
                    }
                }
            }

            for (int i = 0; i < s.Length; i++)
            {
                if (R[i] == 1)
                {
                    Console.Write(" ");
                }

                Console.Write(s[i]);
            }
        }

        static void Zadanie5(string source1, string source2)
        {
            var source1Length = source1.Length;
            var source2Length = source2.Length;

            var matrix = new int[source1Length + 1, source2Length + 1];

            // First calculation, if one entry is empty return full length
            if (source1Length == 0)
                Console.WriteLine(source2Length);

            if (source2Length == 0)
                Console.WriteLine(source1Length);

            // Initialization of matrix with row size source1Length and columns size source2Length
            for (var i = 0; i <= source1Length; matrix[i, 0] = i++) { }
            for (var j = 0; j <= source2Length; matrix[0, j] = j++) { }

            // Calculate rows and collumns distances
            for (var i = 1; i <= source1Length; i++)
            {
                for (var j = 1; j <= source2Length; j++)
                {
                    var cost = (source2[j - 1] == source1[i - 1]) ? 0 : 1;

                    matrix[i, j] = Math.Min(
                        Math.Min(matrix[i - 1, j] + 1, matrix[i, j - 1] + 1),
                        matrix[i - 1, j - 1] + cost);
                }
            }
            for (int i = 0; i < matrix.GetLength(0); i++)
            {
                for (int j = 0; j < matrix.GetLength(1); j++)
                {
                    Console.Write(matrix[i, j] + "\t");
                }
                Console.WriteLine();
            }
            Console.WriteLine("Odległość edycyjna wynosi: "+matrix[source1Length,source2Length]);
        }

        static void Zadanie6(char[] X, char[] Y) //Najdłuższy wspólny podciąg taki jak w zadaniu6
        {
            int m = X.Length;
            int n = Y.Length;
            int[,] C = new int[m+1,n+1];
            for (int i = 1; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (X[i-1] == Y[j-1])
                    {
                        C[i, j] = C[i - 1, j - 1] + 1;
                    }
                    else if (C[i-1,j] >= C[i,j-1])
                    {
                        C[i, j] = C[i - 1, j];
                    }
                    else
                    {
                        C[i, j] = C[i, j - 1];
                    }
                }
            }

            for (int i = 0; i < C.GetLength(0); i++)
            {
                for (int j = 0; j < C.GetLength(1); j++)
                {
                    Console.Write(C[i, j] + "\t");
                }
                Console.WriteLine();
            }
        }

        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
        {
            int[,] LCStuff = new int[m+1,n+1];
            int result = 0;
            for (int i = 0; i <= m; i++)
            {
                for (int j = 0; j <= n; j++)
                {
                    if (i == 0 || j == 0)
                    {
                        LCStuff[i, j] = 0;
                    }
                    else if(X[i-1] == Y[j-1])
                    {
                        LCStuff[i, j] = LCStuff[i - 1, j - 1] + 1;
                        result = Math.Max(result, LCStuff[i, j]);
                    }
                    else
                    {
                        LCStuff[i, j] = 0;
                    }
                }
            }

            Console.WriteLine("Najdłuższym wspólny podciąg ma długość: "+result);
        }

        static void Zadanie8(string seq) //Algorytm obliczania długości najdłuższego podciągu palindromicznego
        {
            int n = seq.Length;
            Console.Write("Długość najdłuższego podciągu palidromicznego wynosi:  "+ lps(seq));
        }
    }
}