Algorithmus in pseudocode?

Hallo

die aufgabe lautet : schreiben sie einen Algorithmus in pseudocode, welcher die ganzzahlige Division a/b durchführt. Verwenden Sie nur rechneroperationen, die die ALU der Mic-1 beherrscht.

kann mir bitte einer erklären wie man sowas lösen kann. Die zugestellten Folien helfen mir null weiter

2 Antworten

xxxcyberxxx

06.12.2021, 11:26

kann mir bitte einer erklären wie man sowas lösen kann. Die zugestellten Folien helfen mir null weiter

überlege dir, welche Operationen deine ALU beherrscht.

Überlege dir, wie man eine Division "von Hand" durchführt - das kann man auch als wiederholte Subtraktion verstehen.

Überlege dir, wie du mit den gegebenen Operationen dies umsetzen kannst. Wenn deine ALU nicht subtrahieren kann, überlege dir, wie du eine Subtraktion mit einer Addition darstellen kannst.

Woher ich das weiß:Studium / Ausbildung – Abgeschlossenes Studium der Informatik (B.Sc.)

Destranix

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer, Informatik, Informatik

06.12.2021, 11:24

Eine Division lässt sich schreiben als sukzessive Subtraktion des Divisors vom Dividenden. Dabei wird mitgezählt, wie oft dies geschehen kann, bis das Ergebnis der Subtraktion kleiner als 0 ist.

Ich nehme an die ALU beherrschgt Subtraktion. Zudem werden wahrscheinlich bedingte Jumpf zur Verfügung stehen, mit denen einen Schleife und ein Test auf "kleiner 0" implementiert werden können.

Ähnliche Fragen

Was ist ein Pseudocode?

Hi,

Ich verstehe nicht ganz was ein Pseudocode ist, wofür braucht man das? Kann das jemand einfach erklären?

Gibt es dafür mehrere Defintionen?

...zur Frage

Pseudocode lesen?

Hallo, ich tue mich sehr schwer in Pseudocode s lesen. Kann mir jemand helfen, das zu lernen oder zeigen, was im folgenden Pseudocode (es geht um den Countingsort) steht?
Ich verstehe nur die Eingabe und das Ende bei return :((

Ich wäre sehr dankbar!

Um genauer zu sein und die Fragen am Beispiel zu stellen:

was bedeutet zahlen [0]

was ist i++

temporäre Liste ist wahrscheinlich der Hilfsarray?

finaleposition ist dann das Ergebnisarray? Was bedeutet finaleposition++

Ich glaub man sieht, ich komme nicht ganz zurecht, aber ich würde mich freuen, wenn das jemand erklären könnte.

...zur Frage

Java - Distanzmatrix Algorithmus, Wie ansetzen?

Hallo, ich bin gerade dabei ein Graphenprogramm zu schreiben und stecke bisschen bei der Distanzmatrix.

Ich weiß nicht ob sich jemand bei Graphentheorie auskennt oder nicht aber der Algorithmus für die Distanzmatrix ist relativ einfach. Nur das umsetzen in Code fällt mir sehr schwer und deswegen hoffe ich, dass ihr mir vielleicht dabei helfen könnt..

Der Algorithmus für eine Distanzmatrix lautet so:

Man hat eine Eingangsmatrix (Adjazentmatrix).
Die könnte so aussehen:

Man markiert sich alle Nuller die in der Adjazentmatrix vorkommen (AUßER DIE HAUPTDIAGONALE, DIE BLEIBT UNBERÜHRT).

Dann erstellt man sich eine eigene Matrix die man "DistanzMatrix" nennen kann und setzt alle Nuller die eben in der Adjazentmatrix vorkommen auf "Unendlich" oder auch auf INTEGER.MAX_VALUE in der Programmiersprache .

Das schaut dann so aus:

Also haben wir jetzt 2 Matrizen. Bis dahin habe ich es auch geschafft in meinem Programm. Die Ausgabe schaut bei mir so aus:

Die "-9" sind alle Nuller, die auf UNENDLICH gesetzt sind (siehe zweites Bild).

Der nächste Schritt ist es die Potenzen der Eingangsmatrix (Adjazentmatrix) zu berechnen. Das habe ich ebenfalls schon geschafft im Code.

Das heißt, die Adjazentmatrix (siehe Bild 1) wurde potenziert und so könnte das Ergebnis der Potenzberechnug aussehen.

Man schaut sich jetzt alle Nuller (außer die Hauptdiagonale von der Eingangsmatrix an (siehe Bild 1)) und markiert sich nur die Zahlen (rot), die sich von der Potenzierung der Eingangsmatrix verändert haben. (Außer die Nuller (=Neue Nuller die durch die Potenzierung entstanden sind bleiben auch weiterhin eine Null))

Und der letzte Schritt ist es jetzt, die von mir erstellte DistanzMatrix upzudaten, indem ich im ersten Schritt alle rote Zahlen von A²(G) in 2 umwandle. Alle Nuller die übrig bleiben, werden wieder in UNENDLICH umgewandelt.

Und das wird jetzt so oft wiederholt, bis es keine UNENDLICH Zeichen mehr in der Distanzmatrix gibt. Und aus UNENDLICH wird 3. Und immer so weiter.. Falls es zb nach der fünften Potenzierung immer noch Nuller bzw UNENDLICH Werte gibt dann wird aus UNENDLICH 5.

Somit ist D³(G) das Ergebnis.

Ich hoffe ich konnte es ausführlich genug erklären

Danke

...zur Frage

wie lange braucht ein beliebiger Algorithmus mindestens zum erstellen eines binären suchbaums aus einer unsortierten Menge?

Wie lange braucht ein beliebiger Algorithmus mindestens zum erstellen eines binären Suchbaums aus einer unsortierten Menge von n vergleichbaren Elementen und warum?

...zur Frage

C Programmcode Ceasar Cipher?

Hallo,

die aufgabe ist folgende:

Schreiben Sie eine Funktion, welche eine Variante des [Caesar Cipher](https://en.wikipedia.org/wiki/Caesar_cipher) auf einen String anwendet. Hierbei wird anstatt eines vorgegebenen Betrages und einer vorgegebenen Richtung für die Chiffrierung der Schlüssel für jeden Buchstaben des Klartextes neu berechnet.

Funktionsweise:

Jede Verschiebung erfolgt abhängig vom Schlüssel. Ist der Schlüssel für das aktuelle Zeichen eine gerade Zahl, so wird das aktuelle Zeichen um diesen Betrag im Alphabet nach rechts verschoben (z.B. beim Schlüssel 2 wird aus einem A ein C). Ist der Schlüssel ungerade, so erfolgt eine Verschiebung nach links (z.B. beim Schlüssel 3 wird aus einem D ein A).

Würde eine Verschiebung über das Ende des Alphabets hinaus erfolgen, so wird die Zählung bei Beginn des Alphabets fortgesetzt. Beim Schlüssel 2 wird aus einem Z also ein B bzw. beim Schlüssel 3 aus einem A ein X.

Es werden nur Buchstaben des englsichen Alphabets (A-Z und a-z) chiffriert. Alle anderen Zeichen bleiben unverändert.

Der Startschlüssel wird nur auf das erste Zeichen angewendet. Danach wird der Schlüssel nach jeder Anwendung neu berechnet, indem der Zahlenwert des zuletzt veränderten Klartext-Zeichens (also 1 für A und a, 2 für B und b, bis 26 für Z und z) durch den zuletzt verwendeten Schlüssel dividiert wird. Der neue Schlüssel für das nächste Zeichen ist der ganzzahlige Rest dieser Division. Falls es hierbei zu einer Division durch Null kommen würde (weil der zuletzt verwendete Schlüssel 0 war) wird der neue Schlüssel wieder auf den Wert des Startschlüssels gesetzt.

Folgenden Code habe ich bis jetzt geschrieben, allerdings bekomm ich bei großen Schlüsseln (zb: start_key = 100) falsche Ergebnisse raus. Weiß glaube ich auch warum: Mein Algorithmus funktioniert ja über Werteverschiebung, d.h. ab einem bestimmt großen Wert des Schlüssels verschiebt sich mein Zahlenwert des chars zu weit und dann stimmt meine "Formel" nicht mehr. Hätte es jetzt damit gelöst, dass ich zuerst mit einer if Schleife auf einen zu großen Key prüfe (zB.: if Key > 25), anschließend dividiere ich diesen Key und gehe mit dem Ergebniss in eine neue Schleife rein wobei jetzt anstatt des Keys der neue Wert addiert bzw subtrahiert wird. Anschließend durchlaufe ich diese Schleife Key%25 mal.

Aber wie setze ich das um? Zusätzlich dazu wird der Code dann mega unübersichtlich und viel zu lang für eine simple Funktion. Gibt es auch andere Möglichkeiten als meinen Code?

Ps: Ich sende den Code extra weil sonst das Zeichenlimit überschritten wird

...zur Frage

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

...zur Frage

Informatik Verkehsrsystem?

Hallo,

eine Frage an die Informatiker*innen:

Wie realisiert man (pseudocode-mäßig) die Vorfahrtsregeln eines Verkehrssystems, bei dem es einzelne Fahrspuren (jede Straße hat 2; rechts und links) gibt und Abschnitte, bei denen man abbiegen kann (nach links oder rechts).

Viele Grüße.

...zur Frage

Informatik Aufgaben- Methode erklären?

Hallo,

wir haben momentan im Informatik Unterricht einen Exkurs zur Berechenbarkeit angefangen. Dazu sollen wir nun selbstständig die Aufgaben 1 und 2 auf der Seite bearbeiten. Bei der Aufgabe 2 habe ich keine Probleme, da diese sehr gut lösbar ist. Jedoch komme ich bei Aufgabe 1 nicht weiter, das alleine schon weil ich die Methode nicht verstehe. Habe mir dazu einige Texte usw durchgelesen aber ich komm mit der Methode eif nicht weiter, sodass die Aufgabe dann natürlich nicht lösbar ist. Könnte mir da jemand weiterhelfen?

...zur Frage

Was tut dieser Algorithmus?

Ich lerne gerade für meine erste Klassenarbeit in Informatik, komme hier aber nicht wirklich weiter. Habt ihr Ideen/ Erklärungen?

...zur Frage

Ein Kochbuch als Algorithmus?

Ich hab mal so eine Frage bzgl. Algorithmen und Datenstrukturen. In unserer Übung sollen wir beurteilen, ob ein Kochbuch ein Algorithmus wäre und dabei bin ich während einer Recherche ins grübeln gekommen.

Erstmal ist natürlich klar, dass ein Algorithmus eine endliche Abfolge von genau definierten Anweisungen zur Behebung eines Problems ist. Nun muss man bei einem Kochbuch bedenken, dass Anweisungen wie "Eine Prise Salz" nicht genau definiert sind und auch bei der Durchführung es unterschiedliche Resultate geben würde, z.B auf Grund verschiedener Backöfen, Kochtöpfe etc. was der Definition eines Algorithmus widersprechen würde. Wenn man wiederum die Umgebung digital simulieren würde, wäre das Resultat immer identisch.

Daher wollte ich euch mal fragen, wie ihr darüber denkt und ob ein Kochbuch ein Algorithmus wäre oder nicht

...zur Frage

Determinismus in Informatik?

Laut definition ist ein Algorithmus deterministsich, wenn für alle Eingabedaten die Reihenfolge auszuführender Schritte eindeutig bestimmt ist.

Gilt das dann auch für einen Algorithmus mit einer if-else Anweisung? Oder sind alle Algorithmen mit einer if-else Anweisung nicht deterministisch.

...zur Frage

Wie kann man Liste in Java sortieren?

Hey,

Ich muss eine Liste sortieren, die 15 Zahlen speichert. Am Ende sollen die Zahlen von klein nach groß geordnet sein.

Wie kann ich das machen?

Würde mich sehr über Hilfe freuen.

Liebe Grüße

...zur Frage

Wie kann ein Rechteck in möglichst wenige Quadrate zerlegt werden?

Ich habe ein Rechteck mit ganzzahligen Seitenlängen. Dieses Rechteck möchte ich nun in Quadrate zerlegen, die eine Zweierpotenz als Seitenlänge haben. Dabei sollen so wenige Quadrate wie möglich entstehen.

Als Beispiel betrachten wir ein 9 x 6-Rechteck. Ein solches Rechteck lässt sich wie folgt in zwei Quadrate der Seitenlänge 4, vier Quadrate der Seitenlänge 2 und sechs Quadrate der Seitenlänge 1 zerlegen:

Nun suche ich nach einer Möglichkeit, dies nicht zeichnerisch, sondern durch eine Formel oder einen Algorithmus (gerne in Pseudocode) zu bestimmen. Hat jemand eine Idee, wie man da vorgehen könnte? Meine bisherigen Ansätze waren nicht wirklich zielführend und sicherlich auch zu kompliziert gedacht...

...zur Frage

Algorithmen und Pseudocode Unterschied?

Was ist der Unterschied zwischen einem Algorithmus, einem Programm und einem Pseudocode?

Bitte schülergerecht erklären.

Danke schon im Voraus!!

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen