problema EKG Sequence

O secvență de numere întregi poate fi reprezentată grafic foarte ușor, dacă adăugăm pe grafic toate punctele de coordonate (i, ai). În acest caz, i reprezintă o poziție a unui element din secvență, iar ai reprezintă elementul de pe poziția i din secvență.
De exemplu, putem reprezenta grafic secvența (1, 4, 3, 4) în felul următor:
https://ibb.co/3SBvdc7
[ https://ibb.co/3SBvdc7 - Pentru incarcare in pagina (embed) Click aici ]
[ https://ibb.co/3SBvdc7 - Pentru incarcare in pagina (embed) Click aici ]

În această problemă vei folosi o secvență de numere întregi descoperită în anul 2001 și numită Secvența EKG, datorită asemănării graficului ei cu o electrocardiogramă. Poți citi aici mai multe despre ea.
Secvența EKG e definită în felul următor:
a[1] = 1
a[2] = 2
a[n] = cel mai mic număr X care nu apare pe pozițiile anterioare în secvență, iar cmmdc(X, a[n-1]) != 1, unde cmmdc(a, b) e cel mai mare divizor comun al lui a și b
Astfel, secvența începe cu 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15...
Cerință
Află elementul de pe poziția n din secvența EKG.
Date de intrare
Pe prima linie se află un singur număr natural, n.
Date de ieșire
Se va afișa un singur număr natural, reprezentând elementul de pe poziția n din secvența EKG.
Restricții
1 ≤ n ≤ 1000
Exemplu
Date de intrare
10
Date de ieșire
5


imi poate explica si mie cineva problema si cum se face?
multumesc

Cu permutarile cum ai facut?

maccip, on 16 octombrie 2020 - 14:54, said:

inca nu am reusit sa il fac...acuma primesc Crash (SIGSEGV) si incerc sa gasesc problema

Citeste atent exemplul si formula.

a[1] = 1
a[2] = 2
a[n] = cel mai mic număr X care nu apare pe pozițiile anterioare în secvență, iar cmmdc(X, a[n-1]) != 1, unde cmmdc(a, b) e cel mai mare divizor comun al lui a și b
Astfel, secvența începe cu 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15...


nu inteleg cine este X "cel mai mic număr X care nu apare pe pozițiile anterioare în secvență" in ce secventa ca eu nu inteleg cum vine secventa..a[1] = 1; a[2] = 2; a[3] = 3...si tot asa?
si la final cum de a aparut secventa 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15...
de asta spun ca am nevoie de ajutar sa imi explice cineva problema ca nu o inteleg

Sirul Fibonacci ti-e cunoscut?

nu stiam de el...dar am stat si am citit dupa ce ai spus tu..si ii un hint foarte bun pentru problema, o sa incerc sa fac ce reusesc si o sa revin cu intrebari daca ma blochez sau cu un code review
va multumesc pentru ajutor

Ai reusit sa rezolvi problema, pot sa vad codul?

Salut. Vreau si eu sa rezolv problema asta. Sa va zic ce am inteles. Am inteles ce caracteristici are sirul ce trebuie generat. Acuma, exact cum s-a amintit mai sus m-am dus cu gandul la sirul de numere Fibonacci, care era generat dupa o formula simpla, ei bine in cazul nostru nu vad cum ai putea genera urmatorul termen cu ajutorul unei formule. Ma gandesc la vreo 2 for-uri ,chiar 3. Sa fac cumva sa aflu daca intre primul si urmatorul termen al sirului exista cel putin un divizor comun diferit de 1 si sa tin cumva cont de termenii ce au fost afisati deja sa nu se repete.

Edited by Irbaa, 12 July 2022 - 19:39.

Nu are treaba cu Fibonacci. Ala se genereaza din ultimile 2 numere din secventa anterioara. Pentru asta ai nevoie de toata secventa anterioara sa cauti minimul.
Insa are niste proprietati, care trebuie studiate.
1.Din cerinte se vede direct ca un numar nu poate aparea in secventa decat maxim o data.
2.Mai greu, se poate deduce ca orice numar va aparea la un moment dat in secventa.
Deci, fiecare numar va aparea in secventa exact o singura data.

Asta ne duce automat la gandul ca algoritmul de generare va avea structura unui ciur (asemanator cu Ciurul lui Eratostene pentru numere prime).

Apoi, trebuie intrat in fizionomia acestui ciur, sa vedem matematic ce s-ar mai putea optimiza pe-acolo.
Si observam urmatoarele:
Dat fiind faptul ca numarul a[n] trebuie sa aiba divizor comun cu a[n-1], fat sa conteze ce divizor, ne duce cu gandul ca, exprimand numerele in factori primi, conteaza pentru fiecare primi ce multipli apar in secventa.
Pentru fiecare numar prim p, primul multiplu al acestuia care va aparea in secventa va fi p*n prima data, dupa care va urma imediat p deoarece are factor comun cu p*n si e cel mai mic din secventa.

Asta inseamna ca numerele prime vor aparea in ordine crescatoare, iar fiecare numar prim va fi introdus in secventa de catre un alt numar p*n, unde n are factori primi mai mici ca p.
De exemplu primul 5 e prezentat in secventa imeiat dupa 2*5=10,  7 va aparea dupa 2*7=14, 11 dupa 2*11=22 si tot asa. Cel mai probabil numarul prim p va aparea imediat dupa 2*p, dar trebuie demonstrat lucrul asta.
Insa proprietatea asta ca numerele prime sunt in ordine crescatoare in secventa, induce ideea ca subsecventa anterioara trebuie parcursa in cautarea minimului de la un anumit numar in sus, probabil de la a[n/2] pana la [a/n-1].
So, acest lucru s-ar putea implementa sub forma unei cozi. FIFO cu posibilitatea de a elimina orice element din coada. Structura de coada ajutand la parcurgere.
Ai garantia ca numarul prim din coada va fi la un moment dat.

Cam asa se deduce tipul de structura de date cu care lucrezi si algoritmul.
Pentru asta tre sa te joci cu secventa asta si sa mai cauti proprietati ale ei. Poate ar fi mai bine sa faci cate o coada pentru fiecare prim p, mai mic decat o anumita valoare a numarului n (p<n/2, probabil), dar trebuie studiate proprietatile matematice, pentru a fi sigur ca nu uiti un numar sau nu apare de doua ori.
La prima aproximare, ai avea nevoie de un singur for, insa poate daca desparti pe numere prime, va trebui sa mergi cu doua foruri pentru fiecare numar ce vrei sa-l generezi. a[n]

Spre deosebire, sirul fibonacci unde avem proprietatea matematica a[n]=a[n-a]+a[n-2] se poate scrie sub forma a[n]=c*x^n deoarece relatia de definitie se poate aduce sub forma unei ecuatii intre 3 termeni consecutivi aX^2=aX+a, rqadacinile X ale ecuatiei vor reconstitui astfel sirul a[n] fara a cunoaste ceilalti termeni anteriori a[n-1] a[n-2]
In cazul de fata nu se poate face asta deoarece ai functia min() care nu permite deconectarea valorilor secventei de valorile anterioare.

1*1,
2*1,  2*2, 2*3,
3*1, (3*2), 3*3, 3*4,
(4*1), 4*2, (4*3),
5*2,   5*1 , 5*3
(6*1),(6*2), 6*3,
7*2, 7*1, 7*3

e corect?

https://oeis.org/A064413

Edited by MarianG, 17 July 2022 - 12:19.