Άσκηση στην C#

[παπι]

Ξέρεις απο class?

[Kercyn]

Κάτι άλλο που είδα διαβάζοντας διάφορα άλλα threads με παλινδρομικούς αριθμούς είναι ότι δεν είναι απαραίτητο να ψάχνεις να τους βρεις (με brute force ή όπως αλλιώς θέλεις) αλλά να τους φτιάχνεις. Δηλαδή πες ότι θες να βρεις τους παλινδρομικούς αριθμούς απ' το 16061 και μετά. Παρατηρείς ότι μπορείς να απομονώσεις τα 16/61, οπότε ξεκινάς κάνοντας iterate απ' το 0 (0,1,2 κλπ) προσθέτοντας τα 16/61. Αν θες να έχεις 7 αριθμούς, μπορείς να αρχίσεις από το 010, μετά να πας στο 020 κοκ (βάζοντας δηλαδή το 0 στο 16/61 σου). Μετά μπορείς να κάνεις το ίδιο με 1 (1610161, 1611161, 1612161 κοκ). Η λύση αυτή είναι επεκτάσιμη για ό,τι ζευγάρι/πλήθος θες.

 

@παπι

 

 

Τι κάνει η έξυπνη υπογραφή σου; Θέλω κι εγώ!

 

 

[Sheogorath]

Κάτι άλλο που είδα διαβάζοντας διάφορα άλλα threads με παλινδρομικούς αριθμούς είναι ότι δεν είναι απαραίτητο να ψάχνεις να τους βρεις (με brute force ή όπως αλλιώς θέλεις) αλλά να τους φτιάχνεις. Δηλαδή πες ότι θες να βρεις τους παλινδρομικούς αριθμούς απ' το 16061 και μετά. Παρατηρείς ότι μπορείς να απομονώσεις τα 16/61, οπότε ξεκινάς κάνοντας iterate απ' το 0 (0,1,2 κλπ) προσθέτοντας τα 16/61. Αν θες να έχεις 7 αριθμούς, μπορείς να αρχίσεις από το 010, μετά να πας στο 020 κοκ (βάζοντας δηλαδή το 0 στο 16/61 σου). Μετά μπορείς να κάνεις το ίδιο με 1 (1610161, 1611161, 1612161 κοκ). Η λύση αυτή είναι επεκτάσιμη για ό,τι ζευγάρι/πλήθος θες.

 

@παπι

 

 

Τι κάνει η έξυπνη υπογραφή σου; Θέλω κι εγώ!

 

 

Ακριβώς, και για δέκα νούμερα αρκούν δέκα επαναλήψεις με τους δύο πίνακες 3Χ1 και 5Χ1 που πρότεινα πριν, ή όπως αλλιώς προτείνει κάποιος άλλος πιθανόν! Το να κάνεις brute force αν και δουλεύει, είναι υπολογιστικά υπερβολικά βαρύ (χιλιάδες if κτλ)

 

 

 

 

 

 

 

 

Το μικρέ το είπα γιατί αν είσαι μεγάλος και παρόλα αυτά επιλέγεις ελεύθερα να γράψεις το location που έγραψες... υπάρχει πρόβλημα.

 

 

 

Το location τι σχέση έχει, λατρεύω τα γυναικεία πόδια, και όσο δεν είναι της μάνας σου, κοπέλας σου, αδερφής σου, δεν υπάρχει πρόβλημα φαντάζομαι!

Οπως και να έχει, εγώ κακίες δεν κρατώ

[Papakaliati]

Ακριβώς, και για δέκα νούμερα αρκούν δέκα επαναλήψεις με τους δύο πίνακες 3Χ1 και 5Χ1 που πρότεινα πριν, ή όπως αλλιώς προτείνει κάποιος άλλος πιθανόν! Το να κάνεις brute force αν και δουλεύει, είναι υπολογιστικά υπερβολικά βαρύ (χιλιάδες if κτλ)

 Ειναι υπολογιστικα βαρυτερο, αλλα σε καμια περιπτωση δεν μπορεις να πεις οτι μερικες χιλιαδες if ειναι υπερβολικά βαρύ . 

[Sheogorath]

Είναι πολαπλάσια υπολογιστικά πολύπλοκο. Εχω μάθει να τα αποφεύγω όσο ο διάβολος το λιβάνι

 

Δεν είναι απαγορευτικό όμως, φυσικά!

[Papakaliati]

Είναι πολαπλάσια υπολογιστικά πολύπλοκο. Εχω μάθει να τα αποφεύγω όσο ο διάβολος το λιβάνι

 

Δεν είναι απαγορευτικό όμως, φυσικά!

 

 Αμα ο χρονος και η συνολικη προσπαθεια που απαιτειται για να σχεδιασεις και υποποιησεις τον αλγοριθμο (δεν μιλαω προφανως για το συγκεκριμενο που ειναι απλο) ειναι σημαντικος, τοτε ΣΑΦΕΣΤΑΤΑ και θα προτιμησεις την brute force μεθοδο.

   Στην τελικη θα μπορουσες να το τρεχεις σε background thread που δεν θα επιρρεαζε την συνολικη αποδοση σταλα.

   Αμα μιλαμε με ορους προγραμματισμου σε πραγματικες συνθηκες, και οχι σε πανεπιστημιακες του στυλ βρες την λυση με τους λιγοτερους δυνατους κυκλους, τοτε η καλυτερη δυνατη λυση απορρεει απο τα requirements σου και δεν ειναι η πιο γρηγορη παντα. 

[migf1]

Παρεμπιπτόντως, αν το πλήθος των ψηφίων είναι ζυγό, τότε η λογική αλλάζει. Το general case είναι λίγο πιο πολύπλοκο.

[Sheogorath]

Παρεμπιπτόντως, αν το πλήθος των ψηφίων είναι ζυγό, τότε η λογική αλλάζει. Το general case είναι λίγο πιο πολύπλοκο.

Με ένα if και k=length(n)/2 ή k=(length(n)+1)/2

Αλλά και διπλασιάζεις τα μεσσαία ψηφία αν είναι άρτιο πλήθος!

 

Εύκολα είναι, αρκεί να γίνει η αρχή της λογικής! ολα τα άλλα έρχονται αυτόματα

 

 

 

 

TS, τελικά έκανες την άσκηση?

[migf1]

Δεν είπα ότι είναι δύσκολο, λίγο πιο πολύπλοκο είπα. Πάραυτα, όταν πας να το γράψεις σε κώδικα, το general case θέλει αρκετά περισσότερο κώδικα συγκριτικά με το single case (δεν έρχεται δηλαδή και τόσο αυτόματα όσο υπαινίσσεσαι).

[imitheos]

Edit: Το μήνυμα του albNik μου έδωσε να καταλάβω ότι θα ήταν καλύτερα να βάλω το μήνυμα σε spoiler αφού (εκτός ότι είναι κατεβατό) δεν μιλάει για C#. Μια και δεν γνωρίζω c# έγραψα σε c την ιδέα του αλγορίθμου που περιγράφω.

 

Υποθέτω πως το κατεβατό μου ισοδυναμεί με την μία γραμμή σε c# "nextpalindromes" που έγραψε ο defacer

 

 

 

Ειναι υπολογιστικα βαρυτερο, αλλα σε καμια περιπτωση δεν μπορεις να πεις οτι μερικες χιλιαδες if ειναι υπερβολικά βαρύ . 

Όταν μπορείς να αποφύγεις το brute force, ακόμη και να μην είναι υπερβολικά βαρύ γιατί να μην το κάνεις ?

 

Το έχω ξαναγράψει εδώ στο φόρουμ ότι σε ασκήσεις στο πανεπιστήμιο δεν υπήρχε ούτε μία λύση που να μην τρέξει brute force. Για παράδειγμα σου έλεγε η άσκηση βρες τους αριθμούς που ικανοποιούν 3a = 4b και όλες οι λύσεις ήταν

for (i = 0; i < 50; i++) {
  for (j = 0; j < 50; j++) {
    if (3*i = 4*
      printf
  }
}

Κανείς δεν το έκανε με ένα for και να "παράγει" τους αριθμούς με την σχέση που ήδη ξέρεις. Ο παραπάνω κώδικας με τα for δεν είναι φυσικά βαρύς αλλά γιατί να το κάνεις έτσι ?

 

Αμα ο χρονος και η συνολικη προσπαθεια που απαιτειται για να σχεδιασεις και υποποιησεις τον αλγοριθμο (δεν μιλαω προφανως για το συγκεκριμενο που ειναι απλο) ειναι σημαντικος, τοτε ΣΑΦΕΣΤΑΤΑ και θα προτιμησεις την brute force μεθοδο.

Αν πρόκειται για κάποιο μεμονωμένο πρόβλημα με Χ διαστάσεις, τότε ναι. Αν όμως είναι για κάποιο μόνιμο κώδικα που είναι μέρος κάποιου μεγαλύτερου project, τότε σε νοιάζει να σχεδιάσεις τον αλγόριθμο για να έχεις κάτι scalable γιατί μπορεί αύριο η διάσταση του προβλήματος να γίνει 3*Χ ή ακόμη χειρότερα Χ^3 οπότε η brute force θα χρειάζεται ανέφικτα ποσά χρόνου.

 

Παρεμπιπτόντως, αν το πλήθος των ψηφίων είναι ζυγό, τότε η λογική αλλάζει. Το general case είναι λίγο πιο πολύπλοκο.

Δεν είπα ότι είναι δύσκολο, λίγο πιο πολύπλοκο είπα. Πάραυτα, όταν πας να το γράψεις σε κώδικα, το general case θέλει αρκετά περισσότερο κώδικα συγκριτικά με το single case (δεν έρχεται δηλαδή και τόσο αυτόματα όσο υπαινίσσεσαι).

Δεν γίνεται να το κάνουμε χωρίς να ενδιαφέρει τη λογική μας το πλήθος των ψηφίων ? Αν είναι ζυγά θα είναι συμμετρικά οπότε και πάλι δεν θα είναι η ίδια λογική ? Ο παρακάτω κώδικας δεν είναι και ο πιο γρήγορος αλλά εξηγεί αυτό που λέω:

 

#include <stdio.h>
#include <string.h>

void incpalindrome(char *s)
{
	int i;
	int len;
	
	len = strlen(s);
	for (i = (len + 1) / 2; i > 0; i--) {
		/* Auksanoyme to 'messaio' pshfio */
		s[i - 1]++;
		/* Thetoume tin idia timi kai sto summetriko tou to opoio
		 * an milame gia mono arithmo pshfion 8a einai to idio pshfio
		 * opote h ana8esh einai axrhsth alla glytonoyme to if
		 * kai exoume idia logiki gia oles tis periptoseis */
		s[len - i] = s[i - 1];
		/* An to pshfio meta tin auksisi einai mexri kai 9, tote
		 * den xreiazomaste tipota allo opote pairnoyme dromo */
		if (s[i - 1] <= '9')
			return;
		/* An to pshfio perase to 9 shmainei oti ftasame sto telos
		 * opote prepei na ksanamidenisoyme to paron pshfio
		 * kai na auksisoume to/ta pshfia pou briskontai pio ekso.
		 * Auto 8a ginei stin epomeni ektelesi toy for */
		s[len - i] = s[i - 1] = '0';
	}
	/* Gia na ftasoyme edo shmainei oti eimaste sto telos ths seiras
	 * kai prepei na aneboume arithmo pshfion. Gia paradeigma exoyme
	 * ton arithmo 999 o opoios meta to parapano for 8a exei ginei 000.
	 * O protos palindromikos arithmos me 4 pshfia einai 1001 opote
	 * allazoyme to proto pshfio toy 000 se 1 kai prosthetoyme akomi ena
	 * asso sto telos pano sto teliko \0, mh ksexnontas fusika na baloyme
	 * ena teliko \0 oste na exoyme sosto string */
	s[0] = s[len] = '1';
	s[len + 1]='\0';
}

int main(void)
{
	char s[30] = "0";
	int n = 0;

	while (n < 300) {
		incpalindrome(s);
		printf("%s\n",s);
		n++;
	}
	
	return 0;
}

Έξοδος:
1
2
..
9
11
22
.. 
88
99
101
111
..
191
202
..
989
999
1001
1111
..
9999
10001
10101
..
10901
11011
..
20002
20102

 

Επεξ/σία 15 Μαρτίου 2015 από imitheos

[Sheogorath]

 

 

Όταν μπορείς να αποφύγεις το brute force, ακόμη και να μην είναι υπερβολικά βαρύ γιατί να μην το κάνεις ?

Το έχω ξαναγράψει εδώ στο φόρουμ ότι σε ασκήσεις στο πανεπιστήμιο δεν υπήρχε ούτε μία λύση που να μην τρέξει brute force. Για παράδειγμα σου έλεγε η άσκηση βρες τους αριθμούς που ικανοποιούν 3a = 4b και όλες οι λύσεις ήταν

for (i = 0; i < 50; i++) {
  for (j = 0; j < 50; j++) {
    if (3*i = 4*
      printf
  }
}

Κανείς δεν το έκανε με ένα for και να "παράγει" τους αριθμούς με την σχέση που ήδη ξέρεις. Ο παραπάνω κώδικας με τα for δεν είναι φυσικά βαρύς αλλά γιατί να το κάνεις έτσι ?
 
Αν πρόκειται για κάποιο μεμονωμένο πρόβλημα με Χ διαστάσεις, τότε ναι. Αν όμως είναι για κάποιο μόνιμο κώδικα που είναι μέρος κάποιου μεγαλύτερου project, τότε σε νοιάζει να σχεδιάσεις τον αλγόριθμο για να έχεις κάτι scalable γιατί μπορεί αύριο η διάσταση του προβλήματος να γίνει 3*Χ ή ακόμη χειρότερα Χ^3 οπότε η brute force θα χρειάζεται ανέφικτα ποσά χρόνου.
 
Δεν γίνεται να το κάνουμε χωρίς να ενδιαφέρει τη λογική μας το πλήθος των ψηφίων ? Αν είναι ζυγά θα είναι συμμετρικά οπότε και πάλι δεν θα είναι η ίδια λογική ? Ο παρακάτω κώδικας δεν είναι και ο πιο γρήγορος αλλά εξηγεί αυτό που λέω:
 

#include <stdio.h>
#include <string.h>

void incpalindrome(char *s)
{
	int i;
	int len;
	
	len = strlen(s);
	for (i = (len + 1) / 2; i > 0; i--) {
		/* Auksanoyme to 'messaio' pshfio */
		s[i - 1]++;
		/* Thetoume tin idia timi kai sto summetriko tou to opoio
		 * an milame gia mono arithmo pshfion 8a einai to idio pshfio
		 * opote h ana8esh einai axrhsth alla glytonoyme to if
		 * kai exoume idia logiki gia oles tis periptoseis */
		s[len - i] = s[i - 1];
		/* An to pshfio meta tin auksisi einai mexri kai 9, tote
		 * den xreiazomaste tipota allo opote pairnoyme dromo */
		if (s[i - 1] <= '9')
			return;
		/* An to pshfio perase to 9 shmainei oti ftasame sto telos
		 * opote prepei na ksanamidenisoyme to paron pshfio
		 * kai na auksisoume to/ta pshfia pou briskontai pio ekso.
		 * Auto 8a ginei stin epomeni ektelesi toy for */
		s[len - i] = s[i - 1] = '0';
	}
	/* Gia na ftasoyme edo shmainei oti eimaste sto telos ths seiras
	 * kai prepei na aneboume arithmo pshfion. Gia paradeigma exoyme
	 * ton arithmo 999 o opoios meta to parapano for 8a exei ginei 000.
	 * O protos palindromikos arithmos me 4 pshfia einai 1001 opote
	 * allazoyme to proto pshfio toy 000 se 1 kai prosthetoyme akomi ena
	 * asso sto telos pano sto teliko \0, mh ksexnontas fusika na baloyme
	 * ena teliko \0 oste na exoyme sosto string */
	s[0] = s[len] = '1';
	s[len + 1]='\0';
}

int main(void)
{
	char s[30] = "0";
	int n = 0;

	while (n < 300) {
		incpalindrome(s);
		printf("%s\n",s);
		n++;
	}
	
	return 0;
}

Έξοδος:
1
2
..
9
11
22
.. 
88
99
101
111
..
191
202
..
989
999
1001
1111
..
9999
10001
10101
..
10901
11011
..
20002
20102

 

 

 

Απλά σε παραδέχομαι...

 

Λίγο ακόμα και θα πίστευα ότι είμαι τρελός που επέμενα

[albNik]

for (i = 0; i < 50; i++) {
  for (j = 0; j < 50; j++) {
    if (3*i = 4*
      printf
  }
}

Ευτυχώς στην C# αυτο ειναι compiler error

[defacer]

Παρεμπιπτόντως, αν το πλήθος των ψηφίων είναι ζυγό, τότε η λογική αλλάζει. Το general case είναι λίγο πιο πολύπλοκο.

 

Ε σιγά. Μηδέν ή σχεδόν μηδέν διαφορά. Βλέπε παρακάτω.

 

Αμα ο χρονος και η συνολικη προσπαθεια που απαιτειται για να σχεδιασεις και υποποιησεις τον αλγοριθμο (δεν μιλαω προφανως για το συγκεκριμενο που ειναι απλο) ειναι σημαντικος, τοτε ΣΑΦΕΣΤΑΤΑ και θα προτιμησεις την brute force μεθοδο.

 

Αμα μιλαμε με ορους προγραμματισμου σε πραγματικες συνθηκες, και οχι σε πανεπιστημιακες του στυλ βρες την λυση με τους λιγοτερους δυνατους κυκλους, τοτε η καλυτερη δυνατη λυση απορρεει απο τα requirements σου και δεν ειναι η πιο γρηγορη παντα. 

 

(Έτυχε να κάνω quote αυτό αλλά βασικά αναφέρομαι σε όλο το performance debate).

 

Πρώτον, μιλάμε για ασκήσεις βασικού επιπέδου σε κάποια σχολή. Είναι δεδομένο (διαφωνείτε?) ότι η πλειοψηφία των φοιτητών το παλεύει για να βγάλει μια οποιαδήποτε λύση και πως αν αρχίσουμε να μιλάμε για αλγοριθμική πολυπλοκότητα κλπ κανένας τους δεν πρόκειται να καταλάβει τι λέμε. Οι δακτυλοδεικτούμενοι που θα καταλάβουν εξ ορισμού δεν έχουν ανάγκη να τους υπενθυμίσει κανείς το ζήτημα. Αυτό βασικά που είπε ο ημίθεος και που το έχω δει και γω: τους βάζεις να σου λύσουν ένα 2x2 σύστημα και το κάνουν με for επειδή "when all you have is a hammer".

 

Δεύτερον είναι αστείο να το πηγαίνουμε τόσο παραπέρα και να μιλάμε για "κύκλους". Αφ' ενός γιατί αμφιβάλλω αν υπάρχει έστω και ένας σ' αυτό το forum που να είναι στο επίπεδο που τον παίρνει να μιλάει για κύκλους, και αφ' ετέρου γιατί αν φτάσουμε στο σημείο να τα κάνουμε όλα για τους κύκλους τότε θα πρέπει να αρχίσουμε να γράφουμε SIMD assembly στοχευμένη σε συγκεκριμένη CPU και να σκεφτόμαστε πώς μπαίνουν τα δεδομένα μας σε cache lines -- και είμαι σίγουρος πολύ περισσότερα ακόμα πράγματα για τα οποία οι γνώσεις μου δε φτάνουν για να μιλήσω. Και κάπου χάνεται το νόημα όταν έρθει κάποιος να σου πει "είναι αργό το PC τι να κάνω" και εσύ αρχίσεις να του μιλάς για PCI-E SSD σε RAID.

 

Τρίτον η ίδια η άσκηση δεν έχει σα ζητούμενο να δώσει κανείς την πιο performant λύση. Για παράδειγμα, εγώ θα ήμουν το ίδιο χαρούμενος να δω αυτή την προσέγγιση (χαμός το perf)

 

 

 

var start = 12321;
var nextPalindromes = Enumerable.Range(start, int.MaxValue - start + 1)
    .Select(i => i.ToString())
    .Where(s => s.Reverse().SequenceEqual(s))
    .Take(10)
    .ToArray();

 

 

 

όσο και αυτήν εδώ (βρίσκει αντί να τεστάρει και δουλεύει πάντα σε επίπεδο integer οπότε δε μπορεί να είναι και τόσο κακή):

 

public IEnumerable<int> PalindromesStartingFrom(int start)
{
    var digits = (int)Math.Floor(Math.Log10(start) + 1);
    var prefix = (int)(start / Math.Pow(10, digits / 2));

    while (true)
    {
        var palindrome = prefix;
        var scratch = (digits & 1) == 1 ? prefix : prefix / 10;
        var allNines = palindrome % 10 == 9;
        while (scratch > 0)
        {
            var nextDigit = scratch % 10;
            allNines = allNines && nextDigit == 9;
            palindrome = palindrome * 10 + nextDigit;
            scratch /= 10;
        }
        
        yield return palindrome;

        ++prefix;
        if (allNines)
        {
            ++digits;
        }
    }
}

και μετά βέβαια ίσως το καλύτερο μέρος της λύσης:

var sln = PalindromesStartingFrom(12321).Take(10).ToArray();

Σημείωση σχετική με migf1: εδώ η μόνη πρόβλεψη που χρειάστηκε για μονά/ζυγά ψηφία ήταν πως αντί για

var scratch = (digits & 1) == 0 ? prefix : prefix / 10;
var allNines = palindrome % 10 == 9;

αν μπορούσαμε να θεωρήσουμε π.χ. πάντα μονά θα γράφαμε

var scratch = prefix;
var allNines = true;

...που δεν το λες και τεράστια διαφορά.

 

 

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

 

Edit: Παρά το ότι νόμιζα πως πρόσεχα, η δεύτερη λύση είναι buggy. Θα κοιτάξω να τη διορθώσω αργότερα, αλλά αν χρειαζόταν έστω και ένα επιχείρημα ότι τις περισσότερες φορές less code >> faster code, ορίστε live.

 

Και δεν είναι βέβαια και φανταστική ανακάλυψη αυτή η ιδέα:

 

 

Edit 2: Διόρθωσα το λάθος παραπάνω -- αντί για (digits & 1) == 1 που είναι το σωστό, έγραφα αρχικά == 0. Ή εναλλακτικά μπορούσαν να αλλάξουν θέση ο τρίτος τελεστέος με το δεύτερο. Whatever. Less code >> fast code.

Επεξ/σία 15 Μαρτίου 2015 από defacer

[Sheogorath]

Εντάξει, πάντα μπορούμε να γράφουμε σε Assembly ή Fortran (εγώ μαθαίνω την δευτερη ακριβώς λόγω του perf) αλλά το θέμα βγαίνει way off. Φυσικά για επίπεδο 3ης λυκείου-Τει να μην έχει σημασία το performance. Αλλά...

 

Φαντάσου να κάνεις προβλεψη καιρού με δεδομένα, και να ανακοινώνεις τον αυριανό καιρο, σε 4 μέρες. Ε δεν θα πας μακριά.

 

Για αρχή της εκμάνθηνσης όμως, δεν πρέπει να κοιτάμε τον τρόπο, αλλά το αποτέλεσμα, όπως σωστά έθεσες.Γιατί όμως να μην μαθαίνουμε σωστά απο την αρχη?

 

 

 

Ασχετο, αλλά το έλυσες τελικά κοπελιά(φαντάζομαι)?

[defacer]

Για αρχή της εκμάνθηνσης όμως, δεν πρέπει να κοιτάμε τον τρόπο, αλλά το αποτέλεσμα, όπως σωστά έθεσες.Γιατί όμως να μην μαθαίνουμε σωστά απο την αρχη?

 

Γιατί να μη μαθαίνουμε μιγαδικούς αριθμούς από το δημοτικό; Πρόσθεση, πολλαπλασιασμός, προσεταιριστική ιδιότητα. Απλά πράγματα.

 

Τα πράγματα που πρέπει να μαθαίνονται σωστά από την αρχή είναι αυτά που αν δεν τα μάθεις σωστά μετά θα πρέπει να τα ξεμάθεις (πώς κρατάμε την κιθάρα), όχι αυτά που αργότερα θα μάθεις καλύτερα ή περισσότερο και θα χρησιμοποιείς βέβαια αυτά τα νέα "ισχυρότερα" εργαλεία.