Og summen blir hundre

[Nebuchadnezzar]

Ved å bruke sekvensen av tall 123456789 kan vi finne summen 100.

Dette gjøres ved å legge inn + og - mellom tallene. Et eksempel på dette kan være

12 + 3 - 4 + 5 + 67 + 8 + 9 = 100

Hvor mange slike tall par, klarer dere å finne ?

Hva med 987654321?

[Aleks855]

1+23-4+56+7+8+9

1*2+3+4*5+6+78-9

1-2-34+56+7+8*9

Dette var faktisk ganske morsomt. Hvor mange muligheter finnes?

EDIT: 98+7-6+5-4+3-2-1, men det er vel den lette versjonen.

98 - 76 + 54 + 3 + 21, dog også ganske simpel.

[2357]

123-4-5-6-7+8-9

[Thales]

Noen som tar utfordringen å skrive en algoritme som kunne funnet alle mulige kombinasjoner hvis du har en rekke tall(array of numbers), og en sum du vil oppnå?

[Nebuchadnezzar]

Så vidt meg bekjent er det 11 løsninger for 123456789 og 15 for 987654321

[Charlatan]

Det er ikke spesielt vanskelig egentlig å skrive et slikt program. Uten at jeg skal skrive i detalj, kan man f.eks gjøre noe slikt i python (jeg tar eksempelet 5421):

definer en funksjon f(a,b,c) = "5a4b2c1". Så for-looper vi gjennom alle mulige ordnede utvalg (a,b,c) av tegnene {+,-,*}, la f.eks p_i være det i'te utvalget.

Så for-looper man for hver i med følgende:

if ( eval(f(p_i)) = N )
k = k+1

der k er tellevariabelen.

Det eval-funksjonen gjør (uten at jeg påberoper meg noen spesiell ekspertise på detaljene her), er å "tolke" f.eks strengen "4*3+1" som 4*3+1 = 13.

Så hvis (a,b,c) nå er (+,-,+), så vil eval(f(a,b,c)) = eval("5+4-2+1") = 5+3-2+1 = 7, og hvis 7 er tallet man er ute etter (dvs N), så teller man dette.

Er ikke så vanskelig å lage en liste av alle mulige ordnede utvalg (a_1,a_2,...,a_n) av {+,-,*} heller, krever bare litt rekursjonskreativitet.

Dette kan jo også gjøres mer generelt, ved å tillate paranteser, deling, potenser osv.. Man må begrense de ordnede utvalgene til det som gir mening (f.eks hvis "(" intreffer, må ")" inntreffe senere).

[Thales]

Bestemte meg for å finne en løsning, så brukte en time på å skrive følgende, i javscript.
Jeg bemerker at tallsekvens og opersjonstegn må skrives som en "liste", det vil si [a,b,c,...,z], der hvor a, b, c, z er tall, eller tegn. Plus må skrives som "+", minus som "-" og gange som "*".

Eksempel:

Code: Select all

resultat = sumCombinations([1,2,3,4,5],["+","-","*"],7);
alert(resultat.join(" || ")) // Burde vise i en popup boks: 1+2+3-4+5 || 1*2*3-4+5

Running time: [tex]k \cdot (n-1)\cdot m^{(n-1)}[/tex]
Der n = antall tall, og m er antall tegn, og k er en konstant, avhengig av hastigheten til datamskinen.

Funksjon:

Code: Select all

function sumCombinations(tallsekvens, operasjonstegn, sum) { 
    var array1 = tallsekvens,  
        array2 = operasjonstegn;
    var len1 = array1.length - 1,
        len2 = array2.length;
    var arrayComb = [],
        arraySign = [],
        arrayCount = [],
        arrayFinal = [];

    for (var i = 0; i < len1; i++) {
        arrayComb.push(Math.pow(len2, len1 - 1 - i));
        arraySign.push(0);
        arrayCount.push(0);
    }

    for (var j = 0; j < Math.pow(len2, len1); j++) {
        str = array1[0];
        for (var i = 0; i < arrayComb.length; i++) {
            if (arrayCount[i] == arrayComb[i]) {
                arrayCount[i] = 0;
                arraySign[i]++;
                if (arraySign[i] > len2 - 1) {
                    arraySign[i] = 0
                }
            }
            arrayCount[i]++;
            str += array2[arraySign[i]] + array1[i + 1];
        }
        if (eval(str) == sum) {
            arrayFinal.push(str)
        };
    }

    return arrayFinal;
}

[Thales]

La nettop merke til at funskjonen som jeg nettop lagde ikke tillater å sette opp 12+3, men at det alltid blir 1+2+3. Skal sjekke om jeg gidder å løse dette.

[Nebuchadnezzar]

Nå skal det siesat oppgaven ikke tillatet gangetegn eller subtraksjonstegn.

Bare pluss minus, og å trekke sammen tall

1+2+3 , 12+3 , 1+23 , 123

osv =)

[Thales]

Ok, dette tok meg ganske så lang tid, det var vanskelig å arbeide med kombinatorikk i funksjoner. Uansett her er den:

Eksempel:

Code: Select all

resultat = finnAlleSum([1,2,3,4,5],["+","-"],7); 
alert(resultat.join(" || ")) // Burde vise i en popup boks: 1+2+3-4+5 

Running time:
gad ikke å regne ut, men den kan bli lang hvis man bruker en lang sekvens med tall...

Funksjon(er):

Code: Select all

function finnAlleSum(tallsekvens, operasjonstegn, sum) {
    var array1 = tallsekvens,
        array2 = operasjonstegn,
        arrayFinal = [];
    var comb = combinations(array1);

    for (var i in comb) {
        var comb2 = sumCombinations(comb[i], array2, sum);
        for (var j in comb2) {
            arrayFinal.push(comb2[j]);
        }
    }
    return arrayFinal;
}

function sumCombinations(tallsekvens, operasjonstegn, sum) {
    var array1 = tallsekvens,
        array2 = operasjonstegn;
    var len1 = array1.length - 1,
        len2 = array2.length;
    var arrayComb = [],
        arraySign = [],
        arrayCount = [],
        arrayFinal = [];

    for (var i = 0; i < len1; i++) {
        arrayComb.push(Math.pow(len2, len1 - 1 - i));
        arraySign.push(0);
        arrayCount.push(0);
    }

    for (var j = 0; j < Math.pow(len2, len1); j++) {
        var str = array1[0];
        for (var i = 0; i < arrayComb.length; i++) {
            if (arrayCount[i] == arrayComb[i]) {
                arrayCount[i] = 0;
                arraySign[i]++;
                if (arraySign[i] > len2 - 1) {
                    arraySign[i] = 0
                }
            }
            arrayCount[i]++;
            str += array2[arraySign[i]] + array1[i + 1];
        }
        if (eval(str) == sum) {
            arrayFinal.push(str)
        };
    }

    return arrayFinal;
}

function combinations(tallsekvens) {
    var array1 = tallsekvens,
        len1 = array1.length - 1;
    var arrayComb = [],
        arrayPlace = [],
        arrayCount = [],
        arrayFinal = [];
    var sum = 0;

    for (var i = 0; i <= len1; i++) {
        arrayComb.push(Math.floor(Math.pow(2, len1 - 1 - i)));
        sum += arrayComb[i];
        arrayPlace.push(0);
        arrayCount.push(0);
    }

    for (var j = 0; j <= sum; j++) {
        var str = "";
        for (var i = 0; i < arrayComb.length; i++) {
            if (arrayCount[i] >= arrayComb[i]) {
                arrayCount[i] = 0;
                arrayPlace[i]++;
                if (arrayComb[i] == 0) {
                    arrayComb[i] = Math.floor(Math.pow(2, len1 - 1 - i));
                } else {
                    arrayComb[i] = Math.floor(arrayComb[i] / 2);
                }
                if (arrayPlace[i] > len1 - i) {
                    arrayPlace[i] = 0
                }
            }
            arrayCount[i]++;
            str += array1[i];
            if (arrayPlace[i] == 0 && i != arrayComb.length - 1) {
                str += ",";
            }
        }
        arrayFinal.push(eval("[" + str + "]"))
    }
    return arrayFinal;
}

[Thales]

Og i ditt eksempel, Nebu, så blir dette:

Code: Select all

finnAlleSum([1,2,3,4,5,6,7,8,9],["+","-"],100)

Som gir 11 muligheter:

Code: Select all

1+2+3-4+5+6+78+9 = 100
1+2+34-5+67-8+9 = 100
1+23-4+5+6+78-9 = 100
1+23-4+56+7+8+9 = 100
12+3+4+5-6-7+89 = 100
12-3-4+5-6+7+89 = 100
12+3-4+5+67+8+9 = 100
123-4-5-6-7+8-9 = 100
123+4-5+67-89 = 100
123+45-67+8-9 = 100
123-45-67+89 = 100

Code: Select all

finnAlleSum([9,8,7,6,5,4,3,2,1],["+","-"],100)

Gir 15 muligheter:

Code: Select all

9-8+7+65-4+32-1 = 100
9+8+76+5+4-3+2-1 = 100
9+8+76+5-4+3+2+1 = 100
9-8+76-5+4+3+21 = 100
9-8+76+54-32+1 = 100
98+7+6-5-4-3+2-1 = 100
98+7-6+5-4+3-2-1 = 100
98+7-6+5-4-3+2+1 = 100
98+7-6-5+4+3-2+1 = 100
98-7+6+5+4-3-2-1 = 100
98-7+6+5-4+3-2+1 = 100
98-7+6-5+4+3+2-1 = 100
98-7-6+5+4+3+2+1 = 100
98-7-6-5-4+3+21 = 100
98-76+54+3+21 = 100

Slitet var verdt det

[Thales]

For moro skyld prøvde jeg:

Code: Select all

finnAlleSum([1,2,3,4,5,6,7,8,9],["+","-","*","/"],100)

Den brukte ca 10 sekunder, men kom fram til 101 muligheter:
Dette blir halveis spamming, men følte at jeg måtte bare teste funskjonen min litt ut

Code: Select all

1+2+3+4+5+6+7+8*9 = 100
1+2+3-4*5+6*7+8*9 = 100
1+2-3*4+5*6+7+8*9 = 100
1+2-3*4-5+6*7+8*9 = 100
1+2*3+4*5-6+7+8*9 = 100
1+2*3*4*5/6+7+8*9 = 100
1-2+3*4*5+6*7+8-9 = 100
1-2+3*4*5-6+7*8-9 = 100
1-2*3+4*5+6+7+8*9 = 100
1-2*3-4+5*6+7+8*9 = 100
1-2*3-4-5+6*7+8*9 = 100
1*2*3+4+5+6+7+8*9 = 100
1*2*3-4*5+6*7+8*9 = 100
1*2*3*4+5+6+7*8+9 = 100
1*2*3*4+5+6-7+8*9 = 100
1+2+3*4-5-6+7+89 = 100
1+2*3-4-5+6+7+89 = 100
1*2-3+4-5+6+7+89 = 100
1*2/3+4*5/6+7+89 = 100
1+2+3-4+5+6+78+9 = 100
1+2+3*4*5/6+78+9 = 100
1*2+3+4*5+6+78-9 = 100
1*2+3-4+5*6+78-9 = 100
1*2+3*4+5-6+78+9 = 100
1*2-3+4*5-6+78+9 = 100
1*2*3-4+5+6+78+9 = 100
1*2*3*4-5-6+78+9 = 100
1+2*3+4+5+67+8+9 = 100
1-2+3*4+5+67+8+9 = 100
1-2-3+4*5+67+8+9 = 100
1+2+3*4*56/7-8+9 = 100
1-2-3+4*56/7+8*9 = 100
1/2*3/4*56+7+8*9 = 100
1+2*3-4+56/7+89 = 100
1*2-3+4+56/7+89 = 100
1-2+3+45+6+7*8-9 = 100
1-2-3+45+6*7+8+9 = 100
1-2-3+45-6+7*8+9 = 100
1-2-3+45-6-7+8*9 = 100
1+2+3-45+67+8*9 = 100
1*2+3+45+67-8-9 = 100
1*2*3-45+67+8*9 = 100
1/2/3*456+7+8+9 = 100
1+2+34*5+6-7-8*9 = 100
1*2+34+5+6*7+8+9 = 100
1*2+34+5-6+7*8+9 = 100
1*2+34+5-6-7+8*9 = 100
1/2*34-5+6-7+89 = 100
1+2+34-5+67-8+9 = 100
1-2-34+56+7+8*9 = 100
1*2+34+56+7-8+9 = 100
1*2+34-56/7+8*9 = 100
1*2*34+56-7-8-9 = 100
1+2*34-56+78+9 = 100
1+23-4-5+6+7+8*9 = 100
1+23*4+5-6+7-8+9 = 100
1+23*4-5+6+7+8-9 = 100
1-23+4*5+6+7+89 = 100
1-23-4+5*6+7+89 = 100
1-23-4-5+6*7+89 = 100
1*23-4+5-6-7+89 = 100
1+23-4+5+6+78-9 = 100
1*23+4+5+67-8+9 = 100
1+23-4+56+7+8+9 = 100
1+23-4+56/7+8*9 = 100
1+23*4+56/7+8-9 = 100
1*23+4+56/7*8+9 = 100
1*23*4-56/7/8+9 = 100
1*23-4-56/7+89 = 100
1+234*5/6-7-89 = 100
1+234*5*6/78+9 = 100
1*234+5-67-8*9 = 100
1+234-56-7-8*9 = 100
12+3*4+5+6+7*8+9 = 100
12+3*4+5+6-7+8*9 = 100
12-3+4*5+6+7*8+9 = 100
12-3+4*5+6-7+8*9 = 100
12-3-4+5*6+7*8+9 = 100
12-3-4+5*6-7+8*9 = 100
12*3-4-5-6+7+8*9 = 100
12/3+4*5*6-7-8-9 = 100
12/3+4*5*6*7/8-9 = 100
12+3+4+5-6-7+89 = 100
12-3-4+5-6+7+89 = 100
12/3+4*5-6-7+89 = 100
12+3*4-5-6+78+9 = 100
12*3-4+5-6+78-9 = 100
12/3/4+5*6+78-9 = 100
12+3-4+5+67+8+9 = 100
12*3-4*5+67+8+9 = 100
12+3+4-56/7+89 = 100
12+3*45+6*7-89 = 100
12+34+5*6+7+8+9 = 100
12+34-5+6*7+8+9 = 100
12+34-5-6+7*8+9 = 100
12+34-5-6-7+8*9 = 100
123+4*5-6*7+8-9 = 100
123-4-5-6-7+8-9 = 100
123+4-5+67-89 = 100
123+45-67+8-9 = 100
123-45-67+89 = 100

[Thales]

Så vidt meg bekjent er det 11 løsninger for 123456789 og 15 for 987654321

Dette stemmer med det jeg fant. Men hvordan kom du fram til dette?

[Nebuchadnezzar]

Stod liste på ei side jeg var innom ^^ Selv fant jeg tre av løsningene før jeg tittet på fasiten.

Me la oss ta en liten oppfølger da, som kanskje krever litt større regnekraft.

Du skal bruke tallene fra 1 til 9 en gang. Og plassere disse i en slik rekkefølge at de gir flest muligheter til å summeres til hundre.

1) Finn den sekvensen av 10 tall, som gir flest muligheter til å summeres til
100 når vi bare har lov til å bruke + og -

2) Samme problem over, bare nå har vi lov til å bruke + - * og /. De fire
elementære regneoperasjonene.