Zahl ohne *, /, +, - und % durch 3 dividieren
Zahl ohne *, /, +, - und % durch 3 dividieren
Mal wieder eine kleine Denkaufgabe
Wie kann man einen Integer durch 3 dividieren, ohne die Operatoren *, /, +, - oder % zu verwenden?
Vorweg: Das ist keine Fangfrage. Das Problem ist wirklich programmiertechnisch zu lösen und wurde angeblich bei einem Oracle-Jobinterview gestellt.
Lösung:
http://stackoverflow.com/questions/1169 ... -operators
Wie kann man einen Integer durch 3 dividieren, ohne die Operatoren *, /, +, - oder % zu verwenden?
Vorweg: Das ist keine Fangfrage. Das Problem ist wirklich programmiertechnisch zu lösen und wurde angeblich bei einem Oracle-Jobinterview gestellt.
Lösung:
http://stackoverflow.com/questions/1169 ... -operators
- Xin
- nur zu Besuch hier
- Beiträge: 8858
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Also nur Bit-Operatoren?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Das wäre eine Möglichkeit, es gibt aber noch andere.Xin hat geschrieben:Also nur Bit-Operatoren?
- cloidnerux
- Moderator
- Beiträge: 3123
- Registriert: Fr Sep 26, 2008 4:37 pm
- Wohnort: Ram (Gibts wirklich)
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Man kann es auch nähern.Das wäre eine Möglichkeit, es gibt aber noch andere.
Sei a der Quotient und x der Ergebnis, so ist a / 2 * 2/3= x, das Ergebnis der Division durch 2 liegt also etwas über dem zu erwarteten Ergebnis.
a / 4 * 4/3 = x, die Division der zahl durch 4 liegt also etwas unter dem Ergebnis.
Addiert man nun das Ergebnis der Division durch 4 und der Division durch 2(Division per Shift) und shiftet dieses wieder um 2(Mittelwert), erhält man das voraussichtliche Ergebnis der Division durch 3(Bei Zahlen bis 1k >2% Fehler). Eine Addition lässt sich Bitweise nach dem Volladdierer bauen, indem man sich durch die Bits iteriert, der ++ Operator ist ja nicht verboten.
Verbessern lässt sich das Ergebnis durch bessere Aufteilung der Division von 4 und 2, man nur beachten das die gesamtsumme 2^n entspricht.
Redundanz macht wiederholen unnötig.
quod erat expectandum
quod erat expectandum
- Xin
- nur zu Besuch hier
- Beiträge: 8858
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Ich habe durch Fragen meiner Möglichkeiten an dani93 und dem einen oder anderen Tipp, worauf er hinauswill, eine ziemlich kranke Lösung gefunden:
Man lege eine Datei der Größe X an und lese anschließend X Blöcke der Größe 3 Bytes ein. Das passt nicht, denn das wären ja 3*x Bytes. Also ist nach X/3 Blöcken Schluss und das gibt fread zurück.
Das Ziel ist also wirklich, kranke Lösungen zu finden, um die Operatoren nicht selbst zu verwenden.
Vielleicht kann dani93 ja mal die eine oder andere Lösung vorstellen, sofern niemand mehr einen Versuch starten möchte.
Man lege eine Datei der Größe X an und lese anschließend X Blöcke der Größe 3 Bytes ein. Das passt nicht, denn das wären ja 3*x Bytes. Also ist nach X/3 Blöcken Schluss und das gibt fread zurück.
Das Ziel ist also wirklich, kranke Lösungen zu finden, um die Operatoren nicht selbst zu verwenden.
Vielleicht kann dani93 ja mal die eine oder andere Lösung vorstellen, sofern niemand mehr einen Versuch starten möchte.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
- fat-lobyte
- Beiträge: 1398
- Registriert: Sa Jul 05, 2008 12:23 pm
- Wohnort: ::1
- Kontaktdaten:
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Also ich hätt da mittlerweile doch noch eine Idee. Hat zwar nichts mehr mit optimierung zu tun, aber funktionieren tuts.
Haters gonna hate, potatoes gonna potate.
- fat-lobyte
- Beiträge: 1398
- Registriert: Sa Jul 05, 2008 12:23 pm
- Wohnort: ::1
- Kontaktdaten:
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?
Haters gonna hate, potatoes gonna potate.
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Dann nur her damitfat-lobyte hat geschrieben:Also ich hätt da mittlerweile doch noch eine Idee. Hat zwar nichts mehr mit optimierung zu tun, aber funktionieren tuts.
Kannst du natürlich auch machen ^^ Die Angabe ist etwas schwammig formuliert, aber das bedeutet auch, dass du kein ++, --, +=, -= usw. verwenden darfst. Das kannst du dir aber natürlich auch selber bauen ^^fat-lobyte hat geschrieben:Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?
Es geht nicht darum eine optimierte oder besonders elegante Lösung zu finden. Es geht darum auf etwas an sich selbstverständliches zu verzichten und trotzdem ans Ziel zu kommen. Die von Xin beschriebene Lösung ist alles andere als optimal oder elegant, aber sie führt zum Ziel und erfüllt die Kriterien.
- Xin
- nur zu Besuch hier
- Beiträge: 8858
- Registriert: Fr Jul 04, 2008 11:10 pm
- Wohnort: /home/xin
- Kontaktdaten:
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Das Schwammige war auch der Grund, weswegen ich Dich quasi so lange fragte, was erlaubt war, bis klar war, dass ich die Std-Lib habe und andere Dinge notfalls von Hand nachbauen kann.dani93 hat geschrieben:Kannst du natürlich auch machen ^^ Die Angabe ist etwas schwammig formuliert, aber das bedeutet auch, dass du kein ++, --, +=, -= usw. verwenden darfst. Das kannst du dir aber natürlich auch selber bauen ^^fat-lobyte hat geschrieben:Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?
War ++/-- nicht nun auch nicht erlaubt?
Fragen aus Jobinterviews, die ich hatte waren "Wieviele Menschen spielen jetzt in Neuseeland Golf?", "Warum sind Gullideckel rund?" oder "Was wiegt eine Jumbojet beim Start?"
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
- fat-lobyte
- Beiträge: 1398
- Registriert: Sa Jul 05, 2008 12:23 pm
- Wohnort: ::1
- Kontaktdaten:
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Code: Alles auswählen
#include <cmath>
inline int my_round(long double d)
{ return (d + 0.5L); }
int divide_by_3(int x)
{
return my_round(
tan(static_cast<long double>(atan2(
static_cast<long double>(x),3.0L))
));
}
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Haters gonna hate, potatoes gonna potate.