Dzień dobry, chciałem się dowiedzieć czy jest jakiś inny sposób na sprawdzenie czy X jest w vectorze niż na pętli.
W bibliotece standardowej jest find, ale jeśli chodzi Ci o szybszy sposób, to nie ma, złożoność wyszukiwania liniowego jest zawsze n
.
p = std::find (myints, myints+4, 30);
30 oznacza liczbe szukaną?
- a może potrzebujesz innej struktury danych, np std::map?
- Hipotetycznie, gdyby to było na wskaźnikach / referencjach to typu danych, można by myśleć o dualnym kontenerze
na pewno sa liczne biblioteki poza std:: do twojego zagadnienia
Jeśli elementy są nieuporządkowane to raczej nie ma innego wyjścia, niż przejść po elementach w O(n)
.
Co innego, gdyby był uporządkowany, bo wtedy mógłbyś wykorzystać wyszukiwanie binarne w O(logn)
.
Wydaje mi się, że znając rozkład wartości dało się nawet zejść do O(loglogn)
czy jakoś tak, przynajmniej optymistycznie.
A gdybyś zamiast wektora mógł użyć zbioru wartości (zależy co z nim jeszcze robisz, poza szukaniem elementów) z czymś pokroju hash table pod spodem, to miałbyś znajdowanie elementu w O(1)
;)
@AnyKtokolwiek:
Nie znam std::map i nie mam pojęcie jak działa.
A jeśli chodzi o zadanie to (http://szkopul.edu.pl/problemset/problem/Cgw52wK7lgkABFnX_GbP-kiD/site/?key=statement)
i warto zauważyć że w pewnym momencie pojawia się cykl, ale można go użyć tylko wtedy gdy X==2,4,8,16,14,10.
Czy cykl występuje też dla cyfr 3, 5, 6, 7, 9? Jeśli tak to czy wszystkie liczby można znormalizować do cyklu? Jeśli tak to tutaj nie potrzeba tablicy a dzielenie modulo.
@lubie_programowac: takie rozwiązanie jest za wolne, dla tego zadania
Na razie takie coś wyszło, ale czy może zmienić p=find (t,t+N,X);
ponieważ ten element zgłasza błąd o złym operatorze.
#include <iostream>
#include <vector>
using namespace std;
int suma(long long X)
{
int wynik=0;
while(X!=0);{
wynik = wynik + X%10;
X=X/10;
}
return wynik;
}
int main()
{
ios_base::sync_with_stdio(0);
int N,X,p;
cin >> N >> X;
int A=X;
if(N==1){
cout << X;
}
else{
X=suma(X)*2;
vector <int> t={2,4,8,16,14,10};
p=find (t,t+N,X);
if(p==X){
cout << t[(N-2)%6];
break;
}
else{
for(int i =2;i<=N;i++){
A=suma(A)*2;
}
cout << A;
break;
}
}
return 0;
}
Sugerowałbym użycie vector<size_t> used(18*9*2+1);
Zaznaczasz w tym wektorze elementy które już były oprócz elementu pierwszego jeżeli jest poza zakresem.
used[wartość]=numer;
A ja bym sugerował przeanalizować problem.
W tym ciągu pojawiają się cykle, na dodatek każda wartość początkowa, zawsze zbiega się do jednego z cykli, więc nie trzeba liczyć tego siłowo.
Wpisz te cykle "twardo" w kod. Potem licz kolejne elementy ciągu, aż do napotkania cyklu, a potem korzystając z cykliczności skacz do wyniku końcowego.
Tych cykli jest mało, więc można liczyć je na kartce.
Okaże się, że std::vector
jest tu zbędny.
@KomnatoMan: Raczej nie, inaczej po sprawdzeniu miliona losowych liczb, (co wyklucza, imo, przypadek) widać, że średnia ilość iteracji, żeby znaleźć cykl to 7.21
, maksymalna 10
. Liczy to kod w Pythonie, samotłumaczący się:
def sum_digit(n):
s = 0
while n > 0:
s += n % 10
n //= 10
return s
def cycle(n):
x0 = n
cnt = 0
xn = None
s = set()
s.add(x0)
while True:
xn = 2 * sum_digit(x0)
x0 = xn
cnt += 1
if xn in s:
return xn, cnt
else:
s.add(xn)
if __name__ == '__main__':
n = 10 ** 18
max = 0
acc = 0
iters = 1000000
for _ in range(iters):
k = random.randint(1, n)
m = cycle(k)[1]
acc += m
if m >= max:
max = m
print(max) # -> 10
print(acc / iters) # -> 7.21
Istnieją tylko trzy cykle:
18
6
,12
2
,4
,8
,16
,14
,10