Ausgabe in C
-
#include <stdio.h> #include <stdlib.h> static void writeBinary(int n, int *c) { if (n != 0) { ungetc(n % 2 + '0', stdin); writeBinary(n / 2, c); (*c)++; } } void toBinary(int n, char **s) { int c = 0; ungetc(' ', stdin); writeBinary(n, &c); *s = (char*) malloc(sizeof(char) * c + 1); scanf("%s", *s); } int main() { char *s = NULL; toBinary(8, &s); printf("%s\n",s); free(s); return 0; }
-
Was haltet Ihr denn von dieser Herangehensweise?
#include <stdio.h> #include <stdlib.h> #include <assert.h> void print_binary(unsigned int number) { unsigned int flag = 1 << ((sizeof(unsigned int) * CHAR_BIT) - 1); /* directly print 0 if number is 0 */ if (!number) { putchar(number + '0'); return; } /* cut off leading zeros */ while (!(number & flag)) flag >>= 1; /* print the result */ while (flag) { putchar(number & flag ? '1' : '0'); flag >>= 1; } } typedef struct binary_string { /* guaranteed to be big enough to hold all bits of an unsigned int plus the terminating null character */ char buffer[(sizeof(unsigned int) * CHAR_BIT) + 1]; } binstr_t; void to_binary(unsigned int number, binstr_t * output) { unsigned int n = (sizeof(unsigned int) * CHAR_BIT) - 1; char * p = NULL; assert(output != NULL); p = output->buffer; /* almost the same like above */ if (!number) { output->buffer[0] = '0'; output->buffer[1] = '\0'; return; } while (!(number & (1 << n))) --n; do { *p++ = (number & (1 << n)) ? '1' : '0'; } while(n--); *p = '\0'; } int main(void) { unsigned int n = 0; binstr_t str; for (; n < 16; ++n) { printf("print_binary: "); print_binary(n); putchar('\n'); to_binary(n, &str); printf("to binary: %s\n", str.buffer); } return 0; }
-
Steffo schrieb:
#include <stdio.h> #include <stdlib.h> static void writeBinary(int n, int *c) { if (n != 0) { ungetc(n % 2 + '0', stdin); writeBinary(n / 2, c); (*c)++; } } void toBinary(int n, char **s) { int c = 0; ungetc(' ', stdin); writeBinary(n, &c); *s = (char*) malloc(sizeof(char) * c + 1); scanf("%s", *s); }Diese Art des Missbrauchs von ungetc ist durch den Standard nicht gedeckt:
ISO/IEC 9899:1999 7.19.7.11 (3) schrieb:
One character of pushback is guaranteed. If the ungetc function is called too many times on the same stream without an intervening read or file positioning operation on that stream, the operation may fail.
Ich sehe auch nicht, was man hier groß mit Rekursion wollen sollte. Geht auch, aber die Gruppierung wird auf die Weise ziemlich umständlich, und Performancevorteile darf man sich in diesem Fall von einem rekursiven Vorgehen sicher nicht versprechen.
Eine einfache Möglichkeit, die ganze Problematik mit der Suche nach der Länge des Ergebnisstrings zu umgehen, ist, von hinten zu schreiben und einen Zeiger mitten in den Buffer als String zu benutzen. Ich stelle mir das etwa so vor:
#include <limits.h> #include <stddef.h> #include <stdio.h> #include <string.h> char *binary_representation(char *buffer, size_t buflen, unsigned x) { char *p = buffer + buflen - 1; size_t used = 0; int group = 0; do { ++used; if(used >= buflen) return NULL; --p; if(group == 4) { group = 0; *p = ' '; } else { ++group; *p = (x & 1) + '0'; x >>= 1; } } while(x != 0); buffer[buflen - 1] = '\0'; return p; /* * Wenn man die Daten unbedingt am Anfang des Eingabebuffers haben will, * kann man hier statt der letzten zwei Zeilen * * memmove(buffer, p, used); * buffer[used] = '\0'; * return buffer; * * schreiben. Frisst natürlich etwas mehr Laufzeit, aber für Linksjustierung * braucht man halt ein Zwischenergebnis. */ } int main(void) { char buffer[100]; char *bin; bin = binary_representation(buffer, sizeof(buffer), 1234); if(bin) { puts(bin); } return 0; }
-
seldon schrieb:
Diese Art des Missbrauchs von ungetc ist durch den Standard nicht gedeckt:
ISO/IEC 9899:1999 7.19.7.11 (3) schrieb:
One character of pushback is guaranteed. If the ungetc function is called too many times on the same stream without an intervening read or file positioning operation on that stream, the operation may fail.
Dann nimmt man halt einen Stack oder so etwas ähnliches. Jedenfalls ist Rekursion hier m. A. n. eleganter. Und das Performance-Argument zählt nicht. Weshalb?
Nehmen wir mal an, man will 1000 000 000 in binär umwandeln. Wieviel rekursive Aufrufe sind das? Das sind aufgerundet genau log2(1000 000 000) = 30 Aurufe --> Sich hier Performancegedanken zu machen, ist fehl am Platz.Schau dir mal meine Schnittstelle an (Parameter: beliebige Zahl, mit NULL initialisierter Pointer) und deine Schnittstelle (Parameter: buffer, mit der fixen Größe 100, Größe des Buffers und beliebige Zahl). Bei meiner Methode hat der Endanwender weniger Arbeit und muss sich weniger Gedanken machen.
L. G.
Steffo
-
Ich sehe irgendwie dein Argument nicht. Es geht wunderbar als Schleife. Rekursion ist hier technisch gar nicht nötig, es ist bloß eine andere Art, die Schleife zu schreiben.
-
SeppJ schrieb:
Ich sehe irgendwie dein Argument nicht. Es geht wunderbar als Schleife. Rekursion ist hier technisch gar nicht nötig, es ist bloß eine andere Art, die Schleife zu schreiben.
Alles geht als Schleife. Selbst nicht endrekursive Aufrufe kann man in Schleifen mit Stack umwandeln. Die Frage ist hier, was eleganter ist und dennoch eine zufriedenstellende Performance hergibt.
-
Ob Performance von Interesse ist, hängt stark davon ab, wie oft solche Umwandlungen geschehen sollen. So oder so ist aber die Vorstellung, dass 30 Funktionsaufrufe für die Umwandlung einer Ganzzahl in Binärnotation eine vernünftige Implementation wären, ziemlich albern.
Was die Schnittstelle angeht, die hat mit den Implementationsdetails hier ziemlich wenig zu tun. Den Code, mit dem man die gleiche Schnittstelle nachbilden kann, habe ich ja schon in den Kommentar geschrieben - auch mit memmove hinten drangehängt dürfte das allemal schneller sein als die Rekursion, und wenn du zusätzlich zur Rekursion noch einen Stack benutzen willst, mit ziemlicher Sicherheit auch übersichtlicher. Die Gruppierung in Nibbles hattest du übrigens auch nicht erschlagen, und das ist rekursiv auch nicht wirklich elegant zu machen. Oder?
-
seldon schrieb:
Ob Performance von Interesse ist, hängt stark davon ab, wie oft solche Umwandlungen geschehen sollen. So oder so ist aber die Vorstellung, dass 30 Funktionsaufrufe für die Umwandlung einer Ganzzahl in Binärnotation eine vernünftige Implementation wären, ziemlich albern.
Worauf willst du hinaus? Dass viele Sortier- und Suchalgorithmen albern sind? Dass Rekursion an sich albern ist? 30 Funktionsaufrufe sind nichts! Stackoverflow? Gar nicht möglich! Viel zu wenig Aufrufe!
auch mit memmove hinten drangehängt dürfte das allemal schneller sein als die Rekursion
Von wieviel Mikrosekunden redest du?!
und wenn du zusätzlich zur Rekursion noch einen Stack benutzen willst, mit ziemlicher Sicherheit auch übersichtlicher.
Was ist bei einem stack.add(x) unübersichtlich? Das vereinfacht sogar meine Implementierung nochmals!
Die Gruppierung in Nibbles hattest du übrigens auch nicht erschlagen, und das ist rekursiv auch nicht wirklich elegant zu machen. Oder?
Das ist Sache der Ausgabe, nicht der Eingabe.
L. G.
Steffo
-
Ich vermutet mal Seldon will darauf hinaus, dass Dein Lösungsansatz einem mit "Kanonen auf Spatzen schiessen" entspricht.
-
Shiba schrieb:
Ich vermutet mal Seldon will darauf hinaus, dass Dein Lösungsansatz einem mit "Kanonen auf Spatzen schiessen" entspricht.
Laser-Kanone, wenn schon denn schon.
Mal was anderes:
Kann es sein, dass diese Webseite ziemlicher Mist ist?
http://www.acm.uiuc.edu/webmonkeys/book/c_guide/2.12.html#ungetcHier wird erstens nicht erwähnt, wie von Seldon behauptet, dass ungetc nur maximal ein einmaliges Zeicheneinlesen garantiert und danach ggf. die Operation misslingt, zweitens wird hier behauptet, dass das Einlesen nach dem FIFO-Prinzip erfolgt. Folgender Code ist aber eindeutig LIFO!
ungetc('2', stdin); ungetc('1', stdin); printf("%c", getchar()); printf("%c\n", getchar()); /* Liefert 12 */L. G.
Steffo
-
Du kannst nicht davon ausgehen, dass eine Funktion immer nur einmal aufgerufen wird. Stackoverflow ist hier in der Tat kein Thema, aber dass ein Holzklotz nicht explodieren kann, heißt nicht, dass er einen passablen Fußball abgäbe. Es mag Anwendungsfälle geben, in denen eine verhältnismäßig langsame Implementation völlig ausreicht, aber guter Stil ist selbige dadurch trotzdem nicht.
Die Frage, ob die Anwendung eines Stacks deine Implementation vereinfacht, stellt sich im Grunde erst dann, wenn du eine hast. Bislang hast du ja nur diesen Haufen undefinierten Verhaltens. Allerdings: Einen Stack musst du implementieren und in der Gegend herumreichen, wie auch die Position, an der geschrieben werden soll. Mit einer Funktion kommst du da schon nicht mehr hin (was an sich nicht unbedingt problematisch wäre), wenn du die Schnittstelle erhalten willst, und dass die Hilfsfunktion einfacher wird als eine simple Schleife, daran habe ich meine Zweifel.
Aber ich lasse mich gern überraschen. Zeig mal her, wie du dir das vorstellst. Kleiner Tip übrigens: Achte darauf, dass du auch zurechtkommst, wenn dir mal eine 0 übergeben wird.
Re: ungetc: Ich habe aus dem ISO-Standard zitiert. Was der sagt, das gilt, völlig unabhängig von dem, was in irgendeiner Referenz aus dem Netz nicht erwähnt wird.
-
Der Standard sagt zu
ungtc(), dass es einmal garantiert ist.
Es kann mehrmals funktionieren, muss es aber nicht.
-
seldon schrieb:
Du kannst nicht davon ausgehen, dass eine Funktion immer nur einmal aufgerufen wird. Stackoverflow ist hier in der Tat kein Thema, aber dass ein Holzklotz nicht explodieren kann, heißt nicht, dass er einen passablen Fußball abgäbe. Es mag Anwendungsfälle geben, in denen eine verhältnismäßig langsame Implementation völlig ausreicht, aber guter Stil ist selbige dadurch trotzdem nicht.
Ich finde den Stil ehrlich gesagt super (wenn man einen Stack nehmen würde) und um wieviel langsamer das ist, müsste man messen.
Einen Stack musst du implementieren
Das ist kein Problem, denn so ein Stack ist ja prinzipiell universell einsetzbar und deswegen schreibe ich hier keinen Stack für einen einzigen Anwendungsfall.
wie auch die Position, an der geschrieben werden soll.
Was für ne Position? Das kommt alles oben drauf mit der add-Funktion. Das ist ja das tolle am Stack - du brauchst keine Positionen mitangeben!
Aber ich lasse mich gern überraschen. Zeig mal her, wie du dir das vorstellst. Kleiner Tip übrigens: Achte darauf, dass du auch zurechtkommst, wenn dir mal eine 0 übergeben wird.
Sorry, würde ja gerne bei dem Contest mitmachen, muss aber Mathe lernen!
Kannst es ja selbst versuchen. Kleiner Tipp übrigens: Nicht so kompliziert denken. Re: ungetc: Ich habe aus dem ISO-Standard zitiert. Was der sagt, das gilt, völlig unabhängig von dem, was in irgendeiner Referenz aus dem Netz nicht erwähnt wird.
Das ist nicht irgendeine Referenz aus dem Netz, sondern die "Association for Computing Machinery", die ich über einen Wikipedia-Link entdeckt habe! Aber offensichtlich schreiben die ziemlichen Mist!
L. G.
Steffo
-
*seufz*
Du musst einen Stack herumreichen, in dem die Bits umgekehrt liegen, und du musst eine Positionsangabe herumreichen, wo sie nachher hingeschrieben werden sollen. Bedenke: Du befindest dich, wenn du das vorderste Zeichen schreiben willst, in der innersten Rekursionsebene! Du musst in den äußeren jeweils wissen, wo das bisherige Ende des Strings ist.
Ferner musst du, um die Gruppierung zu erreichen, herumreichen, wann der nächste Trenner eingefügt werden muss. Das sind alles lösbare Probleme, aber die Rekursion macht es unnötig umständlich.
Insgesamt wäre eine Queue für einen rekursiven Ansatz wohl zielführender; beides ist aber völliger Overkill.
-
Jetzt weiß ich wenigstens warum meine installierten Java-Programme so langsam laufen. Der Sprache werde ich die Schuld jedenfalls nicht mehr zuschieben.
-
Man kann in jeder Sprache Fortran schreiben
Man kann in jeder Sprache langsame Programme schreiben.
