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;

?

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