Strings and set of chars - βοήθεια σε άσκηση!

Συζητήσεις σχετικές με την Delphi και την πρόγονη της Pascal

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
Άβαταρ μέλους
giannis19
Δημοσιεύσεις: 38
Εγγραφή: 11 Ιουν 2006 14:12
Τοποθεσία: London, UK

Strings and set of chars - βοήθεια σε άσκηση!

Δημοσίευση από giannis19 » 09 Απρ 2009 22:13

Μελετώ για μια ολυμπιάδα προγραμματισμού και έχω μια άσκηση που με προβληματίζει..

την απάντηση την έχω αλλά δεν έχω αντιληφθεί τη λογική..

θα εκτιμούσα ιδιέταιρα αν θα μπορούσατε να με βοηθήσετε..
Ζητείται να γραφεί πρόγραμμα το οποίο να δέχεται μια συμβολοσειρά από το
πληκτρολόγιο και να τυπώνει όλες τις δυνατές αντιμεταθέσεις των συμβόλων της. Η
συμβολοσειρά εισόδου θα αποτελείται από τουλάχιστον 2 και το πολύ 7 χαρακτηρές. Ο
ίδιος χαρακτήρας μπορεί να εμφανίζεται το πολύ δύο φορές στη συμβολοσειρά. Κάθε
αντιμετάθεση θα πρέπει να τυπωθεί μόνο μια φορά στην οθόνη.
Write a program that accepts a string of alphabetic characters from the keyboard, and
then prints to the screen a list of all the possible permutations of those characters. The
input string can have a minimum of 2 characters, and a maximum of 7 characters. A
character may appear at most twice in the string. Each permutation should only appear
once in the output.
Παραδείγματα - Examples
Είσοδος/Input: GST
Έξοδος/Output: GST, GTS, TGS, TSG, STG, SGT
Είσοδος/Input: AAT
Είσοδος/Output: AAT, TAA, ATA

Κώδικας: Επιλογή όλων

program Problem4;
type
CharSet = set of Char;
var
InputString : string[7];
procedure perm(prefix, rest : string);
var
i : Integer;
S : string;
visited : CharSet;
begin
visited := []; {empty set}
if Length(rest) = 1 then
WriteLn(Concat(prefix,rest))
else
begin
for i:=1 to Length(rest) do
begin
if not (rest[i] in visited) then
begin
S := rest;
Delete(S,i,1);{remove character at index i}
visited := visited + [rest[i]];
perm(Concat(prefix,rest[i]),S);
end;
end;
end;
end;
begin
Write('Enter string: ');
ReadLn(InputString);
perm('',InputString);
end.

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

Strings and set of chars - βοήθεια σε άσκηση!

Δημοσίευση από dva_dev » 10 Απρ 2009 14:37

Αυτό που ζητάει είναι να δώσεις μια λέξη μήκους Χ.

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

Και αρχίζουν οι περιορισμοί:
Αφού στην λέξη που δίνεις μπορεί κάποιοι χαρακτήρες να υπάρχουν 2 φορές (π.χ. η λέξη ΑΝΝΑ έχει μέν 4 χαρακτήρες αλλά μόνο 2 διαφαρετικούς) μερικοί από τους συνδιασμούς των λέξεων θα φτιαχτούν πολλές φορές (πχ. αντιθεταθέτοντας τα δύο μεσαία Ν, ναι μεν έχεις φτιάξει νέα λέξη χρησιμοποιώντας τα γράμματα σε διαφορετική θέση αλλά είναι η ίδια με την αρχική σου, και δεν τη θέλεις αυτή).

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

Ετσι αν έχεις τη λέξη ΑΝΝΑ (θα αριθμήσω τα γράμματα) έχεις τους χαρακτήρες Α=1, Ν=2, Ν=3, Α=4, και οι λέξεις που μπορείς να φτιάξεις είναι:
1) 1234 -> ΑΝΝΑ (1)
2) 1243 -> ΑΝΑΝ (2)
3) 1342 -> ΑΝΑΝ (έχει δημιουργηθεί ήδη)
4) 1324 -> ΑΝΝΑ (έχει δημιουργηθεί ήδη)
5) 1423 -> ΑΑΝΝ (3)
6) 1432 -> ΑΑΝΝ (έχει δημιουργηθεί ήδη)

Κ) ....

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

Ελπίζω να είναι κατανοητά.

[edit]
Επίσης από το πρόγραμμα λείπου κάποιοι έλεγχοι, αν το string που δίνει ο χρήστης είναι όντως από 2-7 χαρακτήρες και αν ο κάθε χαρακτήρας εμφανίζεται το πολύ 2 φορές.
[/edit]

Άβαταρ μέλους
giannis19
Δημοσιεύσεις: 38
Εγγραφή: 11 Ιουν 2006 14:12
Τοποθεσία: London, UK

Strings and set of chars - βοήθεια σε άσκηση!

Δημοσίευση από giannis19 » 18 Απρ 2009 21:39

ευχαριστώ πάρα πολύ!

ο πρώτος γύρος πέρασε επιτυχώς


και τώρα ήρθαν τα δύσκολα:p

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

Strings and set of chars - βοήθεια σε άσκηση!

Δημοσίευση από dva_dev » 21 Απρ 2009 12:33

Καλή επιτυχία.
Ισως σου φανεί χρήσιμο να δεις και αυτές http://ioinformatics.org/contest/prev.shtml

gianpan
Δημοσιεύσεις: 275
Εγγραφή: 03 Ιουν 2006 16:53
Επικοινωνία:

Strings and set of chars - βοήθεια σε άσκηση!

Δημοσίευση από gianpan » 24 Απρ 2009 13:03

πάντως μου κάνει εντύπωση η χρήση strings.

Νομίζω ότι μπορείς με μία διπλή loop και swaps να πετύχεις αυτό που θες σε πίνακες με char.

Βέβαια δεν έχω λάβει υπόψιν μου διπλές συμβολοσειρές κτλ. βέβαια κάθε συμβολοσείρα μπορείς να τι σώζεις σε ένα πίνακα και να την συγκρίνεις με κάθε μία που σου προκύπτει.. (το πιο απλό και ίσως το πιο resource-intensive). Φαντάζομαι οτι θα υπάρχουν περιορισμοί σε μέγεθη, μνήμη,CPU time κτλ. οπότε δεν είναι και οτι πιο αποδοτικό.

Απάντηση

Επιστροφή στο “Delphi, Pascal”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες