Feedback Software Testing, Opdrachten Week 1 Driehoek-test Deze opdracht is in het algemeen zeer goed uitgevoerd. Algemeen valt in vergelijking met vorig jaar op dat de ingeleverde oplossingen veel minder redundantie bevatten. Eenvoud is het kenmerk van het ware: dit is een simpel probleem dus de oplossing kan er ook simpel uitzien. Dat is jullie allemaal goed gelukt. Hier is een mogelijke aanpak. Achterliggend idee: als we het drietal getallen x, y, z ordenen naar grootte kunnen we in onze specificatie gebruik maken van: x ≤ y ≤ z. Dat blijkt het redeneren over de mogelijke gevallen zeer te vereenvoudigen. Om te kijken of x, y, z samen een driehoek specificeren hoeven we alleen nog maar de driehoeksongelijkheid te controleren: x, y, z moeten voldoen aan: x + y > z ∧ y − x < z. Als dit zo is, dan zijn x, y, z de zijden van een driehoek, anders niet. Beeldende uitleg (met dank aan Paul Griffioen): denk aan de grote wijzer en de kleine wijzer van de klok. De derde zijde (het lijnstuk tussen de wijzerpunten) kun je zo klein mogelijk krijgen door de wijzers naar elkaar toe te bewegen. Maar de wijzers mogen elkaar niet precies overlappen. De derde zijde moet dus altijd groter zijn dan het verschil in lengte tussen de grote en de kleine wijzer. We kunnen ook proberen de derde zijde zo lang mogelijk te maken. Maar de langste zijde kan nooit even lang zijn als of langer zijn dan de som van de wijzerlengten. Merk nu op dat het tweede conjunct, y − x < z, volgt uit y ≤ z, gesteld dat we weten dat x positief is. Maar dat volgt uit het eerste conjunct plus de aanname x ≤ y ≤ z. Immers: als er een zijde ≤ 0 is dan moet dat zeker voor x gelden, want x is de kleinste zijde. Uit x ≤ 0 en y ≤ z volgt x + y ≤ z, dus in dit geval is niet aan x + y > z voldaan. Met andere woorden: als wel aan de driehoeksongelijkheid x + y > z is voldaan, volgt daaruit dat x > 0, dus een extra test is hier overbodig. Uit 0 < x en y ≤ z volgt dat y < z + x, en dus ook dat y − x < z. Dus kan de test voor ‘geen driehoek’ bestaan uit: x+y ≤z
Dit is immers de ontkenning van x + y > z. Nogmaals: testen of een van zijden negatief of gelijk aan 0 is, hoeft niet. x, y, z specificeren een gelijkzijdige driehoek als x == y en y == z. Merk op dat uit deze twee gelijkheden volgt dat x == z, dus dat hoef je niet apart te testen. x, y, z specificeren een gelijkbenige maar niet gelijkzijdige driehoek als x == y of y == z, maar niet beide (‘exclusief of’). Als we aannemen dat we de test voor x == y ∧ y == z al gehad hebben kunnen we gelijkbenigheid testen met x == y ∨ y == z, waarbij ∨ staat voor ‘inclusief of’. x, y, z specificeren een rechthoekige driehoek precies wanneer x2 + y 2 = z 2 (volgens Pythagoras). Een subtiliteit hier is het volgende. Neem aan dat x, y, z gehele getallen zijn. Hoe weten we nu dat er geen gelijkbenige rechthoekige driehoek kan zijn, dat wil zeggen: waarom is 2x2 = z 2 , met x, z geheel, uitgesloten? Een aantal groepen merkt op dat dat zo is, en √ ze hebben√gelijk. Maar 2 2 waarom? Omdat uit 2x = z volgt dat z = 2x2 = x 2, en dat is geen geheel getal. De oude Grieken beredeneerden dit nog meer in detail als volgt. Stel dat 2x2 = z 2 , met x, z geheel. Dan mogen we wel aannemen dat x en z geen factoren gemeenschappelijk hebben. Met name: we mogen aannemen dat x en z niet allebei deelbaar zijn door 2. Als x, z allebei even zijn vervangen we x en z respectievelijk door x/2 en z/2, net zolang tot minstens een van x, y oneven is. Maar nu is er een moeilijkheid: uit 2x2 = z 2 volgt dat z even is. Immers, als z oneven zou zijn, dan z 2 ook oneven moeten zijn (ga zelf na). Maar dan mogen we z schrijven als z = 2k, voor zekere k, en we krijgen: 2x2 = (2k)2 = 4k 2 , dus x2 = 2k 2 . Nu kunnen we dezelfde redenering voor x2 = 2k 2 herhalen, en er blijkt dat x ook even is. Maar dat is in tegenspraak met wat we over x en z hadden aangenomen. Hiermee is de aanname dat x, z allebei geheel kunnen zijn weerlegd.
def triangle list # assume list is ordered number triple x, y, z = list # x <= y <= z if x + y <= z # note : x <= 0 and y <= z imply x + y <= z puts "no triangle"; return end if x == y and y == z puts "equilateral"; return end if x**2 + y**2 == z**2 puts "rectangled"; return end if x == y or y == z puts "isosceles"; return end puts "other" end puts "give three numbers" puts "first number" a = gets.to_i puts "second number" b = gets.to_i puts "third number" c = gets.to_i triangle [a,b,c].sort Hier is, als verdere illustratie, nog een Haskell oplossing:
module Triangle where import List data Shape = NoTriangle | Equilateral | Isosceles | Rectangular | Other deriving (Eq,Show)
triangle :: Integer -> Integer -> Integer -> Shape triangle x y z = triangle’ xs where xs = sort [x,y,z] triangle’ :: [Integer] -> Shape triangle’ [x,y,z] = if x + y <= z then NoTriangle else if x == y && y == z then Equilateral else if x^2 + y^2 == z^2 then Rectangular else if x == y || y == z then Isosceles else Other Een andere aanpak (van Paul Griffioen) is: ga uit van de driehoeksongelijkheid in zijn meest algemene vorm: |a − b| < c < a + b Maar dit moet gelden ongeacht hoe we a, b, c kiezen. Het bovenstaande is equivalent met: a−b
∧
b−a
∧
c < a + b.
Aan beide zijden van de eerste twee ongelijkheden a + b erbij optellen, en c optellen bij de derde ongelijkheid, geeft: 2a < a + b + c
∧
2b < a + b + c
∧
2c < a + b + c.
Dus: ∀x ∈ {a, b, c} : 2x < a + b + c. De Ruby test wordt dus:
def valid_triangle?(a,b,c) [a,b,c].all? {|x| 2*x < a+b+c} end Net zo voor rechthoekig: ga gewoon na of a2 +b2 == c2 of a2 +c2 == b2 of b2 + c2 == a2 . De eerste van deze drie vergelijkingen kunnen we ook schrijven als a2 + b2 + c2 == 2c2 , de tweede als a2 + b2 + c2 == 2b2 , en de derde als a2 + b2 + c2 == 2a2 . Geschreven als een enkele test: ∃x ∈ {a, b, c} : a2 + b2 + c2 == 2x2 . Dit suggereert de volgende Ruby implementatie: def rectangular?(a,b,c) [a,b,c].any? {|x| 2 * x**2 == a**2 + b**2 + c**2} end
Scores van de groepen Alle groepen hebben hier uitstekend gescoord. Joe en Jill opdracht Het hele eieren eten hier is de volgende redenering. Noem de verdeling van de eerste koek x. Neem aan dat x het grootste stuk aangeeft, dus x ≥ 12 . Als Jill eerst kiest krijgt ze x (plus een kruimeltje). Als Jill de eerste keuze voorbij laat gaan krijgt ze (1 − x) + 12 . De beste strategie voor Joe is dus: bij het snijden ervoor zorgen dat deze twee gelijk zijn: x = (1 − x) + 21 . Dit wil zeggen 2x = 1 12 , en dus x = 43 . Hier volgt meteen uit wat de beste strategie voor Jill is: als x groter is dan 34 , x kiezen, en anders de eerste keuze voorbij laten gaan.
Iedereen had dit door. Kanttekening: groep 4 deed het met ‘proberen’, en dat is iets minder dan analyseren, zeker omdat in dit geval de analyse niet heel lastig was. Omzetten van SAT naar CNF Hier zijn de meeste groepen niet aan toe gekomen, of niet helemaal uit gekomen. Alleen groep 2 heeft dit helemaal rond gekregen. Chapeau. Algehele beoordeling Alle groepen ++.
