tag:forum.selfhtml.org,2005:/self Informatik zum Dienstag – SELFHTML-Forum 2020-08-10T09:40:39Z https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774131#m1774131 1unitedpower 2020-08-04T15:42:30Z 2020-08-04T16:14:44Z Informatik zum Dienstag <p>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:</p> <ol> <li><code>0</code> kodiert eine natürliche Zahl.</li> <li>Falls <code>n</code> eine natürliche Zahl kodiert, so auch <code>u0(n)</code>.</li> </ol> <p>Das entspricht der unären Kodierung einer Zahl. Die Zahl <code>3</code> wird bspw. durch <code>u0(u0(u0(0)))</code> kodiert. Das Symbol <code>u0</code> repräsentiert die einzige Ziffer des unären Zahlensystems. Es ist wichtig zwischen der Ziffer <code>u0</code> und dem Terminal-Symbol <code>0</code> zu unterscheiden.</p> <p>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:</p> <ol> <li><code>0</code> kodiert eine natürliche Zahl.</li> <li>Falls <code>n</code> eine natürliche Zahl kodiert, so auch <code>b0(n)</code> und <code>b1(n)</code>.</li> </ol> <p>Die Zahl <code>5</code> wird bspw. durch <code>b1(b0(b1(0)))</code> kodiert. <code>b1</code> entspricht der binären Ziffer <code>1</code> und <code>b0</code> der binären Ziffer <code>0</code>.</p> <p>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.</p> <p>Ich habe bei Stackblitz eine <a href="https://stackblitz.com/edit/typescript-unary-and-binary-number-encodings-tdw5br" rel="nofollow noopener noreferrer">TypeScript-Vorlage für die Aufgabe</a> angelegt, die Funktion <code>unaryToBinary</code> muss noch mit leben gefüllt werden. Die Vorlage enthält bereits Definitionen für das Terminal-Symbol <code>0</code> und die unären und binären Ziffern.</p> <pre><code class="block language-typescript"><span class="token keyword">const</span> zero <span class="token operator">=</span> <span class="token punctuation">{</span>tag<span class="token operator">:</span> <span class="token string">'zero'</span><span class="token punctuation">}</span> <span class="token comment">// Das Terminal-Symbol 0</span> <span class="token keyword">const</span> <span class="token function-variable function">u0</span> <span class="token operator">=</span> <span class="token punctuation">(</span>pred<span class="token punctuation">)</span> <span class="token operator">=></span> <span class="token punctuation">(</span><span class="token punctuation">{</span>tag<span class="token operator">:</span> <span class="token string">'U0'</span><span class="token punctuation">,</span> pred<span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token comment">// Die unäre Ziffer 0</span> <span class="token keyword">const</span> <span class="token function-variable function">b0</span> <span class="token operator">=</span> <span class="token punctuation">(</span>pred<span class="token punctuation">)</span> <span class="token operator">=></span> <span class="token punctuation">(</span><span class="token punctuation">{</span>tag<span class="token operator">:</span> <span class="token string">'B0'</span><span class="token punctuation">,</span> pred<span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token comment">// Die binäre Ziffer 0</span> <span class="token keyword">const</span> <span class="token function-variable function">b1</span> <span class="token operator">=</span> <span class="token punctuation">(</span>pred<span class="token punctuation">)</span> <span class="token operator">=></span> <span class="token punctuation">(</span><span class="token punctuation">{</span>tag<span class="token operator">:</span> <span class="token string">'B1'</span><span class="token punctuation">,</span> pred<span class="token punctuation">}</span><span class="token punctuation">)</span> <span class="token comment">// Die binäre Ziffer 1</span> <span class="token comment">// Beispiele</span> <span class="token keyword">const</span> unaryThree <span class="token operator">=</span> <span class="token function">u0</span><span class="token punctuation">(</span><span class="token function">u0</span><span class="token punctuation">(</span><span class="token function">u0</span><span class="token punctuation">(</span>zero<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">const</span> binaryFive <span class="token operator">=</span> <span class="token function">b1</span><span class="token punctuation">(</span><span class="token function">b0</span><span class="token punctuation">(</span><span class="token function">b1</span><span class="token punctuation">(</span>zero<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span> </code></pre> <p>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.</p> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774139#m1774139 Rolf B 2020-08-04T19:01:48Z 2020-08-04T19:01:48Z Informatik zum Dienstag <p>Hallo 1unitedpower,</p> <p>ohne deine Helferfunktionen wüsste man zu wenig.</p> <p>Frage wäre gewesen: n sei die Binärcodierung einer natürlichen Zahl und val(n) der Zahlenwert dazu. Ist dann <code>val(b0(n)) == val(n)</code> oder <code>val(b0(n)) == 2*val(n)</code>? Meint: Setzt b0(n) ein neues most significant bit oder ein neues least significant. Dein Helper macht klar: es ist ersteres.</p> <p>Frage ist aber auch: Ist die rekursive Darstellung der unären und binären Codierung vorgegeben? Oder darf ich auch eine andere Implementierung der Peano- oder Binärcodierung benutzen, solange ich dabei keine Zahlen verwende? Ich denke da an ein Array, auf das ich push, pop, shift oder unshift anwenden könnte.</p> <p>Allgemeiner gefragt: Welchen Funktionsumfang hat deine zahlenlose Sprache? JavaScript minus Number? Oder noch weniger?</p> <p>Und ich nehme mal an, dass binaryLength bei der Implementierung von unaryToBinary nicht als Helper zur Verfügung steht, gelle?</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - obstruxi </div> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774141#m1774141 Rolf B 2020-08-04T19:28:45Z 2020-08-04T19:28:45Z Informatik zum Dienstag <p>Hallo 1unitedpower,</p> <p>by the way braucht man binaryLength gar nicht. Das verleitet nur zum cheaten. Man muss nur binaryToNumber etwas umgestalten:</p> <pre><code class="block language-js"><span class="token keyword">function</span> <span class="token function">binaryToNumber</span><span class="token punctuation">(</span><span class="token parameter"><span class="token literal-property property">n</span> <span class="token operator">:</span> BNat</span><span class="token punctuation">)</span> <span class="token operator">:</span> number <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token function">b2n</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">function</span> <span class="token function">b2n</span><span class="token punctuation">(</span><span class="token parameter"><span class="token literal-property property">val</span><span class="token operator">:</span> number<span class="token punctuation">,</span> <span class="token literal-property property">n</span><span class="token operator">:</span> BNat</span><span class="token punctuation">)</span> <span class="token operator">:</span> number <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'zero'</span><span class="token punctuation">)</span> <span class="token keyword">return</span> val<span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token function">b2n</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token operator">*</span>val <span class="token operator">+</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'B1'</span> <span class="token operator">?</span> <span class="token number">1</span> <span class="token operator">:</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span> n<span class="token punctuation">.</span>pred<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> </code></pre> <p>Die Abfrage <code>n.tag === 'zero'</code> statt <code>n === zero</code> hilft TypeScript bei der korrekten Typdiskriminierung. Ich könnte sonst <code>n.pred</code> nicht verwenden.</p> <p>Warum hast Du eigentlich Zero, U0, B0 und B1 als interface definiert und nicht als type? Ich habe ja von TypeScript fast gar keine Ahnung...</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - obstruxi </div> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774390#m1774390 1unitedpower 2020-08-10T08:42:46Z 2020-08-10T08:43:40Z Lösung <p><a href="/users/6547" class="mention registered-user" rel="noopener noreferrer">@Rolf B</a> hat die Aufgabe sehr elegant gelöst. Meine eigene Lösung stinkt dagegen ziemlich ab.</p> <p><a href="https://stackblitz.com/edit/typescript-unary-and-binary-number-encodings" rel="nofollow noopener noreferrer">Meine Lösung</a> basiert auf einer <code>binaryIncrement</code>-Funktion, die eine binäre Zahl um 1 erhöht.</p> <pre><code class="block language-typescript"> <span class="token keyword">function</span> <span class="token function">unaryToBinary</span><span class="token punctuation">(</span>n<span class="token operator">:</span> UNat<span class="token punctuation">)</span> <span class="token operator">:</span> BNat <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'zero'</span><span class="token punctuation">)</span> <span class="token operator">?</span> zero <span class="token operator">:</span> <span class="token function">binaryIncrement</span><span class="token punctuation">(</span><span class="token function">unaryToBinary</span><span class="token punctuation">(</span>n<span class="token punctuation">.</span>pred<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> <p>Für die <code>binaryIncrement</code> Funktion brauchte ich zwei Helfer-Funktionen. Die erste Funktion testet, ob alle Ziffern <code>b1</code> sind. In dem Fall muss bei der Addition nämlich eine neue Ziffer am Anfang hinzugefügt werden.</p> <pre><code class="block language-typescript"><span class="token keyword">function</span> <span class="token function">binaryOverflow</span><span class="token punctuation">(</span>n <span class="token operator">:</span> BNat<span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token builtin">boolean</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'zero'</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token boolean">true</span> <span class="token operator">:</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'B0'</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token boolean">false</span> <span class="token operator">:</span> <span class="token comment">/*n.tag === 'B1'*/</span> <span class="token function">binaryOverflow</span><span class="token punctuation">(</span>n<span class="token punctuation">.</span>pred<span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> <p>Die zweite Helfer-Funktion setzt alle Ziffern einer Binärzahl auf <code>b0</code>.</p> <pre><code class="block language-typescript"><span class="token keyword">function</span> <span class="token function">binaryNullify</span><span class="token punctuation">(</span>n<span class="token operator">:</span> BNat<span class="token punctuation">)</span> <span class="token operator">:</span> BNat <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'zero'</span><span class="token punctuation">)</span> <span class="token operator">?</span> zero <span class="token operator">:</span> <span class="token function">b0</span><span class="token punctuation">(</span><span class="token function">binaryNullify</span><span class="token punctuation">(</span>n<span class="token punctuation">.</span>pred<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">}</span> </code></pre> <p>Die Additions-Funktion muss dann vier Fälle unterscheiden:</p> <pre><code class="block language-typescript"><span class="token keyword">function</span> <span class="token function">binaryIncrement</span><span class="token punctuation">(</span>n <span class="token operator">:</span> BNat<span class="token punctuation">)</span> <span class="token operator">:</span> BNat <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token punctuation">(</span><span class="token function">binaryOverflow</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token function">b1</span><span class="token punctuation">(</span><span class="token function">binaryNullify</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'B0'</span> <span class="token operator">&&</span> <span class="token function">binaryOverflow</span><span class="token punctuation">(</span>n<span class="token punctuation">.</span>pred<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token function">b1</span><span class="token punctuation">(</span>n<span class="token punctuation">.</span>pred<span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'B0'</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token function">b0</span><span class="token punctuation">(</span><span class="token function">binaryIncrement</span><span class="token punctuation">(</span>n<span class="token punctuation">.</span>pred<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'B1'</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token function">b1</span><span class="token punctuation">(</span><span class="token function">binaryIncrement</span><span class="token punctuation">(</span>n<span class="token punctuation">.</span>pred<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token keyword">undefined</span> <span class="token punctuation">}</span> </code></pre> <p>Das ist sozusagen die Grundschulmethode. Sie ist nicht besonders effizient, weil sich bei der Addition mit Eins im schlimmsten Fall alle Ziffern ändern können. Die Addition mit 1 ist also keine konstante Operation, sondern brauch O(log(n)). Die Gesamtlaufzeit der Konvertierung liegt deshalb bei O(n * log(n)).</p> <hr> <p><a href="/users/6547" class="mention registered-user" rel="noopener noreferrer">@Rolf B</a> hat einen Linear-Laufzeit-Algorithmus <a href="https://stackblitz.com/edit/typescript-unary-and-binary-number-encodings-rolf" rel="nofollow noopener noreferrer">implementiert</a>, der nicht auf der Addition mit 1 basiert, sondern auf der Multiplikation mit 2.</p> <p>Dafür hat er zunächst eine Helfer-Funktion geschrieben, die eine unäre Zahl durch 2 teilt und sich den Rest der Division merkt.</p> <pre><code class="block language-typescript"><span class="token keyword">type</span> <span class="token class-name">UQuotRem</span> <span class="token operator">=</span> <span class="token punctuation">{</span> q<span class="token operator">:</span> UNat<span class="token punctuation">,</span> r<span class="token operator">:</span> UNat <span class="token punctuation">}</span> <span class="token comment">// Ergebnistyp einer Division mit Rest</span> <span class="token keyword">function</span> <span class="token function">halfValue</span><span class="token punctuation">(</span>n <span class="token operator">:</span> UNat<span class="token punctuation">)</span> <span class="token operator">:</span> UQuotRem <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'zero'</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">{</span> q<span class="token operator">:</span> zero<span class="token punctuation">,</span> r<span class="token operator">:</span> zero <span class="token punctuation">}</span><span class="token punctuation">;</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>pred<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'zero'</span><span class="token punctuation">)</span> <span class="token keyword">return</span> <span class="token punctuation">{</span> q<span class="token operator">:</span> zero<span class="token punctuation">,</span> r<span class="token operator">:</span> <span class="token function">u0</span><span class="token punctuation">(</span>zero<span class="token punctuation">)</span><span class="token punctuation">}</span><span class="token punctuation">;</span> <span class="token keyword">const</span> half <span class="token operator">=</span> <span class="token function">halfValue</span><span class="token punctuation">(</span>n<span class="token punctuation">.</span>pred<span class="token punctuation">.</span>pred<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token punctuation">{</span> q<span class="token operator">:</span> <span class="token function">u0</span><span class="token punctuation">(</span>half<span class="token punctuation">.</span>q<span class="token punctuation">)</span><span class="token punctuation">,</span> r<span class="token operator">:</span> half<span class="token punctuation">.</span>r<span class="token punctuation">}</span> <span class="token punctuation">}</span> </code></pre> <p>Die <code>unary2binary</code>-Funktion sah dann wie folgt aus.</p> <pre><code class="block language-typescript"><span class="token keyword">function</span> <span class="token function">unaryToBinary</span><span class="token punctuation">(</span>n<span class="token operator">:</span> UNat<span class="token punctuation">)</span> <span class="token operator">:</span> BNat <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token function">u2b</span><span class="token punctuation">(</span>zero<span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">function</span> <span class="token function">u2b</span><span class="token punctuation">(</span>b<span class="token operator">:</span> BNat<span class="token punctuation">,</span> u<span class="token operator">:</span> UNat<span class="token punctuation">)</span> <span class="token operator">:</span> BNat <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>u<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'zero'</span><span class="token punctuation">)</span> <span class="token keyword">return</span> b<span class="token punctuation">;</span> <span class="token keyword">const</span> half <span class="token operator">=</span> <span class="token function">halfValue</span><span class="token punctuation">(</span>u<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token punctuation">(</span>half<span class="token punctuation">.</span>r<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'zero'</span><span class="token punctuation">)</span> <span class="token operator">?</span> <span class="token function">u2b</span><span class="token punctuation">(</span><span class="token function">b0</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">,</span> half<span class="token punctuation">.</span>q<span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token comment">// u war gerade</span> <span class="token function">u2b</span><span class="token punctuation">(</span><span class="token function">b1</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">,</span> half<span class="token punctuation">.</span>q<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// u war ungerade</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> </code></pre> <p>Der Vorteil ist ganz klar, dass die Mulitplikation mit 2 eine konstante Operation für die binären Zahlen ist. So ergibt sich für Rolfs Lösung eine Gesamtlaufzeit für die Konvertierung von O(n).</p> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774142#m1774142 1unitedpower 2020-08-04T19:33:17Z 2020-08-04T19:33:17Z Informatik zum Dienstag <blockquote> <p>ohne deine Helferfunktionen wüsste man zu wenig.</p> <p>Frage wäre gewesen: n sei die Binärcodierung einer natürlichen Zahl und val(n) der Zahlenwert dazu. Ist dann <code>val(b0(n)) == val(n)</code> oder <code>val(b0(n)) == 2*val(n)</code>? Meint: Setzt b0(n) ein neues most significant bit oder ein neues least significant. Dein Helper macht klar: es ist ersteres.</p> </blockquote> <p>Stimmt, danke für die Ergänzung.</p> <blockquote> <p>Frage ist aber auch: Ist die rekursive Darstellung der unären und binären Codierung vorgegeben? Oder darf ich auch eine andere Implementierung der Peano- oder Binärcodierung benutzen, solange ich dabei keine Zahlen verwende? Ich denke da an ein Array, auf das ich push, pop, shift oder unshift anwenden könnte.</p> </blockquote> <p>Ich bin auch gespannt auf Lösungen mit alternativen Definitionen für die Kodierungen. Die Vorlage war eine reine Hilfestellung und muss nicht benutzt werden.</p> <blockquote> <p>Allgemeiner gefragt: Welchen Funktionsumfang hat deine zahlenlose Sprache? JavaScript minus Number? Oder noch weniger?</p> </blockquote> <p>Meine Sprache ist noch dramatisch reduzierter, sie ist ein rein akademisches Experiment, das würde hier aber zu weit führen. Sie dient als prototypsche Sprache, um die <a href="https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence" rel="nofollow noopener noreferrer">Curry-Howard Korrespondenz</a> auf kombinatorische Logik auszuweiten. Das wäre von praktischem Nutzen für die Implementierung von Compilern für funktionale Programmiersprachen und (semi-)automatischen Beweisassistenten. Die Sprache eignet sich nicht wirklich, um darin zu programmieren, sie ist mehr eine Zwischensprache, wie WebAssembly oder die JVM, die unter der Haube von Programmiersprachen benutzt wird. Beim Entwickeln von Fallballbeispielen bin ich kürzlich auf dieses Problem der Umkodierungen gestoßten und dachte mir, das hat einen Rätsel-Charakter und könnte vielleicht jemanden aus dem Forum Spaß machen. Deshalb habe ich TypeScript/JavaScript als Sprache für die Aufgabe gewählt, weil damit wohl viele Selfler vertraut sind.</p> <blockquote> <p>Und ich nehme mal an, dass binaryLength bei der Implementierung von unaryToBinary nicht als Helper zur Verfügung steht, gelle?</p> </blockquote> <p>Korrekt, die Funktion benutzt ja unter der Haube JavaScript nativen number-Typen.</p> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774144#m1774144 1unitedpower 2020-08-04T19:42:41Z 2020-08-04T19:42:41Z Informatik zum Dienstag <blockquote> <p>Hallo 1unitedpower,</p> <p>by the way braucht man binaryLength gar nicht. Das verleitet nur zum cheaten. Man muss nur binaryToNumber etwas umgestalten:</p> <pre><code class="block language-js"><span class="token keyword">function</span> <span class="token function">binaryToNumber</span><span class="token punctuation">(</span><span class="token parameter"><span class="token literal-property property">n</span> <span class="token operator">:</span> BNat</span><span class="token punctuation">)</span> <span class="token operator">:</span> number <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token function">b2n</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> n<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token keyword">function</span> <span class="token function">b2n</span><span class="token punctuation">(</span><span class="token parameter"><span class="token literal-property property">val</span><span class="token operator">:</span> number<span class="token punctuation">,</span> <span class="token literal-property property">n</span><span class="token operator">:</span> BNat</span><span class="token punctuation">)</span> <span class="token operator">:</span> number <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'zero'</span><span class="token punctuation">)</span> <span class="token keyword">return</span> val<span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token function">b2n</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token operator">*</span>val <span class="token operator">+</span> <span class="token punctuation">(</span>n<span class="token punctuation">.</span>tag <span class="token operator">===</span> <span class="token string">'B1'</span> <span class="token operator">?</span> <span class="token number">1</span> <span class="token operator">:</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span> n<span class="token punctuation">.</span>pred<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> </code></pre> </blockquote> <p>Sehr gut, gefällt mir wesentlich besser als meine eigene Implementierung. Du sparst nicht nur die wiederholte Berechnung der Länge, sondern hast auch noch einen tail-rekursiven Ansatz und sparst darurch Platz auf dem Callstack.</p> <blockquote> <p>Die Abfrage <code>n.tag === 'zero'</code> statt <code>n === zero</code> hilft TypeScript bei der korrekten Typdiskriminierung. Ich könnte sonst <code>n.pred</code> nicht verwenden.</p> </blockquote> <p>Seltsam, dass die Typ-Verfeinerung in einem Fall klappt und im anderen nicht.</p> <blockquote> <p>Warum hast Du eigentlich Zero, U0, B0 und B1 als interface definiert und nicht als type? Ich habe ja von TypeScript fast gar keine Ahnung…</p> </blockquote> <p>Da habe ich mir nichts bei gedacht, für die Vorlage ist das wohl äquivalent. Eine type-Deklaration wäre wohl sogar etwas schöner, weil intuitiver, gewesen.</p> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774150#m1774150 Rolf B 2020-08-04T21:28:58Z 2020-08-04T21:28:58Z Informatik zum Dienstag <p>Hallo 1unitedpower,</p> <p>ok, hab eine Lösung basierend auf deinen Typen.</p> <p>Benutzte Sprachfeatures: Abfragen (if und ?:), Funktionsaufruf mit Parametern, Rekursion, Bilden von Tupeln, Test auf Gleichheit, Merken von Werten in const-Speicherplätzen. Das war's.</p> <p>Alternative Implementierungen zu verwenden ist so eine Sache. Angesichts deiner u0/b0/b1 Funktionen, die die Werte definieren, ist die rekursive Konstruktion fast schon vorgegeben. Heute habe ich dafür keinen Nerv mehr.</p> <p>Ich stolpere - rein logisch - vor allem über eine dusselige Eigenschaft von b0 (value als Shortcut für binaryToNumber):</p> <p>Es ist: <code>value(n) == value(b0(n))</code>, d.h. <code>b0(n)</code> codiert die gleiche natürliche Zahl wie <code>n</code>.</p> <p>Aber <code>n</code> und <code>b0(n)</code> sind nicht gleich, denn: <code>value(b1(n)) != value(b1(b0(n)))</code></p> <p>Hatten wir das Thema mit führenden Nullen, die Durcheinander anrichten, letztens nicht schonmal bei den milliardenstelligen Ziffernfolgen?</p> <p>Am liebsten wäre mir ja, wenn diese Definitionen gelten würden, mit value(n) als der von n codierte Zahlenwert:</p> <pre><code class="block">b0(zero) := zero value(b0(n)) := 2*value(n) value(b1(n)) := 2*value(n)+1 </code></pre> <p>Aber ob damit <code>unaryTobinary</code> so einfach realisierbar ist, hmmm. Spieglein, Spiegelein...</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - obstruxi </div> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774164#m1774164 1unitedpower 2020-08-05T08:20:42Z 2020-08-05T08:20:42Z Informatik zum Dienstag <blockquote> <p>ok, hab eine Lösung basierend auf deinen Typen.</p> </blockquote> <p>Sehr schöne Lösung übrigens. Mal wieder effizienter als meine eigene </p> <blockquote> <p>Ich stolpere - rein logisch - vor allem über eine dusselige Eigenschaft von b0 (value als Shortcut für binaryToNumber):</p> <p>Es ist: <code>value(n) == value(b0(n))</code>, d.h. <code>b0(n)</code> codiert die gleiche natürliche Zahl wie <code>n</code>.</p> <p>Aber <code>n</code> und <code>b0(n)</code> sind nicht gleich, denn: <code>value(b1(n)) != value(b1(b0(n)))</code></p> </blockquote> <p>Man könnte das Problem auch auf Typ-Ebene beseitigen, indem man die binären Zahlen so beschränkt, dass an der signifikanteste Position immer die Ziffer <code>b1</code> stehen muss. Dann hätte man eine normalisierte, eindeutige Kodierung. In TypeScript:</p> <pre><code class="block language-typescript"><span class="token keyword">type</span> <span class="token class-name">BNatSuffix</span> <span class="token operator">=</span> Zero <span class="token operator">|</span> <span class="token constant">B0</span> <span class="token operator">|</span> <span class="token constant">B1</span> <span class="token comment">// Binärzahlen mit potenziell führenden Nullen</span> <span class="token keyword">type</span> <span class="token class-name">BNat</span> <span class="token operator">=</span> Zero <span class="token operator">|</span> <span class="token constant">B1</span> <span class="token comment">// Normalisierte Binärzahlen</span> </code></pre> <p>Die Definitionen müssten entsprechend angepasst werden.</p> <blockquote> <p>Hatten wir das Thema mit führenden Nullen, die Durcheinander anrichten, letztens nicht schonmal bei den milliardenstelligen Ziffernfolgen?</p> </blockquote> <blockquote> <p>Am liebsten wäre mir ja, wenn diese Definitionen gelten würden, mit value(n) als der von n codierte Zahlenwert:</p> <pre><code class="block">b0(zero) := zero value(b0(n)) := 2*value(n) value(b1(n)) := 2*value(n)+1 </code></pre> </blockquote> <p>Das löst auf jeden Fall das Problem, dass du oben beschrieben hast (ich gehe mal davon aus, dass die erste Zeile <code>value(zero) = 0</code> lauten sollte). Die Binärkodierung ist damit aber auch nicht eindeutig: Jede Zahl kann dann beliebig viele abschließende b0-Ziffern haben.</p> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774165#m1774165 Rolf B 2020-08-05T08:41:24Z 2020-08-05T08:41:24Z Informatik zum Dienstag <p>Hallo 1unitedpower,</p> <blockquote> <p>ich gehe mal davon aus, dass die erste Zeile value(zero) = 0 lauten sollte</p> </blockquote> <p>Hm. Darüber musste ich erstmal nachdenken. Mein b0(zero) := zero soll aussagen, dass ich eine Binärcodierung nicht mit einer 0 beginnen kann. Versuche ich es, passiert einfach nichts. Es verbietet allerdings auch die Konstruktion eines Codes für den Wert 0, das habe ich übersehen. Das ist bei deiner Typdefinition ebenfalls der Fall.</p> <blockquote> <p>Die Binärkodierung ist damit aber auch nicht eindeutig</p> </blockquote> <p>Das Witzige ist, dass die Forderung <code>value(b0(n)) := 2*value(n)</code> überhaupt nichts über die Art des Codes aussagt. Es verlangt nur, dass die Operation b0 einen Code liefert, dessen Wert dem Doppelten des Ausgangscodes entspricht. Das <strong>kann</strong> man dadurch implementieren, indem man an eine Binärzahl eine 0 anhängt. Oder anders, irgendwie, tief in einer Blackbox, z.b. unär codiert durch Verdoppeln der Ziffern. Aber nehmen wir an, b0 und b1 konstruieren eine Liste aus Einsen und Nullen. Dann kann ich eben nicht beliebig viele Nullen anhängen, ohne den Wert zu verändern.</p> <p>Also lassen wir das, das ufert aus.</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - obstruxi </div> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774394#m1774394 Rolf B 2020-08-10T09:06:05Z 2020-08-10T09:06:05Z Lösung <p>Hallo 1unitedpower,</p> <p>mit Komplexitätsbestimmungen bin ich auf Kriegsfuß. Es hat mich jetzt etwas Überlegung gekostet, warum eine Schachtelung von zwei Schleifen lineare Laufzeit haben sollte </p> <p>Aber ist schon klar. Für die erste Binärziffer gibt's n/2 Durchläufe im Halbierer. Für die zweite sind es n/4, und so weiter, in Summe irgendwas zwischen n/2 und n.</p> <p><em>Rolf</em></p> <div class="signature">-- <br> sumpsi - posui - obstruxi </div> https://forum.selfhtml.org/self/2020/aug/04/informatik-zum-dienstag/1774402#m1774402 1unitedpower 2020-08-10T09:40:39Z 2020-08-10T09:46:43Z Lösung <blockquote> <p>Aber ist schon klar. Für die erste Binärziffer gibt's n/2 Durchläufe im Halbierer. Für die zweite sind es n/4, und so weiter, in Summe irgendwas zwischen n/2 und n.</p> </blockquote> <p>Genau, die Summe <code>n/2 + n/4 + n/8 + …</code> konvergiert gegen <code>n</code>. Man kann sogar zeigen, dass dein Algorithmus hinsichtlich Laufzeit nicht zu überbieten ist. Wenn es einen Algorithmus mit geringerer Laufzeitschranke gäbe, würde er nicht alle Ziffern der Eingabe lesen, das heißt, er würde manche Eingaben nicht unterscheiden können und falsche Ergebnisse liefern (da die zu berechnende Funktion bijektiv ist). Für eine korrekte Lösung ist <code>O(n)</code> deshalb optimal.</p>