Drugio_efektas

//Drugio efektas
// 3 lygis, 1 pamokele, 4 uzduotis
/******************************************************
* Parasykite programa, kuri isspausdintu ilgiausia zodziu grandinele, sudaryta is pradiniu duomenu zodziu.
* Jei egzistuoja keletas vienodo ilgio zodzių grandineliu, rezultatu faile isveskite pirmaja.
*******************************************************/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <fstream>
#include <string>

using namespace std;
//---------------------------------------------------------
//Programoje naudojamos konstantos
const int MAKSIMALUS_ZODZIU_SKAICIUS = 100;
//---------------------------------------------------------
//Programoje naudojamu funkciju prototipai
void Skaityti(string zodziai[], int &zodziuSkaicius);
void Spausdinti(string ilgiausiaZodziuGrandinele);
string Grandineles_Sudarymas(string zodziai[], int zodziuSkaicius, int index, int ilgis[]);
bool Tikrinimas(string zodis1, string zodis2);
string ILgiausia(string z[], int n, int ilgis[]);
//---------------------------------------------------------
int main()
{
   int zodziuSkaicius = 0;
   string zodziai[MAKSIMALUS_ZODZIU_SKAICIUS];
   string ilgiausiaZodziuGrandinele;
   //Kitu programoje naudojamu kintamuju aprasymai
   string grandineles[MAKSIMALUS_ZODZIU_SKAICIUS]; // grandineliu variacijos
   int ilgis[zodziuSkaicius];                      // kiekvienos grandineles ilgis
   bool ar_eina;                                   // ar eina sudaryti grandinele
   //Programos veiksmai
   Skaityti(zodziai, zodziuSkaicius);

   for(int i = 0; i<zodziuSkaicius; i++)
     ilgis[i] = 0;

   // Siunciami skirtingi zodziai kaip pirmieji sudarantys grandinele:
   for(int i = 0; i<zodziuSkaicius; i++){
       grandineles[i] = Grandineles_Sudarymas(zodziai, zodziuSkaicius, i, ilgis);
       if(!ar_eina && grandineles[i]>zodziai[i]) ar_eina = true; // grandinele eina sudaryti
       cout << ar_eina << " --> " << grandineles[i] << "   " << ilgis[i] << endl;
   }
   if(ar_eina) ilgiausiaZodziuGrandinele = ILgiausia(grandineles, zodziuSkaicius, ilgis);
   else ilgiausiaZodziuGrandinele = zodziai[0]; // jei grandineles sudaryti neimanoma, atspausdinamas
   Spausdinti(ilgiausiaZodziuGrandinele);       // pirmaiss duomenu failo zodis

   return 0;
}
//---------------------------------------------------------
// Zodziu nuskaitymo funckija
void Skaityti(string zodziai[], int &zodziuSkaicius)
{
    ifstream fd("U1.txt");
    while(!fd.eof()){
        fd >> zodziai[zodziuSkaicius];
        zodziuSkaicius++;
    }
    fd.close();
}
//---------------------------------------------------------
// Funkcija, sudaranti zodziu grandinele
// index - pirmasis zodis, kuriuo pradedama grandinele
string Grandineles_Sudarymas(string zodziai[], int zodziuSkaicius, int index, int ilgis[])
{
    string kriterijus = zodziai[index];        // kriterijus, pagal kuri ieskoma atitinkamu zodziu grandinelei
    string Grandinele = zodziai[index] + '-';  // formuojama zodziu grandinele
    string AtsZodz[zodziuSkaicius];            // atsarginis zodziu masyvas

    for(int i = 0; i<zodziuSkaicius; i++)
        AtsZodz[i] = zodziai[i];
    AtsZodz[index] = "";                       // nebereikalingas zodis

    for(int i = 0; i<zodziuSkaicius; i++){     // dvigubas ciklas, kad butu griztama prie ankstesniu
        for(int j = 0; j<zodziuSkaicius; j++){ // zodziu, tokiu atveju, jei sarasas yra nerikiuotas
            if(Tikrinimas(kriterijus, AtsZodz[j])){ // rastas sekantis zodis
              kriterijus = AtsZodz[j];              // naujas paieskos kriterijus
              Grandinele += AtsZodz[j] + '-';       // kuriama grandinele
              AtsZodz[j] = "";                      // pasalinama zodzio reiksme
              ilgis[index]++;                       // didinamas grandineles ilgis
            }
        }
    }
    return Grandinele.substr(0, Grandinele.length()-1);
}
//---------------------------------------------------------
// Tikrinama, ar zodis zodziai tenkina salyga
bool Tikrinimas(string zodis1, string zodis2)
{
    /**
    * Kiekvienas grandinėlę sudarantis žodis nuo savo kaimyno gali skirtis tik vienu simboliu.
    * Vadinasi, gali tas zodis buti vienu simboliu didejantis, pvz.: lapas --> lapasa --> lapasas
    **/

    string ilg, tru; // ilgiausias ir trumpiausias zodis
    if(zodis1>zodis2){
        ilg = zodis1;
        tru = zodis2;
    }else{
        ilg = zodis2;
        tru = zodis1;
    }

    int kiek = 0;                               // lapas <--> lapad; lapas <--> lapasa
    if(ilg.length() - tru.length() <= 1){       // zodziai arba vienodo ilgio (skiriasi viduje), arba
        for(int i = 0; i<tru.length(); i++){    // antrasis zodis yra simboliu ilgesnis
            if(ilg[i] != tru[i]) kiek++;
        }
    }else return false;
    if((kiek==1 && ilg.length()==tru.length()) || (kiek==0 && ilg.length()-tru.length()==1)) return true;
    else return false;
}
//---------------------------------------------------------
// Surandama ir grazinama ilgiausia grandinele
string ILgiausia(string z[], int n, int ilgis[])
{
    /**
    * Daugiau '-' - ilgesne grandinele
    **/
    int max_ilg = 0;
    string grandinele = "";
    for(int i = 0; i<n; i++){
        if(ilgis[i] > max_ilg){
          grandinele = z[i];
          max_ilg = ilgis[i];
        }
    }
    return grandinele;
}
//---------------------------------------------------------
void Spausdinti(string ilgiausiaZodziuGrandinele)
{
   cout << ilgiausiaZodziuGrandinele;
}