Hackerboard WikiHaboBlog

[HaBo]

 
Programmieraufgaben Hier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann.

X * y < z ?

Diskussion: X * y < z ? im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Zitat: Zitat von sw33tlull4by 2+4+7+8 = 21 für 170 1+2+4+7+8 = 22 für 171 voilá. Meinst Du, dass man letzendlich ...
Antwort
Seite 2 von 2 1 2
Themen-Optionen Ansicht
   
Alt 25.11.09, 10:43   #16 (permalink)
CDW
Moderator
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 156
Standard


Zitat:
Zitat von sw33tlull4by Beitrag anzeigen
2+4+7+8 = 21 für 170
1+2+4+7+8 = 22 für 171
voilá.
Meinst Du, dass man letzendlich nur die Summe der Exponenten vergleichen soll? Mein erster "intuitiver" Gedanke war nämlich wirklich die einzelnen Exponenten zu vergleichen. Denn die Summe ist imho nicht eindeutig.
Bsp:
2+4+6+8=20 für 170
2^1+2^2+2^5+2^8=294 bzw. Potenzerhöhung:
2+3+6+9=20 für 294

Oder habe ich das falsch verstanden?
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 26.11.09, 18:29   #17 (permalink)
Senior Member
 
Benutzerbild von sw33tlull4by
 
Registriert seit: 12.06.07
sw33tlull4by Leistung: Facit NTK
Likes: 0
Standard
Zitat:
Meinst Du, dass man letzendlich nur die Summe der Exponenten vergleichen soll? Mein erster "intuitiver" Gedanke war nämlich wirklich die einzelnen Exponenten zu vergleichen. Denn die Summe ist imho nicht eindeutig.
Bsp:
2+4+6+8=20 für 170
2^1+2^2+2^5+2^8=294 bzw. Potenzerhöhung:
2+3+6+9=20 für 294
Stimmt.
__________________
Nur die Schwachen klammern sich an die Moral.

Kill my daemons and my angels will follow them.
sw33tlull4by ist offline   Mit Zitat antworten
Alt 26.11.09, 20:48   #18 (permalink)
CDW
Moderator
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 156
Standard
Hier mal ein PoC in Prolog:
SWI   
Code:
bit_power(0,[]).
bit_power(Num,[2^Exp|Res]):- Exp is msb(Num),             %hier etwas gecheatet
                             NewNum is Num >< (1<<Exp),   %performanter Weg wäre
                             bit_power(NewNum,Res),!.     %aber aufwendiger umzusetzen

%zusammenfassen, da bei der "Multiplikation" auch
%[2^4, 2^2, 2^3, 2^1, 2^2, 2^0] als Ergebnis auftreten kann
trans([],[]).
trans([X],[X]).
trans([2^X,2^X|T],[2^Y|Res]):-Y is X+1,trans(T,Res),!.
trans([X,Y|T],[X|Res]):- X\=Y,trans([Y|T],Res),!.

transform(ExpList,Result):-msort(ExpList,Sorted),
                           trans(Sorted,Trans),
                           Sorted\=Trans,
                           transform(Trans,Result),!.
transform(Result,Result).
%'Kreuzaddition'
mul_exps(ExpList1,ExpList2,Res):-
        findall(2^ExpSum,(
                           member(2^Exp1,ExpList1),
                           member(2^Exp2,ExpList2),
                           ExpSum is Exp1+Exp2
                         ),Sums),
        transform(Sums,Trans),
        sort(Trans,Sorted),reverse(Sorted,Res).

cmp_pow([2^Exp1|_],[2^Exp2|_]):- Exp1<Exp2,!.             %ist ein Exponent kleiner =>fertig
cmp_pow([2^Exp1],[2^Exp2|T]):- T\=[],Exp1=:=Exp2,!.       %mehr Exponenten vorhanden =>eher größer
cmp_pow([2^Exp1|List1],[2^Exp2|List2]):- Exp1=:=Exp2,
                  cmp_pow(List1,List2),!.

compare(X*Y<Z):- bit_power(X,XBit),write(X=XBit),nl,
                 bit_power(Y,YBit),write(Y=YBit),nl,
                 bit_power(Z,ZBit),write(Z=ZBit),nl,
                 mul_exps(XBit,YBit,Mul),write(X*Y=Mul),nl,
                 cmp_pow(Mul,ZBit).

Zerlegt die Eingabe in 2-er Potenzen und
operiert damit. Eingabe in "natürlicher" Syntax: compare(X*Y<Z)

Bsp/Ausgabe   

Code:
7 ?- compare(7*5<35).
7=[2^2, 2^1, 2^0]
5=[2^2, 2^0]
35=[2^5, 2^1, 2^0]
7*5=[2^5, 2^1, 2^0]
false.

8 ?- compare(7*5<36).
7=[2^2, 2^1, 2^0]
5=[2^2, 2^0]
36=[2^5, 2^2]
7*5=[2^5, 2^1, 2^0]
true.

9 ?- compare(71*35<36).
71=[2^6, 2^2, 2^1, 2^0]
35=[2^5, 2^1, 2^0]
36=[2^5, 2^2]
71*35=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^0]
false.

10 ?- X is 71*35.
X = 2485.

11 ?- compare(71*35<2485).
71=[2^6, 2^2, 2^1, 2^0]
35=[2^5, 2^1, 2^0]
2485=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^0]
71*35=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^0]
false.

12 ?- compare(71*35<2486).
71=[2^6, 2^2, 2^1, 2^0]
35=[2^5, 2^1, 2^0]
2486=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^1]
71*35=[2^11, 2^8, 2^7, 2^5, 2^4, 2^2, 2^0]
true.
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Antwort
Seite 2 von 2 1 2
   

Werbung ist gerade online    

[HaBo] » Software Home » Code Kitchen » Programmieraufgaben » X * y < z ?
« Vorheriges Thema | Nächstes Thema »
Themen-Optionen
Ansicht
Linear-Darstellung Linear-Darstellung

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.
BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks sind aus
Pingbacks sind aus
Refbacks sind aus

Alle Zeitangaben in WEZ +1. Es ist jetzt 00:39 Uhr.
vBulletin® v3.8.7, Copyright ©2000-2012, vBulletin Solutions, Inc.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61