Zadanie algorytmy i C=++

[sfinkss]

Moja dziewczyna dostała na infie zadanie, ja nie za bardzo moge jej pomóc bo nie znam tych spraw, a wiem, że tutaj znakomita część ludzi to zna i to baaardzo dobrze.

Jeśli pomożecie to ja będę wdzięczny a ona to już w ogóle:D

Więc:

 

Mam opracować 2 algorytmy, w postaci schematu blokowego, obliczając pole powierzchni pod znaną krzywą y=f(x) przy znanej wartości argumentów i minimalnej xmin i maksymalnej xmax.

-pierwszy algorytm oblicza pole metodą prostokątów "z niedomiarem" lub " z nadmiarem"

- drugi algorytm oblicza pole metodą trapezów

 

do obu należy dołączyć specyfikację

potem zakodować w języku C++ w środowisku Xcode i porównać ilość interakcji potrzebnych do otrzymania tego samego wyniku.

[Kofel]

wtf? Xcode? Co, ona ma zajęcia na OS X? I czemu nauczyciel/wykładowca wymaga od uczniów posiadania owego systemu? :D

[sfinkss]

Aaaa, bo oni w ogole mają maci w szkole, takze... no ale bez komentarza;p

to moze nie xcode, ale po rpostu kod

[Kofel]

Nie mówię, że mają w szkole to źle :D Ale wymaganie tego od ucznia ekhem... jest głupotą :D

[sfinkss]

no to już temat na osobną dyskusje^^

ktoś podejmie się zadania? bo Myslę ze dla Was nie jest to trudne, chcoaiz ja tego wcale nie znam.

a Julia (Moja dziewczyna) będzie na pewno wdzieczna.;p

[Marmot]

Tutaj materiały wszelkie na temat całkowania dam, które dostałem od swojego nauczyciela informatyki. Pliki 002 i 003 poruszają te algorytmy, o których ma powiedzieć Twoja dziewczyna. Są tam zarówno schematy blokowe, jak i przykłady w językach programowania napisane.

http://www.przeklej.pl/plik/calkowanie-zip-0020cu46k7tb

Sądzę, że to dość pomoże :P .

[en_6280]

Mi się zdaję, że to i tak będzie robiła ta twoja na lekcji, a jeśli ona tego nie rozumie to i tak nauczyciel się z czai, że to ktoś jej robił...

Zrobiłem metodę prostokątów, jak pasuję to mogę zrobić jeszcze trapezów, ale napisz wtedy.

METODA PROSTOKĄTÓW

 

Specyfikacja:

problem algorytmu: Obliczyć pole pod wykresem znanej funkcji y=f(x), ograniczone Osią OX, dla x?<xmin,xmax>, metodą prostokoątów

dane wejściowe: xmin ?R, xmax ?R

dane wyjściowe: pole pod wykresem, pole?R

 

?-to znak należy, niestety nie umiem prawidłowo napisać na kompie...

pole?R, jakby wykres był pod osią OX !!!

(nie pamiętam, czy złożoność obliczeniową też trzeba)

 

Schemat blokowy: (robiony w programie magiczne bloczki)

 

Algorytm w c++:

#include <iostream>

//metoda prostokatow
using namespace std;

int main()
{ 
    float a,xmin,xmax,x,y,pole=0; //definujemy nasze zmienne
    
    cout<<"Podaj xmin: ";
    cin>>xmin;
    cout<<endl<<"podaj xmax: ";
    cin>>xmax;
    
    if(xmin>xmax)//zabezpieczenie przed zlosliwymi ludzi i debilami :)
    {
      a=xmax;
      xmax=xmin;
      xmin=a;  
    }
    
    for(x=xmin;x<=xmax-1;x=x+1)//dzieli na prostokąty o stałej podstawie = 1
    {
     y=2*x;//jest to nasza funkcja, która jest zdefiniowana (podana przed kompilacją programu)
     pole=pole+(y*1); /* bo to są prostokąty dlatego jest *1, 
                        niemusu być to y*1,moze być samo y, 
                        ale dla podkreślenia, ze to są prostokątu jest y*1,
                        informacja zbyteczna dla kompilatora(gorsza złożoność obliczeniowa),
                        lecz bardzo ułatwia życie laikom;) */                                                
    }
    
    if((xmax-x)>0 && (xmax-x)<1)// ten warunek jest zabezpieczeniem, gdyby ostatni prostokąt miał mniejszy bok podstawy od 1, szczególny przypadek
    {
                    y=2*x;// tu ta sama funckja co w petli powyzej!!!! 
                    pole=pole+(y*(xmax-x));
    }
    
    cout<<endl<<pole;
           
     
    return 0;
}

 

Jakby czegoś nie rozumiała to mogę coś rozpisać, ewentualnie niech pisze mi na gg.

 

A i niech twoja laska pozdrowi Pana Cz. :D Swoją drogą to podniósł poprzeczkę bo my robiliśmy takie coś w 1 LO, ale w excelu...

 

Edit 1. Dodałem Specyfikacje programu, znalazłem stary zeszyt. Jestem pewien wszystkiego tak na 90%, więc 4 powinno być spokojne.

Edit 2. u mie funkcja ma postać y=2*x ale można zmienić na dowolną, zmienić trzeba wtedy to wyrażenie (y=2*x) wszędzie w całym programie!!!

Edit 3. Złożoność tego algorytmu należy do klasy O(n), więc jest całkiem całkiem, choć zawsze mógł być lepszy.

[Morro]

Wykorzystam okazję i zapytam (nie goglowałem) jak wygląda schemat blokowy algorytmu na wypisanie liczb pierwszych? Mam to na jutro ale w autobusie nie wymyśliłem sposobu.

[Dawidds]

No na wyszukiwanie liczb pierwszych nie ma lepszego sposobu niż sprawdzanie wszystkich po kolei - dzielisz (konkretnie sprawdzasz resztę z dzielenia) liczby przez wszystkie liczby aż do osiągnięcia jej połowy. Czyli że dla 13 sprawdzisz 2, 3, 4, 5, 6, 7.

 

Ed: A z mniej "przenośnych" sposobów to możesz zrobić bufor dla wszystkich liczb od 2 do n, i wtedy wykreślasz z tego bufora wszystkie wielokrotności wszystkich liczb w nim. Czyli że dla 2 wykreślisz 4, 6, 8 ... dla 3 6 9 12 itd.

I to, co zostanie jest pierwsze. Ta metoda się nawet jakoś nazywa chyba.

[Platyna]

No na wyszukiwanie liczb pierwszych nie ma lepszego sposobu niż sprawdzanie wszystkich po kolei - dzielisz (konkretnie sprawdzasz resztę z dzielenia) liczby przez wszystkie liczby aż do osiągnięcia jej połowy. Czyli że dla 13 sprawdzisz 2, 3, 4, 5, 6, 7.

 

Brednie! Mógłbyś chociaż napisać, że ci się tak wydaje, a nie że nie ma. Po pierwsze jest znacznie lepszy algorytm działający liniowo (twój działa kwadratowo), a po drugie nie do jej połowy tylko do pierwiastka.

 

Zaraz ci napiszę w C++ sito wypluwające liczby pierwsze.

 

 

EDIT:

 

Funkcja Sito zapisze wszystkie liczby pierwsze mniejsze bądź równe n w tablicy prw. W zmiennej ile natomiast będzie ich ilość.

int sit[N];
int prw[N];
int ile=0;

void Sito(int n)
{
   for(int i=2; i*i<=n; i++)
   {
      for(int j=2*i; j<=n; j+=i)
         sit[j]=1;
   }
   for(int i=2;i<=n;i++)
   {
      if(sit[i]==0)
      {
         prw[ile]=i;
         ile++;
      }
   }
}

 

EDIT2:

Działanie algorytmu jest proste. Mamy tablicę sit. Każda liczba do n ma swoją komórkę. Wartość 1 oznacza, że liczba jest wykreślona. Bierzemy dwójkę i skacząc po tablicy wykreślamy wszystkie jej wielokrotności czyli 4, 6, 8, itd. Bierzemy kolejną liczbę, czyli 3 i wykreślamy wielokrotności czyli 6, 9, 12, 15, itd.

Na końcu w tablicy niewykreślone zostaną tylko liczby pierwsze.

Co ciekawe okazuje się, że wystarczy, że wykreślimy wielokrotności liczb nie większych niż pierwiastek z n. To sprawia, że algorytm działa liniowo.

[Dawidds]

Ejno, napisałem edita jak mnie oświeciło :( Ten drugi sposób już ma liniową złożoność.

 

Ed: A w sumie to jeszcze lepiej by było zacząć z tablicą, gdzie wszystkie liczby są oznaczone jako złożone - znajdujemy sobie jakąś liczbę która się ładnie rozkłada (120 dajmy na to, ma dość dużo dzielników na oko) i możemy wykreślić z nich wszystkie wielokrotności dzielników naszej liczby (liczba%60 jest równa 2 4 6 itd - wykreślamy, liczba%60jest równa 3 6 9 itd też wykreślamy i tak dla wszystkich dzielników), i dopiero na tym, co zostanie stosujemy te zwykłe sitko.

[Platyna]

Ale nie napisałeś, że do pierwiastka więc twoim sposobem złożoność by wyszła jakoś koło n*sqrt(n). :D

 

I to, co zostanie jest pierwsze. Ta metoda się nawet jakoś nazywa chyba.

Sito Erastotenesa.

 

A z mniej "przenośnych" sposobów

Co masz na myśli?

[en_6280]

Każdy może napisać własny algorytm, mój wypisze ilość liczb pierwszych wskazanych przez użytkownika, niestety istnieje nieskończenie wiele liczb pierwszych, dlatego nie da się ich wszystkich wypisać za pomocą programu, dlatego dałem takie ograniczenie, aby mój algorytm mógł zwać się algorytmem ;)

Oto schemat blokowy:

Mam nadzieję, że nie zrobiłem nigdzie błędu, nie twierdze że mój algorytm jest najlepszy...

[Dawidds]

Co masz na myśli?

Że mogę zacząć liczenie od dowolnej liczby a nie od 2 i nie mam ograniczenia w postaci pamięci. No ale dobra, te sitko erotestonesa (czy jak go tam nazwałeś) ma jednak kapkę lepszą złożoność.

Nie wiem, co mnie wzięło na początku z tym "nie da się inaczej niż", przepraszam : D

[Platyna]

Ed: A w sumie to jeszcze lepiej by było zacząć z tablicą, gdzie wszystkie liczby są oznaczone jako złożone - znajdujemy sobie jakąś liczbę która się ładnie rozkłada (120 dajmy na to, ma dość dużo dzielników na oko) i możemy wykreślić z nich wszystkie wielokrotności dzielników naszej liczby (liczba%60 jest równa 2 4 6 itd - wykreślamy, liczba%60jest równa 3 6 9 itd też wykreślamy i tak dla wszystkich dzielników), i dopiero na tym, co zostanie stosujemy te zwykłe sitko.

Nie bardzo ogarniam o co ci chodzi, ale to się wydaje nie mieć żadnego sensu.

[en_6280]

Najważniejsze, żeby dla każdego poprawnego zestawu danych wejściowych, algorytm prowadził do poprawnych wyników, realizując zadany problem w skończonej liczbie kroków.

A czy go rozumiesz czy nie to drugorzędna sprawa :P

[Platyna]

W takim razie czekaj ponad 11 dni na wyniki algorytmu kwadratowego kiedy liniowy może ci je podać w sekundę : )

 

Poza tym ja lubię rozumieć. -.^

[Dawidds]

Na wikipedii pod artem o sicie eratostenesa ("Zobacz też") trafiłem na to:

http://pl.wikipedia.org/wiki/Sito_Atkina

 

I coś, gdzie można przeczytać, jak to działa:

http://en.wikipedia.org/wiki/Sieve_of_Atkin

I coś na jakieś polskiej stronie:

http://edu.i-lo.tarnow.pl/inf/alg/001_search/0012.php

 

Może to nie dokładnie to o czym myślałem, ale opiera się na podobnym założeniu :P

[Morro]

Ooook, wszystko bardzo fajnie, tylko ni w ząb nie potrafię przełożyć to na schemat blokowy xD

[Platyna]

Na wikipedii pod artem o sicie eratostenesa ("Zobacz też") trafiłem na to:

http://pl.wikipedia.org/wiki/Sito_Atkina

 

I coś, gdzie można przeczytać, jak to działa:

http://en.wikipedia.org/wiki/Sieve_of_Atkin

I coś na jakieś polskiej stronie:

http://edu.i-lo.tarnow.pl/inf/alg/001_search/0012.php

 

Może to nie dokładnie to o czym myślałem, ale opiera się na podobnym założeniu tongue2.gif

 

Dobre czary :D

Później to dokładniej przeanalizuję. Chociaż złożoność nie jest jakoś wybitnie lepsza, bo liniówka jest zdecydowanie wystarczająca. Ale ja bym to określił mianem sztuki dla sztuki. To jest piękne. : )

[en_6280]

Morro. dokładnie kogo kodu nie możesz przełożyć na schemat blokowy?? mogę zrobić jak coś, ale mój też jest chyba dobry schemat...

[Platyna]

Twój algorytm jest jaki porąbany i się nie kończy i w kółko wypisuje dwójki.

Na początku i=2 oraz liczba=2. Potem sprawdzasz czy i<=liczba/2 przy czym ani i, ani liczba nie zmieniają swej wartości więc zawsze skręcimy w lewo.

Weź lepiej zrób mu schemat blokowy Sita Erastotenesa.

 

EDIT:

Ach sory. Zakończy się gdy a przekroczy max. Ale i tak wypisze tylko masę dwójek.

[en_6280]

Dzx Platyna, już poprawiłem ;)

a tu kod w c++:

#include <iostream>

using namespace std;

int main()
{ int max,liczba=2;
bool pierwsza;
cin>>max;
cin.ignore();
for(int a=1;a<=max;liczba=(liczba+1))
{
pierwsza=1;
for(int i=2;i<=liczba/2;i++)
{
        if(liczba%i==0)pierwsza=0;
}

if(pierwsza==1){cout<<liczba;a=a+1;}

}
getchar();
    
    return 0;
}

[Morro]

Próbowałem Platyniaka przełożyć ale jakoś gubię się w tych pętlach. Ogólnie nie mam już pojęcia czyj sposób jest dobry/lepszy/łatwiejszydoskumaniadlamnie

 

EDIT:

A i jak by można było dostać listę kroków czy coś to byłoby bosko ^^ Nie uczyłem się C++ i nie rozumiem zastosowania niektórych komend

[sfinkss]

chyba muszę Cię poprosić o drugie zadanie również, en_6280 :))