προγραμμα υπολογισμου αθροισματος

[gfg62]

καλησπερα, χρειαζομαι ενα προγραμμα το οποιο να υπολογιζει το παρακάτω (για διευκολυνση, σας δινω ενα παραδειγμα):

εστω οτι εχω σε μια μεταβλητη, με ονομα "ζητουμενο", το ποσό 8.

στην συνεχεια θελω να εχω ένα πίνακα με 5 αριθμους.

πχ. χ=[1 6 7 2 9]

θελω το προγραμμα να κανει ολα τα πιθανα αθροισματα των ποσων που εχει ο πινακας Χ και αν τα αθροισματα  κάνουν το ποσό 8 (το ποσο της μεταβλητης ζητουμενο), να εμφανιζει τα αποτελεσματα.

δηλαδη η απάντηση για το παραπάνω παράδειγμα ειναι:

1η απαντηση: 6 2

2η απαντηση: 1 7

 

το προγραμμα στην αρχη να με ρωταει:

ποιο ειναι το ποσο της μεταβλητης "ζητουμενο"

ποιο θα ειναι το πληθος των αριθμων που θα δωσω για τον πινακα

ποιοι ειναι οι αριθμοι του πινακα

 

πως μπορει να δημιουργηθει κατι τετοιο; μπορω να το βρω καπου;

παλαιοτερα ασχολουμουν με matlab και ξερω οτι απο εκει θα μπορουσε να φτιαχτει. ωστοσο, μετα από 7 χρονια, δεν θυμαμαι τους κωδικες.

 

μπορει να βοηθήσει καποιος;

 

(το ιδανικο για την δουλεια μου θα ηταν να λυνω το παραπανω προβλημα μεσω excel, αλλά οποιαδήποτε αλλη λυση καλοδεχουμενη)

ευχαριστώ!

[vaiosgtr]

γνωριζεις καποια γλωσσα προγραμματισμου? το παρακατω ειναι το βασικο σωμα. οπου P[n] ειναι ο πινακας και x ειναι το ζητουμενο. τα i και j ειναι απλα μετρητες.

 

for(i=0; i<n/2; i++)
{
	for(j=0; j<n; j++)
	{
		if(P[i+P[j]==x)
			print(P[i], " + ", P[j], "\n");
	}
}

Επεξ/σία 28 Οκτωβρίου 2016 από vaiosgtr

[rafinos]

γνωριζεις καποια γλωσσα προγραμματισμου? το παρακατω ειναι το βασικο σωμα. οπου P[n] ειναι ο πινακας και x ειναι το ζητουμενο. τα i και j ειναι απλα μετρητες.

 

for(i=0; i<n/2; i++)
{
	for(j=0; j<n; j++)
	{
		if(P[k]+P[i]==x)
			print(P[i], " + ", P[j], "\n");
	}
}

Γιατί κάνεις n/2 στο πρώτο for;

Επίσης το k τι είναι;

 

Πιο σωστό θα ήταν κάτι τέτοιο:

for($i=0; $i<($n-1); $i++){ //$n-1 γιατί το τελευταίο ψηφίο θα έχει γίνει ήδη πρόσθεση με τα προηγούμενα
   for($j=($i+1); $j<$n; $j++){ //$i+1 γιατί πάντα γίνεται πρόσθεση με το $i στοιχείο και άρα έχει γίνει το loop με τα προηγούμενα νούμερα
      if(($P[$i]+$P[$j]) == $x){
         echo $P[$k]."+".$P[$j]."\n";
      }
   }
}

Να τονίσω ότι το παραπάνω είναι σε php και δείχνει μόνο τον τρόπο υπολογισμού και όχι το πως γίνεται η εισαγωγή των στοιχείων.

[gfg62]

το μονο που θυμαμαι ειναι η matlab. ειχα κανει παλια php και java αλλα δεν τα θυμαμαι καθολου.

οι παραπανω κωδικες λειτουργουν στην matlab ή θα χρειαστω αλλο προγραμμα;

για την εισαγωγη των στοιχειων;

[vaiosgtr]

το k ηταν συντακτικο λαθος. το διωρθωσα.

 

στο πρωτο for βαζω n/2 επειδη δεν θελω διπλα τα ιδια πραγματα. δηλαδη στο παραδειγμα δεν θελω να μου εμφανισει 1+7 6+2 7+1 2+6.

ο ελεγχος, αν i=j να μην κανει τιποτα, ειναι απαραιτητος. μπραβο, εγω το ξεχασα. δηλαδη δεν θελεις να προσθετεις αριθμους με τον εαυτο τους.

 

με το matlab δεν εχω ασχοληθει, οποτε δεν γνωριζω.

[rafinos]

το k ηταν συντακτικο λαθος. το διωρθωσα.

 

στο πρωτο for βαζω n/2 επειδη δεν θελω διπλα τα ιδια πραγματα. δηλαδη στο παραδειγμα δεν θελω να μου εμφανισει 1+7 6+2 7+1 2+6.

ο ελεγχος, αν i=j να μην κανει τιποτα, ειναι απαραιτητος. μπραβο, εγω το ξεχασα. δηλαδη δεν θελεις να προσθετεις αριθμους με τον εαυτο τους.

 

με το matlab δεν εχω ασχοληθει, οποτε δεν γνωριζω.

Ναι, αλλά έτσι θα γίνει έλεγχος των μισών αριθμών με όλους. Κάπου δεν μου κολλάει. 

Εμείς θέλουμε το 1ο στοιχείο να γίνει πρόσθεση με όλα, μετά το 2ο να γίνει πρόσθεση με όλα αλλά όχι με το 1ο γιατί έγινε ήδη μια φορά κτλ. 

[Anubis13]

def printPairs(ar, arsize, sum):
    hmap = [0]*100
    for i in range(arsize):
        tmp = sum - ar[i]
        if (tmp >= 0 and hmap[tmp] == 1)
            print "Pair:", ar[i], tmp
        hmap[ar[i]] = 1

target = [1, 6, 7, 2, 9]
sum = 8
printPairs(target, len(target), sum)

Ορίστε μία απλή ιδέα που υλοποείται σε matlab(η συγκεκριμένη είναι σε python)

[albNik]

Βασικά δεν ζητάει μόνο άθροισμα δυάδων

[rafinos]

Βασικά δεν ζητάει μόνο άθροισμα δυάδων

Εμείς αυτό καταλάβαμε... αλλά ας μας το διευκρινίσει για σιγουριά. 

[gfg62]

σωστα το καταλαβε ο albNik. το παραδειγμα δεν ηταν τοσο καλο για να διευκρινιστεί. το αθροισμα δεν θα ειναι μονο δυαδων.

δινω παρακάτω αλλο παραδειγμα.

χ=[ 60 70 10 20 40 65 5], ζητουμενο=100

1η απαντηση: 70 10 20

2η απαντηση: 60 40 

3η απαντηση: 65 5 10 20

[rafinos]

http://stackoverflow.com/questions/4720271/find-a-pair-of-elements-from-an-array-whose-sum-equals-a-given-number

[Anubis13]

OP:

http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

[albNik]

σωστα το καταλαβε ο albNik. το παραδειγμα δεν ηταν τοσο καλο για να διευκρινιστεί. το αθροισμα δεν θα ειναι μονο δυαδων.

δινω παρακάτω αλλο παραδειγμα.

χ=[ 60 70 10 20 40 65 5], ζητουμενο=100

1η απαντηση: 70 10 20

2η απαντηση: 60 40 

3η απαντηση: 65 5 10 20

Υπάρχει πολύ γρήγορος τρόπος μα βρεις πόσες n-άδες κάνουν 100. 

Eίναι ο συντελεστής του x¹⁰⁰ στο (1+x⁶⁰)(1+x⁷⁰​) (1+x¹⁰) (1+x²⁰) (1+x⁴⁰​) (1+x⁶⁵)(1+x⁵​)        

[NickSym]

Μια απόπειρα από εμένα σε ψευδοκώδικα.

Είναι μια αναδρομική συνάρτηση.

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

Δεν έχεις παρά να τον κάνεις trace με κάποιο/α παραδείγματα.

 

function(int array[], int value, int key) {

    int newArray[];

    int i, newValue;

    if(array.length == 0) return null;



    for(i = 0; i < array.length; i++) {

        newValue = array[i];

        if(newValue + value == key) {

             newArray.add(newValue);

             return newArray;

        } else if(newValue + value > key) {

             return null;

        }

        array.delete(i);

        newArray = function(array, value + newValue, key);

        if(newArray != null) {

             newArray.add(newValue);

             return newArray;

        }

        array.add(i, newValue);

    }

    return null;

}

 

Example:

      array [10, 20, 30, 40 50]

      key = 50

      function(array, 0, 50);

Επεξ/σία 29 Οκτωβρίου 2016 από NickSym

[gfg62]

βρήκα την απαντηση μου στο παρακάτω

http://stackoverflow.com/questions/14848731/find-vector-elements-that-sum-up-to-specific-number-in-matlab

ευχαριστώ για την καθοδήγηση!