Ştiri:

Vă rugăm să citiţi Regulamentul de utilizare a forumului Scientia în secţiunea intitulată "Regulamentul de utilizare a forumului. CITEŞTE-L!".

Main Menu

cifra de pe pozitia m dintr-un sir de cifre

Creat de Ayumi, Decembrie 27, 2011, 04:59:05 PM

« precedentul - următorul »

0 Membri şi 2 Vizitatori vizualizează acest subiect.

Ayumi

Buna seara !

Nu reusesc sa rezolv urmatoarea problema :
Ionel este pasionat de matematică. El inventează tot felul de probleme. De data aceasta Ionel s-a gândit să genereze un şir de cifre, plecând de la un număr natural şi aplicând o anumită regulă. De exemplu, pentru numărul 425 el va genera şirul: 4, 4, 4, 4, 2, 2, 5, 5, 5, 5, 5 astfel: ia, în acestă ordine, prima cifra din număr (4) şi o repetă de 4 ori, apoi ia a doua cifră (2) şi o repetă de 2 ori, apoi ia a 3-a cifra (5) şi o repetă de 5 ori. Ionel se întreabă ce cifră se găseşte în şir pe o pozitie precizată. De exemplu, pe poziţia 3 se găseşte cifra 4.

Scrieţi un program care, pentru numărul N dat şi M, poziţia unui termen din şir, determină valoarea termenului al M-lea din şirul generat după regula de mai sus.De exemplu,pentru N = 425 si m = 5 ==> 2,iar pentru N= 302 si m = 2 rezulta 3.
Ma gandeam sa scot cifrele din numarul N si sa le retin intr-un vector a si sa am o variabila i care merge de la 1 pana la numarul de cifre ale lui N. Cum as putea continua? Este de ajuns daca imi puteti da o idee,deoarece cu for-urile pe care le-am folosit eu intr-un while nu merge programul decat pentru unul din exemplele de mai sus.

HarapAlb

Se poate face mai simplu, lungimea sirului e data de suma cifrelor numarului.

Ayumi

Da,asta am observat si eu dupa ce am mai incercat cu programul,dar cum pot continua dupa asta ?

Quantum

Declari un sir de lungime egala cu suma si apoi pentru fiecare element din sirul initial adaugi la al doilea sir elementul respectiv de cate ori indica elementul. Astfel indicele m-1 v-a indica elementul cautat in sirul 2. Am scris un exemplu:

#include<iostream>

using namespace std;
int main()
{
    int N,c[5],m,k=0,j=0, suma=0;
    cin>>N;
    cin>>m;

    while(N!=0)
    {
    c[k]=N%10;
    N/=10;
    suma=suma+c[k];
    k++;
    }
    int sir2[suma];
    k--;
    for (;k>=0;k--)
    {
        for(int i=0;i<c[k];i++)
        {
            sir2[j]=c[k];
            j++;
        }
    }
    cout<<sir2[m-1];
    return 0;
}

AlexandruLazar

Principiul de rezolvare indicat de Quantum e ok, dar se poate face chiar mai simplu de atât, fără a mai genera şirul acela într-un vector. Desigur, pe urmă devine mai mult o problemă de matematică decât de programare.

Ayumi

Citat din: AlexandruLazar din Decembrie 28, 2011, 01:57:01 PM
Principiul de rezolvare indicat de Quantum e ok, dar se poate face chiar mai simplu de atât, fără a mai genera şirul acela într-un vector. Desigur, pe urmă devine mai mult o problemă de matematică decât de programare.
Si metoda mai simpla care ar fi ? Tinand cont de faptul ca lungimea sirului este data de suma cifrelor numarului ?

AlexandruLazar

Cel mai simplu cred că se vede pe o serie de exemple. O să le dau considerând indexarea de la 1 (are mai multă logică să spun prima, a doua, a treia cifră decât a zero-a -- dar ai grijă când faci implementarea în C, unde indecşii încep cu 0, nu cu 1).

Să începem pe cazul banal -- numărul are o singură cifră. De exemplu, pentru M = 3, numărul de pe o poziţie oarecare i din şir va fi cu siguranţă 3.

Pentru M = 34, numărul de pe orice poziţie i = 1..3 va fi 3, iar pentru orice poziţie i > 4 va fi 4 (şirul corespunzător este 3 3 3 4 4 4 4).

Pentru M = 348, numărul de pe orice poziţie i = 1..3 va fi 3; pentru orice poziţie între 4 şi 3 + 4 = 7, va fi 4; şi pentru orice poziţie de la 8 în sus, va fi 8. Sirul corespunzător ar fi 3 3 3 4 4 4 4 8 8 8 8 8 8 8 8

Pentru M = 3482, numărul de pe orice poziţie i = 1..3 va fi 3; pentru orice poziţie i = 3+4...3+4+8 va fi 8; pentru orice poziţie i = 3+4+8..3+4+8+2 va fi 2.

Poţi să prinzi care e regula după care se face asta? Poate îţi e mai uşor să prinzi regula dacă nu te gândeşti, pentru început, la faptul ca ai de-a face cu cifrele unui număr -- imaginează-ţi că în loc să porneşti de la un număr M, porneşti de la un şir format din cifrele lui.

BTW -- motivul pentru care metoda asta e interesantă e acela că e o ilustrare primitivă (dar destul de bună) a unui principiu numit lazy evaluation -- sau oricum, a unui aspect al lui. In cazul de faţă, întrucât nu lucrezi decât cu numere întregi iar regula de generare a şirului este una simplă, nu serveşte niciunui scop interesant, dar în practică apar situaţii în care se poate dovedi util. Poţi să îţi faci o idee a motivului pentru care ar putea fi util dacă încerci să îţi imaginezi ce s-ar întâmpla în cazul în care ai porni de la un număr foarte mare (câteva milioane de cifre de exemplu); de asemenea, îţi poţi pune şi problema de eficienţă -- ce s-ar întâmpla într-un astfel de caz dacă ţi s-ar cere al treilea element din set (hint: ai genera un vector de zeci de milioane de elemente dintre care te-ar interesa doar unul).

Ideea de bază e ca, dacă te interesează să găseşti o valoare dintr-un set, iar timpul în care poţi genera setul respectiv (sau cantitatea de memorie necesara pentru asta) este foarte mare, s-ar putea să merite să investighezi dacă nu cumva poţi, având doar descrierea setului (i.e. regula după care este alcătuit), să găseşti doar valoarea respectivă, atunci când este nevoie de ea, în loc să generezi tot setul şi să o alegi doar pe ea.

zec

 Intradevar,dar se poate face si asa.Eu prezint doar algoritm
Pasul 1:Determinarea cifrelor lui N si asezarea lor intro stiva.Se imparte N cu 10k incepand cu k=1pana cand 10k>N si se citesc resturile si suma cifrelor sale.
Pasul 2:Daca M<Cifra1 atunci afiseaza cifra 1 altfel il faci pe M=M-Cifra1 si compari cu urmatoarea cifra .E evident ca aceasta comparatie merge dupa un ciclu repetativ pana cand cifra devine null.Dar apare o discutie de compatibilitate si anume daca M depaseste suma cifrelor avem incompatibilitate.De aceea trebuie initializata si o discutie de tip if astfel:
if M>Suma cifrelor then cuote<<nu avem solutii>>
  else repeat if M<cifra i then coute<<cifra i
                    else M=M-cifra i i=i+1
        until cifra i=null;
Observatie nu ma pricep prea bine la scrierea sub limbaj dar la algoritmi da.Sper ca ai prins ideea si e mult mai optim sa lucrezi cu pointeri la acest gen de cerinte.

AlexandruLazar

Daca am inteles bine la ce te gandesti, cred ca de fapt vorbim de acelasi lucru -- doar ca nu vroiam sa dau direct algoritmul, ci regula pe baza caruia se poate ajunge la el.