Informatik zum Dienstag
bearbeitet von
Ich arbeite gerade an einer kleinen Programmiersprache, die keine Datentypen für Zahlen kennt. Aber man kann sie innerhalb der Sprache definieren. Bspw. wie die Peano-Zahlen:
1. `0` kodiert eine natürliche Zahl.
2. Falls `n` eine natürliche Zahl kodiert, so auch `u0(n)`.
Das entspricht der unären Kodierung einer Zahl. Die Zahl `3` wird bspw. durch `u0(u0(u0(0)))` kodiert. Das Symbol `u0` repräsentiert die einzige Ziffer des unären Zahlensystems. Es ist wichtig zwischen der Ziffer `u0` und dem Terminal-Symbol `0` zu unterscheiden.
Nun ist die unäre Kodierung nicht besonders Speicher- oder Rechen-freundlich. Deshalb möchte man unäre Zahlen manchmal in die Binärdarstellung bringen bevor man damit rechnet. Eine Definition könnte bspw. so lauten:
1. `0` kodiert natürliche Zahl.
2. Falls `n` eine natürliche Zahl kodiert, so auch `b0(n)` und `b1(n)`.
Die Zahl `5` wird bspw. durch `b1(b0(b1(0)))` kodiert. `b1` entspricht der binären Ziffer `1` und `b0` der binären Ziffer `0`.
Die Aufgabe ist es, einen Algorithmus zu programmieren, der eine unär kodierte Zahl in eine Binärdarstellung umkodiert, ohne dabei auf die eingebauten Zahlendatentypen der Programmiersprache zurück zugreifen.
Ich habe bei Stackblitz eine [TypeScript-Vorlage für die Aufgabe](https://stackblitz.com/edit/typescript-unary-and-binary-number-encodings-tdw5br) angelegt, die Funktion `unaryToBinary` muss noch mit leben gefüllt werden. Die Vorlage enthält bereits Definitionen für das Terminal-Symbol `0` und die unären und binären Ziffern.
~~~typescript
const zero = {tag: 'zero'} // Das Terminal-Symbol 0
const u0 = (pred) => ({tag: 'U0', pred}) // Die unäre Ziffer 0
const b0 = (pred) => ({tag: 'B0', pred}) // Die binäre Ziffer 0
const b1 = (pred) => ({tag: 'B1', pred}) // Die binäre Ziffer 1
// Beispiele
const unaryThree = u0(u0(u0(zero)))
const binaryFive = b1(b0(b1(zero)))
~~~
Außerdem enthält die Vorlage einige Helferfunktionen und ein paar Typ-Definitionen, die die Aufgabe einfacher machen sollen. Wer mit Typen nicht so viel anfangen kann, darf sie natürlich auch löschen.
Informatik zum Dienstag
bearbeitet von
Ich arbeite gerade an einer kleinen Programmiersprache, die keine Datentypen für Zahlen kennt. Aber man kann sie innerhalb der Sprache definieren. Bspw. wie die Peano-Zahlen:
1. `0` kodiert eine natürliche Zahl.
2. Falls `n` eine natürliche Zahl kodiert, so auch `u0(n)`.
Das entspricht der unären Kodierung einer Zahl. Die Zahl `3` wird bspw. durch `u0(u0(u0(0)))` kodiert. Das Symbol `u0` repräsentiert die einzige Ziffer des unären Zahlensystems. Es ist wichtig zwischen der Ziffer `u0` und dem Terminal-Symbol `0` zu unterscheiden.
Nun ist die unäre Kodierung nicht besonders Speicher- oder Rechen-freundlich. Deshalb möchte man unäre Zahlen manchmal in die Binärdarstellung bringen bevor man damit rechnet. Eine Definition könnte bspw. so lauten:
1. `0` kodiert natürliche Zahl.
2. Falls `n` eine natürliche Zahl kodiert, so auch `b0(n)` und `b1(n)`.
Die Zahl `5` wird bspw. durch `b1(b0(b1(0)))` kodiert. `b1` entspricht der binären Ziffer `1` und `b0` der binären Ziffer `0`.
Die Aufgabe ist es, einen Algorithmus zu programmieren, der eine unär kodierte Zahl in eine Binärdarstellung umkodiert, ohne dabei auf die eingebauten Zahlendatentypen der Programmiersprache zurück zugreifen.
Ich habe bei Stackblitz eine [TypeScript-Vorlage für die Aufgabe](https://stackblitz.com/edit/typescript-unary-and-binary-number-encodings-tdw5br) angelegt, die Funktion `unaryToBinary` muss noch mit leben gefüllt werden. Die Vorlage enthält bereits Definitionen für das Terminal-Symbol `0` und die unären und binären Ziffern.
~~~typescript
const zero = {tag: 'zero'} // Das Terminal-Symbol 0
const u0 = (pred) => ({tag: 'U0', pred}) // Die unäre Ziffer 0
const b0 = (pred) => ({tag: 'B0', pred}) // Die binäre Ziffer 0
const b1 = (pred) => ({tag: 'B1', pred}) // Die binäre Ziffer 1
// Beispiele
const unaryThree = u0(u0(u0(0)))
const binaryFive = b1(b0(b1(0)))
~~~
Außerdem enthält die Vorlage einige Helferfunktionen und ein paar Typ-Definitionen, die die Aufgabe einfacher machen sollen. Wer mit Typen nicht so viel anfangen kann, darf sie natürlich auch löschen.