Skocz do zawartości

Zadanie algorytmy i C=++


sfinkss

Rekomendowane odpowiedzi

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.

Odnośnik do komentarza
Udostępnij na innych stronach

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 .

Odnośnik do komentarza
Udostępnij na innych stronach

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)

prostokat.jpg

 

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.

Odnośnik do komentarza
Udostępnij na innych stronach

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.

Odnośnik do komentarza
Udostępnij na innych stronach

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.

Odnośnik do komentarza
Udostępnij na innych stronach

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.

Odnośnik do komentarza
Udostępnij na innych stronach

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?

Odnośnik do komentarza
Udostępnij na innych stronach

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:

lpiersza.jpg

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

Odnośnik do komentarza
Udostępnij na innych stronach

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

Odnośnik do komentarza
Udostępnij na innych stronach

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.

Odnośnik do komentarza
Udostępnij na innych stronach

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

Odnośnik do komentarza
Udostępnij na innych stronach

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. : )

Odnośnik do komentarza
Udostępnij na innych stronach

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.

Odnośnik do komentarza
Udostępnij na innych stronach

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;
}

Odnośnik do komentarza
Udostępnij na innych stronach

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

Odnośnik do komentarza
Udostępnij na innych stronach

Jeśli chcesz dodać odpowiedź, zaloguj się lub zarejestruj nowe konto

Jedynie zarejestrowani użytkownicy mogą komentować zawartość tej strony.

Zarejestruj nowe konto

Załóż nowe konto. To bardzo proste!

Zarejestruj się

Zaloguj się

Posiadasz już konto? Zaloguj się poniżej.

Zaloguj się
  • Ostatnio przeglądający   0 użytkowników

    • Brak zarejestrowanych użytkowników przeglądających tę stronę.
×
×
  • Dodaj nową pozycję...