Új hozzászólás Aktív témák

• #5203 Skaidy csendes tag

  Új Válasz 2011-05-26 12:57:15 #5203

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Skaidy

  csendes tag

  Üdv!

  Remélem jó helyre írok, ha nem akkor sry.
  Nem tudtam megoldani egy feladatot és ebben szeretnék segítséget kérni tőletek.

  A feladat:

  Mérje meg a gráf két csúcsa közötti legrövidebb út keresésének Dijkstra algoritmusának hatékonyságát! Töltsön le különböző méretű txt szövegeket (például a www.gutenberg.org-ról), olvassa be a segédprogram segítségével a memóriába, és hozza létre a gráfot. A gráf csúcsai az adott szavak, és két csúcs között fut él, ha a megadott távolságfüggvény kisebb, mint egy előre megadott szám (ezt a programozó állítja be.) Ezen a gráfon végezze el a keresést különböző méretű bemenetekre. Dokumentálja precízen a mérés lépéseit.

  Igazából az a gond, hogy órán még érintőlegesen sem vettük Dijkstra-algoritmusát, ami nem a legfőbb probléma, mert interneten utánajárva könnyen megtalálom, hogy hogy is működik. Viszont magát a programot sem látom át (mivel keveset programoztam még C++ban, inkább csak C-ben), meg hogy hogy kéne felfogni egy szöveget gráfokban..

  A segédprogram:

  // szavankent beolvasunk egy szoveget
  // a szavakat kisbetusitjuk, kitoroljuk a nem betuket
  // az eredmenyt rendezzuk, toroljuk az ismetlodeseket
  // es elmentjuk az a[] tombbe

  #include <iostream>
  #include <fstream>
  #include <algorithm>
  using namespace std;
  const int Z=10000000;
  string a[Z];
  string b[Z];
  //ha nagyon nagy meretu tombot foglalunk le,
  //azt vagy dinamikusan tudjuk megtenni (new fuggveny)
  //vagy globalis valtozokent
  int N=0;

  void beolvas(){
  string st;
  int i,j,k,s;
  ifstream fin("robinson.txt");
  while(fin>>st){
  s=st.size();
  for(k=0,i=0;k<s;k++){
  if(st>='A'&&st<='Z')st-='A'-'a';
  //nagy betu -> kisbetu
  if(st<'a'||st>'z')st.erase(st.begin()+i);
  //ami nem betu kitoroljuk
  else i++;
  }
  if(st.size()>0)b[N++]=st;
  //ha maradt a szobol berakjuk a tombbe
  }
  sort(b,b+N);
  a[0]=b[0];
  st=b[0];
  j=0;
  for(k=1,i=1;k<N;k++){
  if(b[k]!=st){a[i++]=b[k];st=b[k];j=0;}
  else if(j<2){ //a 2-o atirhato, ha ugy tartja szuksegesnek!
  a=b[k];
  j++;
  for(s=0;s<j;s++)a+='q';
  i++;
  }
  //ha nincs ismetlodes, elmentjuk az a[] tombbe
  //ha van, akkor irjunk moge egy 'q' betut, de max 2-ot, vagy irja at!
  }
  N=i;
  cout<<"N: "<<N<<endl;
  }

  int htavolsag(string a, string b){
  //visszaadja, hogy betuk szerint mi a ket string tavolsaga

  if(a==b)return 0;

  string tmp;
  if(a.size()>b.size()){tmp=a;a=b;b=tmp;}

  int x,z=0,f;

  for(x=0;x<a.size();x++)
  z+=(a[x]!=b[x]); //hany db betuben kulonbozik
  z+=b.size()-a.size(); //+szohossz kulonbseg
  z=z*z; //negyzetre emeljuk
  if(z>25) return 127; //a 0,1,2,3,4,5 betu kulonbsegek elfogadhatoak
  //a '127' a vegtelen nagy
  else return z;
  }

  Természetesen nem feltétlen kell a kész kódot valakinek elkészíteni, csak iránymutatást szeretnék kérni, és hogy egyáltalán hogy álljak neki, és hogy mi a lényege ennek.
  Előre is köszönöm.

Új hozzászólás Aktív témák