Project Euler 113

Sabahlama rutinimin son adımı olarak uyumadan önce bir tane Project Euler sorusu çözüyorum :) Bugünün talihlisi de bu soru.

112379 ya da 98760 gibi, basamaklarındaki rakamların, artan ya da azalan şekilde, sıralanmış hali kendisine eşit olan sayılara monoton sayılar diyelim (her ne kadar soruda böyle bir tanım olmasa da :)). 10^{100}‘den küçük kaç tane monoton sayı vardır?

Sorunun çözümünü bulmak için ilk önce kaç tane monoton sayı olduğunu bulmamız lazım. Sonrasında bu toplamdan, her iki durum için de 11, 1111... gibi tüm basamakları birbirine eşit olan sayılar tekrar ettiği için basamak sayısı * 9’u yani 900‘ü çıkaracağız.

Artan monoton sayılar: 

n basamaklı bir sayının artan monoton bir sayı olması için, n. basamağa gelen sayının n-1. basamaktaki sayıdan büyük ya da eşit olması ve sonuna eklendiği n-1 basamaklı sayının da monoton artan bir sayı olması lazım. İlk durum olarak, 0 dışındaki her bir sayının monoton artan olduğunu düşünelim. Bu sayede, aşağıdaki fonksiyon ile artan monoton sayıların kaç tane olduğunu bulabiliriz;

(1)   \begin{equation*} F(n, digit) = \begin{cases}0, digit = 0 \\ 1, digit > 0 \& n = 0 \\ F(n-1, digit) + F(n, digit - 1), digit > 0 \& n > 0 \end{cases} \end{equation*}

Azalan monoton sayılar: 

Artan monoton sayılara benzer bir şekilde, n basamaklı bir sayının azalan monoton sayı olması için, eklenen sayının n-1. basamaktaki sayıdan küçük ya da eşit olması ve sonuna eklendiği n-1 basamaklı sayının da azalan monoton olması gerekmektedir. Bu sayıları da aşağıdaki fonksiyonla bulabiliriz;

(2)   \begin{equation*} G(n, digit) = \begin{cases}0, digit = 0 \& n = 0\\ 1, digit = 9 \\ G(n-1, digit) + G(n, digit + 1), digit < 9 \& n > 0 \end{cases} \end{equation*}

Tüm sayıların toplamını ise

(3)   \begin{equation*} \sum\limits_{i=0..100, j=0..9} F(i, j) + G(i, j) \end{equation*}

ile bulabiliriz.