Μεσος Ορος τιμων πινακα

[migf1]

Βάζεις και 2ο loop!

[Anubis13]

Βάζεις και 2ο loop!

 

Αυτο ειναι η προφανης λυση η οποια δεν μου αρεσει. Θα το σκεφτω ομως. ευχαριστω για τη μεχρι τωρα βοηθεια.

[migf1]

Έχεις ακούσει πουθενά πως γίνεται χωρίς 2o loop; Όπως και να έχει, καλή συνέχεια

[Anubis13]

Έχεις ακούσει πουθενά πως γίνεται χωρίς 2o loop; Όπως και να έχει, καλή συνέχεια

 

Τοτε αυτό που θελω λυνεται και με αλλο μη προφανη τροπο.

[parsifal]

Κατά τη σάρωση του πίνακα για συνάθροιση, κατασκεύασε παράλληλα ένα δεύτερο ισομεγέθη βοηθητικό πίνακα στον οποίον θα κρατάς running total. Από αυτόν, και αφού ολοκληρωθεί εννοείται η σάρωση του πίνακα εισόδου, είναι τετριμμένο να υπολογίζεις τους μέσους όρους που θες σε O(1)...

 

 

Edit: Ουπς, τώρα κατάλαβα πως θέλεις μία μοναδική καθοριστική λύση για όλους τους πιθανούς συνδυασμούς και όχι απλά παραμετροποιήσιμο από τον χρήστη εύρος θέσεων πίνακα από τον οποίο θα εξάγεται ο μέσος όρος. Συγγνώμη για τη βιαστική απάντηση, δεν προσέφερα τίποτα ουσιαστικό σε σχέση με τους προλαλήσαντες...

[Anubis13]

Σημερα μου ηρθε μια αλλη ιδεα για την οποια δεν πηρα χαρτι και μολυβι να επαληθευσω οποτε πιθανως να ειναι λανθασμενη. Καθως θελω μεσο ορο συνεχων στοιχειων του πινακα πχ {10, -2, 34, -8, 50, 1, -22}

τοτε θα βρω τον μεσο ορο ολων των στοιχειων και στη συνεχεια θα αρχισω να κοβω στοιχεια απο δεξια και απο αριστερα. Βεβαια δεν ειμαι σιγουρος αν παιρνω ολες τις περιπτωσεις γιατι αν δεν κανω λαθος ειναι linear δηλαδη υλοποιειται με ενα loop.

[bnvdarklord]

αν θες τον μεσο όρο των 10 34 1 πχ που ειναι ανακατεμενα και οχι μαζι στον πινακα τα χανεις ομως ετσι.

[Anubis13]

Ναι αλλα εγω θελω μεσο ορο μονο συνεχομενων στοιχειων του πινακα πχ -2, 34, -8 αυτος ειναι ενας συνδυασμος αλλα το 10 με το -22 δεν ειναι

[bnvdarklord]

Ααα πες το ετσι νομιζα ηθελες ολους μα όλους τους συνδιασμούς.

[migf1]

Εγώ ακόμα δεν έχω καταλάβει τι πρόβλημα υπάρχει με τα loops...

 

>
int main( void )
{
int i=0,j=0,k=0, sum=0, arr[] = {1, 2, 3, 4, 5};
float avg = 0.0;
int n = sizeof(arr) / sizeof(int);

printf("n = %d\n\n", n);

for (i=0; i<n; i++)
{
	sum = 0;
	for (j=i; j<n; j++)
	{
		sum = 0;
		printf("sum(");
		for (k=i; k<j+1; k++)
		{
			printf(" %d ", arr[k]);
			sum += arr[k];
		}
		avg = (float)sum / (float)(k-i);
		printf(") = %d / %d\t--> ( avg = %g )\n", sum, k-i, avg);
	}
}

return 0;
}

 

Output...

 

>
n = 5

sum( 1 ) = 1 / 1	--> ( avg = 1 )
sum( 1  2 ) = 3 / 2	--> ( avg = 1.5 )
sum( 1  2  3 ) = 6 / 3	--> ( avg = 2 )
sum( 1  2  3  4 ) = 10 / 4	--> ( avg = 2.5 )
sum( 1  2  3  4  5 ) = 15 / 5	--> ( avg = 3 )
sum( 2 ) = 2 / 1	--> ( avg = 2 )
sum( 2  3 ) = 5 / 2	--> ( avg = 2.5 )
sum( 2  3  4 ) = 9 / 3	--> ( avg = 3 )
sum( 2  3  4  5 ) = 14 / 4	--> ( avg = 3.5 )
sum( 3 ) = 3 / 1	--> ( avg = 3 )
sum( 3  4 ) = 7 / 2	--> ( avg = 3.5 )
sum( 3  4  5 ) = 12 / 3	--> ( avg = 4 )
sum( 4 ) = 4 / 1	--> ( avg = 4 )
sum( 4  5 ) = 9 / 2	--> ( avg = 4.5 )
sum( 5 ) = 5 / 1	--> ( avg = 5 )

[Anubis13]

Σημαινει οτι εχω τετραγωνικη πολυπλοκοτητα οταν εχω 1000000 στοιχεια στον πινακα τοτε εχω προβλημα χρονου.

[migf1]

Σημαινει οτι εχω τετραγωνικη πολυπλοκοτητα οταν εχω 1000000 στοιχεια στον πινακα τοτε εχω προβλημα χρονου.

Για τι είδους εφαρμογή προορίζεται;

[Anubis13]

@migf1:

Programming Challenge: Μου ειπαν οτι πιθανως η καλυτερη πολυπλοκοτητα ειναι Ο(nlogn). Μην μου ζητησετε να σας το μεταφρασω σε κωδικα.

Η καλυτερη μου ιδεα μεχρι στιγμης βρισκεται στο post 21.

[migf1]

1. http://en.wikipedia.org/wiki/Kadane%27s_Algorithm

2. http://n1b-algo.blogspot.com/2010/03/largest-sum-of-consecutive-numbers.html

3. http://www.geeksforgeeks.org/archives/576

 

Από κει και πέρα, δικό σου...

[Anubis13]

Eυχαριστω για τα link. τα εχω ηδη μελετησει