Jan 2020
1 / 8
Jan 2020
Jan 2020
tyren234
Jan '20
3

No nie wiem co nie działa. Nic mi nie pomaga, więc może jakiś prawdziwy człowiek coś będzie wiedział.
Oto zadanie:

image
image.jpg803x314 115 KB

Oto moje rozwiązanie:

#include <iostream>
using namespace std;

int main()
{
    bool jest = false;
     long long a=0,b=0,m=0,n=0,i,j;//minimalna,maksymalna,największa na później, liczba liczb w tablicy (mniejsza niż przedział [a,b], dwie iteracyjne
    cin>>a>>b>>n;//wczytanie a,bi n
    int T[100];//tablica na razie do testów wielkości 100
    for (i = 0;i<n;i++)//wczytanie tablicy liczb
    {
        cin>>T[n-1];
    }
    for (i=b;i>a;i--)//liczby od b do a po kolei
    {
        jest = false;
        for(j=0;j<n;j++)//sprawdzenie czy ta liczba jest w tabeli
        {
            if(T[j]==i)
                jest=true;//jeżeli jest
        }
        if(jest!=true)//jeżeli nie ma
        {
            if(i>m)//ustawiamy aktualną (i) liczbę jako największą jeżeli jest większa niż nasza poprzednia największa
                m=i;
        }
    }
    cout << m;
    return 0;
}

  • created

    Jan '20

  • last reply

    Jan '20
  • 7

    replies

  • 982

    views

  • 4

    users

  • 2

    links

pawoj20
Jan '20

W powyzszym fragmencie n-krotnie wpisujesz do n-tego elementu dane z wejscia standardowego. Prawdopodobnie nie o to Ci chodzilo.
Przydaloby sie zeby program wykorzystywal fakt ze elementy w tabeli T sa juz posortowane. Program robi bardzo duzo porownan (jesli dobrze szacuje to mogloby to byc nawet 0,5nn), a mialy one byc minimalizowane. Jesli zaplanowac dobrze algorytm to mozna zejsc do wartosci mnieszej niz n.

narbej
Jan '20
1

Więc [po]testuj swój kod - napisz jak to robisz.

Żeby znaleźć prawdziwego człowieka, napisz więcej o sobie prawdziwych informacji, a także o zadaniu.

A czego próbowałeś? Może porywasz się z motyką na słońce? Może powinieneś zacząć od łatwiejszych “projektów”

Wystarczy wpisać w gogle np: “zadanie 1 brakujący element” i znajdziesz kilkanaście stron i opisy bardzo podobnych problemów algorytmicznych - “projektów”, np pierwsza z brzegu: https://blog.robertolechowski.com/zadanie-rekrutacyjne-4/,.5 omówiona tam jest także złożoność pamięciowa i obliczeniowa chociaż twój problem jest łatwiejszy, u Ciebie elementy są już posortowane. Czy chodzi o najmniejszy czy o największy element przecież chyba nie ma dla Ciebie znaczenia - chodzi o samą metodę - algorytm [a nawet jest tam kilka sposobów].

PS
Tak z ciekawości, na ilu forach zamieściłeś swoje pytanie projektowe?

PS 2
Gdyby ciąg nie był posortowany, to dodatkowa tablica jest jednym ze sposobów i tak jak napisał @pawoj20, poprawnie, to:

Jeżeli chodzi o złożoność obliczeniową, to, przy już posortowanym ciągu, optymalne jest wyszukiwanie binarne - O(ln n).

narbej
Jan '20

Nie chodziło mi o “czyste” wyszukiwanie binarne, a powinienem nazwać to dziel i rządź właśnie o takiej samej złożoności jak wyszukiwanie binarne i o zbliżonej zasadzie działania.

tyren234
Jan '20
narbej

  1. Popełniłem klasyczną okropną głupotę i po przeczytaniu zadania oczywiście o czymś zapomniałem. Zapomniałem o tym, że są uporządkowane rosnąco…

Testowałem go wpisując różne liczby, ale nie działało. Na przykład o ile pamiętam a=0,b=15,n=7,1,2,3,4,15,14,13., przeprowadzałem sobie to na kartce, bo jest na tyle nieskomplikowane, że się dało, ale mimo, że jestem przekonany o tym że jest dobrze - nie jest.

Absolutnie nie będę podawał tutaj żadnych danych o sobie, bo przede wszystkim nie jestem tu po to by dzielić się moimi danymi osobistymi tylko, żeby uzyskać pomoc od kogoś kto jest mądrzejszy ode mnie (i podejrzewam, że jest tutaj wiele takich osób). O zadaniu napisałem dosłownie wszystko. Powyżej jest tylko nazwa konkursu.

Jak najbardziej tak jest, tzn. porywam się z motyką na słońce, spodobało mi się to zadanie i zależy mi aby je zrobić. Wiem, że należy zacząć od prostszych rzeczy - robię łatwiejsze zadania na SPOJu, ale to nie zmienia faktu, że raz na jakiś czas można spróbować czegoś trudniejszego. Jak mi się nie uda to trudno.

Na to nie wpadłem, czuję się głupio…

To jest mój pierwszy i jedyny do tej pory wpis na jakimkolwiek forum dotyczącym c++.

Tak swoją drogą to bardzo dziękuję za odpowiedź, nie spodziewałem się, że ktoś podejmie próbę pomocy.
I widzę, że edytor coś mi wyciął przy wklejaniu i i–.

narbej
Jan '20
1

Twój ciąg, podany wyżej, nie jest posortowany. Wydaje mi się, że po poprawieniu wczytywania i podaniu prawidłowych testów, twój kod powinien działać - ale aż tak mocno nie testowałem i nadal w takim razie co jeszcze nie działa?

Jeżeli chodzi o wczytywanie, to łatwiej moim zdaniem wczytać w podanej kolejności, bez odwracania, jeżeli jednak chcesz mieć wczytane w odwróconej kolejności, to rzeczywiście tak to trzeba zrobić. No i jeżeli ciąg jest posortowany, to najprościej jezst zrobić zwykłe liniowe przeglądanie - przeszukanie tablicy. Ale to jest szacunkowa złożóność O(n);

Oczywiście, że nie, nie musisz się przedstawiać, ale po prostu zobaczyłem, że dopiero co zapisałeś się na forum [joined 1 day ago] i od razu napisałeś pytanie - stąd moje zakłopotanie i pytanie.

Dodatkowo, w podanej przez Ciebie treści zadania jest pytanie o oszacowanie złożoności, a to natychmiast kojarzy się raczej z pracą domową a na pewno nie ze SPOJ’em - więc dodatkowe zakłopotanie :wink:
Jeśli zaczynasz, przeczytaj koniecznie! <-- zaczynasz naukę-zabawę na SPOJ’u i korzystanie z forum.

thefoxpl
Jan '20

Skąd masz zadania przykładowe na Stema? Chciałbyś podesłać więcej?