prüfen auf teilbarkeit < Haskell < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Aufgabe | wir habe folgendes als aufgabe:
[mm] t:\IN \to [/mm] {1,0},wobei [mm] t(n)=\begin{cases} 0, & \mbox{für } n \mbox{sonst } \\ 1, & \mbox{für } n \mbox{ ganzahlig durch 5 teillbar }\end{cases}
[/mm]
|
in eine haskellfunktion zu programmieren.
Dies habe ich mittels modulo auch hinbekommen, nur möchte ich noch wissen ob dies auch in irgendeinerweise auch ohme 'mod' gehen würde.
Gruß niesel
|
|
| |
|
Hallo nieselfriem!
> wir habe folgendes als aufgabe:
>
> [mm]t:\IN \to[/mm] {1,0},wobei [mm]t(n)=\begin{cases} 0, & \mbox{für } n \mbox{sonst } \\ 1, & \mbox{für } n \mbox{ ganzahlig durch 5 teillbar }\end{cases}[/mm]
>
>
> in eine haskellfunktion zu programmieren.
> Dies habe ich mittels modulo auch hinbekommen, nur möchte
> ich noch wissen ob dies auch in irgendeinerweise auch ohme
> 'mod' gehen würde.
Hab' lange nichts mehr mit Haskell gemacht und war auch nie wirklich gut, aber kannst du nicht eine unendliche Liste definieren, die alle Vielfachen von 5 aufzählt, also sowas: [mm] \{5,10,..\} [/mm] oder so ähnlich müsste man das schreiben, und dann jede Zahl einfach testen, ob sie in dieser Menge drin ist?
Aber deine Lösung mit mod dürfte eigentlich die gewünschte und vor allem auch eleganteste sein, würde ich meinen.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
Naja die ganze sache hat folgenden Hintergrund in unserer Aufgabenstellung heißt es:
Geben Sie induktive Definitionen für die folgenden Funktionen an. Dabei dürfen Sie nur die
Funktionen t, q, p und d sowie die Addition und Subtraktion verwenden.
q::Int->Int
q x =3*x*x
q 0 =0
q(x+1) =q(x)+x+x+x+x+x+x+3
p::Int->Int
p x =x*x*x
p 0 =0
p(x+1) =p(x)+q(x)+x+x+x+1
t::Integer->Integer
t x | (((x 'mod' 5)==0)) =1
| otherwise =0
habe ich bereits nun weis ich nicht wie ich das mit der Funktion t tun soll
weiterhin habe ich noch die folgende Funktion
d : N → N, d(x) = y , wobei 3 ⋅ y ≤ x und 3 ⋅ (y + 1) > x.
die ich überhaupt nicht verstehe
Gruß niesel
|
|
|
| |
|
Hallo,
bei den Definitionen von p und q wird aber immer jeweils nur die erste Zeile ausgewertet! War das so gedacht?
Was ist denn nun Aufgabenstellung und was deine Lösung?
Bei d kann ich das eine Zeichen nicht erkennen, aber falls es das Malzeichen sein soll, dann wäre das eine ganzzahlige Division durch 3.
Ach ja: Wenn du meinen Ansatz (den einfachen, in O(n)) verfolgst, dann reicht doch die Subtraktion aus.
Gruß
Martin
|
|
|
| |
|
Geben Sie induktive Definitionen für die folgenden Funktionen an. Dabei dürfen Sie nur die
Funktionen t, q, p und d sowie die Addition und Subtraktion verwenden.
[mm]t: \IN \to \{0,1\} t(n)=\begin{cases} 0, & \mbox{sont } \\ 1, & \mbox{falls ganzzahlig durch 5 teilbar ist } \end{cases}[/mm]
[mm]q : \IN \to \IN[/mm], wobei [mm]q(x) = 3*x^2[/mm] ,
[mm]p : \IN \to \IN[/mm], wobei [mm] p(x) = x^3[/mm] ,
[mm]d : \IN \to \IN, d(x) = y[/mm] , wobei [mm]3 * y \le x[/mm] und [mm]3 * (y + 1) > x[/mm].
Geben Sie weiterhin für jede induktive Definition auch eine Definition in Haskell-Notation an!
Gruß niesel
|
|
|
| |
|
Hallo,
was mich letztes Mal gestört hat, ist die Tatsache, dass die Zeilen "q x =3*x*x" und "p x =x*x*x" da wegmüssen, weil sonst deine Arbeit unnötig gewesen ist.
Zu den beiden anderen Aufgaben: Ich wüsste nicht, wie ich hier die beiden anderen Funktionen verwenden könnte, aber ich würde Folgendes vorschlagen:
d::Int -> Int
d (n+3) = 1 + d n
d _ = 0
Was die Funktion macht, kannst du ja mal mit map d [0..20] ausprobieren.
t::Int -> Int
t (n+5) = t n
t 0 = 1
t _ = 0
Ich habe beide Aufgaben durch simpelstes Pattern Matching gelöst, weil ich nicht wusste, ob weitere Konstrukte erlaubt sind.
Gruß
Martin
|
|
|
| |
|
Hallo,
der "komplementäre" Ansatz zu Bastianes (richtiger) Idee wäre die wiederholte Subtraktion von 5. Falls das Ergebnis positiv ist, wird die Funktion rekursiv auf das Ergebnis angewandt. Falls das Ergebnis 0 ist, ist die Division aufgegangen, also 1. Falls es negativ ist, dann ist die Division nicht aufgegangen, also 0.
Diesen Ansatz könnte man von O(n) auf O(log n) pushen, wenn man im Vorfeld prüft, welche größte 5er-Potenz in die Zahl n hineinpasst. Dann könnte man zuerst diese größte Potenz wiederholt abziehen, bis das Ergebnis negativ ist. Dann würde man von dem letzten positiven Ergebnis wiederholt die nächstkleinere Potenz wiederholt abziehen usw. Sobald man bei der Subtraktion der kleinsten Potenz 5 eine negative Zahl bekommt, dann ist n nicht teilbar durch 5. Falls irgendwann im diesem Algorithmus eine 0 als Ergebnis herauskommt, dann geht die Division auf.
Das Verfahren lohnt sich für größere n, weil es eben in O(log n) liegt.
Hier mal eine Beispielanwendung: n=410
410 - 5 > 0 => Potenzen = [5]
410 - 5*5 > 0 => Potenzen = [25,5]
410 - 5*25 > 0 => Potenzen = [125,25,5]
410 - 5*125 < 0 => Potenzen unverändert, Liste fertig
410 - 125 = 285
285 - 125 = 160
160 - 125 = 35
35 - 125 < 0 => nächstkleinere Potenz
35 - 25 = 10
10 - 25 < 0 => nächstkleinere Potenz
10 - 5 = 5
5 - 5 = 0 => Division aufgegangen, n teilbar durch 5
Gruß
Martin
|
|
|
|
