ligh voh8eia xreiazomai!

antonios88 · 21 Οκτωβρίου 2007

geia xara paidia!

mou dw8hke mia ergasia kai thn exw ksekinisei.

kapou omws mesa ston kwdika kati dn paei kala!

an mporeite,rixte mia matia na mou peite ti sumvainei!

o kwdikas mou einai autos(dn ton exw teleiwsei)

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <conio.h>

int binarySearch(int A[], int left, int right, int key, int *elements);

int main (void)

{

int i,diast,choice,sh;

unsigned long int A[]={0};

printf("Doste thn epithymhth diastash toy pinaka:");

scanf("%d",&diast);

printf("Doste to eidos arxikopoihshs (1:almost uniform, 2: non-uniform)\n");

scanf("%d",&choice);

printf("\n\nArxikopoihsh me times\n\n");

if (choice==1){

srand(time(NULL));

A[0] = (rand() % 100);

srand(time(NULL));

for(i = 1; i < diast; i++){

A = A[i-1]+1+(rand() % 100);

}}

else{

srand(time(NULL));

A[0] = (rand() % 100);

for(i = 1; i < diast; i++){

A = A[i-1]+1+(rand() % 100);

}

A[diast-1]=A[diast-2]*50;

}

printf("Arxikopoihsh me times oloklirothike\n\n");

printf("Ta stoixeia toy pinaka einai:");

//!!!!provlima meta thn 5h print ,kati ginetai!

printf("\t%d \n",A[0]);

printf("\t%d \n",A[1]);

printf("\t%d \n",A[2]);

printf("\t%d \n",A[3]);

printf("\t%d \n",A[4]);

printf("\t%d \n",A[5]);

printf("\t%d \n",A[6]);

printf("\t%d \n",A[7]);

printf("\t%d \n",A[8]);

printf("\t%d \n",A[9]);

//kai an to kanw me for ta pragmata ginontai xeirotera!!!!

for (i=0;i<diast;i++){

printf("%d",A);

}

printf("Doste ena stoixeio anazhthshs:");

scanf("\n%d\n",&sh);

}

int binarySearch(int A[], int left, int right, int key, int *elements)

{

return 0;

}

DD_lab2.zip

ask2(prototupo ka8hghth).zip

ask2(diko mou).zip

asxeto4 · 22 Οκτωβρίου 2007

Den mas les prota ti akrivos theleis na kanei to programma sou?

antonios88 · 22 Οκτωβρίου 2007

edw einai h askhsh!

>ΜΑΘΗΜΑ: ΕΡΓΑΣΤΗΡΙΟ ΔΟΜΕΣ ΔΕΔΟΜΕΝΩΝ 
ΕΡΓΑΣΤΗΡΙΑΚΗ ΑΣΚΗΣΗ: 2
ΛΗΞΗ ΠΡΟΘΕΣΜΙΑΣ ΥΠΟΒΟΛΗΣ: 30/10/07 

Θεματολογία: Δυναμικοί Πίνακες, Αναζήτηση 
Υλοποιήστε τις ακόλουθες συναρτήσεις:
int binarySearch(int A[], int left, int right, int key, int *elements)
Λειτουργία: Υλοποιεί τη δυαδική αναζήτηση σε πίνακα με όρια [left..right]. key είναι 
το κλειδί αναζήτησης και elements μια μεταβλητή που περνιέται με αναφορά και μετρά
το πλήθος των στοιχείων του πίνακα που επισκέφτηκε η διαδικασία. Η συνάρτηση 
επιστρέφει τη θέση που βρέθηκε το key ή -1 αν δε βρέθηκε.
int interpolationSearch(int A[], int left, int right, int key, int *elements)
Λειτουργία: Όμοια με παραπάνω μόνο που η αναζήτηση γίνεται με παρεμβολή (interpolation search). Θυμηθείτε ότι στην παρεμβολή σαν μεσαίο στοιχείο εκλέγεται το:
mid=((double)(key-A[left])/(A[right]-A[left]))*(right-left)+left
int mixedSearch(int A[], int left, int right, int key, int *elements)
Λειτουργία: Όμοια με παραπάνω μόνο που σε κάθε φάση ο αλγόριθμος έχει 50% πιθανότητα να λειτουργήσει σαν binary search και 50% σαν interpolation search.
void displayMatrix(int A[], int length)
Λειτουργία: παίρνει σαν παράμετρο έναν πίνακα και τυπώνει τα στοιχεία του.
Η main() θα διαβάζει το επιθυμητό όριο ενός πίνακα ακεραίων και θα τον δημιουργεί. Η αρχικοποίηση του πίνακα με τιμές θα μπορεί να γίνει με δύο τρόπους (έπειτα από αντίστοιχη επιλογή του χρήστη). Στον πρώτο οι τιμές θα ακολουθούν περίπου uniform κατανομή. Πιο συγκεκριμένα το Α[0] θα αρχικοποιείται σαν τυχαία τιμή από 0...99 και ένα οποιοδήποτε στοιχείο Α[i] ως: A[i]=A[i-1]+1+τιμή τυχαία από [0...99]. Ο δεύτερος τρόπος είναι ακριβώς ίδιος με τον πρώτο, μόνο που η τελευταία τιμή του πίνακα ορίζεται σαν 50*προτελευταία τιμή. Στη συνέχεια θα εμφανίζονται τα στοιχεία του πίνακα και θα ζητείται από το χρήστη μια τιμή αναζήτησης. Στα αποτελέσματα θα εμφανίζονται: η θέση που βρέθηκε το στοιχείο και οι πράξεις (στοιχεία του πίνακα που 
ελέγχθησαν) που εκτέλεσε ο κάθε αλγόριθμος.

Πείραμα: Δημιουργήστε έναν πίνακα 100000 στοιχείων και βάλτε προς αναζήτηση το πρότελευταίο στοιχείο του. Σημειώστε τις πράξεις που εκτέλεσε ο κάθε αλγόριθμος και με τις 2 αρχικοποιήσεις. Βάσει του πειράματος ποιον αλγόριθμο θα επιλέγατε αν δεν ξέρετε εκ των προτέρων την κατανομή που ακολουθούν τα στοιχεία του πίνακα; Τεκμηριώστε σύντομα.  

Κατεβάστε το αντίστοιχο exe και τρέξτε το για να δείτε τη λειτουργία του προγράμματος που καλείστε να υλοποιήσετε. Στην παρούσα άσκηση θα πρέπει να γράψετε και μια σύντομη αναφορά όσον αφορά το πείραμα που εκτελέσατε.

edw einai o kwdikas pou exw ftiaxei ws twra

>#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
int binarySearch(int A[], int left, int right, int key, int *elements);
int interpolationSearch(int A[], int left, int right, int key, int *elements);
int mixedSearch(int A[], int left, int right, int key, int *elements);
void displayMatrix(int A[], int length);
int main (void)
{
int i,diast,choice,sh;
unsigned long int A[]={0};
printf("Doste thn epithymhth diastash toy pinaka:");
scanf("%d",&diast);
printf("Doste to eidos arxikopoihshs (1:almost uniform, 2: non-uniform)\n");
scanf("%d",&choice);
printf("\n\nArxikopoihsh me times\n\n");
if (choice==1){
   srand(time(NULL));
       A[0] = (rand() % 100);
	srand(time(NULL));
   for(i = 1; i < diast; i++){
       A[i] = A[i-1]+1+(rand() % 100);
}}
else{
   srand(time(NULL));
       A[0] = (rand() % 100);

   for(i = 1; i < diast; i++){
       A[i] = A[i-1]+1+(rand() % 100);
}
A[diast-1]=A[diast-2]*50;
}
printf("Arxikopoihsh me times oloklirothike\n\n");
printf("Ta stoixeia toy pinaka einai:");
//!!!!provlima meta thn 5h print  ,kati ginetai!
printf("\t%d \n",A[0]);
printf("\t%d \n",A[1]);
printf("\t%d \n",A[2]);
printf("\t%d \n",A[3]);
printf("\t%d \n",A[4]);
printf("\t%d \n",A[5]);
printf("\t%d \n",A[6]);
printf("\t%d \n",A[7]);
printf("\t%d \n",A[8]);
printf("\t%d \n",A[9]);
//kai an to kanw me for ta pragmata ginontai xeirotera!!!!
for (i=0;i<diast;i++){
printf("%d",A[i]);
}
printf("Doste ena stoixeio anazhthshs:");
scanf("\n%d\n",&sh);
int mixedSearch(A, int left, int right, int key, int *elements);

}

int binarySearch(int A[], int left, int right, int key, int *elements)
{
return 0;
}
int interpolationSearch(int A[], int left, int right, int key, int *elements)
{
return 0;
}
int mixedSearch(int A[], int left, int right, int key, int *elements)
{
int y;
srand(time(NULL));
       y=(rand() % 2);
	if(y==0){	
binarySearch(A,left,right,key,*elements);
	}
	else{
interpolationSearch(A,left,right,key,*elements);
	}
return 0;
}
void displayMatrix(int A[], int length)
{
   int i;
printf("Ta stoixeia toy pinaka einai:");
   for(i = 0; i < length; i++){
       	printf(" %d ", A[i]);
}
printf("\n");
}

ama mporeite dwste mou na katalavw ti exw kanei la8os!

bilco · 22 Οκτωβρίου 2007

Με μια γρήγορη ματιά, δεν βλέπω πουθενά να κάνεις allocation στον Α

alex2005 · 22 Οκτωβρίου 2007

Από την στιγμή που το μέγεθος του πίνακα ορίζεται από τον χρήστη τότε αφού πάρεις το μέγεθος πρέπει να κάνεις.

int* A = new int[diast];

mummy · 22 Οκτωβρίου 2007

Η αλήθεια είναι οτί δεν πολυδιάβασα τον κώδικα σου αλλά για ρίξε μία ματιά και στην malloc συνάρτηση.Δεσμέυει δυναμικά χώρο.Ψάξε στο google θα βρεις αρκετά.

bokarinho · 22 Οκτωβρίου 2007

Ένα είναι το σίγουρο διαβάζοντας το πρόγραμμα σου, οτι μάλλον θα χρειαστείς πολύ βοήθεια και όχι λίγη. Τέλος πάντων αν βρω το χρόνο γιατί αυτήν την περίοδο πνίγομαι θα σου γράψω λίγο κώδικα να βρεις την λύση, να είσαι καλά.

antonios88 · 24 Οκτωβρίου 2007

sas euxaristw polu paidia kai

pio polu esena bokarinho!

8a psaksw na vrw sto internet gia thn malloc pws douleuei,

giati to vivlio ths c++ pou exw den epeksigei kala

pws na thn xrhsimopoihsw,gi'auto exw kollisei!tespa,8a psaksw opws mou eipate

kai an vrw ta duskola 8a sas pw!

Dikemou · 24 Οκτωβρίου 2007

λάθος τόπικ, σόρρυ...

bokarinho · 24 Οκτωβρίου 2007



//---------------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

//---------------------------------------------------------------------------

int binarySearch(int A[], int left, int right, int key, int *elements)
{
	if(left > right)
		return -2;
	else
	{
		int mid = 0;
		int low = left;
		int high = right;
		*elements = 0;
		while(low < high)
		{
			mid = (low + high) / 2;
			if(A[mid] < key)	/* An to kleidi einai megalytero, tote to katw  */
								/* orio (low) einai i epomeni thesi apo to mid. */
				low = mid + 1;
			else
				high = mid;     /* Edw low to idio to high den einai mid-1 giati */
								/* mporei to A[mid] >= key */
			*elements += 1;
		}
		if(low < right && A[low] == key)
			return low;
		else
        	return -1;
    }
}

int *createArray(int Length)
{
	int i;
	int *A = calloc(Length, sizeof(int));
	if(!A)
		return NULL;
	else
	{
		srand(time(NULL));
		A[0] = rand() % 100;
		for(i = 1; i < Length; i++)
			A[i] = A[i-1] + 1 + rand() % 100;
		return A;
	}
}

void freeArray(int *A)
{
	free(A);
}
void printArray(int *A, int Length)
{
	int i;
	for(i = 0; i < Length; i++)
		printf("%d\n", A[i]);
}
void printRandomPositionValue(int *A, int Length)
{
	printf("Random value to check for key is: %d\n", A[rand() % Length]);
}

int main(int argc, char* argv[])
{
	int found = -3;
	int elements = 0;
	int key = 0;
	int *A = NULL;
	A = createArray(100000);
	printRandomPositionValue(A,100000);
	printf("The one element of the array before last is: %d\n", A[99998]);
	printf("Give me the key to search:");
	scanf("%d", &key);
	found = binarySearch(A,0,100000, key, &elements);
	if(found < 0)
		printf("Key %d is not found.\n", key);
	else
		printf("Key %d is found in place %d of the input A array\nTotal amount of elements searched is: %d\n", key, found, elements);
	freeArray(A);
	printf("Hit any key to continue....");
	getch();
	return 0;
}
//---------------------------------------------------------------------------

[/Code]

To παραπάνω πρόγραμμα δεν απαντάει πλήρως στην άσκηση σου, κάνει την binary search και στην main() υπάρχει ο τρόπος με τον οποίο ζητάει ο καθηγητής σας να γίνει, δες το και προσπάθησε και πες μου..

afnman · 24 Οκτωβρίου 2007

edw einai h askhsh!

>#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
int binarySearch(int A[], int left, int right, int key, int *elements);
int interpolationSearch(int A[], int left, int right, int key, int *elements);
int mixedSearch(int A[], int left, int right, int key, int *elements);
void displayMatrix(int A[], int length);
int main (void)
{
int i,diast,choice,sh;
unsigned long int A[]={0};
printf("Doste thn epithymhth diastash toy pinaka:");
scanf("%d",&diast);
printf("Doste to eidos arxikopoihshs (1:almost uniform, 2: non-uniform)\n");
scanf("%d",&choice);
printf("\n\nArxikopoihsh me times\n\n");
if (choice==1){
   srand(time(NULL));
       A[0] = (rand() % 100);
	srand(time(NULL));
   for(i = 1; i < diast; i++){
       A[i] = A[i-1]+1+(rand() % 100);
}}
else{
   srand(time(NULL));
       A[0] = (rand() % 100);

   for(i = 1; i < diast; i++){
       A[i] = A[i-1]+1+(rand() % 100);
}
A[diast-1]=A[diast-2]*50;
}

}

ama mporeite dwste mou na katalavw ti exw kanei la8os!

-Kαταρχην tην Srand(time(NULL)) την τρέχεις μια φορα στην main και μονο Μία.

-Δευτερον,Τον πίνακα κάνεις μονο μια φορα Ιnitiliazation αφου πάρεις την diast απο τον χρήστη και δεσμευσεις μνήμη με την calloc() (δες καποιο reference για C) ή new είναι μονο για C++ compilers.

http://www.cplusplus.com/reference/clibrary/cstdlib/calloc.html

px

Initiliazation:

>
unsigned long int *A;
scanf("%d",&diast);
A = (unsigned long int*) calloc (diast,sizeof(unsigned long int));
 if (A==NULL) exit (1);
for(i = 1; i < diast; i++){
       A[i] = A[i-1]+1+(rand() % 100);

}

-Tριτον ... με μονο μια if ελεγχεις για non-uniform ή uniform.

>scanf("%d",&choice);if(choice==2) A[diast-1]=A[diast-2]*50;

Tωρα αν θες να κάνεις και ελεγχο για το αν δοθηκε καποια άλλη τιμή

μπορεις να γραψεις κατι τετοιο

>flag=1;
while(flag)
{ 
if(choose==2) 
{A[diast-1]=A[diast-2]*50;flag=0;} else if(choose==1) flag=0;else{ flag=1; printf("error")}

-Tεταρτον,ανοιξε το βιβλιο των δομων δεδομενων που σου δινουν στο ΤΕΙ για να γραψεις σε functions τους αλγοριθμους αναζήτησης

Αν είναι να στα δωσουμε ολα ετοιμα δεν προκειται να γινεις ΠΟΤΕ καλος προγραμματιστης.

Υ.Γ νομιζω ειναι περιττη η createArray του φιλου παραπάνω ... περιττο jump ...

Υ.Γ και εγω ΤΕΙτζης ειμαι αλλα δεν μας εβαζαν τετοια θέματα...Μπραβο! εχει ανεβει το επιπεδο

antonios88 · 26 Οκτωβρίου 2007

file mou,egw eimai trelos gia ton programmatismo!

dn eimai kanenas tempelhs foithths!alla ama hsoun sto TEI pou eimai egw,8a hkseres oti oxi shmeiwseis,oute vivlia dn exoume akoma!th vgazoume me ena vivlio programmatismou tou a' eksamhnou!gi'auto dn psaxnomai mono egw,alla oloi

sto tmhma mou!gi'auto rwtaw edw kai mh me parekshgeis!

afnman · 29 Οκτωβρίου 2007

Pws 8a ylopoihseis px tin dyadiki anazitish an de sou exoun ypodeicsei ton algori8mo?

Vasika na pigaineis 8ewria....

antonios88 · 29 Οκτωβρίου 2007

vasika...ama dn eisai edw twra na katalaveis ti na sou ekshgw!oute mia 8ewria dn exw xasei!tespa!thanks,file mou,pantws me voh8hses!xrhsimopoihsa thn malloc.mou menoun twra oi 2 anazhthseis...8a tis palepsw!!ta leme!

antonios88 · 30 Οκτωβρίου 2007

paidia thanks gia thn voh8eia alla,telika katafera kai thn ekana monos mou!

exw mono mia aporia sthn interpolationSearch:

>
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
int binarySearch(int A[], int left, int right, int key, int *elements);
int interpolationSearch(int A[], int left, int right, int key, int *elements);
int mixedSearch(int A[], int left, int right, int key, int *elements);
void displayMatrix(int A[], int length);
int main (void)
{
int i,diast,choice,sh;
int as=0;
int *A;
printf("Doste thn epithymhth diastash toy pinaka:");
scanf("%d",&diast);
A = ( int *) malloc (diast* sizeof( int));
do{
printf("Doste to eidos arxikopoihshs (1:almost uniform, 2: non-uniform)\n");
scanf("%d",&choice);
}while((choice!=1)&&(choice!=2));
printf("\n\nArxikopoihsh me times\n\n");
if(!A)

	exit(1);
else
{
srand(time(NULL));
if (choice==1){   
       A[0] = (rand() % 100);
   for(i = 1; i < diast; i++){
       A[i] = A[i-1]+1+(rand() % 100);
}}
if (choice==2){
       A[0] = (rand() % 100);

   for(i = 1; i < diast; i++){
       A[i] = A[i-1]+1+(rand() % 100);
}
A[diast-1]=A[diast-2]*50;
}
printf("Arxikopoihsh me times oloklirothike\n\n");
displayMatrix(A,diast);

printf("Doste ena stoixeio anazhthshs:");
scanf("%d",&sh);


binarySearch(A,0,(diast-1),sh,&as);

printf(" sth thesh:%d\n",as);
interpolationSearch(A,0,(diast-1),sh,&as);
printf(" sth thesh:%d\n",as);
mixedSearch(A,0,(diast-1),sh,&as);
printf(" sth thesh:%d\n",as);
free(A);
printf("Press any key to continue...\t");
   getche();
}

return 0;

}
int binarySearch(int A[], int left, int right, int key, int *elements)
{
int flag=0;

int mid,i;
i=0;
printf("\nbinary search anazhthsh\n");
while(left<=right){
mid=((left+right)/2);
i++;
if (A[mid]==key){
*elements=mid;
flag=1;
printf("Arithmos stoixeion toy pinaka poy koitaxthkan:%d\nTo stoixeio brethike",i);
break;
}

else{
	if(A[mid]<key){
		left=mid+1;
	}
	else{
		right=mid-1;
}}}
if(flag==1){
	return mid;
}
if(flag==0){	
printf("Arithmos stoixeion toy pinaka poy koitaxthkan:%d\n",i);
printf("To stoixeio de brethike ston pinaka,oute");
}
return -1;
}
int interpolationSearch(int A[], int left, int right, int key, int *elements)
{
	int flag=0;
int i,mid;
i=0;
printf("\nInterpolation search anazhthsh\n");
while(left<=right){
/*h askhsh zhtaei to:mid=((double)(key-A[left])/(A[right]-A[left]))*(right-left)+left.
an baloume double omws,xalaei h roh tou programmatos(oxi panta,analoga,mono an tou dwsw na
psaksei gia ena ari8mo pou den uparxei ston pinaka,tote analoga me ton ari8mo,enw h binarySearch
douleuei PANTA,h interpolation den einai sigouro oti 8a doulepsei mporei na kollhsei to
programma!gi'auto to logo anti gia double xrhsimopoihsame int:
mid=((int)(key-A[left])/(A[right]-A[left]))*(right-left)+left.
dokimasame na dhlwsoume thn mid double kai na th metatrepsoume pio katw se integer alla eixame
to idio apotelesma kai den mporoume na broume thn aitia afou 8a eprepe h metatroph na ginotan
automatws:mid=(<<<<<(double)>>>>(key-A[left])/(A[right]-A[left]))*(right-left)+left.*/
mid=((int)(key-A[left])/(A[right]-A[left]))*(right-left)+left;
i++;

if (A[mid]==key){
*elements=mid;
flag=1;
printf("Arithmos stoixeion toy pinaka poy koitaxthkan:%d\nTo stoixeio brethike",i);
break;
}

else{
	if(A[mid]<key){
		left=mid+1;
	}
	else{
		right=mid-1;
}}}
if(flag==1){
	
	return mid;
}
if(flag==0){
printf("Arithmos stoixeion toy pinaka poy koitaxthkan:%d\n",i);
printf("To stoixeio de brethike ston pinaka,oute");	
}
return -1;
}
int mixedSearch(int A[], int left, int right, int key, int *elements)
{
int y;
printf("\n\nMixed search anazhthsh\n");
srand(time(NULL));
       y=(rand() % 2);
	if(y==0){	
binarySearch(A,left,right,key,&elements);
	}
	else{
interpolationSearch(A,left,right,key,&elements);
	}

return 0;
}
void displayMatrix(int A[], int length)
{
   int i;
printf("Ta stoixeia toy pinaka einai:");
   for(i = 0; i < length; i++){
       	printf(" %d ", A[i]);
}
printf("\n");
}

Σύνδεση

ligh voh8eia xreiazomai!

Προτεινόμενες αναρτήσεις

antonios88

asxeto4

antonios88

bilco

alex2005

mummy

bokarinho

antonios88

Dikemou

bokarinho

afnman

antonios88

afnman

antonios88

antonios88

Αρχειοθετημένο

Σύνδεση