Książka do Algorytmiki Opcje

[sztosz]

Kuleje jeśli chodzi o kwestie wynajdywania odpowiednich algorytmów żeby rozwiązać dany problem, czasem czytam o jakimś algorytm w necie i nie mam pojęcia jak go ugryźć.

Stąd moje pytanie: Czy jest jakaś książka z której dowiem się sprawnie tworzyć algorytmy, na czym to dokładnie polega? Ale tak od podstaw? W ogóle nie wiem czy w dobrym kierunku szukam, ale trochę błądzę po omacku. Nigdy nie kończyłem studiów informatycznych, ani matematycznych, więc mam w głowie tylko strzępki informacji na ten temat z liceum (IMG:style_emoticons/default/winksmiley.jpg)

[rzymek01]

@sztosz, wiadomo, że rekurencja jest wolniejsza i zżera więcej pamięci, bo musi pamiętać poprzednie wywołania funkcji

dobra, to teraz c++ (kompilator gcc 3.4.2, windows x86)

żeby zrobić z tego c, wystarczy:
rezerwowac pamięć funkcją calloc,
ctime na time.h
uzywać zamiast iostream, scanf i printf

[CPP] pobierz, plaintext 
/* wykorzystane założenia:
- rozważamy liczby tylko nieparzyste
- przy eliminacji wielokrotości liczby p, eliminujemy tylko liczby nieparzyste,
	więc postaci: p^2, p(p+2), p(p+4), ...
	i jeszcze dlatego, że liczby k*p zostały przesiane wcześniej
 
- wykorzystałem wskazówki i pseukod z książki "Algorytmy", bo komu się chce na nowo koło odkrywać (IMG:style_emoticons/default/tongue.gif) 
 
*/
 
// tutaj mozna dać stałą chudego windowsa ;)
#include <windows.h>
#include <ctime>
#include <iostream>
#include <vector>
 
using namespace std;
 
// Sito - bez wyświetlania danych
//       w celu wyświetlania danych nalezy odkomentować linijki na końcu funkcji
void Sito(int N) {
/* Sito
 * Wejście: parzysta liczba naturalna N
 * Wyjście: tablica liczb pierwszych z zakresu liczb naturalnych <2, N+1>
*/
 
    // inicjalizacja zmiennych
    int M = N / 2;
    bool* aSito = new bool[M + 1];
    for (int i = 1; i < M + 1; aSito[i++] = true);
 
	int i = 1,
        p = 3,
        q = 4,
        j;
 
/*
kod identyczny jak w moim poście wyżej z tym, że usuwamy wszystkie $
*/
 
	vector<int> aPierwsze;
        aPierwsze.push_back(2);
	for (i = 1; i <= M; ++i) {
            if (!aSito[i])
                continue;
 
            aPierwsze.push_back(2*i + 1);
	}
 
    // wyświetlenie wyników
//    vector<int>::iterator it = aPierwsze.begin();
//
//     for ( ; it < aPierwsze.end(); ++it )
//         cout << *it << "\n";
//     cout << endl;
}
 
int main() {
    int n,
        iPomiarow;
    cout << "Podaj liczbe: ";
    cin >> n;
    cout << "\nPodaj liczbe pomiarow: ";
    cin >> iPomiarow;
    cout << endl;
 
    LARGE_INTEGER start, stop, freq;
    unsigned __int64 istart, istop, ifreq;
    // ilość taktów cpu na sek
    QueryPerformanceFrequency(&freq);
    ifreq = freq.QuadPart;
 
    // kalibrujemy czas operacji pomiaru czasu
    QueryPerformanceCounter(&start);
    QueryPerformanceCounter(&stop);
    unsigned __int64 kalibracja = start.QuadPart - stop.QuadPart;
 
    // wykonujemy pomiar czasu
    QueryPerformanceCounter(&start);
 
    // mierzymy
    for(int i = 0; i < iPomiarow; ++i) {
        Sito(n);
    }
 
    // kończymy
    QueryPerformanceCounter(&stop);
 
    istart = start.QuadPart;
    istop  = stop.QuadPart;
    float t = (istop - istart - kalibracja) / (float)(ifreq * iPomiarow); // czas w sekundach
 
    cout << t;
 
    getchar(); // żeby nie zamknęła się konsola (IMG:style_emoticons/default/biggrin.gif) 
 
    return 0;    
}
[CPP] pobierz, plaintext 

najtrudniej było z dobrym liczeniem czasu, ale się udało.. uff (IMG:style_emoticons/default/smile.gif)

Kod

N = 100 000, czas: 0.000765121, pomiarów 10 000
N = 1 000 000, czas: 0,00850865s., pomiarów: 1000
N = 10 000 000, czas: 0,256164s, pomiarów 100
N = 100 000 000, czas: 3,43068s, pomiarów 10
N = 1 000 000 000, czas: 42.1552s, pomiarów 10

ale co by się nie oszukiwać, jesli gdzieś potrzeba liczby pierwsze to stosuje się preprocessing (IMG:style_emoticons/default/tongue.gif)
na jedne konkurs informatyczny trzeba było podać n-tą liczbę pierwszą z ograniczeniem do 100 000, to w necie znalazłem te liczby, wpadkowałem w tablicę i czas programu O(1) (IMG:style_emoticons/default/tongue.gif)

Ten post edytował rzymek01 31.08.2009, 19:23:07