Seite 1 von 2
Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Mo Jul 30, 2012 3:38 pm
von nufan
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
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Mo Jul 30, 2012 4:58 pm
von Xin
Also nur Bit-Operatoren?
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Mo Jul 30, 2012 6:03 pm
von nufan
Xin hat geschrieben:Also nur Bit-Operatoren?
Das wäre eine Möglichkeit, es gibt aber noch andere.
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Mo Jul 30, 2012 10:07 pm
von cloidnerux
Das wäre eine Möglichkeit, es gibt aber noch andere.
Man kann es auch nähern.
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.
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Fr Aug 03, 2012 12:04 am
von Xin
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.
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Fr Aug 03, 2012 1:49 am
von fat-lobyte
Also ich hätt da mittlerweile doch noch eine Idee. Hat zwar nichts mehr mit optimierung zu tun, aber funktionieren tuts.
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Fr Aug 03, 2012 2:33 am
von fat-lobyte
Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Fr Aug 03, 2012 2:40 am
von nufan
fat-lobyte hat geschrieben:Also ich hätt da mittlerweile doch noch eine Idee. Hat zwar nichts mehr mit optimierung zu tun, aber funktionieren tuts.
Dann nur her damit
fat-lobyte hat geschrieben:Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?
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 ^^
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.
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Fr Aug 03, 2012 8:44 am
von Xin
dani93 hat geschrieben:fat-lobyte hat geschrieben:Was hindert einen eigentlich daran, die Integerdivision mit Bitoperatoren nachzubauen? Ich nehme an, das ist nicht der Sinn der Aufgabe?
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 ^^
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.
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?"
Re: Zahl ohne *, /, +, - und % durch 3 dividieren
Verfasst: Mi Aug 08, 2012 11:58 am
von fat-lobyte
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))
));
}