Question

Oare ma ajuta cineva cu aceasta 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:

Î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 ≤ 1 000
Exemplu
Date de intrare Date de ieșire
10 5

Answer 1

► Raspuns :

#include <iostream>

#include <unordered_set>

using namespace std;

//Calculeaza cmmdc dintre a si b

int cmmdc(int a, int b) {

while (b) {

 a = a % b;

 swap(a, b);

}

return a;

}

//Returneaza numarul de pe pozitia n din secventa EKG

int ekg(int n) {

//Cazuri speciale

if (n == 1) return 1;

if (n == 2) return 2;

//Multime de numere deja parcurse

unordered_set<int> parcurse;

parcurse.insert(1);

parcurse.insert(2);

int ante, curent=2;

int i;

//Primele 2 numere sunt deja generate, incepem de la al treilea

for (i = 3; i <= n; i++) {

 ante = curent;

 curent = 1;

 //Cauta urmatoarul numar care nu apare in multime si are cmmdc cu numarul anterior diferit de 1

 while (parcurse.find(curent) != parcurse.end() || cmmdc(ante, curent)==1) ++curent;

 //Adauga numarul gasit in multimea de elemente deja gasite in secventa

 parcurse.insert(curent);

}

return curent;

}

int main() {

int n;

cin >> n;

cout << ekg(n);

}

► Explicatie :

◘ unordered_set este o structura de date predefinita in STL care permite retinerea unei multimi de elemente:

• Structura retine toate elementele care apar, dar o singura data
• Daca incercam inserarea aceluiasi element de mai multe ori se va adauga o singura data
• Reprezinta o generalizare a notiunii de vector caracteristic. Intr-un vector caracteristic multimea posibila a cheilor trebuie sa fie finita si destul de mica. In unordered_set nu avem aceste limitari, structura are la baza o functie de hashing care calculeaza hash pentru fiecare element introdus si se repartizeaza apoi intr-un vector caracteristic. Astfel complexitatea obtinuta este foarte buna (teoretic constanta). Varianta aceasta e mult mai rapida decat daca am cauta manual prin vector ce valori am vazut deja.

◘ Functii membre unordered_set folosite in program:

• insert(element) → Insereaza element in multime
• find(element) → Returneaza (iterator) pointer catre element daca acesta exista in multime sau iterator catre sfarsitul structurii (.end()) daca acesta nu exista in multime

Iti recomand sa cauti mai multe informatii despre unordered_set (functii membre, cum e implementat, de ce are complexitatea O(1) ), dar si despre alte structuri de date din STL pe internet. Aceste elemente simplifica foarte mult treaba programatorului si fac diferenta intre o aplicatie proasta si una excelenta.