Speicherung von mehreren Paare < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
Hallo!
Also ich habe eine while-Schleife. Für jeden Durchgang möchte ich folgendes machen:
Falls eine Variable X kleiner als Y ist, dann möchte ich das Paar (***, ...) irgendwo abspeichern. Falls X/2 kleiner als Y ist möchte ich das Paar (---, .....) auch abspeichern.
Später, möchte ich dann schauen ob eine andere Variable R mit *** oder --- übereinstimmt.
Leider weiß ich gar nicht wie das geht?
Muss ich die Paare in einen Array speichern? Es soll so sein, dass in diesen Array, falls es einer ist, mehrere Paare rein kommen und ich bei jedem Durchgang alle --- und *** aus allen Paaren, die ich bis jetzt habe verglichen wird.
Ich habe keine Ahnung wie ich das anstellen soll....
Könnt ihr mir bitte, bitte weiterhelfen?
Gruß,
Pepino
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:00 So 26.08.2012 | | Autor: | felixf |
Moin Pepino!
> Also ich habe eine while-Schleife. Für jeden Durchgang
> möchte ich folgendes machen:
> Falls eine Variable X kleiner als Y ist, dann möchte ich
> das Paar (***, ...) irgendwo abspeichern. Falls X/2 kleiner
> als Y ist möchte ich das Paar (---, .....) auch
> abspeichern.
> Später, möchte ich dann schauen ob eine andere Variable R
> mit *** oder --- übereinstimmt.
>
> Leider weiß ich gar nicht wie das geht?
> Muss ich die Paare in einen Array speichern? Es soll so
> sein, dass in diesen Array, falls es einer ist, mehrere
> Paare rein kommen und ich bei jedem Durchgang alle --- und
> *** aus allen Paaren, die ich bis jetzt habe verglichen
> wird.
> Ich habe keine Ahnung wie ich das anstellen soll....
> Könnt ihr mir bitte, bitte weiterhelfen?
Kannst du das mal ein wenig genauer beschreiben?
Ich wuerde (auch) einen Baum / eine Hash-Tabelle verwenden, in der alle ***, ---, ... reingeschrieben werden mit jeweils einen Zeiger auf das Paar, in denen die vorkommen (falls man das Paar ueberhaupt braucht; das Paar selber koennte man z.B. in eine verkettete Liste packen). Dann koenntest du beim Hinzufuegen eines neuen Paars (x, y) schnell feststellen, ob x oder y schonmal irgendwo vorkommt (und hast gleich einen Zeiger zum alten Paar).
Wenn dir das zu unkonkret ist, beschreib doch mal das was du machen willst etwas genauer...
LG Felix
|
|
|
| |
|
| Aufgabe | [mm] \textbf{Schritt 1: Initialisierung}
[/mm]
[mm] \\
[/mm]
N = zufaktorisierende Zahl. S [mm] $\leftarrow$ $\lfloor \sqrt{D} \rfloor$, $\hat{Q} \leftarrow$ 1, P $\leftarrow$ S, Q $\leftarrow$ D - P $\cdot$ P, L $\leftarrow$ $\lfloor 2\sqrt{2\sqrt{D}} \rfloor$, $ B \leftarrow 2 \cdot L$ und i = 0.
\\ \\
Schritt 2
\\
$2a$ bis $2e$ für $i = 1, 2, 3 \ldots$ wiederholen.
\\
\textit{2a)} Zunächst berechnen wir $q = \lfloor \frac{S + P}{Q}\rfloor$ und $P' = q \cdot Q - P$
\\
\\
\textit{2b)} Falls $Q \le L $ schreibe Paar $(Q/2, P \pmod {Q/2})$ in Liste. Falls $Q \le L/2 $ schreibe Paar $(Q, P \pmod Q)$ in die QUEUE.
\\
\\
\textit{2c)} Sei $t = \hat{Q} + q \cdot (P -P')$, $\hat{Q} = Q$, $Q \leftarrow t$ und $P = P'$.
\\
\\
\textit{2d)} Falls i gerade ist oder Q keine Quadratzahl, gehen zu $2e)$. Ansonsten sei $r = \sqrt{Q}$ eine positive gerade Zahl. Ist in der QUEUE kein Tupel (r, t), für das r P-t teilt, gehen zu 3. Falls r > 1 ist und es in der QUEUE ein Paar (r, t) gibt, für welches r P-t teilt, lösche alle Paarel vom Anfang bis zu inklusive diesem Paar und gehen $2e)$. Ist jedoch r = 1 und in der QUEUE befindet sich ein Paar (1, t), schlägt der Algorithmus fehl.
\\
\\
\textit{2e)} i = i+1. Falls i > B ist, bricht der Algorithmus ab, sonst zu Schritt $2a)$.
hey felix,
so das ist genau beschrieben, was ich machen möchte.
Die schleife mit den Rechnungen habe ich.
Jetzt nur noch das Problem mit der QUEUE (Was heißt das eigentlich auf deutsch? Liste?)
also ich kann weder mit Baum, hasch-tabelle oder verkettete Liste etwas anfangen :(
LG Pepi
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:44 Mo 27.08.2012 | | Autor: | felixf |
Moin!
> [mm]\textbf{Schritt 1: Initialisierung}[/mm]
> [mm]\\[/mm]
> N = zufaktorisierende Zahl. S [mm]\leftarrow[/mm] [mm]\lfloor \sqrt{D} \rfloor[/mm],
> [mm]\hat{Q} \leftarrow[/mm] 1, P [mm]\leftarrow[/mm] S, Q [mm]\leftarrow[/mm] D - P
> [mm]\cdot[/mm] P, L [mm]\leftarrow[/mm] [mm]\lfloor 2\sqrt{2\sqrt{D}} \rfloor[/mm], [mm]B \leftarrow 2 \cdot L[/mm]
> und i = 0.
> [mm]\\ \\[/mm]
> Schritt 2
> [mm]\\[/mm]
> [mm]2a[/mm] bis [mm]2e[/mm] für [mm]i = 1, 2, 3 \ldots[/mm] wiederholen.
> [mm]\\[/mm]
> [mm]\textit{2a)}[/mm] Zunächst berechnen wir [mm]q = \lfloor \frac{S + P}{Q}\rfloor[/mm]
> und [mm]P' = q \cdot Q - P[/mm]
> [mm]\\[/mm]
> [mm]\\[/mm]
> [mm]\textit{2b)}[/mm] Falls [mm]Q \le L[/mm] schreibe Paar [mm](Q/2, P \pmod {Q/2})[/mm]
> in Liste. Falls [mm]Q \le L/2[/mm] schreibe Paar [mm](Q, P \pmod Q)[/mm] in
> die QUEUE.
> [mm]\\[/mm]
> [mm]\\[/mm]
> [mm]\textit{2c)}[/mm] Sei [mm]t = \hat{Q} + q \cdot (P -P')[/mm], [mm]\hat{Q} = Q[/mm],
> [mm]Q \leftarrow t[/mm] und [mm]P = P'[/mm].
> [mm]\\[/mm]
> [mm]\\[/mm]
> [mm]\textit{2d)}[/mm] Falls i gerade ist oder Q keine Quadratzahl,
> gehen zu [mm]2e)[/mm]. Ansonsten sei [mm]r = \sqrt{Q}[/mm] eine positive
> gerade Zahl. Ist in der QUEUE kein Tupel (r, t), für das r
> P-t teilt, gehen zu 3. Falls r > 1 ist und es in der
> QUEUE ein Paar (r, t) gibt, für welches r P-t teilt,
> lösche alle Paarel vom Anfang bis zu inklusive diesem Paar
> und gehen [mm]2e)[/mm]. Ist jedoch r = 1 und in der QUEUE befindet
> sich ein Paar (1, t), schlägt der Algorithmus fehl.
> [mm]\\[/mm]
> [mm]\\[/mm]
> [mm]\textit{2e)}[/mm] i = i+1. Falls i > B ist, bricht der
> Algorithmus ab, sonst zu Schritt [mm]2a)[/mm].
> hey felix,
>
> so das ist genau beschrieben, was ich machen möchte.
>
> Die schleife mit den Rechnungen habe ich.
> Jetzt nur noch das Problem mit der QUEUE (Was heißt das
> eigentlich auf deutsch? Liste?)
Schau mal ![[]](/images/popup.gif) hier. Warteschlange ist im Allgemeinen eine recht gute Uebersetzung.
Da die Suche hier darauf zielt, alle Elemente der Reihe nach vorliegen zu haben und sequentiell durchzusuchen, wuerde ich das ganze entweder als verkettete Liste (in C++: std::list<>) oder als dynamisches Array (in C++: std::vector<> bzw. besser std::queue<>) zu speichern.
> also ich kann weder mit Baum, hasch-tabelle oder verkettete
> Liste etwas anfangen :(
Das kommt in jeder einfuehrenden Informatik-Veranstaltung (Thema Algorithmen und Datenstrukturen) vor; somit bist du vermutlich eher ein Mathematiker mit kaum/keinem Informatik-Background.
LG Felix
|
|
|
|
|
