# Shkenca > Informatikë dhe Internet > Arti i programimit >  Sfida nga PR-TECH: Trekëndëshi i Paskalit

## edspace

_Sfida është hapur nga Grupi Teknologjik i Prishtinës. Ato hidhen në forum që anëtarët të mund të diskutojnë zgjidhjet dhe të mësojnë nga eksperienca e njëri-tjetrit. Tema do qëndrojë e mbyllur gjatë kohës që sfida është e hapur dhe zgjidhja juaj nuk duhet bërë publike gjatë kësaj kohe. Kur të skadojë afati i lejuar, tema do hapet dhe pastaj mund të postoni përgjigjet tuaja dhe të diskutoni me anëtarët e tjerë._

Trekëndëshi i Paskalit 
Problemi eshte i hapur
Prej:03/11/2004     Deri:15/11/2004  

Në këtë sfidë ju duheni t'a krijoni një skriptë që do të merr vlerën e rreshtit dhe vlerën e elementit mbrenda rreshtit të dhënë tek Trekëndëshi i Paskalit (ang. Pascal's Triangle). Pas marrjës të këtyre vlerave, skripta e kalkulon vlerën adekuate. Pra, nëse vlera hyrëse për rresht është *4* dhe vlera për elementin mbrenda këtij rreshti është *3*, atëherë rezultati do të jetë *3*. 
Nëse i shikoni katër rreshtat e parë të Trekëndëshit të Paskalit, do të vëreni që elementi i tretë i rreshtit të katërt ka vlerën *3*, ku kjo është në pajtueshmëri me kalkulimin e shfaqur në rreshtat e mësipërm.



```
1
1  1
1  2  1
1  3  3  1
```

Merreni parasysh që skripta duhët t'a bëj edhe vërtetimin e vlerës të elementit mbrenda rreshtit. P.sh. nëse vlera e rreshtit është 2 dhe vlera e elementit mbrenda këtij rreshti është 4, atëherë skripta duhet të jep mesazh që rreshti adekuat nuk përmbanë atë element.

Skripta mundet të bëhet në C, C++, Java, ose Perl. Nëse programi juaj përmbanë më shumë se një skedar atëherë le të arkivohet si tar.gz apo zip dhe si i tillë le të dërgohet në *programim ET pr-tech PIKË net*.
Rrezultatet dhe kodet e sakta do të paraqiten deri më 1 javë pas skadimit të afatit të problemit.

----------


## edspace

```

// Emri: Trekendeshi i Paskalit
// Autori: Eduard Papa 
// Email: edspace ET comcast PIKË net
// Data: 04/11/04 
// Pershkrim: Sfida e Javes nga Grupi Teknologjik i Prishtines
// Perpiluesi: Dev-C++ 4.9.9.0
// Perdorimi: paskali.exe #rreshtit #elementit
//       P.sh. paskali.exe 4 5
        
#include <iostream>

using namespace std;

// funksioni: faktorial
// merr: numer
// kthen: faktorialin e numrit
// psh. 3! = 3 * 2 * 1 = 6
// funksion riperserites (recursive)
int faktorial(int numri);

// funksioni: main
// merr: numrin e argumentave, argumentat
// argumenti i pare: adresa e programit
// argumenti i dyte: rreshti
// argumenti i trete: elementi
int main(int argc, char *argv[])
{ 
  // nqs jane me pak se tre argumenta
  // nxjerrim mesazh gabimi dhe mbyllim programin
  if( argc < 3 )
  {
    cout << "Numer i gabuar argumentash." << endl;
    return 0;
  }
  
  // merr argumentin e rreshtit dhe elementit
  // i shnderrojme ne int me funksionin atoi
  int rreshti = atoi(argv[1]);
  int elementi = atoi(argv[2]);
  
  // kontrollojme nqs te dhenat jane te gabuara
  // dhe nxjerrim mesazh, mbyllim programin
  if( elementi < 1 || elementi > rreshti )
  {
    cout << "Gabim: Rreshti " << rreshti
       << " nuk permban elementin " << elementi << endl;  
    return 0;
  }
  
  rreshti--; // zbresim 1 sepse numerimi fillon nga 0
  elementi--; // zbresim 1 sepse numerimi fillon nga 0
  
  // formula per te gjetur vleren: rreshti! / ( elementi! * (rreshti - elementi)! )
  int rezultati = faktorial(rreshti) / (faktorial(elementi) * faktorial(rreshti - elementi)); 
  
  cout << "Elementi " << elementi + 1
     << " ne rreshtin " << rreshti + 1 
     << " eshte " << rezultati << endl; 
  
  // gjithcka mbaroi me sukses, mbyllim programin
  return 0;
}

int faktorial(int numri) {
  if(numri <= 1) return 1;
  return numri * faktorial(numri - 1);
}

// fund 



```

----------


## edspace

```

/****************************************************
* Zgjidhja e problemit te javes : Trekendeshi i Paskalit 
* Autor: Hasan Cana <vpb ET albabsd PIKË org> 
*      
* Ska fillozofi veq keni me shkru vleren e rreshtit 
* edhe vleren e elementit edhe ka me ju tregu rrezultatin
* nese e keni shkru ndonje vlere te naj elementit qe nuk egziston
* ne ate rresht ateher ka me ju tregu qe aj element nuk egziston     
****************************************************/

#include <stdio.h>

int main ()
{

/* Definimi i ARRAY-ave
*/
int rreshti_i_kerkuar;
int rreshti;
int elementi;
/* ktu mirret vlera e rreshtit edhe elementit
*/ 
printf("Vlera e rreshtit: ");
scanf("%d", &rreshti_i_kerkuar);
rreshti = rreshti_i_kerkuar;
printf("\nVlera e elementit: ");
scanf("%d", &elementi);
int x, y;
/* ktu x edhe y barazohen me vlerat qe i kina jap ma nalt
* qe me dit cilin rresht edhe cilin
* element me kerku per me gjet rrezulltatin
*/
 for (x=rreshti; x <= rreshti; x++) 
 for (y=elementi; y <= elementi; y++) 
/* nese y osht ma e madhe se x ateher na tregon qe elementi nuk egziston
* sepse numri i rreshtave smunet me kon ma i vogel se numri i elementeve psh
* 1  2  1  ky osht rreshti i tret edhe ka tri elemente edhe domethon qe
* x munet me qen ma e madhe se y po munet me kon edhe baraz me y ama sguxon me qen
* ma i vogel se y se rreshti i tret nuk ka element tkatert kshtut qe po tregon qe numri 
* i elementeve smunet me kon ma i madh se i rreshtave  ishalla pe kuptoni :P
*/
 if (y>x) 
   printf("\nKy element nuk egziston ne rreshtin qe e keni cekur me lart\n");
/* nese y osht ma e vogel se x ateher zbatohet formula e shkrume ma posht
*/ 
else if (y<x) 
   printf ("\n\n%6d\n\n",formula(x,y));
/* edhe ktu gjithashtut
*/
 else if (y=x) 
 printf("\n\n%6d\n\n",formula(x,y));

}
/* funksioni qe i kryn qato operacionet per trekendeshin e paskalit
*/
int formula (int x, int y)
{
/* qitu duhet me bo y barazi me 1 se me bo y barazi me 0 ja nis 
* mi numru rreshtat edhe elementet prej zeros
*/
if (y==1)
return 1;
else if (x==y)
return 1;
else
return (formula(x-1,y-1)+formula(x-1,y));
} 



```

----------


## qoska

meqenese programi punon por eshe shkruar ne c style per te qene i plote  o edspace veri dhe ca kontroll gabimesh te nevojshme per nje program te plote. 
Gjithsesi zgjidhja per mua mbetet e sakte, panvaresisht se nqs fundkisoni faktorial do te zevendesohej me nje menyre iterative cka do te thote nje cikel(loop) si "while" do te ishte me i shpejte.
P.S. Eshte vetem nje kendveshtrim mos fillojme te bejme sherre jo kush di me shume a me pak , JU LUTEM  :buzeqeshje:

----------


## edspace

Përdora metodën ripërsëritëse sepse e kisha të gatshme, është funskion i shkurtër, dhe i lehtë për të kuptuar. Mënyra iterative me While dhe For janë pak më të shpejta por me një përpilues të mirë, mund të eliminohet fare ndryshimi. 

Nuk të kuptova në lidhje me kontrollin e gabimeve. E ke fjalën për gabimet e tipit  try..catch apo return 0, 1, 2...

Gabimet më të rëndësishme kapen nga if-et.

----------


## qoska

try dhe catch 
e kisha fjalen ose me mire te themi assert() qe perdoret ne keto raste sidomos nga konvertimi qe behet ne atoi()

----------


## edspace

Menjëherë pas atoi(), kam shkruajtur IF për të kapur gabimet. Nuk besoj të ngelet ndonjë gabim pa kapur. 

Shkruaj ndonjë rresht kod si shëmbull për të treguar diçka që do kapje ti me assert() që nuk e kap IF që kam shkruajtur unë.

----------


## IlirDeda

Po jap edhe une disa mendime meqe tema me duket interesante.

Programi i Edit jep rezultate korrekte deri ne rreshtin e 13. 
Per rreshtin e 14 e me tej rezultatet jane te gabuara. P.sh. rezultati i ketij programi per elementin 2 ne rreshtin 14 eshte 4. Natyrisht pergjigja e sakte eshte 13.
Arsyeja  e ketij gabimi eshte qe 13! = 6227020800 nuk mund te paraqitet nga nje int ne C++ (Windows).  Kur sistemi mundohet te paraqese 13! me int kemi nje integer overflow. Numri i plote me i madh qe mund te paraqitet nga nje int eshte 2147483648 kurse numri me i madh qe mund te paraqitet nga nje unsigned int eshte 4294967296. Nese do te paraqitesh numra me te medhenj se keto duhet te perdoren metoda te tjera.
Per me teper programi i Edit jep nje division by zero error, p.sh. per elementin 4 ne rreshtin 100. Prandaj nje try ... catch do kishte ndihmuar ne kete rast. Arsyeja e gabimit eshte e njejte si me pare, integer overflow.

Programi i Hasanit jep rezultate te sakta per sa kohe qe rezultati vete mund te paraqitet me nje integer. Nese do perdorej unsigned int mund te merreshin me shume rezultate te sakta sic e permenda me lart.

Ne lidhje me dallimin me funksioneve rekursive dhe iterative: Eshte teper e veshtire qe nje kompilator i nje gjuhe imperative si C++ ose Java te jape te njejten shpejtesi per funksionet rekursive dhe iterative. Ceshtja eshte se sa here qe therritet nje funksion duhet krijuar nje stack frame e re e cila sigurisht qe merr kohe dhe memorie. Vetem ne gjuhe funksionale dhe vetem kur eshte e mundur dhe vetem kur programuesi e di se c'ben eshte e mundur qe nje program rekursiv te kete te njejten shpejtesi me nje program iterativ. Ndonje dite mund te flasim per kete kocept ne ndonje thread te posaçme. Kush nuk pret dot le te kerkoje ne Google per "tail recursive".

Sic thashe me lart programi i Hasanit jep rezultate te sakta, por shpejtesia e tij le per te deshiruar.
Problemi nuk eshte vetem qe programi eshte rekursiv, por edhe menyra e perdorimit te algoritmit eshte naive.
Vini re qe formula e perdorur eshte 
p(x,y) = p(x-1, y-1) + p(x-1, y)
Ku x eshte rreshti dhe y pozicioni ne rresht.
Por :
p(x-1, y-1) = p(x-2, y-2) + p(x-2, y-1)
p(x-1, y) = p(x-2, y-1) + p(x-2, y)

Vini re qe p(x-2, y-1) llogaritet dy here ne programin e Hasanit. Nese futesh me tej ne rekursion do shohesh qe shumica e elementeve llogariten shume shume here, nderkohe qe natyrisht nese nje element eshte llogaritur me pare nuk ka nevoje te llogaritet me.
Ne fakt programi i Hasanit eshte eksponencial ne run-time dhe eksponecial ne memorie. Une bera disa eksperimente ne kompjuterin tim dhe mora keto rezultate:
Elementi 4 ne rreshtin 500 merr 2 sekonda per tu llogaritur.
Elementi 4 ne rreshtin 1000 merr 19 sekonda per tu llogaritur.
Elementi 4 ne rreshtin 2000 merr 148 sekonda per tu llogaritur.

Prandaj nje zgjidhje me e mire e problemit duhet te llogarise cdo element vetem nje here. Ka menyra te ndryshme per ta bere kete. Nje program ilustrativ (por jo profesional) eshte ky qe po jap me poshte. Nje pjese te kodit (kontrolli i te dhenave dhe shtypja e rezultatit) e kam kopjuar nga Edi.



```

// Pascal3.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


#include <iostream> 

using namespace std; 

unsigned int paskal(unsigned int rreshti, unsigned int elementi); 

// funksioni: main 
// merr: numrin e argumentave, argumentat 
// argumenti i pare: adresa e programit 
// argumenti i dyte: rreshti 
// argumenti i trete: elementi 
int main(int argc, char *argv[]) 
{ 
    // nqs jane me pak se tre argumenta 
    // nxjerrim mesazh gabimi dhe mbyllim programin 
    if( argc < 3 ) 
    { 
        cout << "Perdorimi: " << argv[0] << " rreshti elementi" << endl; 
        return 0; 
    } 
    
    // merr argumentin e rreshtit dhe elementit 
    // i shnderrojme ne int me funksionin atoi 
    unsigned int rreshti = atoi(argv[1]); 
    unsigned int elementi = atoi(argv[2]); 
    
    // kontrollojme nqs te dhenat jane te gabuara 
    // dhe nxjerrim mesazh, mbyllim programin 
    if( elementi < 1 || elementi > rreshti ) 
    { 
        cout << "Gabim: Rreshti " << rreshti 
            << " nuk permban elementin " << elementi << endl;   
        return 0; 
    } 
    
    unsigned int rezultati = paskal(rreshti, elementi);
    cout << "Elementi " << elementi 
        << " ne rreshtin " << rreshti 
        << " eshte " << rezultati << endl; 
    
    // gjithcka mbaroi me sukses, mbyllim programin 
    return 0; 
} 

//Klase teper elementare. E programuar keshtu vetem per thjeshtesi programimi.
//Mos e perdor per asnje program serioz
class Matrica {
public:
    Matrica(unsigned int rreshta, unsigned int kolona) {
        memorie = new unsigned int[rreshta * kolona];
    }
    unsigned int getElement(unsigned int rreshti, unsigned int kolona) {
        return memorie[kolona-1 + (rreshti - 1) * (kolona - 1)];
    }
    void setElement(unsigned int rreshti, unsigned int kolona, unsigned int vlera) {
        memorie[kolona-1 + (rreshti - 1) * (kolona - 1)] = vlera;
    }


private:
    unsigned int* memorie;
};

unsigned int paskal(unsigned int rreshti, unsigned int elementi) {
    Matrica matrica(rreshti, elementi);
    for(unsigned int i = 1; i <= rreshti; i++) {
        for(unsigned int j = 1; j <= i && j <= elementi; j++) {
            if(j==1 || i==j) {
                matrica.setElement(i, j, 1);
            } else {
                unsigned int vlera = matrica.getElement(i-1, j-1) + matrica.getElement(i-1, j);
                matrica.setElement(i, j, vlera);
            }
        }
    }
    return matrica.getElement(rreshti, elementi);

} 



```


Ky program e llogarit elementin 4 ne rreshtin 2000 per me pak se 10 milisekonda, pra me shume se 100 mije here me shpejt se programi i Hasanit.

----------


## werewolf

normale qe do punoj me shpejte joti.
sic e the dhe vete hasani e ka bere ne O(2^n) kurse ti duke perdorur tekniken e dynamic programming  e ke bere ne O(n^2).
Problemet qe japin per tu zgjidhur tek PR-TECH jane te lehte!
Nese doni probleme me te bukur (dhe me te veshtire, normale) shkoni tek http://acm.uva.es/problemset/

----------


## edspace

Zor se hedh njeri kod në forum tani.  :buzeqeshje: 

Kodi tënd punon shpejt por zë goxha memorje dhe për numra të mëdhenj ndodhin gabime në rezervimin e memorjes: This application has requested the runtime to terminate in an unusual way. 

Një pjesë e mirë e memorjes që rezervon nuk shfrytëzohet dhe shpejtësia e programit bie rëndshëm kur fillon përdorimi i memorjes virtuale. 

Për numrat e mëdhenj mendoj se do ishte më i përshtashëm përdorimi i një formule.

----------


## IlirDeda

Edi, me vjen keq nese pergjigja ime eshte konsideruar si sfide apo dicka tjeter e ketij lloji.
Une kam 20 vjet qe programoj dhe nese kam mesuar nje gje eshte qe gjithkush ka mundesi te te mesoje dicka. Ketu perballe meje ne pune une kam nje djale 20 vjecar te cilit i bej pyetje te pakten nje here ne dite dhe me ndihmon goxha.
Une i kam ndjekur per nje kohe shume te gjate forumet shqiptare por nuk jam futur pasi nuk me interesonin diskutimet. Por keto kohet e fundit vura re qe ishin futur ne kete forum njerez si ti e disa te tjere. Shume inteligjente pa diskutim por te tille ka pasur edhe me pare. E reja ketu eshte qe ju keni njohuri te thella, keni bonsens per te ndihmuar dhe keni vullnet ti uleni nje dickaje qe "dihet" dhe vertet ta beni realitet.
Une bera nje pyetje ketu ne forum dhe vertet mora pergjigje te vlefshme.
Ndaj dhe vendosa te shikoj nese mund te jap edhe une ndihmen time ne ndonje teme diskutimi.
Une besoj se ke mesuar dicka te vlefshme nga pergjigja ime. Kufizimet e numrave dhe zgjedhja e algoritmit me te pershtatshem jane probleme qe nuk dalin shpesh neper shkolla por ndodhin shpesh ne praktike. P.sh. para disa javesh une po shkruaja nje sistem ne C++ qe komunikonte me nje sistem ne Java. Sistemi ne Java perdorte nje long (64 bit) per te paraqitur nje moment ne kohe. Nese do perdorej nje long ne anen tjeter ne C++ do humbnim rezultatin sepse nje long ne C++ eshte 32 bit. Mu desh te mendohesha disa kohe derisa gjeta nje zgjidhje te pershtatshme.
Shpresoj se nuk eshte e vertete ajo qe askush nuk do hedhe kod ne forum tani. Ne fund te fundit nese njerezit bezdisen une po heq dore, bile edhe s'po i lexoj fare. 
Por duhet te vesh re qe i pari qe hodhi kod ketu pas jush jam une, dhe ti menjehere gjete disa probleme. Nuk ka kod pa probleme Edi, ka vetem kod qe eshte "good enough".

Ti nese ke deshire mund te gjesh nje zgjidhje me te mire se imja.
Problemi i pare me kodin tim eshte qe nuk jep pergjigje te sakte nese rezultati eshte me i madh se 4294967295. Arsyeja eshte sepse perdor unsigned int per te paraqitur rezultatin. Pra ti mund te gjesh menyra te tjera per te llogaritur numra me te medhenj. Mund te shkosh me 64 bit, ose mund te ndertosh nje klase Integer qe paraqet nje numer me precizion te cfaredoshem te kufizuar vetem nga memoria e makines. Meqe ra fjala numra te tille kaq te medhenj kane vlere ne kriptografi.
Problemi i dyte eshte ai qe ke gjetur ti qe per numra te medhenj programi shkaton gabime memorie. Ti sugjeron qe mund te perdoret ndonje formule. Pse nuk e gjen nje formule te tille? Ti mund te vesh re p.sh. qe formula origjinale qe ti paraqite eshte e tipt n!/k!(n-k)! ku k<n. Pra k! perfshihet ne n!. Pra ti nuk ke nevoje te llogaritesh k! asfare (pasi do thjeshtohet). Ne programin tend ti mund te shikosh se kush eshte me e madhe k apo n-k dhe te eliminosh numrin me te madh qe te kesh nevoje te besh sa me pak llogaritje. Me tej gjate llogaritjeve ti mund ta sajosh algoritmin qe te mos lejosh overflow. P.sh. kur llogarit  (6*7*8) /(1*2*3) dhe numrat i ke paraqitur ne 8 bit (byte), 6*7*8 eshte overflow, por nese ti ve re se 2*3 eshte 6 dhe e thjeshton 6, atehere rezultati eshte 56 qe nuk eshte overflow.
Une mund te sugjeroja nje drejtim tjeter. Nese e studion me kujdes ciklin qe kam shkruar une ne funksionin paskal() do shohesh qe per te llogaritur elementet e nje rreshti te duhen vetem elementet e nje rreshti me lart. Pra ti mund te shkruash nje program qe sapo perfundom se llogarituri nje rresht i fshin rezultatet e rreshtit te mesiperm duke liruar keshtu memorien. Ne kete menyre ne cdo kohe do kesh ne memorie jo me shume se dy rreshta.
Nese shkruan nje program te tille do vesh re qe do jesh gjithe kohen duke zene memorie te re dhe duke fshire te vjetren (new and delete). Keto operacione harxhojne kohe. Por ti mund te shkosh me tej dhe te fillosh ta riperdoresh memorien qe ke zene ne vend qe ta lirosh per ta zene prape. E keshtu me radhe Edi, permiresimet jane te pafundme.
Shpresoj qe te kem qene me shume ndihme se sa bezdi Edi. Te jesh i bindur qe une vete mesoj shume nga diskutimet qe behen ketu.

----------


## edspace

Ilir, 

Gëzohem me pjesëmarrjen tënde dhe sa më shumë kod të hedhësh, aq më mirë do jetë. Thashë "nuk do hedh kod njeri" dhe vendosa  :buzeqeshje:  sepse ishte shaka. 

Kritikat e tua për kodin tim ishin me vënd dhe do ti kem parasysh herën tjetër. Unë i mirëpres kritikat dhe i kërkova dhe nga qoska. 

Kam marrë klasa për gjetjen e gabimeve të tilla por siç thua dhe ti, këto gabime dalin më shumë në praktikë. Praktika ime në shkollë ka qënë më shumë për të patur një program funksional, dhe për ta dorëzuar kodin brënda 3-4 ditëve që mund të lejojë profesori. Nuk ngelet kohë në shkollë për të shkruajtur kod të përkryer. 

Duke ditur sa e vështirë është lënda, unë mundohem të ndihmoj anëtarët e tjerë që janë në hapat e para të programimit. Në të njëjtën kohë pres që të mësoj diçka edhe vetë, dhe prandaj të vlerësoj ty dhe të tjerët që kanë më shumë eksperiencë dhe bëjnë kritika të dobishme.

----------


## qoska

o edspace se mbase une nuk jam aq i zgjeruar ne pergjigjet qe jap.
Per njohuri une mund ta hap forumin shume shpesh por koha qe mund te kem ne dispozicion eshte shume e vogel dhe prandaj nuk mund te te kthej pergjigje te plota dhe nganjehere paksa enigmatike.
Gjithsesi do mundohem qe te permiresoj cilesine e pergjigjeve dhe me kundrashembuj e referenca ok.
Persa i perket kodit do qe me kerkove do mundohem te shkruaj program per trekendeshin e paskalit qe te ket sa me pak probleme dhe do ta postoj behet fjale per nja dy dite ok?  :buzeqeshje:

----------


## werewolf

Sja vlen te shifni per gabime te tilla ne programe, si ato qe po kerkonit.......dhe po te kerkosh ne cdo kod gjen ndo1 gabim, ska program perfekt!
gjeja qe ja vlente te thuhej per ndryshimet midis programeve besoj ishte vetem koha qe i duhej atij te hasanit & atij te edit, dhe koha qe i duhej atij te ilirit per te gjetur zgjidhjen, dhe kjo besoj eshte nje gje e mire pasi kalon nga nje algoritem O(2^n) ne nje qe do vetem O(n^2) kohe.......... e kote qe shikoni per gabime ne kod pra........

----------


## qoska

o werewolf ne nuk po mundohemi te gjejme gabime por te ndajme dijen tone nepermjet ketyre programeve nqs ti e di se si te parandalosh disa gabime do te jete shume me e thjeshte kur krijon programe per perdorim ne mase per te gjetur disa gabime te cuditshme dhe te papritura, panvaresisht se ne informatike shpeshhere ca gabime tolerohen per shkak te kompromiseve qe duhen pranuar  :buzeqeshje:

----------


## Ardi_Pg_ID

Per mendimin tim nje kontroll gabimesh duhet ne cdo argumet apo loop te programit .. nuk e di po mbase kjo eshte teknika qe ne na kane dhene en shkollat ne USA nuk e di po mua me kane ndihmuar shume gjate te gjitha programeve qe kam programuar edhe me eshte bere shprehu ne cdo kod qe shkruaj vendos nje kontrollor per te pare nese gjithcka shkon per sembari
Ardi

----------

