W jaki sposób przyspieszyć mój program?

0

Jak można przyspieszyć program?
Zakładam, że chodzi o złożoność programu i nie powinna być liniowa, niestety nie wiem jak z tym sobie poradzić.
Coś mi świta o binary search ale jak grochem o ścianę :-(

Zadanie:

http://solve.edu.pl/contests/download_desc/1871

#include <iostream>
using namespace std;
int
main ()
{
  long long int ktorazkolei = 0, liczba = 5;
  cin >> ktorazkolei;
  for (int i = 0; i < ktorazkolei; liczba = liczba + 2)
    {
      if ((liczba % 2 != 0) && (liczba % 3 != 0) && (liczba % 5 != 0))
	{
	  i++;
	}
    }
  cout << liczba - 2;
  return 0;
}


0

liczba = liczba + 2 + liczba % 2 != 0 = hmmm

Tak czy siak: wypisz liczby od 1 do 100 na kartce, zaznacz markerem te prawiepierwsze i zobacz, czy coś Ci się rzuca w oczy.

0
Patryk27 napisał(a):

liczba = liczba + 2 + liczba % 2 != 0 = hmmm

A jaśniej?

0

Powiedz mi w jakiej sytuacji Twoja liczba będzie podzielna przez dwa, skoro zaczynasz od 5 i inkrementujesz co 2, otrzymując zbiór {5, 7, 9, 11, 13, 15, ...} zawierający liczby wyłącznie nieparzyste.

Nie wpływa to na złożoność algorytmu, lecz z całą pewnością na czas jego wykonania - co obrót pętli sprawdzasz liczba % 2 != 0, które zawsze jest i będzie prawdziwe.

0
Patryk27 napisał(a):

Nie wpływa to na złożoność algorytmu, lecz z całą pewnością na czas jego wykonania - co obrót pętli sprawdzasz liczba % 2 != 0, które zawsze jest i będzie prawdziwe.

Program działa poprawnie ale przekracza czas w 3 testach.
Jak ominąć sprawdzanie w każdej pętli liczba % 2 != 0 ?

0

Usunąć po prostu ten warunek z ifa, ponieważ jest zawsze prawdziwy; masz w ogóle pojęcie co robi kod, który napisałeś / dostałeś? ;-p

0
Patryk27 napisał(a):

Usunąć po prostu ten warunek z ifa, ponieważ jest zawsze prawdziwy; masz w ogóle pojęcie co robi kod, który napisałeś / dostałeś? ;-p

Tak mam pojęcie bo sam go pisałem :-)
Mimo, że mam 13 lat to coś tam myślę ale dopiero się uczę C++, chodzę do 7 klasy SP i może nie do końca znam wszystkie niezbędne zasady matematyczne ale staram się.
Dlatego dopytuję i proszę o wyrozumiałość.

Czyli kod ostatecznie wygląda tak:

#include <iostream>
using namespace std;
int
main ()
{
  long long int ktorazkolei = 0, liczba = 5;
  cin >> ktorazkolei;
  for (int i = 0; i < ktorazkolei; liczba = liczba + 2)
    {
      if ((liczba % 3 != 0) && (liczba % 5 != 0))
    {
      i++;
    }
    }
  cout << liczba - 2;
  return 0;
}

Dalej niestety przekraczam czas na trzech testach :-(

1

Ach, no widzisz - trochę zmienia to pogląd na sprawę ;-)

W przypadku Twojej instrukcji warunkowej wystarczy if ((liczba % 3 != 0) && (liczba % 5 != 0)) - warunek liczba % 2 != 0 jest zawsze spełniony, ponieważ wyżej robisz liczba = liczba + 2, czyli liczba cały czas będzie nieparzysta (5, 7, 9, 11 itd.).

Wydaje mi się, że mimo wszystko trzeba będzie podejść do tego problemu mądrzej, niż iterując na pałę po wszystkich liczbach - dlatego poprosiłem Cię o wypisanie stu liczb i zaznaczenie tych pasujących do warunków.

0

Przekraczasz bo zapewne operacja wypisywania bierze za dużo czasu. Poczytaj jak przyspieszyć cout.i dlaczego tak się dzieje

Jak nie znajdziesz nic to wtedy Ci napisze jak

0
fasadin napisał(a):

Przekraczasz bo zapewne operacja wypisywania bierze za dużo czasu. Poczytaj jak przyspieszyć cout.i dlaczego tak się dzieje

Jak nie znajdziesz nic to wtedy Ci napisze jak

ios_base::sync_with_stdio (false);
 cin.tie (0);
 cout.tie (0);

cout << fixed <<liczba - 2;

?

0

Wymuszanie wysokiej wydajności iostream

ale slusznie @Patryk27 zauwazyl, ze tutaj nie bedzie z tym problemu. Wypisz liczby prawie pierwsze do 100 (czy do 200) i zobacz zaleznosc tak jak zasugerowal @Patryk27

1

W wątku, który poleciał do kosza dałem taką odpowiedź:

oblicz lcm(2, 3, 5), policz ile liczb miedzy 0 a tą liczbą mieści się prawie pierwszych i główkuj dalej.
Zgodnie z definicją 1 jest prawie pierwsza, a dane testowe tego nie uwzględniają, wiec trzeba na to wziąć poprawkę (prawie pierwsza o indeksie zero).

Z tego wychodzi metoda o stałym czasie. Całość zamknie się w 4 linijkach kodu.

0

Mam taki kod ale dalej działa za wolno.
Wypisałem liczby do jeden do 100 zaznaczyłem podzielne przez 2, 3, 5 i z zależności mam taki kod:

#include <iostream>
using namespace std;


int main ()
{
  long long int ktorazkolei = 0, liczba = 1, wzrost=1;
  cin >> ktorazkolei;
  while (ktorazkolei--)
    {
      if ((wzrost==1)||(wzrost==7))
      {
          liczba+=6;
      }
      if ((wzrost ==2)||(wzrost ==4)||(wzrost==6))
      {
          liczba+=4;
      }
      if ((wzrost==3)||(wzrost==5))
      {
         liczba+=2;
      }
      if (wzrost==8)
      {
          liczba+=2;
          wzrost=0;
      }
      wzrost++;
    }
  cout << liczba;
  return 0;
}

0

lcm (2,3,5)=30
od 0 do 30 mamy 7 liczb prawiepierwszych (jak dobrze policzyłem :))
0,1,2,3,4,5,6,(7),8,9,10,(11),12,(13),14,15,16,(17),18,(19),20,21,22,(23),24,25,26,27,28,(29),30.

Chyba czegaś nie widzę:(

Tak jak pisałem w innym wątku mam 13 lat (7kl. SP), może nie znam jeszcze wielu zależności matematycznych :( ale staram się :)

1

Dobrze wypisałeś liczby, ale żeby "zadziałało" jednak dodaj tę jedynkę, bo 30+1, 60+1 itd. są liczbami prawie pierwszymi. Musisz tylko przypadek n==1 uwzględnić osobno, a pozostałe n wg schematu.
Np. dla n = 10 obliczysz to jako:
30*(10/ile_liczb_prawie_pierwszych_od_0_do_30) + liczba_prawie_pierwsza_od_0_do_30(10-ile_liczb_prawie_pierwszych_od_0_do_30) = 30 + 7 = 37

0
cs napisał(a):

Dobrze wypisałeś liczby, ale żeby "zadziałało" jednak dodaj tę jedynkę, bo 30+1, 60+1 itd. są liczbami prawie pierwszymi. Musisz tylko przypadek n==1 uwzględnić osobno, a pozostałe n wg schematu.
Np. dla n = 10 obliczysz to jako:
30*(10/ile_liczb_prawie_pierwszych_od_0_do_30) + liczba_prawie_pierwsza_od_0_do_30(10-ile_liczb_prawie_pierwszych_od_0_do_30) = 30 + 7 = 37

Kurcze nie wiem jak :-(
w linii 31 dałem 1 zamiast 0 i przy teście 10 wypisuje 37, wcześniej wypisywało 41 :-)

0
Zakręcony Jeleń napisał(a):
cs napisał(a):

Dobrze wypisałeś liczby, ale żeby "zadziałało" jednak dodaj tę jedynkę, bo 30+1, 60+1 itd. są liczbami prawie pierwszymi. Musisz tylko przypadek n==1 uwzględnić osobno, a pozostałe n wg schematu.
Np. dla n = 10 obliczysz to jako:
30*(10/ile_liczb_prawie_pierwszych_od_0_do_30) + liczba_prawie_pierwsza_od_0_do_30(10-ile_liczb_prawie_pierwszych_od_0_do_30) = 30 + 7 = 37

Kurcze nie wiem jak :-(
w linii 31 dałem 1 zamiast 0 i przy teście 10 wypisuje 37, wcześniej wypisywało 41 :-)

Sorry za brak logowania, inny komputer :-)

0

Zrobiłbym tutaj mapę przeliczników wzrostu na liczbę, która uczestniczy w dodawaniu:

#include <iostream>
#include <map>
using namespace std;

int main()
{
    map<int, int> przelicznik {
        { 1, 6 }, { 7, 6 },
        { 2, 4 }, { 4, 4 }, { 6, 4 },
        { 3, 2 }, { 5, 2 },
        { 8, 2 },
    };

    long long int ktorazkolei = 0, liczba = 1, wzrost = 1;
    while (ktorazkolei--)
    {
        liczba += przelicznik[wzrost];
        wzrost++;
    }
    cout << liczba;
    return 0;
}

Wg mnie mapa powinna być szybsza niż drabinka ifów w pętli.

2

Oki, tabelka liczb prawie pierwszych w zakresie od 0 do 30:

1 2 3 4 5 6 7 8 <- n = która z kolei
(1) 7 11 13 17 19 23 29 <- liczby prawie pierwsze

kolejna trzydziestka

9 10 11 12 13 14 15 16 <- n = która z kolei
31 37 41 43 47 49 53 59 <- 30 x 1 + prawie_pierwsza_z_pierwszej_trzydziestki[n - 1 * 8]

następna

17 18 19 20 21 22 23 24 <- która z kolei
61 67 71 73 77 79 83 89 <- 2 x 30 + prawie_pierwsza_z_pierwszej _trzydziestki[n - 2 * 8]

Umieść w tablicy pierwsze 8 liczb a potem z n oblicz ile się w niej mieści 8 i ile jest reszty z dzielenia n przez 8, to da Ci indeks liczb z tablicy, która musisz dodać do wielokrotności 30 (w tablicy indeksy masz od 0 do 7)

4

ta 30 powtarza się w nieskończoność, występowanie prawie pierwszych ma okres 30, więc wiesz ile ich jest w każdej 30 i jak są w niej ułożone.

int prawiePierwsza(int n)
{
    static const int pp[] { 1, 7, 11, 13, 17, 19, 23, 29 };
    rerurn 30 * (n / std::size(pp)) + pp[n % std::size(pp)];
}
0

Bardzo dziękuję za okazaną pomoc, zadanie rozwiązane, nowa wiedza zdobyta :-)

1 użytkowników online, w tym zalogowanych: 0, gości: 1