Witam, mam taki problem, że chcę napisać program, który przyjmuje n liczb w różnej kolejności i mam wyświetlić tą, której reszta z dzielenia przez 3 jest równa 0. W całym ciągu n liczb jest tylko jedna taka liczba, której %3 jest równe 0. Problem polega na tym, że nie wiem jakiej struktury danych użyć by program napisać najoptymalniej, czyli tak by działał jak najszybciej i używał jak najmniej pamięci. Najlepiej by było przy tym jak już jakaś liczba w danym ciągu wystąpi 3 raz to wyrzucić ją ze struktury danych, ale nie wiem jaka struktura danych umożliwiłaby mi taką operację ;)
0
0
A po co w takim razie struktura? wczytujesz do zmiennej, sprawdzasz czy dzieli się przez 3, jak tak to wyświetlasz jak nie to wczytujesz następną liczbę do tej samej zmiennej (bo poprzednia nie jest ci do niczego potrzebna skoro nie dzieli się przez 3 bez reszty).
ps to o czym piszesz było by raczej kontenerem, struktury służą do przechowywania zestawów danych dotyczących się jakiegoś obiektu.
editowy ps nie ten dział, takie coś to raczej do Newbie.
0
Źle mnie zrozumiałeś (lub źle wytłumaczyłem), nie liczba ma być podzielna przez 3 a ilość jej wystąpień w ciągu n
0
przyjmuje n liczb w różnej kolejności i mam wyświetlić tą, której reszta z dzielenia przez 3 jest równa 0.
Co to jest np. "1000 liczb w różnej kolejności"? Co to za liczby i co ustala ich kolejność?
Najlepiej by było przy tym jak już jakaś liczba w danym ciągu wystąpi 3 raz to wyrzucić ją ze struktury danych
Teraz piszesz o wystąpieniu trzeci raz a nie o podzielności.
Może napisz treść tego zadania, bo póki co to jest albo bez sensu, albo ja jestem za głupi żeby to zrozumieć.
Skoro chcesz sprawdzać podzielność to niepotrzebna Ci żadna struktura. Odczytujesz kolejno liczby w pętli i sprawdzasz jak z tą podzielnością. Skoro jest tylko taka jedna to jeżeli się zgadza wypisujesz ją i koniec.
Edit: o, zmieniłeś zdanie. To teraz liczba wystąpień liczby ma być podzielna przez 3?!
0
Postaram się wytłumaczyć to łopatologicznie
Załóżmy, że mamy dany ciąg 13 liczb
13 (liczba n)
100
100
5432121
23
5432121
23
100
5
23
5
23
5432121
5
Widać, że 5, 100, 5432121 występuje po 3 razy, natomiast liczba 23 wystąpiła 5 razy, ilość jej wystąpienia nie jest podzielna przez 3, więc na wyjściu zwracamy liczbę 23.
Dodam tylko, że n <= 1000000
edit: Sory za błąd w tłumaczeniu na początku ;)
0
To w końcu ma być podzielna czy nie być? Dla takiego zadania jakie przedstawiłeś wyżej najprościej chyba będzie zrobić tablicę o 1000001 elementach (jedynka na końcu bo jej indeks zaczyna się od zera), i potem po wczytujesz liczbę i tab[liczba] zwiększasz o jeden. Na koniec starczy sprawdzić który z indeksów tablicy spełnia aktualne warunki.
2
hashmapa gdzie kluczem jest liczba a wartością jest ilość jej wystąpień.
1
Shalom napisał(a):
hashmapa gdzie kluczem jest liczba a wartością jest ilość jej wystąpień.
Z tym się zgadzam i mogę powiedzieć, że w C++ nada się do tego std::map albo std::unordered_map. (Napisałem sobie i całość ma jakieś 10 linijek kodu :-P)
Jeżeli zakres nie jest jakiś ogromny to to, co napisał @sig też może być.
0
Ogólne założenie ma być takie, że liczby mają mieścić się w int, a n ma nie przekraczać miliona. Nie znam ani minimalnej, ani maksymalnej liczby od razu, ponieważ ciąg jest podawany losowo, z tym, że w ciągu tylko jedna liczba powtarza się tak, że reszta z dzielenia ilości jej wystąpienia przez 3 jest większa niż 0. Chcę aby program działał szybciej niż przy zastosowaniu tablicy, gdzie musiałbym przechowywać wszystkie elementy i przechodzić całą tablice. Hashmapa wydaje mi się dobrą propozycją, sprawdzę jak będzie pamięciowo z jej użyciem.
0
Nie zrozumiałeś pomysłu od sig'a
robisz tablicę:
char tb[MAX_INT+1];
wczytujesz kolejną liczbe:
cin>>a;
i podajesz:
if(++tb[a]>3) tb[a]-=3;
Z tym że pomysł z mapą std::map może okazać się lepszy, ponieważ na końcu możesz przejrzeć tylko te liczby które występowali w ciągu.
0
Skoro liczba ma mieć zakres int-a to chyba faktycznie mapa będzie lepsza, wpisać liczby i potem przeglądać ją iteratorem szukając "właściwej" liczby wystąpień. Tablica przy krótkich ciągach zajęła by dużo więcej miejsca, więc chyba warto poświęcić dodatkowy "czas programowania" na zastosowanie mapy.
0
Jednak jeżeli zastosować taki tryk:
unsigned Tb[3][(7U+MAX_INT)/(8*sizeof(unsigned)]={0};
Czyli trzy-bitowe liczby "w pionie".
To może wyjść nawet szybciej niż mapa.
0
Shalom, wiem, że piszę nieprecyzyjnie, ale muszę zmieścić się w 3mb pamięci. Zaimplementowałem to właśnie przy użyciu mapy (std::map) i okazuje się, że dla dużych danych zużywa mi prawie 6mb pamięci. Na pewno musi się to dać zrobić w tych 3 mb pamięci...
0
A jak użyjesz unordered_map? Bo hashmapa ma mniejszy narzut niż treemap. Możesz dodatkowo wykorzystać pomysł kolegi @_13th_Dragon i nie robić mapy intów tylko charów i przechowywać tam tylko ilość zliczeń modulo 3.
0
Hm a może przechowywać booley? w przykładzie wypisał liczbę o 4? wystąpieniach, czyli niepodzielnych przez 3 bez reszty. A co za tym idzie można by to zrobić następująco: wczytujemy liczbę, sprawdzamy czy jest: jak nie ma to dodajemy ją z wartością false, jak jest z wartością false nadajemy jej wartość true, a jak jest z wartością true (czyli była już 2x i jest po raz 3 lub wielokrotność 3) usuwamy ją. W ten sposób na koniec zostaną mu tylko liczby (liczba?) spełniające warunki zadania. Obliczeniowo będzie pewnie fatalnie, ale sporo zaoszczędzi na pamięci , a to jest tu chyba główny wyznacznik.
0
Spróbowałem jeszcze mapę z char i iterator z char, pamięciowo nadal jest ponad 5mb, więc nie za bardzo to pomogło. Sprawdzę jeszcze unordered_map ;)
1
Hahaha, dla rozwiązania tego zadania potrzebne jest tylko 33 bajty pamięci ;P
#include <cstring>
#include <iostream>
using namespace std;
int main()
{
char a[11]={0},b[11]={0},x[11];
unsigned n;
cin>>n;
while(n--)
{
memset(x,0,sizeof(x));
cin>>x;
for(unsigned i=0;i<10;++i)
{
b[i]^=a[i]&x[i];
a[i]^=x[i]^(b[i]&x[i]);
}
}
cout<<"wynik: "<<a<<endl;
cin.sync();cin.get();
return 0;
}
Można jeszcze mniej pamięci, ale chyba będzie wolniejsze przez konwersje na int'a:
#include <cstring>
#include <iostream>
using namespace std;
int main()
{
int a=0,b=0;
unsigned n;
cin>>n;
while(n--)
{
int x;
cin>>x;
a^=x^((b^=a&x)&x);
}
cout<<"wynik: "<<a<<endl;
return 0;
}
0
_13th_Dragon, szacunek, nie wpadłbym na coś takiego. Za mało jeszcze programuje, muszę przyjrzeć się temu dokładnie by zrozumieć działanie tych XORów :D