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

Odpowiedz Nowy wątek
2018-12-19 08:01
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;
}
edytowany 1x, ostatnio: furious programming, 2018-12-19 15:16
Trochę nie ten kontekst dla "jak grochem o ścianę". - Delor 2018-12-19 16:07

Pozostało 580 znaków

2018-12-19 08:24
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.


Pozostało 580 znaków

2018-12-19 08:27
0
Patryk27 napisał(a):

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

A jaśniej?

Pozostało 580 znaków

2018-12-19 08:29
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.


edytowany 1x, ostatnio: Patryk27, 2018-12-19 08:29

Pozostało 580 znaków

2018-12-19 08:41
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 ?

Pozostało 580 znaków

2018-12-19 08:44
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


edytowany 1x, ostatnio: Patryk27, 2018-12-19 08:44

Pozostało 580 znaków

2018-12-19 08:47
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 :-(

edytowany 1x, ostatnio: pattom, 2018-12-19 08:51

Pozostało 580 znaków

2018-12-19 08:54
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.


edytowany 2x, ostatnio: Patryk27, 2018-12-19 08:59

Pozostało 580 znaków

2018-12-19 08:56
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

Autor wypisuje tylko jedną liczbę (cout jest poza pętlami) - jest tam co optymalizować? - Patryk27 2018-12-19 08:58

Pozostało 580 znaków

2018-12-19 09:02
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;

?

Pozostało 580 znaków

2018-12-19 09:29
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

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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