Pamatalgoritmi

Uzdevuma formulējums
Naturālo skaitļu ciparu summa. Atrast ciparu kopsummu visiem naturāliem skaitļiem no 1 līdz n. Izvēlēties tādu algoritmu, lai programma strādātu pieņemamā laikā arī uz lieliem skaitļiem (1 .. 1000000000).

Ieejas fails
Ieejais fails satur skaitli, ko vajag apstradāt.

Rezultātu fails
Rezultāta fails satur programmas izpildes rezultātu.

Iespējamie risinājumi un to teorētiskais pamatojums
Es izdomāju 2 risinājumus šim uzdevumam.
1. Pirmam uzdevuma risinājumam ir vienkārša realizācija un algoritms. Tā būtība ir iet no 1 līdz n, katram skaitlim aprēķināt tā ciparu summu un pieskaitīt kopējai summai. Diemžēl šajā gadījumā ir nepieciešams iziet cauri visiem skaitļiem un aprēķināt to ciparu summu, kas ir ļoti ilgs process, it īpaši tad, kad n > 50000.
2. Otrs uzdevuma risinājuma algoritms ir sarežģītāk, toties strādā ātri arī uz lieliem skaitļiem. Tā pamatideja ir aprēķināt gālēja skaitļa sastavdaļu ciparu summu. Skan diezgan briesmīgi, bet ja mēģināt izteikt to ar forumulu, tad skaitlim n=1234 tas varētu izskatīties sekojoši:
sum(1234) = 1*sum(999) + 1*(1234 - (1*103) + 1) + ((1-1)*103) +
+ 2*sum(99) + 2*(234 - (1*102) + 1) + ((2-1)*102) +
+ 3*sum(9) + 3*(34 - (1*101) + 1) + ((3-1)*101) +
+ 4*(4 - (1*100) + 1) + ((4-1)*100)
Protams, ja ciparu ir vairāk, arī aprēķināšana ir garāka – algoritms ir atkarīg no ciparu skaita.…