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.
Kodi PHP:
// 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.
Përgjigju Duke Cituar
Krijoni Kontakt