konto usunięte
Mateusz
Herych
Arch Linux TU,
Student PK
Mateusz Herych edytował(a) ten post dnia 22.09.10 o godzinie 04:28
const int r = 7; // rozmiar, pozwolicie chyba, że nie podstawię tutaj tryliona
int t2[1024]; // zakładam, że nie będziemy szukać większych.
int t3[r];
bool jestSuma(int t[], int sz) {
for(int l=0;l<r;l++) {
if(sz-t[l]>0) {
t2[sz-t[l]]++;
t3[l]=(sz-t[l]);
}
}
for(int l=0;l<r;l++) {
if(t2[t[l]] && (t3[l]!=t[l] || t2[t[l]]>1)) return true;
}
return false;
}
Jakub L. Programista
konto usunięte
Jakub L.:
Pójdę na łatwiznę - skoro mamy trylionowa tablicę, to możemy zrobić sobie inną tak długą jak zakres inta?
Jakub L. Programista
Karim A.:
Jakub L.:
Pójdę na łatwiznę - skoro mamy trylionowa tablicę, to możemy zrobić sobie inną tak długą jak zakres inta?
Dobrze kombinujesz ;)
Rozwiązanie oparte o hashset jest poprawne.
Jerzy
Wierzchowski
Senior Software
Developer
Jakub L. Programista
Marek
Dąbek
Software Engineer,
Intel Technology
Poland
Jerzy Wierzchowski:
Zwykła tablica zajmuje jeden spójny obszar pamięci.
konto usunięte
Marek Dąbek:
Jerzy Wierzchowski:
Zwykła tablica zajmuje jeden spójny obszar pamięci.
Niekoniecznie i im większa tablica tym bardziej powyższe jest nieprawdziwe ;)
Marek
Dąbek
Software Engineer,
Intel Technology
Poland
Aleksander W.:
Marek Dąbek:
Jerzy Wierzchowski:
Zwykła tablica zajmuje jeden spójny obszar pamięci.
Niekoniecznie i im większa tablica tym bardziej powyższe jest nieprawdziwe ;)
Pod względem logicznym jednak prawdziwe; segmentacja załatwia możliwość niespójności fizycznego obszaru pamięci. Czy ja nie wiem o jakimś innym mechanizmie?
konto usunięte
Marek Dąbek:
Aleksander W.:
Marek Dąbek:
Jerzy Wierzchowski:
Zwykła tablica zajmuje jeden spójny obszar pamięci.
Niekoniecznie i im większa tablica tym bardziej powyższe jest nieprawdziwe ;)
Pod względem logicznym jednak prawdziwe; segmentacja załatwia możliwość niespójności fizycznego obszaru pamięci. Czy ja nie wiem o jakimś innym mechanizmie?
Chodziło mi oczywiście o pamięć fizyczną. Zgadzam się, że mając adresy wirtualne tablica wygląda na ciągły obszar pamięci.
konto usunięte
Jerzy Wierzchowski:
Zwykła tablica zajmuje jeden spójny obszar pamięci. Ciężko będzie znaleźć w RAMie miejsce na to chyba.
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
konto usunięte
Piotr Głudkowski:
Oj, Panowie, czepiacie się nieistotnych szczegółów.
I teraz już chyba problem pamięci nie jest istotny, prawda?W ten sposób można każde zadanie sprowadzić do prostszego a tu chodzi o poradzenie sobie także z ilością danych
konto usunięte
Piotr Głudkowski:
Oj, Panowie, czepiacie się nieistotnych szczegółów.
Wystarczy sformułować zadanie inaczej:
<zadanie>
Czytamy ciągły strumień bajtów.
I teraz do wyboru:
a. Należy znaleźć i podać dwa bajty z tego strumienia, których suma wynosi X.
b. Należy znaleźć i podać pozycję dwóch bajtów w tym strumieniu, których suma wynosi X.
Wyszukanie ma zostać wykonane w czasie liniowym.
</zadanie>
I teraz już chyba problem pamięci nie jest istotny, prawda?
konto usunięte
Jakub L. Programista
konto usunięte
Jakub L.:
Przyjmując, że identyfikator pozycji w ciągu jest mniejszy lub równy elementowi ciągu, oraz że mamy daną pamięc albo na identyfikatory, albo na M elementów, to najpierw generujemy identyfikatory, potem je sortujemy, potem odczytujemy ciąg i wybieramy te, których pozycję wylosowaliśmy.
konto usunięte
Adam
Borowiecki
Programista,
analityk,
wdrożeniowiec,...
Karim A.:
Przyznam, poniosło mnie z podkreślaniem wagi tego, że tablica jest duża i należy szukać rozwiązania liniowego. Niemniej jednak, fajną dyskusję sprowokowałem :)
Następna dyskusja:
пропозиції роботи
