GoldenLine
Zaloguj się
Marek Dąbek

Marek Dąbek Software Engineer,
Intel Technology
Poland

Temat: Zagadka/i ;)

Może tak:



struct _list; 



struct _list {

  int          data;

  struct _list *head;

  struct _list *next;

};



struct _list *revert(struct _list* head)

{

  struct _list* prev = NULL, *next_tmp = NULL;

  struct _list* curr = NULL;



  for (curr = head; curr != NULL; ){

      next_tmp = curr->next;

      curr->next = prev;

      prev = curr;

      curr = next_tmp;

  }



  return prev;

}
Marek Dąbek edytował(a) ten post dnia 09.02.11 o godzinie 22:45
Link do wypowiedziLink
Mateusz Herych

Mateusz Herych Arch Linux TU,
Student PK

Temat: Zagadka/i ;)

Wygląda dobrze.
Gratulacje. :^)
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

A teraz dla tej samej listy, używając też O(1) pamięci, znajdź wartość elementu który leży dokładnie w środku listy, lub jeśli jest nieparzysta ilość nodów to ten po środku bliżej końca ;-)
Link do wypowiedziLink
Mateusz Herych

Mateusz Herych Arch Linux TU,
Student PK

Temat: Zagadka/i ;)

Hm. Pewnie dobrym rozwiązaniem byłoby ustawienie dwóch wskaźników. Jeden na początek->next, a drugi na początek. Pierwszy skakałby co dwa nody, a drugi co jeden. Gdy pierwszy osiągnąłby NULL, to drugi byłby środkiem listy.

M/w coś takiego.



struct lista {

        int value;

        lista *next;

};



int main() {

        const int rozmiar = 7;

        lista *wsk = new lista, *head, *wsk2;

        head = wsk;

        wsk->value = 0;

        for(int i=1;i<rozmiar;i++) {

                wsk->next = new lista;

                wsk->next->value = i;

                wsk = wsk->next;

        }

        // szukanie środka start.

        wsk = head;

        wsk2 = head;

        while(wsk!=NULL && wsk->next!=NULL) {

                wsk = wsk->next->next;

                wsk2 = wsk2->next;

        }

        std::cout << wsk2->value << "\n";

        // szukanie środka stop

        while(head!=NULL) {

                lista *temp = head->next;

                delete head;

                head = temp;

        }

        return 0;

}


Ach, Teraz dopiero przeczytałem, że ma wskazywać na ten bliżej końca, a nie bliżej początku. ;) No ale zmiana tego jest już trywialna.

Poprawione. Powinno działać jak powinno. ;)Mateusz Herych edytował(a) ten post dnia 11.03.11 o godzinie 21:11
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

To będzie na trochę głębsze zastanowienie się (nie będzie kodu):

Załóżmy, że projektujemy system dla sklepu. Normalnego, fizycznego sklepu spożywczego. Jakbyście napisali program który obliczy wartość towarów które są w magazynie tego sklepu?

Co w tym trudnego? z pozoru wydaję się, że nic - wystarczy zsumować wartości produktów ale jak byście sobie poradzili z takimi rzeczami jak towary na promocji: 3 w cenie dwóch, ale można kupować oddzielnie bez promocji, albo 2 produkty za 10 zł kupione razem a w przypadku kupna tylko jednej sztuki to są za 7 zł / sztukę.

A teraz, jakbyście zaprojektowali szybki system do kasy tego sklepu? w taki sposób, żeby w momencie kiedy kasjerka skanowała kody kreskowe towarów, kasa automatycznie uwzględniała promocje w optymalny sposób?

Ważne jest to, że promocje często się zmieniają i powinna być możliwość tworzenia/dodawania nowych różnych, nawet dziwnych (np. proszek do prania kupiony z połówką arbuza daję zniżkę na pastę do zębów) promocji w krótkim czasie - najlepiej bez re-kompilacji systemu. Nie wszystkie towary liczy się w ten sam sposób; Niektóre rzeczy kupuję się na kilogramy, niektóre na litry, niektóre na sztuki, na kartony, itd.. i każde z nich może mieć inne rodzaje promocji.
Good luck! :)Karim A. edytował(a) ten post dnia 11.03.11 o godzinie 22:01
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Np. podejście zachłanne, czyli dla każdej promocji ( kombinacji towarów ) liczony jest "zysk". Po zeskanowaniu towarów system sprawdza czy jest wystarczająca ilość towarów aby skorzystać z promocji dającej najlepszy zysk. I potem całość powtarzać...
Oczywiście jeśli w zdaniu "kasa automatycznie uwzględniała promocje w optymalny sposób" chodzi o optymalny dla klienta a nie sklepu.
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Bardziej chodzi o to, jak zaprojektować taki system dający taką elastyczność a przy tym zachowując optymalny (szybki) czas działania. To zadanie to mieszanka Algorytmiki i OOP.

Oryginał zadania jest tu:
http://codekata.pragprog.com/2007/01/code_kata_one_s.html
http://codekata.pragprog.com/2007/01/kata_nine_back_.html
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)

Karim A.:
To będzie na trochę głębsze zastanowienie się (nie będzie kodu):

...

Może maszyna stanowa dla promocji? Na oko trudno mi ocenić jaki byłby rozmiar tej maszyny, zapewne znaczny, ale to taki pierwszy pomysł jaki mi do łba strzelił. Wprowadzanie nowej promocji bądź kasowanie starej polegałoby na zmianie konstrukcji maszyny, a każdy skanowany towar powodowałby zmianę stanu - co może by pozwoliło na złożoność O(1) dla każdego skanowanego towaru?
Link do wypowiedziLink
Mateusz Herych

Mateusz Herych Arch Linux TU,
Student PK

Temat: Zagadka/i ;)

Hm, tyle ludzi na grupie, naprawdę nikogo nie interesują te zagadki? ;-)

Weźmy sobie bazę danych. Mamy w niej tabelę z towarami, promocjami oraz tabelę łączącą promocję z towarami. W tabeli z promocjami mamy kolumnę, która określa sumę/iloraz/jakąś kombinację ID towarów, która musi zostać spełniona, aby promocja została uwzględniona. Mamy tam też kolumnę, która określa zniżkę, która ma zostać nałożona na rachunek, gdy promocja 'zadziała'.

Teraz towary lecą przez kasę, wczytujemy do jakich promocji należy każdy z nich. Do specjalnej tablicy 'dodajemy' wartość ID produktu do elementów promocji. Jeżeli któryś element promocji osiąga wartość 'docelową', to wtedy nakładamy na paragon odpowiednią zniżkę.

Przy dodawaniu nowych promocji do bazy musimy uwzględnić oczywiście, że jakaś promocja może być rozszerzeniem innej. Np. cena jednej pasty do zębów to zwykle 8 zł. Gdy kupujemy dwie, to mamy je za 7 zł/szt, a gdy trzy, to po 6 zł/szt. Wtedy może się zdarzyć, że najpierw nałożymy zniżkę na dwie pasty, a później na trzecią. Tak więc kwota zniżki na 3 pasty musi uwzględniać, że mieliśmy już zniżkę na 2 pasty.

Wydaje mi się, że gdyby jeszcze dopracować trochę szczegółów, to mogłoby to doprowadzić do całkiem niezłej złożoności przy skanowaniu towarów.

Naprawdę ciekawy problem.Mateusz Herych edytował(a) ten post dnia 26.03.11 o godzinie 00:19
Link do wypowiedziLink
Adam Borowiecki

Adam Borowiecki Programista,
analityk,
wdrożeniowiec,...

Temat: Zagadka/i ;)

Moje uwagi:

1. Jesli zdefiniujemy język opisujący promocje to bedziemy
mieli rozwiazanie.

2. Co znaczy 'optymalny'? Dla sklepu czy dla klienta?

3. Kwestia jednostek miary nie jest istotna.

Karim A.:
To będzie na trochę głębsze zastanowienie się (nie będzie kodu):

Załóżmy, że projektujemy system dla sklepu. Normalnego, fizycznego sklepu spożywczego. Jakbyście napisali program który obliczy wartość towarów które są w magazynie tego sklepu?

Co w tym trudnego? z pozoru wydaję się, że nic - wystarczy zsumować wartości produktów ale jak byście sobie poradzili z takimi rzeczami jak towary na promocji: 3 w cenie dwóch, ale można kupować oddzielnie bez promocji, albo 2 produkty za 10 zł kupione razem a w przypadku kupna tylko jednej sztuki to są za 7 zł / sztukę.

A teraz, jakbyście zaprojektowali szybki system do kasy tego sklepu? w taki sposób, żeby w momencie kiedy kasjerka skanowała kody kreskowe towarów, kasa automatycznie uwzględniała promocje w optymalny sposób?

Ważne jest to, że promocje często się zmieniają i powinna być możliwość tworzenia/dodawania nowych różnych, nawet dziwnych (np. proszek do prania kupiony z połówką arbuza daję zniżkę na pastę do zębów) promocji w krótkim czasie - najlepiej bez re-kompilacji systemu. Nie wszystkie towary liczy się w ten sam sposób; Niektóre rzeczy kupuję się na kilogramy, niektóre na litry, niektóre na sztuki, na kartony, itd.. i każde z nich może mieć inne rodzaje promocji.
Good luck! :)
Link do wypowiedziLink
Janusz U.

Janusz U.
elektronik/informaty
k,
fizyk/optoelektronik

Temat: Zagadka/i ;)

Witam wszystkich - moja druga wypowiedź na tej grupie.

Zacznę może od nie zagadki, a pewnych fajnych zagadek-sztuczek w C/C++:
- w kodzie picocom-a znalazłem kiedyś tej natury:


/*

 * Sprytny pomysl na ucieczke od "label/goto"

 * i wymyslania nazw typu "crit_error:",

 * jesli sa niezbedne...

 */

init_device();

do {

  if (!set_baudrate()) break;

  do_something();

  if (!set_parity()) break;

  send_data();

} while(0);

close_device();

- w kodzie kernela Linuxa (chyba to był jakiś sterownik - nie pamiętam):


// Jak nie stosowac tego?:

if(port[0xfffe] & 0x80)

  return 1;

   else

  return 0;



// Mozna uzyc:

return (port[0xfffe] & 0x80 ? 1 : 0);



// A jak prosciej?

return !!(port[0xfffe] & 0x80);



// Idac dalej:

return !!!!!!!!!!!!!!!!!!!!!!!!!!!only_binary_value; // :)


W następnym poście będzie zagadka:)Janusz U. edytował(a) ten post dnia 18.06.11 o godzinie 23:39
Link do wypowiedziLink
Janusz U.

Janusz U.
elektronik/informaty
k,
fizyk/optoelektronik

Temat: Zagadka/i ;)

Oto i zagadka/problem:

Mamy tablicę zmiennych typu unsigned char, czyli po 255 i dodaniu 1 mamy 0 (przepełnienie). Inaczej można powiedzieć (x % 256).
Zadanie: uśrednić wartości w tablicy. Podpowiedź: zwykła średnia arytmetyczna prowadzi na manowce:)
Podobny problem można spotkać uśredniając kąty - dość popularne zagadnienie w sieci.
Google: circular statistic, mean of circular quantities, average angle, average of consecutive angles

Najczęstsze rozwiązanie to uśrednianie wektorów. Czyli np. kąty zamieniamy na sin i cos, uśredniamy je, a następnie liczymy arctan.
Ktoś ma pomysł jak osiągnąć podobny efekt używając tylko modulo, dzielenia oraz dodawania i odejmowania? :)

Drugie pytanie: przejechał się już ktoś z Was, że procesor Intela x86 może dać inny wynik obliczeń niż np. ARM? Chodzi rzecz jasna o FPU i IEEE754, czyli double (64bit) vs extended precision (80bit registers and 64bit variables:). Na szczeście SSE rozwiązuje większość takich problemów. Zjawisko można podziwiać uruchamiając algorytm np. szukający zbieżnego wyniku lub filtru o nieskończonej odpowiedzi impulsowej (NOI/IIR). Można się zdziwić:)Janusz U. edytował(a) ten post dnia 18.06.11 o godzinie 23:56
Link do wypowiedziLink
Krzysztof Mierzejewski

Krzysztof Mierzejewski SharePoint
Consultant

Temat: Zagadka/i ;)

http://codility.com/ - demo test na 100% bez korzystania z wbudowanej obsługi dowolnie dużych liczb (czyli nie używamy pythona albo System.Numerics.BigInteger z .NET 4.0).
Link do wypowiedziLink
Tomasz S.

Tomasz S. If the
implementation is
easy to explain, it
may be a goo...

Temat: Zagadka/i ;)

Witam, a ja mam takie pytanie, jak uzywajać for_each STL-owego zrobic polimorficzny call po vektorze, tzn:

class B {
public: virtual void DoSomething(void) = 0;
};

class D: public B {
public:
void DoSomething(void) { std::cerr << "D::DoSomething()..." << "\n"; }
};

class E: public B {
public:
void DoSomething(void) { std::cerr << "E::DoSomething()..." << "\n"; }
};

int main(void) {
typedef std::vector<B*> poly_vec;
poly_vec v;
v.push_back(new D());
v.push_back(new E());

//
// !!! zamiast tego for-a chce for_each-a
//
for (poly_vec::const_iterator i = v.begin();
i != v.end(); ++i) {
(*i)->DoSomething();
}
// zwolnienie pamieci sobie daruje...
std::cin.get();
return 0;
}

Da sie to zrobic?
Dziekuje!Tomasz Stasik edytował(a) ten post dnia 16.08.11 o godzinie 10:01
Link do wypowiedziLink
Paweł Grzegorz Kwiatkowski

Paweł Grzegorz Kwiatkowski Architekt
oprogramowania,
Ericsson

Temat: Zagadka/i ;)

Tomasz Stasik:
Witam, a ja mam takie pytanie, jak uzywajać for_each STL-owego zrobic polimorficzny call po vektorze, tzn:

Zaznaczam, że nie czuję się w C++ dobrze ;-) ale kombinowałbym w następujący sposób:



 class B {

 public: virtual void DoSomething(void) = 0;

 };

 

 class D: public B {

 public:

    void DoSomething(void) { std::cerr <<  "D::DoSomething()..." << "\n"; }

 };

 

 class E: public B {

 public:

    void DoSomething(void) { std::cerr <<  "E::DoSomething()..." << "\n"; }

 };



// PKW start

        struct call : public unary_function<B *, void> {

                void operator()(B *x) { x->DoSomething(); }

        };

// PKW end

 

 int main(void) {

    typedef std::vector<B*> poly_vec;

    poly_vec v;

    v.push_back(new D());

    v.push_back(new E());

    

    //

    // !!! zamiast tego for-a chce for_each-a

    // 



     for_each(v.begin(), v.end(), call() );  // PKW



    std::cin.get();

    return 0;

 }


Materiały pomocnicze: http://www.sgi.com/tech/stl/for_each.html
Link do wypowiedziLink
Tomasz S.

Tomasz S. If the
implementation is
easy to explain, it
may be a goo...

Temat: Zagadka/i ;)

Dzieki!

Widze ze musze sie bardziej pochylic nad naglowkiem functional.
dzieki jeszce raz!Tomasz Stasik edytował(a) ten post dnia 16.08.11 o godzinie 12:13
Link do wypowiedziLink

konto usunięte

Temat: Zagadka/i ;)



std::for_each(v.begin(), v.end(),

    std::bind(&B::DoSomething, std::placeholders::_1) );


jeżeli nie masz tr1 "wsyśniętego" do std:



std::for_each(v.begin(), v.end(),

    std::tr1::bind(&B::DoSomething, std::tr1::placeholders::_1) );


jeżeli nie masz tr1 w ogóle, zawsze zostaje boost:



std::for_each(v.begin(), v.end(),

    boost::bind(&B::DoSomething, _1) );
Maciej O. edytował(a) ten post dnia 16.08.11 o godzinie 17:32
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

Kolejna zagadka algorytmicz...




Wyślij zaproszenie do
Anuluj