Δυνατοί συνδυασμοί αριθμών που κάνουν συγκεκριμένο άθροισμα

[defacer]

0   0   0   2   2   0

0   0   1   0   3   0

0   0   2   1   0   1

0   1   0   2   0   1

0   1   1   0   1   1

1   0   0   0   2   1

1   1   0   0   0   2

3   4   1   0   0   0

4   1   3   0   0   0

4   2   1   1   0   0

4   3   0   0   1   0

5   0   1   2   0   0

5   0   2   0   1   0

5   1   0   1   1   0

6   0   1   0   0   1

10   2   0   0   0   0

11   0   0   1   0   0

 

Εγώ αυτά βγάζω. Τα νούμερα είναι οι συντελεστές των εκάστοτε σκορ.

 

 

Αυτό όμως δε μπορεί να είναι σωστό. Π.χ. η πρώτη γραμμή φαίνεται να λέει πως 2 * 23 + 2 * 29 = 100 πράγμα που προφανώς δεν ισχύει. Επίσης από την εκφώνηση προκύπτει ότι ψάχνεις να βρεις γραμμές όπου το άθροισμα των συντελεστών είναι ακριβώς 6, όμως καμία από τις λύσεις που προτείνεις δεν έχει αυτό το χαρακτηριστικό.

 

Ο κώδικας που δίνεις έχει λάθη (a = 11 ενώ εννοείς a <= 11) αλλά δεν ξέρω αν είναι απλά λάθη αντιγραφής.

 

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

 

Update για τα μερακλίκια: dynamic programming λύση σε PHP.

Επεξ/σία 27 Δεκεμβρίου 2014 από defacer

[AfterForever]

Ρ[1]←7
Ρ[2]←15
Ρ[3]←19
Ρ[4]←23
Ρ[5]←29
Ρ[6]←37
 
για α απο 0 μέχρι 6
για β απο 0 μέχρι 6
για γ απο 0 μέχρι 6
για δ από 0 μεχρι 6
για ε απο 0 μεχρι 6
για ζ απο 0 μεχρι 6
αν α*Ρ[1]+β*Ρ[2]+γ*Ρ[3]+δ*Ρ[4]+ε*Ρ[5]+ζ*Ρ[6]=100 και α+β+γ+δ+ε+ζ=6 τότε
γράψε α," ", β," ", γ," ", δ," ", ε," ", ζ
τέλος_αν
τέλος_επανάληψης
τέλος_επανάληψης
τέλος_επανάληψης
τέλος_επανάληψης
τέλος_επανάληψης
τέλος_επανάληψης

1   3   1   0   1   0
2   0   3   0   1   0
2   1   1   1   1   0
2   2   1   0   0   1
3   0   1   1   0   1

Ίσως τώρα είναι σωστό. Πριν είχα κάνει λάθος στα νούμερα των πινάκων και δεν είχα βάλει και τη συνθήκη που πολύ σωστά είπες.

Λογικά τώρα είναι σωστό. Πολλές επαναλήψεις μεν, δε μπορώ να σκεφτώ κάτι καλύτερο δε.

[defacer]

Ναι αυτό είναι σωστό.

 

Αν θέλεις μπορείς να δεις τη λογική με την οποία δουλεύει η top-down dynamic programming λύση παραπάνω:

 

Κρατάμε ένα πίνακα όπου το κάθε στοιχείο είναι μια (ενδεχομένως κενή) λίστα με λύσεις για τον αριθμό που αντιστοιχεί στην εκάστοτε θέση του πίνακα. Ο πίνακας ξεκινάει τελείως κενός εφόσον αρχικά δεν ξέρουμε καμία λύση.

 

(Επίπεδο αναδρομής: 0) Ξεκινάμε να βρούμε λύση για τον αριθμό π.χ. 22 (βολεύει για να κάνω το παράδειγμα αντί για το 100). Κοιτάμε τον πίνακα, βλέπουμε πως δε γνωρίζουμε λύση για το 22. Παίρνουμε λοιπόν τους αριθμούς του P με τη σειρά. Πρώτα είναι το 7. Αν λοιπόν ξέραμε λύση για το 22 - 7 = 15 έστω ακολουθία Χ, Υ, Ζ τότε θα ήταν προφανής και μια λύση για το 22: Χ, Υ, Ζ, 7. Επομένως καλούμε αναδρομικά τη συνάρτηση να μας βρει λύση για το 15.

 

(Επίπεδο αναδρομής: 1) Δε γνωρίζουμε λύση για το 15. Παίρνουμε πάλι το 7, 15 - 7 = 8, ψάχνουμε αναδρομικά λύση για το 8.

 

(Επίπεδο αναδρομής: 2) Δε γνωρίζουμε λύση για το 8. Παίρνουμε πάλι το 7, 8 - 7 = 1, ψάχνουμε αναδρομικά λύση για το 1.

 

(Επίπεδο αναδρομής: 3) Δε γνωρίζουμε λύση για το 1. Τώρα όμως 1 - 7 < 0, προφανώς δεν πρόκειται να βρούμε ποτέ λύση για το 1. Δεν κάνουμε τίποτα άλλο, επιστρέφουμε στο προηγούμενο επίπεδο.

 

(Επίπεδο αναδρομής: 2) Εδώ ψάχναμε λύση για το 8 και μόλις είχαμε δοκιμάσει με το 7. Βρήκαμε; Όχι (αν βρίσκαμε, θα ήταν τώρα αποθηκευμένη στον πίνακα με τις λύσεις). Δοκιμάζουμε με το 15, όμως 8 - 15 < 0 οπότε προφανώς δεν πρόκειται ποτέ να βρούμε λύση για το 8. Δεν κάνουμε τίποτα άλλο, επιστρέφουμε στο προηγούμενο επίπεδο.

 

(Επίπεδο αναδρομής: 1) Εδώ ψάχναμε λύση για το 15 και μόλις είχαμε δοκιμάσει με το 7. Βρήκαμε; Όχι (αν βρίσκαμε, θα ήταν τώρα αποθηκευμένη στον πίνακα με τις λύσεις). Δοκιμάζουμε με το 15 και παρατηρούμε πως 15 - 15 = 0 άρα βρήκαμε λύση! Τη σημειώνουμε στον πίνακα και συνεχίζουμε να ψάχνουμε, όμως στην επόμενη προσπάθεια 15 - 19 < 0 άρα δεν κάνουμε τίποτα άλλο, επιστρέφουμε στο προηγούμενο επίπεδο.

 

(Επίπεδο αναδρομής: 0) Μόλις είχαμε δοκιμάσει να βρούμε λύση για το 22 - 7 = 15. Ελέγχουμε τον πίνακα των λύσεων να δούμε αν βρήκαμε. Ναι! Βρήκαμε, η λύση είναι η [15]. Έτσι τώρα ξέρουμε πως μια λύση για το 22 είναι [15 + 7].

 

Αυτή η φάση γίνεται σε μεγαλύτερη κλίμακα για να βρεις λύσεις για το 100.

 

Η διαφορά σε σχέση με την "αφελή" λύση είναι τεράστια: λύνοντας για το 100 με 6 προσθετέους αυτός ο αλγόριθμος βρίσκει τις 5 λύσεις κάνοντας 375 επαναλήψεις αντί για 6^6 = 46.656. Λύνοντας για το 200 με 12 προσθετέους βρίσκει τις 52 λύσεις με 975 επαναλήψεις αντί για 6 ^ 12 = 2.176.782.336. Λύνοντας για 300 με 18 προσθετέους βρίσκει τις 173 λύσεις με 1575 επαναλήψεις σε λίγα δευτερόλεπτα αντί για 6 ^ 18 = 101.559.956.668.416 επαναλήψεις, τις οποίες αν δοκιμάσεις το πρόγραμμα δε θα τελειώσει "ποτέ".

 

Αν σ' ενδιαφέρει να καταλάβεις το πώς και το γιατί, ένα πολύ πολύ ευκολότερο στη σύλληψη πρόβλημα όπου θα δεις το ίδιο φαινόμενο είναι ο αναδρομικός υπολογισμός της ακολουθίας Fibonacci:

int fibonacci(int n) {
    return n == 0 || n == 1 ? 1 : fibonacci(n - 1) + fibonacci (n - 2);
}

Δοκίμασε να το τρέξεις αυτό για n = 10 και ανέβαινε με βήμα 5 να δεις τι θα γίνει όταν περάσεις το 30. Με dynamic programming όμως μπορείς να φτάσεις μέχρι όποιο ρεαλιστικό νούμερο θέλεις (αν και χρησιμοποιώντας int για τους υπολογισμούς μετά το n = 46 πιθανότατα θα έχεις "τεχνικό πρόβλημα" λόγω overflow, πράγμα που βέβαια είναι άσχετο με τη μέθοδο του υπολογισμού).

[Directx]

Θα συμφωνήσω με τον defacer, για την ιστορία πάντως - από περιέργεια μπορείς να εξαλείψεις τα nested-for μεταφέροντας τα σε έναν πίνακα από μετρητές (p_c).

 

Ακολουθεί κώδικας σε C (γραμμένος δίχως αναδρομή).

 

/*
 * Darts!
 */
#include <stdio.h>
#include <string.h>

int main(void) {

	int i_p = 5,
		p[6] = { 7, 15, 19, 23, 29, 37 },
		p_c[6] = { 0, 0, 0, 0, 0, -1 },
		p_c_end[6] = { 5, 5, 5, 5, 5, 5 };

	bool skip;

	do {
		if((skip = p_c[i_p] >= 5)) {
			p_c[i_p] = 0;

			i_p--;
		}
		else {
			p_c[i_p]++;

			i_p = 5;
		}

		if(!skip) {
			int sum = 0,
				p_c_sum = 0;

			for(int i_sum = 0; i_sum < 6; ++i_sum) {
				sum += p_c[i_sum] * p[i_sum];
				p_c_sum += p_c[i_sum];
			}

			if(sum == 100 && p_c_sum == 6) {
				static int i_chr;

				for(i_chr = 0; i_chr < 6; ++i_chr)
					printf("%d ", p_c[i_chr]);

				printf("\n\t => ");

				for(i_chr = 0; i_chr < 6; ++i_chr)
					for(int i_times = 0; i_times < p_c[i_chr]; ++i_times)
						printf("%d ", p[i_chr]);

				putchar('\n');
			}
		}

	} while( memcmp(&p_c, &p_c_end, sizeof(p_c_end)) );

	puts("Press Enter to exit..");
	getchar();

	return 0;
}

ΕΞΟΔΟΣ:

1 3 1 0 1 0
         => 7 15 15 15 19 29
2 0 3 0 1 0
         => 7 7 19 19 19 29
2 1 1 1 1 0
         => 7 7 15 19 23 29
2 2 1 0 0 1
         => 7 7 15 15 19 37
3 0 1 1 0 1
         => 7 7 7 19 23 37
Press Enter to exit..

Υ.Γ.

Το πρόγραμμα έχει γραφθεί σε C++ Builder και μπορεί να περιέχει bugs ή άλλες αβλεψίες.

 

 

Καλή συνέχεια

[AfterForever]

Σας ευχαριστώ πολύ όλους για το χρόνο που διαθέσατε και τις απαντήσεις.

Καλή χρονιά να έχουμε.

[AfterForever]

Πιο σωστό είναι νομίζω και το πιο απλό:

for (a=0;i<6;i++)
for (b=0;i<6;i++)
for (c=0;i<6;i++)
for (d=0;i<6;i++)
for (e=0;i<6;i++)
for (f=0;i<6;i++)
if(P[a]+P[b]+P[c]+P[d]+P[e]+P[f]=100) then
print P[a],P[b],P[c],P[d],P[e],P[f]

Και βγάζει όλους τους πιθανούς συνδυασμούς και τελείωνει η ιστορία.

Γιατί "μπλέξαμε" με συντελεστές κτλ δεν καταλαβαίνω.

Μιλάω πάντα για την εκφώνηση της άσκησης Darts

Στο παιχνίδι Darts (βελάκια) τα επιτρεπτά σκορ με ένα βέλος είναι: 
7, 15, 19, 23, 29 και 37. Στόχος του παιχνιδιού είναι να συγκεντρωθούν 100 βαθμοί 
ακριβώς με 6 βολές. Ποιοι είναι οι δυνατοί συνδυασμοί για να επιτευχθεί αυτό; 
(Θεωρήστε ότι τα 6 διαφορετικά επιτρεπτά σκορ βρίσκονται σε πίνακα ακεραίων Ρ[6]).

Και πάλι ευχαριστώ για το ενδιαφέρον.