[Zadatak] Suma cifara

[ proka_92 @ 13.02.2010. 15:17 ] @

Definišemo funkciju f(n) kao sumu cifara prirodnog broja n. U datom celobrojnom intervalu [ A, B ] naći broj k koji se najviše puta pojavljuje u nizu f(A), f(A + 1), f(A + 2), ..., f(B - 1), f(B). U slučaju da postoji više takvih brojeva k, ispisati onaj najveći.

INPUT:
U prvom redu se nalaze prirodni brojevi A i B (1 <= A <= B <= 10.000.000).

OUTPUT:
U prvom i jedinom redu ispisati broj k koji predstavlja vrednost objašnjenju u postavci zadatka.
Izvor: www.z-trening.com
Ja sam odradio ovako, ali mi 3 testa ne prolaze vremenski:

Code:

#include <stdio.h>
int f(long n){
    if(n!=0) return (n%10+f(n/10)); //probao sam i slucaj kada funkcija nije rekurzivna
    else return 0;}
int maxniza(int a[],int n){
    int i,max=a[0],maxpoz=0;
    for(i=1;i<n;i++)
        if((a[i]>=max) && (i>maxpoz)){
            max=a[i];
            maxpoz=i;}
    return maxpoz;}
main(){
    long A,B;
    int x[64],i,s,max;
    scanf("%ld%ld",&A,&B);
    for(i=0;i<63;i++)
        x[i]=0;
    for(A;A<=B;A++){
        s=f(A);
        x[s]++;}
    max=maxniza(x,64);
    printf("%d",max);
    return 0; }

_{[Ovu poruku je menjao proka_92 dana 13.02.2010. u 19:40 GMT+1]}

[ Picsel @ 13.02.2010. 19:53 ] @

Jedan nacin je da ne prolazis petljom kroz interval i "izvlacis" cifre iz broja pomocu % i /, vec generises sve brojeve dodavajuci cifru po cifru na broj, a i na zbir cifara tog broja koji generises.
Evo moja realizacija ove ideje (generisem sve brojeve sa 7 i manje cifara i samo jos proverim za 10 000 000 naknadno)

Code:
#include <stdio.h>

int a,b,res,zbirovi[64];

void gen(int cifra, int broj, int zbir)
{
  int i;
  if (cifra>7)
  {
    if (broj>=a && broj<=b)
      zbirovi[zbir]++;
  }
  else
    for (i=0; i<10; i++)
      gen(cifra+1,broj*10+i,zbir+i);
}

int main()
{
  int i,k,max=0;
  scanf("%d %d",&a,&b);
  gen(1,0,0);
  if (10000000>=a && 10000000<=b)
    zbirovi[1]++;
  for (i=0; i<64; i++)
    if (zbirovi[i]>=max)
    {
      max=zbirovi[i];
      k=i;
    }
  printf("%d",k);
  return 0;
}

Drugi i mnogo efikasniji, ali i komplikovaniji, nacin bi bilo dinamicko programiranje. Osnovna ideja je da imas matricu gde je jedna dimenzija sve moguce sume (do 63) a druga dimenzija broj cifara (do 7), popunis tu matricu tako da na mestu i,j se nalazi broj brojeva sa i cifara i sumom cifara j i onda tu matricu iskoristis tako da proveris samo potreban interval. Popunjavanje matrice se vrsi na osnovu ranije popunjenih polja matrice.

[ proka_92 @ 14.02.2010. 18:34 ] @

Code:
void gen(int cifra, int broj, int zbir)
{
  int i;
  if (cifra>7)
  {
    if (broj>=a && broj<=b)
      zbirovi[zbir]++;
  }
  else
    for (i=0; i<10; i++)
      gen(cifra+1,broj*10+i,zbir+i);

Jel mozes da mi malo objasnis kako radi ova funkcija, na nekom primeru? Hvala unapred.

[ Picsel @ 14.02.2010. 20:05 ] @

Cifra je cifra koju generise, odnosno prvu, drugu, trecu itd. Broj je taj broj koji generise (on nije neki odredjeni broj vec trenutno generisani broj) a zbir je zbir cifara (tog trenutnog generisanog broja).
Posle svakog poziva funkcije, generise se sledeca cifra u broju i tako dok se ne dodje do generisanja 8. cifre. Kad se dodje do 8. cifre, odnosno cifra>7, onda se proverava da li je taj broj u trazenom intervalu i ako jeste dodaje se zbir.
Ukoliko se generise neka ranija cifra, onda jednostavno petlja prolazi kroz sve moguce cifre od 0 do 9 i prelazi na sledecu cifru.
Znaci, prvo se generise broj 0000000, pa onda se generise 0000001, pa 0000002 itd.
Ne mogu bolje da objasnim, koristi debug ako i dalje nije jasno, ili ispisuj parametre u svakom rekurzivnom pozivu da vidis sta se desava. Mozes i staviti uslov na cifra>2 da vidis kako generise sve dvocifrene brojeve, ako je tako lakse.