Για πολύ πολύ ζόρικους - Το ανάποδο του αθροίσματος

[UserXP]

Thanks MrTryANalyzer

[alkisg]

x+y+z = 100 <=>

x από 0 μέχρι 100

y από 0 μέχρι 100-x

z = 100 - x - y

 

Δεν χρειάζεται brute force. Μόνο 2 for loops, το δεύτερο να τελειώνει στο 100-x.

[UserXP]

Για 3 αριθμούς θέλεις 2 loops,

για 4 θέλεις 3,

για 5 θέλεις 4,

.

.

.

[chiossif]

#include <stdio.h>

#include <stdlib.h>

 

int plithos_athroisma(int,int);

 

int main() {

printf("Proigithikan %d sindiasmoi. Ch Iossif @ 2005\n",plithos_athroisma(4,100));

 

return 0;

}

 

/*

 

I think this is the routine you are looking for:

 

Variables:

k stands for number of results

m is the matrix

n is the number of numbers

s is the sum

i is a temporary integer

Main idea:

Put S into m[1],

subtract one from m[1],

add one to the rest m[j],

display matrix.

If m[1] become zero stop.

Todo:

If you eliminate permutations,

i think, it cannot become faster.

Ch Iossif @ 2005

*/

int plithos_athroisma(int n, int s) {

int k, *m, ok, j;

register int i;

 

k=ok=0;

if ((m=calloc(n,sizeof(int)))==NULL)

exit(1);

 

m[0]=s;

j=1;

while (!ok) {

printf("%07d:",++k);

for (i=0;i<n;i++)

printf(" %7d",m);

putchar('\n');

 

m[0]--;

if (m[0]==0)

ok=1;

m[j]++;

 

if (j<n)

j++;

else {

j=1;

m[0]++;

}

}

return k;

}

 

Λυπάμαι αλλά το 'γραψα σε C...

 

Ch 1oosif

[alkisg]

Για 3 αριθμούς θέλεις 2 loops' date='

για 4 θέλεις 3,

για 5 θέλεις 4,

.

.

.[/quote']

Sure, όμως για να το κάνει κάποιος για την "γενική περίπτωση" θα έπρεπε να χρησιμοποιήσει ΜΟΝΟ ΕΝΑ while στο οποίο θα αυξομειώνει με if όλους τους μετρητές, οι οποίοι στη γενική πάλι περίπτωση θα είναι array...

[Pleasure]

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

[chiossif]

... για το ίδιο πρόβλημα με πολλαπλασιασμό:

 

Δίνονται οι θετικοί ακέραιοι Ν και Μ. Ζητείται υποπρόγραμμα το οποίο να εμφανίζει όλους τους συνδιασμούς Ν θετικών ακεραίων των οποίων το γινόμενο να είναι Μ.

 

Μήπως υπάρχει forum για "αλγοριθμικές σπαζοκεφαλιές";

Αν όχι, τι θα λέγατε να φτιαχτεί ένα;

[alkisg]

Χε χε για τον πολλαπλασιασμό το πρόβλημα είναι ΤΕΛΕΙΩΣ διαφορετικό, για τον απλό λόγο του ότι το π.χ. 100/y δεν είναι πάντα ακέραιος.

 

Για να καταλάβεις το μέγεθος του προβλήματος, ο αλγόριθμος κρυπτογράφησης RSA στηρίζεται στην μέθοδο που λες, αλλά με N=2 και M=γινόμενο δύο τεράστιων ΠΡΩΤΩΝ αριθμών. Και συχνά βάζουν υπολογιστικά προβλήματα του στυλ "σας δίνω M=123487618273461827341 και βρείτε μου τους παράγοντές του" και όποιος το λύσει παίρνει μεγάλο χρηματικό ποσό.

Μάλιστα η λύση τέτοιου προβλήματος μπορεί να πάρει μήνες, και μερικές φορές κυκλοφορούν και trojans οι οποίοι κολλάνε σε άλλα PC για να εκμεταλλευτούν την επεξεργαστική ισχύ τους, να λύσουν γρηγορότερα το πρόβλημα και να κερδίσουν το χρηματικό βραβείο...

[chiossif]

... αλλά δεν ψάχνουμε τις μη ακέραιες λύσεις. Άλλωστε ο αλγόριθμος της 'ιδεας' στον C κώδικα που προηγήθηκε για την πρόσθεση δεν είναι εξαντλητικός.

 

Ch 1ossif

[alkisg]

...Φυσικά, αν ψάχναμε τις μη ακέραιες θα είχαμε άπειρες λύσεις.

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

 

Για μια μη εξαντλητική μέθοδο εύρεσης των παραγόντων ενός αριθμού google για quadratic sieve, είναι από τους πιο χαρακτηριστικούς αλγορίθμους.

 

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

 

Για την παραγοντοποίηση απ' όσο ξέρω δεν υπάρχει ούτε καν λύση πολυωνυμικού χρόνου...

[UserXP]

Αντίστοιχος κώδικας για πολλαπλασιασμό

 

>
' GetNumsMult
' Επιστρέφει σε ένα string χωρισμένο με vbCrLf όλους τους
' συνδυασμούς από HowManyNums (χωρισμένους με vbTab) που
' έχουν γινόμενο MultOfAll
' Στην κλήση της πρέπει NumsSoFar = ""
Function GetNumsMult(HowManyNums As Long, MultOfAll As Long, NumsSoFar As String) As String
Dim i As Long

If HowManyNums <= 1 Then
   GetNumsMult = NumsSoFar & MultOfAll & vbCrLf
   'List1.AddItem NumsSoFar & MultOfAll ' Just for test
Else
   For i = 2 To MultOfAll - 1
       If MultOfAll Mod i = 0 Then
           GetNumsMult = GetNumsMult & GetNumsMult(HowManyNums - 1, MultOfAll \ i, NumsSoFar & i & vbTab)
       End If
   Next i
End If

End Function

' GetNumsMult2
' Επιστρέφει σε ένα string χωρισμένο με vbCrLf όλους τους
' ΜΟΝΑΔΙΚΟΥΣ συνδυασμούς από HowManyNums (χωρισμένους με vbTab)
' που έχουν γινόμενο MultOfAll
' Στην κλήση της πρέπει NumsSoFar = "" και MinNumber = 0
Function GetNumsMult2(HowManyNums As Long, MultOfAll As Long, NumsSoFar As String, MinNumber As Long) As String
Dim i As Long

If HowManyNums <= 1 Then
   If MultOfAll < MinNumber Then Exit Function
   GetNumsMult2 = NumsSoFar & MultOfAll & vbCrLf
   'List1.AddItem NumsSoFar & MultOfAll ' Just for test
   'Print #1, NumsSoFar & MultOfAll
Else
   For i = 2 To MultOfAll \ 2
       If i >= MinNumber Then
           If MultOfAll Mod i = 0 Then
               GetNumsMult2 = GetNumsMult2 & GetNumsMult2(HowManyNums - 1, MultOfAll \ i, NumsSoFar & i & vbTab, i)
           End If
       End If
   Next i
End If

End Function

[small_boy22]

Aν καταλαβα καλα προσπαθεις να λυσεις μια διοφαντικη εξισωση ??

 

Δεν θυμαμαι καλα απο το λυκειο αν η διοφαντικη ειναι μονο για φυσικους και οχι για ακεραιους..

[UserXP]

Αν θυμάμαι κι εγώ καλά, διοφαντική είναι μια εξίσωση της μορφής 2x + 5y = 42

Όχι, δεν προσπαθούμε κάτι τέτοιο τώρα. Αρχικά ναι, προσπαθούσαμε να λύσουμε διοφαντική της μορφής x + y + z + ... = <a number>

Φυσικά δεν μας ενδιέφεραν αρνητικές τιμές γιατί οι λύσεις είναι άπειρες

[alkisg]

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

Π.χ. έχω το 24

Δεν έχει νόημα να πω ότι προκύπτει σαν 2*12 ή 3*4*2 κτλ.

Αυτό που έχει νόημα είναι

 

Βήμα 1) Να βρω ότι το 2 είναι διαιρέτης του, και άρα το 24 γράφεται σαν 2*12.

Βήμα 2) Συνεχίζω αναδρομικά παραγοντοποιώντας το 12 κτλ

 

Έτσι βρίσκω ότι οι παράγοντες του 24 είναι οι 2, 2, 2, 3.

 

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

 

Το δύσκολο της όλης διαδικασίας είναι το βήμα 2. Δηλαδή αν ο αριθμός είναι 2^1024 - 1, τότε θα χρειαστούν αρκετά χρόνια για να βρω ΕΝΑΝ παράγοντά του. Εκεί βασίζεται ο RSA και τα υπόλοιπα που έλεγα.

[Sakis_drm]

User XP: μου άρεσε πολύ ο αναδρομικός κώδικας σου!

 

MrTryANalyzer: Δεν κατάλαβα τι ρόλο παίζει η γραμμή

"Label1.Caption = plus"

μου φαίνεται ότι θα έχει σαν αποτέλεσμα το label1 να δείχνει συνέχεια 101

 

Επίσης η DoEvents τι ακριβώς κάνει;

 

Αυτόν τον καιρό προπαθώ να σκεφτώ έξυπνο αλγόριθμο για το παιχνίδι Othello. Το γράφω σε VB.