Μικρή βοήθεια σε C++

[captaingr]

Καλημέρα σε όλα τα παιδιά του forum.

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

Δηλαδή αν η συνάρτηση έχει 2 παραμέτρους π.χ.

method(10, 5) { . . . }

πρέπει να φτιάχνει τους συνδυασμούς:

11116

11125

11134

11224

11233

12223

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

Οπότε αν υπάρχει μια τέτοια μέθοδος θα ήταν σαν λύση στο πρόβλημα μου.

Ευχαριστώ εκ των προτέρων όσους ασχοληθούν έστω και λίγο.

[parsifal]

Καλημέρα.

 

Έστω number ο αριθμός που πρέπει να διασπαστεί, digits ο αριθμός των ψηφίων του και pieces ο αριθμός των ψηφίων στα οποία τον διασπάς. Πρέπει να ισχύει απαραίτητα:

>number - (pieces - 1) < 10

...ή όχι; Δηλαδή, π.χ. για method(11, 2), ακολουθία 1, 10 είναι αποδεκτή ή δεν έχει νόημα στη λύση που θέλεις... ;

[captaingr]

Ευχαριστώ που ασχολήθηκες.

Για method(11, 2); η ακολουθία 1,10 είναι αποδεκτή αλλά μάλλον θα χρειαστώ από method(10, 5); και πάνω π.χ.

method(10, 6);

method(11, 5);

method(11, 6); κτλ.

[parsifal]

Αν η λύση παριστάνεται σε έναν πίνακα ακεραίων π.χ. Digit[pieces], τον αρχικοποιείς στην οριακή λύση:

>
Digit[0] == 1
Digit[1] == 1
...
Digit[pieces - 2] == 1
Digit[pieces - 1] == last_max

όπου last_max == number - pieces - 1. Στη συνέχεια σε έναν επαναληπτικό βρόχο, κάθε φορά αφαιρείς 1 από τον Digit[pieces - 1] και το προσθέτεις (με εμφωλευμένο βρόχο, γιατί υπάρχουν αρκετές πιθανές θέσεις) σε ορισμένα (εδώ θα παίξουν ρόλο οι συνθήκες ελέγχου που θα χρησιμοποιήσεις) από τα προηγούμενα ψηφία μέχρι και το 2ο...

[parsifal]

Χμμμ, φαίνεται πως έκανα μεγάλο λάθος. Η παραπάνω λύση δε δίνει όλους τους δυνατούς συνδυασμούς. Το παλεύω με άλλον τρόπο, προσπαθώντας να αποφύγω αναδρομική λύση που κοστίζει...

[bilco]

Χωρίς να υπολογίζω το πρώτο ψηφίο που είναι πάντα 1, κάτι τέτοιο πρέπει να κάνει

>
inline void exch(int &a, int & {
int tmp = a; a = b; b = tmp;
}

void reverse(int *arr, int size)
{
if (size < 2) return;
for (int i = 0; i < size / 2; i++)
	exch(arr[i], arr[size - 1 - i]);
}

bool next_number(int *num, int digits)
{
int shift_from = 0;

// Ψάχνω το μικρότερης τάξης ψηφίο το οποίο
// μπορώ να μειώσω κατά μια μονάδα
while (num[shift_from] == 0) shift_from++;

// Ψάχνω ψηφίο μεγαλύτερης τάξης από το shift_from
// το οποίο μπορώ να αυξήσω κατά μια μονάδα
for (int i = shift_from + 1; i < digits; i++)
	if (num[i] < 9) {
		// Βρέθηκε -> κάνω το shift
		num[shift_from]--;
		num[i]++;
		// Τα ψηφία δεξιά του i (αριστερά στον πίνακα) 
		// σχηματίζουν τον μεγαλύτερο δυνατό αριθμό από
		// αυτούς που έχουν ίδιο πλήθος και ίδιο άθροισμα
		// ψηφίων με αυτόν (μπορούμε εύκολα να το δείξουμε με
		// επαγωγή). Εγώ θέλω τον μικρότερο δυνατό, άρα
		// τα αντιστρέφω.
		reverse(num, i);
		return true;
	}
return false;
}

void main()
{
int n[] = {5,3,2,1};
int sz = sizeof(n)/sizeof(int);

while (next_number(n, sz)) {
	for (int i = sz - 1; i >= 0; i--)
		printf("%d", n[i]);
	printf("\n");
}
}

[captaingr]

Ευχαριστώ πολύ parsifal και bilco για την προσπάθεια που κάνετε.

bilco ωραίος ο κώδικας σου. Θα προσπαθήσω να δω που μπορώ να φτάσω.

[parsifal]

Yep, κοιτώντας και τον κώδικα του bilco, κατάλαβα που ήταν το λάθος στο σκεπτικό μου. Δε μπορείς να αφαιρείς μόνο από το Digit[pieces - 1] ψηφίο, αλλά και από όσα προηγούνται και έχουν ήδη αυξηθεί με την προηγούμενη διαδικασία.

 

Προσπάθησα με greedy μέθοδο, αλλά με μειωμένες πράξεις χρησιμοποιώντας την επόμενη ιδιότητα. Για το i-οστό στοιχείο της ακολουθίας (i = 2, 3, ..., pieces - 1), η ελάχιστη τιμή που μπορεί να πάρει είναι 1, ενώ η οριακή μέγιστη τιμή που έχει νόημα είναι:

current_digit_max = (last_max + pieces - current_digit_position - 1) / (current_distance_from_last + 1);

 

Πάντως, αν η λύση του bilco δουλεύει σωστά, μάλλον θα έχει καλύτερη απόδοση ως αλγόριθμος...

[captaingr]

Τελικά τα κατάφερα με τη βοήθεια ενός παιδιού από άλλο forum (ευχαριστώ effect).

Ο κώδικας σε C++ (για να υπάρχει):

>
void method(int sum, int theseis, int min, int* pin, int diastima) {
if(theseis==2) {
pin[theseis-1]=min;
pin[theseis-2]=sum-min;
for(int i=diastima-1; i>=0; i--) {
cout << pin[i] << " ";
}
cout << endl;
}
else {
pin[theseis-1]=min;
for(int i=min; i<=(sum-min)/(theseis-1); i++) {
method(sum-min, theseis-1, i, pin, diastima);
}
}
}

void sindiasmoi(int sum, int theseis) {
int* pin=new int[theseis];
int diastima=theseis;
method(sum, theseis, 1, pin, diastima);
}

int main() {
int diastima=5;
int units=10;

sindiasmoi(units, diastima);

cout << endl;

system("PAUSE");
return 0;
}

 

Ευχαριστώ όσους ασχολήθηκαν.

[bilco]

Μάλλον δεν κατάλαβα τι ακριβώς ζήταγες captaingr. Να διευκρινίσω για να μην μπερδευτεί κάποιος τρίτος, ότι ο κώδικας που έδωσα βρίσκει όλους τους αριθμούς που είναι μεγαλύτεροι απ'τον αρχικό και έχουν ίδιο πλήθος και άθροισμα ψηφίων με αυτόν.

[parsifal]

Είπα κι εγώ! Τόσην ώρα έφαγα να τον κοιτάω. Tracing έκανα. Δε μπορούσα να καταλάβω πώς δούλευε τελικά!

[bilco]

Είπα κι εγώ! Τόσην ώρα έφαγα να τον κοιτάω. Tracing έκανα. Δε μπορούσα να καταλάβω πώς δούλευε τελικά!

 

Ε, μα τον 11116 τον βλέπω σαν έναν αριθμό, όχι σαν διαδοχικούς. Τα κόμματα (1,1,1,1,6) θα έσωζαν την κατάσταση

[bilco]

Για την ιστορία και ένας μη αναδρομικός τρόπος που λύνει το σωστό πρόβλημα αυτή τη φορά

>
void arrange(int *arr, int target) {
int sum = 0;
for (int i = target - 1; i > 0; i--) {
	sum += arr[i] - arr[target]; arr[i] = arr[target];
}
arr[0] += sum;
}

bool next_sequence(int *seq, int size) {
int shift_to = 0;
while (seq[0] < seq[++shift_to] + 2 && shift_to < size-1);
if (shift_to == size-1) return false;
seq[shift_to]++; seq[0]--; arrange(seq, shift_to);
return true;
}

void display_seq(int *seq, int size) {
for (int i = size-1; i >= 0; i--) printf("%d ", seq[i]);
printf("\n");
}

void all_sequences(int sum, int count) {
int *seq = new int[count]; sum -= count - 1;
for (int i = 1; i < count; i++) seq[i] = 1;
seq[0] = sum; display_seq(seq, count);
while (next_sequence(seq, count)) display_seq(seq, count);
delete [] seq;
}

void main() { 
all_sequences(30, 10); 
}

[captaingr]

Όντως ήταν λάθος η μορφή 11116. Έπρεπε να το γράψω όπως το λες. Αλλά ξέρεις πως είναι συνήθως: ασχολείσαι με κάτι και νομίζεις πως και οι άλλοι θα το καταλάβουν όπως το καταλαβαίνεις και εσύ. Συγνώμη που σε έκανα να ψάχνεις για κάτι που δε χρειαζότανε και ευχαριστώ πολύ για την προσπάθεια.

Και κάτι τελευταίο: Μήπως γνωρίζει κανείς πως αποθηκεύουμε σε αρχείο χρωματιστό κείμενο. Χρησιμοποιώ wxDev-cpp και έχω ένα wxRichTextCtrl όπου εμφανίζονται τα αποτελέσματα του προγράμματος με διάφορα χρώματα.

Προσπαθώ να περάσω τα περιεχόμενα του σε ένα αρχείο αλλά μου τα περνάει όλα με μαύρο χρώμα.

[bilco]

Συγνώμη που σε έκανα να ψάχνεις για κάτι που δε χρειαζότανε και ευχαριστώ πολύ για την προσπάθεια.

Να σαι καλά

Μήπως γνωρίζει κανείς πως αποθηκεύουμε σε αρχείο χρωματιστό κείμενο. Χρησιμοποιώ wxDev-cpp και έχω ένα wxRichTextCtrl όπου εμφανίζονται τα αποτελέσματα του προγράμματος με διάφορα χρώματα.

Προσπαθώ να περάσω τα περιεχόμενα του σε ένα αρχείο αλλά μου τα περνάει όλα με μαύρο χρώμα.

 

Δεν το ξέρω το συγκεκριμένο control αλλά από ένα γρήγορο ψάξιμο είδα ότι δεν υποστηρίζει rtf, αλλά χρησιμοποιεί δικό του φορμάτ. Άρα για να διαβαστεί σωστά το αρχείο πρέπει να το ανοίξεις με πρόγραμμα που υποστηρίζει αυτό το format.

Αν τώρα εννοείς ότι δεν το διαβάζει σωστά όταν ξαναανοίγεις το αρχείο με το ίδιο control, μήπως δεν το έχεις σώσει όπως πρέπει; (από GetBuffer().SaveFile)