Πρόβλημα με παλινδρομικούς αριθμούς

[TSMGeorge]

@defacer

 

Επειδή δεν έχω χρόνο, διάβασα μόνο τις 2 πρώτες παραγράφους.

 

- Δεν γίνεται να αποφύγεις το for { ... }, πως δηλαδή σε ένα διάστημα [a;b] θα βρεις πόσοι παλινδρομικοί αριθμοί είναι;

- Αυτό πιστεύω και εγώ... δεν θα περάσει ποτέ το τεστ άμα παίζω συνέχεια με strings.

- Δεν ξέρουμε τελικά αν αυτό (ο χρόνος) είναι το πρόβλημα, πολύ πιθανό να είναι η 1η αιτία που δεν περνάει το Τεστ αλλά αυτό δεν σημαίνει ότι μετά δεν μπορεί να προκύψει κάποιο "Wrong Answer".

 

θα δω αυτά που μου έγραψες αύριο...

 

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

Επεξ/σία 15 Οκτωβρίου 2014 από TSMGeorge

[imitheos]

Συνήθως αυτό που γίνεται σε μια άσκηση είναι να πάρουν όλοι σβάρνα τα for. Όταν βλέπεις να υπάρχει όριο χρόνου είναι για να σε βάλει να σκεφτείς.

 

Θυμάμαι μια άσκηση που είχε μπει στη σχολή και ήταν να βρεθούν αριθμοί κάτι με τρίγωνο νομίζω είχε σχέση όπου α + β = γ

 

for (a = 1; a < τάδε; a++)
  for (b = 1; b < τάδε; b++)
    for (c = 1; c < τάδε; c++)
       Κάνε κάτι που ζητούσε η άσκηση

Το παραπάνω υπήρχε στο 95% των λύσεων. Κανείς δεν σκέφτηκε ούτε καν να διώξει το τρίτο for υπολογίζοντας το c με βάση τη σχέση που έχουμε.

 

Άλλη άσκηση έλεγε να βρεθεί ο αριθμός των διαιρετών ενός αριθμού N. Όλοι πήραν πάλι σβάρνα ένα for από το 1 μέχρι τον αριθμό Ν αντί να διαιρούν τον Ν με τον κάθε διαιρέτη που βρίσκουν ώστε να οι επαναλήψεις της for να μειωθούν δραματικά.

 

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

[albNik]

Επρεπε να βαλουν οριο 64 bit (ή και χιλιαδες bit) για να αποκλειστεί brute force λυση.

[defacer]

Θυμάμαι μια άσκηση που είχε μπει στη σχολή και ήταν να βρεθούν αριθμοί κάτι με τρίγωνο νομίζω είχε σχέση όπου α + β = γ

 

for (a = 1; a < τάδε; a++)
  for (b = 1; b < τάδε; b++)
    for (c = 1; c < τάδε; c++)
       Κάνε κάτι που ζητούσε η άσκηση

Το παραπάνω υπήρχε στο 95% των λύσεων. Κανείς δεν σκέφτηκε ούτε καν να διώξει το τρίτο for υπολογίζοντας το c με βάση τη σχέση που έχουμε.

 

Τώρα με γύρισες πολλά χρόνια πίσω.

 

Εκφώνηση άσκησης σε μάθημα προγραμματισμού που έλεγε με δεδομένο ακέραιο Χ <= 999999 (ζητείται σαν είσοδος από το χρήστη) να βρεθούν 2 ακέραιοι Α, Β τέτοιοι ώστε 5Α = 3Β και Α + Β = Χ. Αν δεν υπάρχουν να εμφανιστεί ανάλογο μήνυμα.

 

Φυσικά πρόκειται για γελοίο 2x2 γραμμικό σύστημα το οποίο μαθαίνουμε πώς λύνεται στο γυμνάσιο άντε λύκειο (δε θυμάμαι πάει καιρός  )... το οποίο οι πρωτοετείς σε πολυτεχνείο(!!!!!) έλυναν με for. Δε θυμάμαι ούτε έναν να το έλυσε αλγεβρικά.

 

Κλασική περίπτωση βλάβης που ενώ δεν έχεις μάθει στον άλλο να σκέφτεται του έχεις μάθει πώς να γράφει for. If all you have is a hammer...

[Lanike71]

 

 

 

Άλλη άσκηση έλεγε να βρεθεί ο αριθμός των διαιρετών ενός αριθμού N. Όλοι πήραν πάλι σβάρνα ένα for από το 1 μέχρι τον αριθμό Ν αντί να διαιρούν τον Ν με τον κάθε διαιρέτη που βρίσκουν ώστε να οι επαναλήψεις της for να μειωθούν δραματικά.

 

 

Για έλεγχο αν κάποιος αριθμός είναι πρώτος μάλλον θα λες.

Διαιρέτες από 1 ως Ν, αν και είναι αρκετό από 1 ως Ν/2.

[albNik]

 

 

 

 

 

Για έλεγχο αν κάποιος αριθμός είναι πρώτος μάλλον θα λες.

Διαιρέτες από 1 ως Ν, αν και είναι αρκετό από 1 ως Ν/2.

 

Βασικα υπαρχει πιο γρηγορος τρόπος 

Βρισκεις τους πρωτους  1 ως sqrt(n) και τον εκφραζεις ως γινομενο τους

 

π.χ 600 =2³*3¹* 5²     

 

d=(3+1)(1+1)(2+1)=24

[imitheos]

Για έλεγχο αν κάποιος αριθμός είναι πρώτος μάλλον θα λες.

Διαιρέτες από 1 ως Ν, αν και είναι αρκετό από 1 ως Ν/2.

 

Όχι δεν εννοούσα τους πρώτους αριθμούς αλλά και στους πρώτους αριθμούς ισχύει αυτό που λέμε ότι η άσκηση θέλει να σε βάλει να σκεφτείς.

 

#include <stdio.h>

void main()
{
	int i, n, count;

	for (n = 1; n <= 25; n++) {
		count = 0;
		for (i = 2; i <= n / 2; i++) {
			if ((n % i) == 0) {
				count = count + 1;
			}
		}
		if (count == 0)
			printf("%d is prime\n",n);
	}
}
Έξοδος:
1 is prime
2 is prime
3 is prime
5 is prime
7 is prime
11 is prime
13 is prime
17 is prime
19 is prime
23 is prime

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

 

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

 

Ο αλγόριθμος, με την χρήση του υπολοίπου, ψάχνει να βρει διαιρέτες και αυξάνει μια μεταβλητή. Έτσι αν βρει διαιρέτες σου λέει δεν είναι πρώτος. Αυτή η μέθοδος υπήρχε σε όλες τις λύσεις με αυτήν να είναι η καλύτερη (οι άλλες ελέγχανε μέχρι Ν αντί για ν / 2 ή ρίζα ν).

 

Γιατί όμως να το κάνεις αυτό ? Εμάς μας ενδιαφέρει αν ένας αριθμός είναι πρώτος οπότε δεν μας νοιάζει πόσους διαιρέτες έχει αλλά ΑΝ έχει. Είτε έχει 1 είτε 700, τότε δεν είναι πρώτος. Αυτή η σκέψη αντικατοπτρίζεται στον παρακάτω κώδικα.

#include <stdio.h>

int isprime(int n);

int main(void)
{
	int n;

	for (n = 1; n <= 25; n++)
		if (isprime(n))
			printf("%d is prime\n",n);

	return 0;
}

int isprime(int n)
{
	int i;

	for (i = 2; i <= n / 2; i++)
		if ((n % i) == 0)
			return 0;
	return 1;
}

Με το που θα βρεις τον πρώτο διαιρέτη, return 0 και δρόμο. Έβαλα επίτηδες την συνάρτηση ώστε να υπάρχει ένα έξτρα overhead λόγω των πολλών κλήσεων της συνάρτησης.

 

Αν τρέξουμε τους δύο αυτούς αλγορίθμους πάνω σε 1,000,000 αριθμούς, ο πρώτος θα τελειώσει σε 14:22.45 (862 δευτερόλεπτα), ενώ ο δεύτερος που έχει και τις κλήσεις των συναρτήσεων θα τελειώσει σε 1:04.83 (64 δευτερόλεπτα).

 

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