Euler problem 76


Euler Problem 76: Particioniranje broja.

Particioniranje broja detaljno je objašnjeno na ovom linku, pa stoga je vrlo jednostavno implementirati rješenje.

Ne ulazeći dublje u optimizaciju ovog koda implementacija traje malo duže, mada se vrijeme izvršavanja lako može skratiti.

static long PartitionFn(long k, long n)
{
    if (k > n)
        return 0;
    else if (k == n)
        return 1;
    else
        return PartitionFn(k + 1, n) + PartitionFn(k, n - k);
}
static void Main(string[] args)
{
    Console.WriteLine(PartitionFn(1,100) - 1);
    Console.Read();
}

Mada Mathematica ima posebnu funkciju za ovo:

PartitionsP[100] - 1

Na ovom linku (numerikana.com) se mogu naći bezbroj algoritama vezanih za teoriju brojeva.

Advertisements

Subset Sum Problem


Subset sum problem ili problem sume podskupa definiše se nad skupom cijelih brojeva, iz kojeg je potrebno naći podskup čija suma elemenata iznosi određenu vrijednost.

Problem se može poopćiti na sljedeći jednostavan primjer:

Pretpostavimo da imamo skup S = \{{ 1,2,3,4,5,6 \}}. Potrebno je prebrojati koliko ima podskupava datog skupa čiji zbir elemenata iznosi npr. 7.

Prejednostavan problem, čak se i napamet se može izračunati, bez olovke i papira, a implementacija u nekom programskom jeziku je prejednostavna. Međutim, u koliko se radi o skupu koji ima veći broj elemenata, i ako se radi o vrijednosti sume takodjer velikom broju, tada nastupa problem, jer se klasično ne može riješiti. Problem je poznat po imenu Subset-Sum problem ili Problem Sume Podskupa. Ovo je pojednostavljena verzija Knapsack problema.

SUBSET-SUM = (S,t): postoji podskup S^{'} \subseteq S za koji vrijedi t = \sum_{S \in S^{'}}S

SUBSET-SUM problem: Pretpostavimo da imamo skup S = \{{ x_{1},x_{2},...,x_{N} \}}, od N članova koji predstavljaju cijele brojeve i t cijeli broj.

  1. Decision problem (problem odluke) postavlja pitanje da li postoji podskup S^{'} čija suma članova iznosi t.
  2. Optimization problem (optimizacijski problem) postavlja pitanje koliko ima podskupova S^{'} čija suma članova iznosi t.

Problem koji smo definisali tretira se kao NP problem. Više o NP može se pogledati na datom linku. Koliko je kompleksan ovaj problem zavisi od N i t, a shodno njima se i implementiraju algoritmi za rješavanje.

Matematička analiza problema

Kako je broj elemenata skupa S jednak broju N , to možemo zaključiti da ukupan broj svih podskupova S^{'} koji se mogu definisati iz datog skupa je sljedeći:

C_{N}^{1}+C_{N}^{2}+...+C_{N}^{N}

Vidimo da su podskupovi skupa S, kombinacije bez ponavljanja klasa 1 do N. Zbir ovih kombinacija iznosi:

\sum_{sk=0}^{N}\binom{N}{k}=(1+1)^{N}=2^{N}

Svaki podskup sadrži 0,1,2,3,....,3,2,1 elemenata shodno razvoju Binomnog obrazca iz gornjeg izraza.

Kompleksnost problema

Obični postupak rješavanja ovih problema je “brute-force”, koji generira sve kombinacije podskupova, kojih ima 2^{N}, a generirane podskupove sada je potrebno provjeriti da li zadovoljavaju (ne)jednakost, što čini još dodatnih N operacija. S toga ovaj problem ima kompleksnost odnosno vrijeme izvršavanje O(2^{N}N). Ovo spada u grupu eksponencijalnih vremena izvršavanja. Neki pristupi rješavanja svode kompleksnos na O(2^{N/2}N), djeleći skup na dva podskupa.

Algoritam

Za specifične vrijednosti N i t, problem je moguće svesti na pseudo-polinomalni, koji se rješava dinamičkim programiranjem.

Algoritam dinamičkog programiranja za problem odluke:

Pretpostavimo da imamo polje: x_{1} ,x_{2} ,..., x_{N}. Potrebno je provjeriti da li postoji nepazan podskup čija suma iznosi 0. Neka je N suma negativnih članova polja, a P suma pozitivnih članova polja. Definišimo boolovu funkciju Q(i,s) na način: “postoji neprazan podskup od  x_{1} ,x_{2} ,..., x_{i} čija suma elemenata iznosi s“.

Rješenje problema je vrijednost Q(n,0).

  1. Q(i,s)=false, ako je s<N \vee s>P, s toga ove vrijednosti netrebaju da budu čuvane tokom izvršavanja.
  2. Formirati polje za čuvanje vrijednosti Q(i,s) za 1\leq i\leq n \wedge N\leq s\leq P.
  3. Ova kolekcija se popunjava sljedećom rekurzijom
    1. Inicijalizirati N\leq s\leq P
    2. Postaviti početnu vrijednost funkcije Q(1,s)=(x1=s)
    3. Za i=2 ,...., n
    4. Postaviti Q(i,s)=Q(i-1,s) ili (x_{i}=s) ili Q(i-1,s-x_{i}), za N\leq s\leq P.

Za svaki Q(i,s) vrijednost na desnoj strani je poznata, jer je izračunata iz prethodnih iteracija ili zbog Q(i-1,s-x_{i})=false ako je s-x_{i}>P.

Algoritam optimizacijskog problema

Optimizacijski problem je sličan gore prezentiranom problemu, samo umjesto definisanja boolove funkcije Q(i,s), definišemo funkciju Q(i,s), koja vraća broj podskupova, čija suma elemenata iznosi s.

Rješenje optimizacijskog problema je vrijednost Q(n,0).

Primjena Subset Sum problema

U nekoliko narednih primjera biće demonstrirano korištenje prethodnih definicija i algoritma dinamičkog programiranja:

Problem 1. Koliko se može napraviti podskupova skupa S=\{{1,2,3,4,5,6\}}, čija je suma t=7.

Problem je vrlo jednostavan jer želimo vidjeti na koji način algoritam radi. Prvo, rješimo ovaj problem „pješice“ i pogledajmo koliko takvih posdkupova ima. To su:

S^{'}_{1}= \{{ 6,1 \}}, S^{'}_{2}= \{{ 5,2 \}}, S^{'}_{3}= \{{4,3 \}}, S^{'}_{4}= \{{1,2,4 \}}.

Vidimo da ukupno postoji 4 takva podskupa.Napišimo implementaciju ovog problema shodno gore prezentiranom algoritmu.

static void Main(string[] args)
{
    Console.Title = "Subset Sum Problem...";
    //Inicijalizacija skupa S i vrijednosti t
    int[] S = new int[6] { 1, 2, 3, 4, 5, 6 };
    int t = 7;

    //polje za čuvanje vrijednosti Q(s)
    int[] Q=new int[t+1];
    //Pocetna vrijednost
    Q[0]=1;
    //Iteracija od 0-N
    for (int i = 0; i < S.Length; i++)
    {
        int s=S[i];
        //Iteracija od t-si
        for (int j = t; j >= s; j--)
            Q[j] += Q[j - s];
    }
    Console.WriteLine("Postoji {1} podskupa čija je suma>={0}",t,Q.Sum()-1);
    Console.Read();
}

Izlaz na konzolu je sljedeći:

Linija 18 čini čaroliju kod ove implementacije. Važno je naglasiti da iteracija kod druge petlje mora ići u silaznom smijeru od t do s_{i} . U koliko bi išla u suprotnom smjeru tada bi ova implementacija imala sasvim drugi smisao kojem će biti riječi možda neki drugi put.
Gornjom implementacijom ne samo da smo prebrojali koliko postoji podskupova čija je suma 7, nego smo prebrojali i sve podskupove čija je suma manja ili jednaka 7. Kako smo kazali kroz definiciju algoritma da je vrijednost Q[n,t] broj podskupova čija je suma iznosi s, to znači da je Q(N,t-1) rješenje za problem t-1, i td. Sve do praznog skupa onosno 0. Ovim se želi kazati da algoritam rješava problem sume manje ili jednake od t.
U koliko bi, shodno prethodnom (nemjenjajući logiku gornje implementacije) željeli znati koliko ima podskupova čija je vrijednost manja ili jednaka 7, potrebno je samo promjeniti liniju 20, i to na sljedeći način:
Console.WriteLine("Postoji {1} podskupa čija je suma>={0}",t,Q.Sum()-1);

Od sume oduzimamo jedinicu jer želimo izbaciti prazan skup odnosno m[0].
Na jednostavnom problemu prikazan je Subset sum problem, koji je vrlo koristan kod rješavanja složenijih problema. Jedan od primjene ovog problema je u Euler Problem 249 i 250, koji se mogu riješiti primjenjujući upravo ovaj način implementacije. U nekom od narednih postova biće prikazana rješenja ovih problema.
References:

Euler Problem 125


Euler Problem 125:

Unutar minute:

class Program
{
    static void Main(string[] args)
    {
        int N = 100000000;
       // int N = 1000;
        List<long> nums= new List<long>();
        List<int> palindrom= new List<int>();
        for (int i = 2; i < N; i++)
            if (IsPalindrom(i.ToString()))
                palindrom.Add(i);

       for (int i = 0; i < palindrom.Count; i++)
        {
            int num=palindrom[i];
            if (IsSumSquare(num))
                nums.Add(num);

        }
       Console.WriteLine(nums.Sum());
       Console.WriteLine("Press any key to continue...");
       Console.Read();
    }

    private static bool IsSumSquare(int num)
    {
        int sqrt = (int)Math.Sqrt(num);
        if (sqrt * sqrt == num)
            sqrt -= 1;
        for (int j = sqrt; j >= 2; j--)
        {
            bool found = false;
            int k = j;
            int sum = 0;
            while (true)
            {
                sum += k * k;
                if (sum == num)
                  return true;
                else if (sum > num)
                    break;
                else if (k > 1)
                    k--;
                else
                    break;
            }
            if (found)
                break;

        }
        return false;
    }
     static bool IsPalindrom(string n)
    {
        int lnl;
        if (n.Length % 2 != 0)
            lnl = 1 + n.Length / 2;
        else
            lnl = n.Length / 2;

        int ln = n.Length;
        for (int i = 0; i < ln / 2; i++)
            if (n[i] != n[ln - 1 - i])
                return false;
        return true;
    }

}

Euler Problem 230


Euler Problem 230: Fibonacci Words

Članak o Fibonacci words može se pogledati na wikipedia. Fibonacci Words predstavlja L-System. Formula pomoću koje se dobije n-to slovo u Fibonaccijevom nizu data je izrazom:

a(n) = \left \lfloor (n+2)*r \right \rfloor-\left \lfloor (n+1)*r \right \rfloor

gdje je

a(n) = \left \lfloor x\right \rfloor floor funkcija (najveći cijeli broj r<=x),

r=\frac{\varphi }{1+2\cdot \varphi}

\varphi=\frac{1+\sqrt{5} }{2} – zlatni rez (Golden ratio)

Obzirom da su ovdje u pitanju riječi A i B, koje čine 100 cifara (karaktera), potrebno je formulu modificirati nanačin da je n-to slovo koje se traži mora oduzeti od 200 odnosno Length(A+B). Nakon toga n se podjeli sa 100 i izračuna spomenuta formula. Ostatak djeljenja n sa 100 je cifra u riječi A ili B, zavisno od evaluacije formule.

static string a = "1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
static string b = "8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196";
static double phi = (1 + Math.Sqrt(5)) / 2.0;//Golden Ratio
static double r = phi / (1 + 2 * phi);

public static int D(long n)
{

    if (n > 200)
        n -= 200;      // -> ab-200
    else if (n > 100)
        n -= 100;      //B -> ab-100
    //else
    //    n = n;       //A -> a

    long m = n / 100;

    int index = (int)(n % 100);//Index of digit of word A or B

    //nth Fibonacci Word http: // research.att.com/~njas/sequences/A003849
    double nthDigit = (long)((m + 2) * r) - (long)((m + 1) * r);

    if (nthDigit == 1)//A
        return int.Parse(a[index - 1].ToString());
    else//B
        return int.Parse(b[index - 1].ToString());
}

static void Main(string[] args)
{
    long sum = 0;
    for (int i = 0; i <= 17; i++)
    {
       long m = (127 + 19 * i) * (long)Math.Pow(7, i);

        int digit = D(m);

        sum += digit * (long)Math.Pow(10, i);
    }
    Console.WriteLine(sum);
    Console.ReadLine();
}

Euler Problem 104


Euler Problem 104:

Na prvi pogled zadatak vrlo prost. Mathematica bi trebala da ga riješi za pa sekundi. Medjutim…
Prvi Brute force pokušaj i nije bio toliko loš.

For[i=45,True,i++,lst=IntegerDigits[Fibonacci[i]];
If[Sort[lst[[1;;9]]]=={1,2,3,4,5,6,7,8,9},If[Sort[Take[lst,-9]]=={1,2,3,4,5,6,7,8,9},Break[],Print[i]]]
];i

Print[i] koji je stavljen ispisiva pandigitalne brojeve prvih 9 cifara Fibonaccievog broja. Ovim se htjelo vidjeti kako se često takvi brojevi pojavljuju, i drugo kako brzo algoritam radi.
Ubrzo se vidjelo da kod neće završiti brzo.

Druga optimizacija bila je da se izračunava ostatak djeljenja Fibonaccievog niza sa 10^9, a onda da se provjeri da li je prvi dio cifara pandigitalan. Odmah se vidjelo da je algoritam dosta brži ali i da neće završiti za 60 sekundi.

For[i=45,True,i++,
If[Sort[IntegerDigits[Mod[Fibonacci[i],10^9]]]=={1,2,3,4,5,6,7,8,9},
If[Sort[IntegerDigits[Fibonacci[i]][[1;;9]]]=={1,2,3,4,5,6,7,8,9},Break[],Print[i]]]];

U implementaciji najsporiji dio je funkcija Fibonacci[], koja svaki put mora ispočetka da izračunava Fobonaccijev broj. Sada je potrebno ovaj dio optimizirati:

f1=1;f2=1;For[i=3,True,i++,
f=f1+f2;
If[Sort[IntegerDigits[Mod[f,10^9]]]=={1,2,3,4,5,6,7,8,9},
If[Sort[IntegerDigits[f][[1;;9]]]=={1,2,3,4,5,6,7,8,9},Break[],Print[i]]];
f1=f2;
f2=f
];i

Kod se izvršava za 20 sec što je prihvatljiv rezultat. Približan rezultat dobijemo i sa C# implementacijom:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
namespace EulerProblem104
{
    class Program
    {
        static void Main(string[] args)
        {
            BigInteger div=BigInteger.Pow(10,9);
            long n = 1;
            foreach (var x in FibonacciNiz())
            {
                if (IsPanDigital(x % div))
                {
                    string ss = x.ToString();
                    if (ss.Length > 8)
                    {
                        var digits = ss.Substring(0, 9);
                        if (IsPanDigital(BigInteger.Parse(digits)))
                            break;
                    } 
                }
                n++;
                
            }
            Console.WriteLine(n);
            Console.WriteLine("Press any key to continue...");
            Console.Read();

        }
        static bool IsPanDigital(BigInteger numb)
        {
            var v = numb.ToString();
            if (v.Length < 9)
                return false;
           var ss=v.OrderBy(x => x).ToArray();
            for (int i = 0; i < ss.Count(); i++)
                if (ss[i].ToString() != (i + 1).ToString())
                    return false;
                return true;
        }
        static IEnumerable<BigInteger> FibonacciNiz()
        {
            BigInteger a = 1;
            BigInteger b = 1;
            BigInteger c = 0;
            yield return a;
            yield return b;
            while (true)
             {
               yield return c = a + b;
               a = b;
               b = c;
             }
        }
   }

}