Vold
Πολύ δραστήριο μέλος
Ο Vold αυτή τη στιγμή δεν είναι συνδεδεμένος. Είναι 28 ετών, Φοιτητής και μας γράφει απο Ηράκλειο (Κρήτη). Έχει γράψει 1,629 μηνύματα.
15-05-16
17:18
Έτοιμο και το πρόγραμμα, μου πήρε λίγο παραπάνω απ' όσο περίμενα αλλά χαλάλι. Φαίνεται πως η θεωρία απέχει αρκετά από την πράξη, ορισμένες φορές.
Ακολουθώ τον αλγόριθμο που παρέθεσα προηγουμένως εκτός από την προσθήκη των μονό-συνόλων όπου και τα προσθέτω ξεχωριστά για λόγους διευκόλυνσης.
Η αναδρομική συνάρτηση είναι κάπως πολύπλοκη αλλά αν κατάλαβες το σκεπτικό μου, τότε μπορείς να το καταλάβεις και στο πρόγραμμα πολύ εύκολα.
Ακολουθώ τον αλγόριθμο που παρέθεσα προηγουμένως εκτός από την προσθήκη των μονό-συνόλων όπου και τα προσθέτω ξεχωριστά για λόγους διευκόλυνσης.
Η αναδρομική συνάρτηση είναι κάπως πολύπλοκη αλλά αν κατάλαβες το σκεπτικό μου, τότε μπορείς να το καταλάβεις και στο πρόγραμμα πολύ εύκολα.
Code:
public class Subsets {
static String[] Subsets;
static String string;
static int[] Elems;
static int counter = 1;
static int inputSize;
static int i, j;
public static void main(String[] args) {
string = args[0];
inputSize = args[0].length();
Subsets = new String[(int)Math.pow(2, inputSize)];
// Empty Subsets
for(i = 0; i < Subsets.length; i++) {
Subsets[i] = "";
}
// Initialize the one-element Subsets
for(i = 0; i < string.length(); i++) {
Subsets[counter] += string.charAt(i);
counter++;
}
findSubsets(2);
// Print Subsets
for(i = 0; i < Subsets.length; i++) {
System.out.print('{');
for(j = 0; j < Subsets[i].length(); j++) {
System.out.print(Subsets[i].charAt(j) + (j<Subsets[i].length() - 1?",":""));
}
System.out.println('}');
}
}
public static void findSubsets(int sz) {
if(sz > inputSize) return;
Elems = new int[sz];
for(i = 0; i < sz; i++) {
Elems[i] = i;
}
for(j = sz - 1; j > 0; j--) {
while(Elems[sz - 1] < inputSize) {
for(int k = 0; k < sz; k++) {
Subsets[counter] += string.charAt(Elems[k]);
}
counter++;
Elems[sz - 1]++;
}
if(Elems[j - 1] != inputSize - sz + j - 1) {
Elems[j - 1]++;
for(i = j; i < sz; i++) {
Elems[i] = Elems[i - 1] + 1;
}
j = sz;
}
}
findSubsets(++sz);
}
}
Σημείωση: Το μήνυμα αυτό γράφτηκε 7 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.
Vold
Πολύ δραστήριο μέλος
Ο Vold αυτή τη στιγμή δεν είναι συνδεδεμένος. Είναι 28 ετών, Φοιτητής και μας γράφει απο Ηράκλειο (Κρήτη). Έχει γράψει 1,629 μηνύματα.
15-05-16
08:55
Ωραίο topic Ξεχασμένε, ελπίζω να υπάρξει και η αντίστοιχη ανταπόκριση
Από πλευράς μου θα προσπαθήσω να παρουσιάσω αλγορίθμους για την επίλυση των ασκήσεων ή εναλλακτικά αν αυτό δεν είναι εφικτό(λόγω αυξημένης δυσκολίας - πολυπλοκότητας), έχω χρόνο και διάθεση και μπορώ φυσικά, απευθείας προγράμματα(σε JAVA). (Ελπίζω αυτό να είναι αποδεκτό εκ μέρους σου )
Για την συγκεκριμένη άσκηση θα παρουσιάσω έναν απλοϊκό αλγόριθμό όπου εύκολα μετατρέπεται σε πρόγραμμα.
Παράδειγμα: Για το σύνολο abcd, 4ων χαρακτήρων, έχουμε την εξής διαδικασία-έξοδο.
Από πλευράς μου θα προσπαθήσω να παρουσιάσω αλγορίθμους για την επίλυση των ασκήσεων ή εναλλακτικά αν αυτό δεν είναι εφικτό(λόγω αυξημένης δυσκολίας - πολυπλοκότητας), έχω χρόνο και διάθεση και μπορώ φυσικά, απευθείας προγράμματα(σε JAVA). (Ελπίζω αυτό να είναι αποδεκτό εκ μέρους σου )
Για την συγκεκριμένη άσκηση θα παρουσιάσω έναν απλοϊκό αλγόριθμό όπου εύκολα μετατρέπεται σε πρόγραμμα.
- Η είσοδος του αλγορίθμου είναι ένα string με n χαρακτήρες.
- Η αναδρομική συνάρτηση θα κληθεί n φορές, με είσοδο από το 1 έως το n.
- Η είσοδος αντικατοπτρίζει το πλήθος των χαρακτήρων/στοιχείων του εκάστοτε συνόλου.
- Η αφετηρία των νέων συνόλων είναι αυτή που ξεκινάει με το πρώτο στοιχείο του αρχικού συνόλου και κάθε επόμενο είναι το επόμενο του προηγούμενου. (π.χ για είσοδο cdefg, με είσοδο της αναδρ. συνάρτησης τον αριθμό 3, τα νέα σύνολα ξεκινάνε από το cde.)
- Κατόπιν, κάθε χαρακτήρας/στοιχείο του συνόλου αυτού αλλάζει, ξεκινώντας από τον τελευταίο, έως ότου πάρει τον τελευταίο του επιτρεπτό χαρακτήρα/στοιχείο. cdefg: cde -> cdf ->cdg.
- Όταν ο χαρακτήρας που αλλάζει δεν είναι ο τελευταίος τότε οι επόμενοι του αλλάζουν κι αυτοί και ξεκινούν από τον επόμενο χαρακτήρα εκείνου που άλλαξε τελευταίος. cde -> ... -> cdg-> cef.
- Όλοι οι χαρακτήρες αλλάζουν τις ίδιες φορές κι εξαρτάται από την είσοδο. Συγκεκριμένα αλλάζουν κατά n - input.
- Προσθέτουμε το κενό σύνολο ή εναλλακτικά καλούμε την αναδρομική συνάρτηση μια παραπάνω φορές προσθέτοντας κατάλληλη συνθήκη ελέγχου.
Tip: To πλήθος των δυνατών υποσυνόλων ενός συνόλου είναι ίσο με το δυναμοσύνολο του, δηλαδή 2 εις το πλήθος των στοιχείων της εισόδου - του αρχικού συνόλου.
Παράδειγμα: Για το σύνολο abcd, 4ων χαρακτήρων, έχουμε την εξής διαδικασία-έξοδο.
Κλήση αναδρομικής συνάρτησης με είσοδο 1:
a
b
c
d
(4 αλλαγές σε όλα - εδώ είναι μόνο ένα στοιχείο)
Κλήση αναδρομικής συνάρτησης με είσοδο 2:
ab
ac
ad
bc
bd
cd
(3 αλλαγές σε όλα)
Κλήση αναδρομικής συνάρτησης με είσοδο 3:
abc
abd
acd
bcd
(2 αλλαγές σε όλα)
Κλήση αναδρομικής συνάρτησης με είσοδο 4:
abcd
(1 αλλαγή σε όλα)
Προσθήκη κενού συνόλου - Συνολικά:
{ }
a
b
c
d
ab
ac
ad
bc
bd
cd
abc
abd
acd
bcd
abcd
a
b
c
d
(4 αλλαγές σε όλα - εδώ είναι μόνο ένα στοιχείο)
Κλήση αναδρομικής συνάρτησης με είσοδο 2:
ab
ac
ad
bc
bd
cd
(3 αλλαγές σε όλα)
Κλήση αναδρομικής συνάρτησης με είσοδο 3:
abc
abd
acd
bcd
(2 αλλαγές σε όλα)
Κλήση αναδρομικής συνάρτησης με είσοδο 4:
abcd
(1 αλλαγή σε όλα)
Προσθήκη κενού συνόλου - Συνολικά:
{ }
a
b
c
d
ab
ac
ad
bc
bd
cd
abc
abd
acd
bcd
abcd
Σημείωση: Το μήνυμα αυτό γράφτηκε 7 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.