patrate

[•claudiu25]

Va rog ma ajutati si pe mine la urmatoarea problema : Pentru un numar n dat trebuie sa realizati un program care determina cate numere de n cifre din baza 10 au proprietatea ca patratul lor se termina in secventa 987654321. Numarul n se va citi de la tastatura si va avea maxim 6 cifre. exemplu : n=9 si numarul 111111111 ridicat la patrat se termina in 987654321.

[•Kira96]

Pai din numarul ala de n cifre doar ultimele 9 conteaza ca sa iti iasa sufixul ala. Acum, poti sa bagi brute 10^8 numere, si fixezi ultima cifra 1 sau 9 ca sa iti iasa patratul terminat in 1, asa poti afla numerele de 9 cifre sau mai putin pentru care patratul are sufixul ala. Apoi, pentru n cifre(n>=9), raspunsul va fi :
numarul de numere gasite cu 9 cifre * 10^n-10^(n-1)

[•claudiu25]

Pai din numarul ala de n cifre doar ultimele 9 conteaza ca sa iti iasa sufixul ala. Acum, poti sa bagi brute 10^8 numere, si fixezi ultima cifra 1 sau 9 ca sa iti iasa patratul terminat in 1, asa poti afla numerele de 9 cifre sau mai putin pentru care patratul are sufixul ala. Apoi, pentru n cifre(n>=9), raspunsul va fi :
numarul de numere gasite cu 9 cifre * 10^n-10^(n-1)

pai si daca n=9 cum fac ca sa aflu numerele care ridicate la patrat se termina in 987654321?

[•Kira96]

Fixezi ultima cifra 9 sau 1 si faci 10^8 iteratii pentru restul cifrelor pentru a afla...

[•proflaurian]

Denis are dreptate pana la un punct si anume ca te intereseaza doar ultimele 9 cifre si inceputul de idee.

Cel mai usor e sa folosesti metoda backtracking prin care sa depistezi cifra cu cifra numerele de 1, 2 , 3, ..., 9 cifre care ridicate la patrat se termina in 1, 21, 321, ..., 987654321. Iti dau mai jos o posibila implementare a unui astfel de back.

Cod:

void bk(int poz) 
{
    int i,j,c;
    if(poz==9)
    {
        for(i=8;i>=0;i--)
            g<<sol[i];
        g<<'\n';
        return;
    }
    for(c=0;c<=9;c++)
    {
        sol[poz]=c;
        for(i=0;i<=poz;i++)ver[i]=0;
        for(i=0;i<=poz;i++)for(j=0;j<=poz;j++)ver[i+j]+=sol[i]*sol[j];
        for(i=0;i<=poz;i++){ver[i+1]+=ver[i]/10;ver[i]%=10;}
        for(i=0;i<=poz;i++)if(ver[i]-i-1)break;
        if(i==poz+1)bk(poz+1);
    }
}

Am rulat si se pare ca raspunsul la intrebarea ta e foarte simplu. In primul rand trebuie sa ai n > = 9. In al doilea rand ultimele 9 cifre nu pot fi decat in una dintre urmatoarele 8 variante:

Cod:

111111111
611111111
380642361
880642361
119357639
619357639
388888889
888888889

Daca nu gresesc atunci raspunsul este :
0 daca n<9
8 daca n=9
8*10^n-9 daca n>9 ( 8 moduri de a forma sufixul de 9 cifre a numarului cautat si 10^n-9 moduri de a pune cele cel mult n-9 cifre din prefixul numarului.