[ALG] Probleem analytisch benaderen

[Verwijderd]

Stel, ik krijg de opdracht om het eerste gehele getal te vinden waarvoor geldt dat 'mod 1' tot en met 'mod 20' 0 oplevert (sommigen herkennen dit probleem misschien wel ).
Nu is het natuurlijk niet erg moeilijk om een dergelijk probleem numeriek aka. brute-force op te lossen, dat kost alleen maar een beetje tijd en is natuurlijk niet zo efficiënt.

Eerst schreef ik een klein programmaatje waarvan ik weet dat het werkt (ik weet dat het antwoord voor 'mod 1' tot en met 'mod 10' 2520 moet zijn).

Vervolgens is het zaak om zoveel mogelijk mogelijkheden uit te sluiten en zo het algoritme zo min mogelijk te hoeven laten rekenen.
Ik bedacht me dat een even getal alleen geen rest overhoudt wanneer het door een even getal gedeeld wordt, waarop ik me bedacht dat aangezien het altijd deelbaar door 20 moet kunnen zijn (want mod 20 == 0), ik stappen kan gaan nemen van 20. Er zijn vast nog wel meer dingen te verzinnen om het aantal tests te verkleinen en het algoritme te versnellen.

Nu is mijn vraag, hoe benaderen jullie dergelijke problemen (dit is slechts een voorbeeld probleem, waar ik toevallig net aan begonnen ben)? Hoe los je zoiets methodisch/analytisch op? Welke stappen neem je en waarom neem je die?

[TvdW]

getal is deelbaar door 20
deelbaar door 10 dus ook, valt weg uit je berekening
deelbaar door 5 dus ook, ook weg
deelbaar door 2 dus ook, ook weg
deelbaar door 1 dus ook, ook weg

deelbaar door 15 dus 3 valt weg

enz

zodra je deze allemaal hebt gedaan vermenigvuldig je de overgebleven getallen en je hebt je antwoord?

[let op: ik ben geen wiskunde-wonder, maar ik denk dat dit ongeveer klopt]

[Verwijderd]

Ik zelf ben sinds kort begonnen met een HBO opleiding voor Software Engineering en een van de aspecten die wij gaan behandelen is het analystisch en methodisch oplossen van problemen, hier heb ik dus NOG geen goed antwoord op ik wou je er alleen even op wijzen dat deze vraag beter geplaatst kan worden in:
Software Engineering & Architecture

edit:
Om er toch even technisch op in te gaan is het een questie van 2 variabelen verglijking die je met hetzelfde getal vermenigvuldigd (als ik het niet verkeerd begrijp!) en dan zou het (even uit het hoofd) zo moeten uitzien

C#:

int getal1 = 1;
int getal2 = 20;
int count = 0;
bool solved = false;
while(!solved)
{
   if((getal1 * count) == (getal2 * count))
         solved = true;            
   else
          count++;
}
//en hier is count je kleinste gemeenschappelijke waarde
//dit is gewoon een zetje in de richting en geen copy/paste code

[ Voor 43% gewijzigd door Verwijderd op 07-03-2009 13:54 ]

[ValHallASW]

Je bent überhaupt al op de verkeerde toer bezig: namelijk het doorlopen van de antwoorden. Bedenk eerst eens hoe je het op papier zou oplossen - en bedenk even wat je precies wilt weten. Wat je namelijk wilt weten is het kleinste gemene meervoud van 1..20.. en hoe je dat bepaalt heb je op de basisschool gehad

[RayNbow]

Klinkt als Project Euler #5?

rest van verhaal = spuit11

[Creepy]

Verwijderd schreef op zaterdag 07 maart 2009 @ 13:33:
Ik zelf ben sinds kort begonnen met een HBO opleiding voor Software Engineering en een van de aspecten die wij gaan behandelen is het analystisch en methodisch oplossen van problemen, hier heb ik dus NOG geen goed antwoord op ik wou je er alleen even op wijzen dat deze vraag beter geplaatst kan worden in:
Software Engineering & Architecture

Wat hij zegt

Move Programming -> Software Engineering & Architecture

[Verwijderd]

Het is inderdaad nummertje 5 en heb hem op 2 manieren opgelost, via ontbinden in priemfactoren en het steeds vernauwen van het ehm. zoekdomein door steeds meer voorwaarden te stellen aan de tests.

Waar het me meer om ging is, hoe gaan jullie met een probleem om (iets abstracts) waar mee je geconfronteerd wordt, dat ik een concreet probleem als voorbeeld aanhaalde staat daar even buiten

[ Voor 8% gewijzigd door Verwijderd op 07-03-2009 14:19 ]

[Verwijderd]

Uhm, chinese reststelling? Al geld hij niet als de ggd van elk koppel niet 1 is. Streep dus weg wat TvDw zegt, en los het dan op.
Wikipedia: Chinese reststelling

[RayNbow]

Verwijderd schreef op zaterdag 07 maart 2009 @ 13:48:
Het is inderdaad nummertje 5 en heb hem op 2 manieren opgelost, via ontbinden in priemfactoren en het steeds vernauwen van het ehm. zoekdomein door steeds meer voorwaarden te stellen aan de tests.

De beste manier om PE #5 op te lossen is hoe ValHallASW het beschreef. Je moet dus het probleem niet aanpakken door aan delen te denken, maar door juist meer aan vermenigvuldigen (veelvouden) te denken. In plaats van te controleren of een getal deelbaar is door 1..20, moet je juist getallen construeren die veelvouden van 1..20 zijn. Dit kan met behulp van de functie lcm (least common multiple, of kleinst gemeenschappelijke veelvoud).

In Haskell kan je het probleem zo oplossen:

Haskell:

answerPE5 = foldl1 lcm [1..20]

{- NB: foldl1 f [a,b,c,d]  = f (f (f a b) c) d -}

Waar het me meer om ging is, hoe gaan jullie met een probleem om (iets abstracts) waar mee je geconfronteerd wordt, dat ik een concreet probleem als voorbeeld aanhaalde staat daar even buiten

In het algemeen helpt het dus soms om een probleem van meerdere kanten te bekijken. Als je bijv. weet hoe je een antwoord kan controleren, probeer te kijken of je ook een antwoord kan construeren. (Let wel, niet voor elk probleem is het vinden van een oplossing net zo gemakkelijk als het controleren ervan.) Soms helpt het ook om het probleem anders te formuleren. Kun je een instantie van het probleem representeren met behulp van natuurlijke getallen? Of misschien een graaf? Of iets anders?

Het is een kwestie van een beetje puzzelen.

[Verwijderd]

RayNbow schreef op zaterdag 07 maart 2009 @ 14:21:


Het is een kwestie van een beetje puzzelen.

True en dat vind ik ook leuk om te doen, vandaar dat ik de euler puzzeltjes ook oplos
Ik heb geen sterke wiskunde achtergrond en dit soort dingen dwingen me (min of meer) te onderzoeken en wijzer te worden. En omdat ik geen sterke wiskunde achtergrond heb vroeg ik me af hoe jullie met dergelijke problemen omgaan.

[Verwijderd]

Verwijderd schreef op zaterdag 07 maart 2009 @ 14:32:
[...]
True en dat vind ik ook leuk om te doen, vandaar dat ik de euler puzzeltjes ook oplos
Ik heb geen sterke wiskunde achtergrond en dit soort dingen dwingen me (min of meer) te onderzoeken en wijzer te worden. En omdat ik geen sterke wiskunde achtergrond heb vroeg ik me af hoe jullie met dergelijke problemen omgaan.

Ik heb zelf ook geen wiskundige achtergrond afgezien de wiskunde B1 en B2 die ik op dit moment weer aan het leren ben op school. Mijn aanpak bij dit soort dingen: ik schrijf zoiezo altijd alles even neer op papier en schrijf ook de punten op die ik wil bereiken en hoe deze bereikt moeten worden (bij deze punten is het belangrijk dat je precies weet wat elk punt inhoud) zodat je precies weet waar je naartoe werkt en waarmee je dit doet/wil doen.

Vervolgens is het inderdaad een questie van "puzzelen" en dit kan natuurlijk op meerdere manieren door bestaande theorien/formules te gebruiken of zelf "creatief" te zijn hierin verschilt het natuurlijk per persoon in. Natuurlijk is deze aanpak EEN manier en zeker niet DE manier haha hoop dat je hier ooit wat mee kan!

Het is hierbij gewoon belangrijk dat je het doel en de middelen niet uit het oog verliest

[ Voor 7% gewijzigd door Verwijderd op 07-03-2009 15:05 ]

[RayNbow]

Verwijderd schreef op zaterdag 07 maart 2009 @ 13:33:

edit:
Om er toch even technisch op in te gaan is het een questie van 2 variabelen verglijking die je met hetzelfde getal vermenigvuldigd (als ik het niet verkeerd begrijp!) en dan zou het (even uit het hoofd) zo moeten uitzien

C#:

int getal1 = 1;
int getal2 = 20;
int count = 0;
bool solved = false;
while(!solved)
{
   if((getal1 * count) == (getal2 * count))
         solved = true;            
   else
          count++;
}
//en hier is count je kleinste gemeenschappelijke waarde
//dit is gewoon een zetje in de richting en geen copy/paste code

Volgens mij zit er een fout in je code. De loop eindigt pas wanneer a*c = b*c, waarbij a en b constant en c variabel. Dit is dus alleen wanneer a=b of c=0. In alle andere gevallen wordt je CPU alleen maar heet.

[Verwijderd]

Concreet was één van mijn oplossingen als volgt (het is geen nette code ):

C#:

        static void Main(string[] args)
        {
            int increment = 20;
            int maxmod = 20;
            
            for (int test = 20; test < int.MaxValue; test+=increment)
            {
                   for (int modTest = 11; modTest <= maxmod; modTest++)
                    {
                        if (test % (maxmod - 1) == 0)
                        {
                            increment = test;
                            maxmod--;
                            if (maxmod == 11)
                            {
                                Console.WriteLine("Gevonden!: {0}", test);

                            }
                        }
                }
            }
        }

[ Voor 4% gewijzigd door Verwijderd op 07-03-2009 16:42 ]

[Verwijderd]

RayNbow schreef op zaterdag 07 maart 2009 @ 15:49:
[...]


Volgens mij zit er een fout in je code. De loop eindigt pas wanneer a*c = b*c, waarbij a en b constant en c variabel. Dit is dus alleen wanneer a=b of c=0. In alle andere gevallen wordt je CPU alleen maar heet.

Heb even geen compiler tot mijn beschikking, dacht eerlijk gezegd dat het zo "ongeveer" zou werken . Het was eigenlijk meer om een idee te geven hoe je aan de kleinste (oftewel eerste) gemene eenvoud kwam en dat doe je door de constanten te vermenigvuldigen met een variable en deze elke keer vergelijken op waarde, waaruit dan uiteindelijk de kleinste(eerste) gemene eenvoud rolt

[Creepy]

Verwijderd schreef op zaterdag 07 maart 2009 @ 15:54:
Concreet was één van mijn oplossingen als volgt (het is geen nette code ):

C#:

        static void Main(string[] args)
        {
            int increment = 20;
            int maxmod = 20;
            
            for (int test = 20; test < int.MaxValue; test+=increment)
            {
                   for (int modTest = 11; modTest <= maxmod; modTest++)
                    {
                        if (test % (maxmod - 1) == 0)
                        {
                            increment = test;
                            maxmod--;
                            if (maxmod == 11)
                            {
                                Console.WriteLine("Gevonden!: {0}", test);

                            }
                        }
                }
            }
        }

Die increment zou nog hoger kunnen. 19 is een priem getal dus alleen de getallen die deelbaar zijn door 19 * 20 zijn de kleinste getallen die deelbaar zijn door 19 en 20

[roy-t]

Dit klinkt als het type denken/wiskunde dat behandelt wordt in het 1e jaars informatica vak Discrete Structuren op de RuG, het boek dat we daar voor gebruiken is http://www.bol.com/nl/p/b...01004001751382/index.html

misschien heb je daar iets aan? (damn dat boek wordt elk jaar duurder)

[Verwijderd]

roy-t schreef op zaterdag 07 maart 2009 @ 18:55:
Dit klinkt als het type denken/wiskunde dat behandelt wordt in het 1e jaars informatica vak Discrete Structuren op de RuG, het boek dat we daar voor gebruiken is http://www.bol.com/nl/p/b...01004001751382/index.html

misschien heb je daar iets aan? (damn dat boek wordt elk jaar duurder)

Ik heb wel eens eerder naar dat boek gekeken, maar ik heb zelf binnenkort ook 2 wiskunde vakken (discrete wiskunde A en discrete wiskunde B (goh)) en wil eerst even afwachten hoe diepgaand de stof van die 2 vakken is voor ik een boek van € 100,- aanschaf (die vakken zijn namelijk al duur genoeg)

[AaroN]

zoals eerder aangegeven heb je hiervoor geen hogere wiskunde nodig, je hoeft slechts de factoren van een getal op te schrijven en vervolgens cijfers weg te strepen. Mijn aanpak is als volgt:

Ik kijk alleen naar de cijfer 11 t/m 20 omdat de cijfers 1 t/m 10 sowieso voorkomen als factoren in deze cijfers. Vervolgens schrijf ik alle factoren van de cijfers uit en kijk of ze allemaal nog aanwezig zijn. Dit levert de volgende status op:

code:

20 = {2, 10}, {4, 5}, {2, 2, 5} 
19 = 19
18 = {2, 9}, {3, 6}, {2, 3, 3}
17 = 17
16 = {2, 8}, {2, 2, 4}, {2, 2, 2, 2} 
15 = {3, 5}
14 = {2, 7}
13 = 13
12 = {2, 6}, {3, 4}, {2, 2, 3}
11 = 11
10 = {2, 5}
9 = {3, 3}
8 = {2, 4}, {2, 2, 2}
7 = 7
6 = {2, 3}
5 = 5
4 = {2, 2}
3 = 3
2 = 2
1 = 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Vervolgens ga ik van bovenaf omdat we het kleinste getal zoeken dat deelbaar is door alle factoren, dus bij 20 beginnend kijken of ik getallen weg kan strepen door te kijken of het mogelijk is om alle factoren van eent getal op te sommen uit factoren van lagere getallen. Als je kijkt naar 20, zie je dat deze samengesteld kan worden uit 2 en 10. 10 heeft een 5 in zich als factor en 8 een 2, dat beteken dat ik door 10 * 8 uit te rekenen een getal vindt dat deelbaar is door 20. Wat uiteraard klopt als je het narekent. Zodoende streep ik de 20 weg. Zolang je alle factoren van een ontbinding kunt terug vinden als een combinatie van een lager getal of een van haar factoren, dan kun je dit getal met een gerust hart verwijderen. Dit levert de volgende getallen op:

code:

19 = 19
18 = {2, 9}, {3, 6}, {2, 3, 3}
17 = 17
16 = {2, 8}, {2, 2, 4}, {2, 2, 2, 2} 
15 = {3, 5}
14 = {2, 7}
13 = 13
12 = {2, 6}, {3, 4}, {2, 2, 3}
11 = 11
10 = {2, 5}
9 = {3, 3}
8 = {2, 4}, {2, 2, 2}
7 = 7
6 = {2, 3}
5 = 5
4 = {2, 2}
3 = 3
2 = 2
1 = 1

Vervolgens kijk ik naar 19, dit is een priemgetal, dus deze laat ik onaangetast, maar bij 18 is het weer raak: 3 en 6 komen beide voor als factoren van 2 verschillende lagere getallen.

code:

19 = 19
17 = 17
16 = {2, 8}, {2, 2, 4}, {2, 2, 2, 2} 
15 = {3, 5}
14 = {2, 7}
13 = 13
12 = {2, 6}, {3, 4}, {2, 2, 3}
11 = 11
10 = {2, 5}
9 = {3, 3}
8 = {2, 4}, {2, 2, 2}
7 = 7
6 = {2, 3}
5 = 5
4 = {2, 2}
3 = 3
2 = 2
1 = 1

Vervolgens ga ik zo door, continu lettend op het feit dat alle factoren aanwezig dienen te blijven:

code:

19 = 19
17 = 17
13 = 13
11 = 11
7 = 7
6 = {2, 3}
5 = 5
4 = {2, 4}
3 = 3
2 = 2
1 = 1

De vermenigvuldiging van deze getallen is: 232792560

Dit moet volgens mij wel het kleinste getal zijn.
Edit:
Het zelfde getal als hieronder
Ik heb de term ontbinden weggehaald en het opsommen van factoren genoemd. De ontbinding in priemgetallen zoals hieronder wel gedaan wordt, is in principe niet nodig. Het aantal bewerkingen bij gebruik van ontbinding in zo weinig mogelijk factoren is namelijk minimaal.

[ Voor 18% gewijzigd door AaroN op 10-03-2009 09:33 . Reden: opmerkingen verwerkt / weerlegd ]

[.oisyn]

Sorry maar de logica van je post ontgaat me een beetje. Waarom haal je bijv. wel 8 weg, maar 4 niet? Ontbinden in factoren is een goede stap, maar daarna hoef je simpelweg alleen nog maar de subset van factoren te nemen. En als je gaat ontbinden in factoren vind je sowieso alleen maar priemgetallen. 20 is dus 2²*5, oftewel { 2, 2, 5 }. En dus niet { 2, 4, 5, 10 }.

Dan kom je dus op

code:

20 = 2 2 5
19 = 19
18 = 2 2 3
17 = 17
16 = 2 2 2 2
15 = 3 5
14 = 2 7
13 = 13
12 = 2 2 3
11 = 11
10 = 2 5
9 = 3 3
8 = 2 2 2
7 = 7
6 = 2 3
5 = 5
4 = 2 2
3 = 3
2 = 2

De kleinste subset waar al die combinaties in voorkomen is
{ 2, 2, 2, 2, 3, 3, 5, 7, 11, 13, 17, 19 }

Die met elkaar vermenigvuldigen levert op 232792560.

Het kan echter nog makkelijker. Vindt alle priemgetallen <= 20. Vermenigvuldig vervolgens elke priem met zichzelf totdat de waarde groter is dan 20. Hiermee vindt je effectief hoe vaak dat priemgetal in bovenstaande subset voorkomt, dus als je het resultaat ook meteen meevermenigvuldigt zolang je <= 20 blijft heb je na afloop meteen je antwoord.

C++:

// returns the least common multiple of all numbers up to n 
int getlcm(int n) 
{ 
    std::vector<bool> sieve(n+1, false); // Sieve of Eratosthenes 
    int result = 1; 
    for (int i = 2; i <= n; i++) 
    { 
        if (sieve[i]) 
            continue; 
        for (int j = i; j <= n; j += i) 
            sieve[j] = true; 
        int pow = i; 
        while(pow <= n) 
            pow *= i, result *= i; 
    } 

    return result; 
}

[ Voor 57% gewijzigd door .oisyn op 10-03-2009 01:18 ]

[RayNbow]

RayNbow schreef op zaterdag 07 maart 2009 @ 14:21:
In Haskell kan je het probleem zo oplossen:

Haskell:

answerPE5 = foldl1 lcm [1..20]

{- NB: foldl1 f [a,b,c,d]  = f (f (f a b) c) d -}

Ik had nog wat tijd over, dus hier nog een kleine visualisatie van de fold: **

$ ghci
Prelude> :s prompt "ghci> "
ghci> :s -XParallelListComp
ghci> :m Data.List Text.Printf
ghci> let pairs xs = [(a,b) | (a:b:_) <- tails xs]
ghci> sequence_ [printf "lcm(%d,%d) = %d\n" a b c | a <- [1..] | (b,c) <- pairs (scanl lcm 1 [1..20])]
lcm(1,1) = 1
lcm(2,1) = 2
lcm(3,2) = 6
lcm(4,6) = 12
lcm(5,12) = 60
lcm(6,60) = 60
lcm(7,60) = 420
lcm(8,420) = 840
lcm(9,840) = 2520
lcm(10,2520) = 2520
lcm(11,2520) = 27720
lcm(12,27720) = 27720
lcm(13,27720) = 360360
lcm(14,360360) = 360360
lcm(15,360360) = 360360
lcm(16,360360) = 720720
lcm(17,720720) = 12252240
lcm(18,12252240) = 12252240
lcm(19,12252240) = 232792560
lcm(20,232792560) = 232792560

** Technisch gezien is dit eigenlijk een visualisatie van `foldl (flip lcm) 1 [1..20]`, maar (ℕ,lcm) vormt een commutatieve monoïde, dus het mag.