• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

SPOJ - NWD Przekroczono limit czasu

VPS Starter Arubacloud
0 głosów
1,904 wizyt
pytanie zadane 7 lutego 2016 w C i C++ przez XPACK Początkujący (320 p.)

Witam! Stworzyłem program do obliczania najwyższego wspólnego dzielnika. Program według mnie działa(sprawdzałem go wiele razy), ale nie mogę go sprawdzić na SPOJu(pojawia się komunikat: Przekroczono limit czasu). Byłbym bardzo wdzięczny za pomoc.

link do zadania: http://pl.spoj.com/problems/PP0501A/

#include <iostream>

using namespace std;

int nwd(int a, int b)
{
	int i=1,dzielnik=0;
	if (a>=b)
	{
		for ( i = 1; i <= b; i++)
		{
			if (a%i == 0 && b%i == 0)
			{
				dzielnik=i;
			}
		}
	}
	else
	{
		for (i = 1; i <= a; i++)
		{
			if (a%i == 0 && b%i == 0)
			{
				dzielnik = i;
			}
		}
	}
	return dzielnik;
}


int main()
{
	
	int testy,liczbaA,liczbaB;
	cin >> testy;
	for (int i = 0; i <testy; i++)
	{
		cin >> liczbaA >> liczbaB;
		cout<<nwd(liczbaA, liczbaB)<<endl;

	}
	
	
	return 0;
}

 

5 odpowiedzi

+1 głos
odpowiedź 7 lutego 2016 przez Janusz programowania Bywalec (2,710 p.)
wybrane 7 lutego 2016 przez XPACK
 
Najlepsza

Też miałem problem z tym zadaniem. Zaimplementowany przez ciebie algorytm wyznaczający największy wspólny dzielnik jest wolny. Znacznie szybszym sposobem jest użycie rekurencji.

ja to zrobiłem tak:

int NWD(int a, int b)
{
    if(b!=0)
      return NWD(b,a%b);
 
    return a;
}

EDIT: Troszkę się spóźniłem crying

komentarz 7 lutego 2016 przez XPACK Początkujący (320 p.)
Chciałem to właśnie zrobić rekurencją, ale nie wiedziałem jaki powinien być warunek. Teraz gdy zobaczyłem twój kod to wydaje się to oczywiste. Dzięki za rozjaśnienie!
0 głosów
odpowiedź 7 lutego 2016 przez jeremus Maniak (59,720 p.)
po prostu to nie jest dość szybki algorytm a by spełnić wymogi SPOJA

albo wymyśl samodzielnie szybszą metodę   , albo poczytaj o  o algorytmach wyznaczania NWD np. Euklidesa i zaimplementuj .
0 głosów
odpowiedź 7 lutego 2016 przez XPACK Początkujący (320 p.)

Skróciłem mój kod do takiej formy, lecz ciągle to samo.

#include <iostream>

using namespace std;

int nwd(int a, int b)
{
	int i = 1, dzielnik = 0;

		for (i = b; i >= 1; i--)
		{
			if (a%i == 0 && b%i == 0)
			{
				dzielnik = i;
				break;
			}
		}
	
	
	return dzielnik;
}


int main()
{
	
	int testy,liczbaA,liczbaB;
	cin >> testy;
	for (int i = 0; i <testy; i++)
	{
		cin >> liczbaA >> liczbaB;
		cout<<nwd(liczbaA, liczbaB)<<endl;

	}
	
	
	return 0;
}

 

komentarz 19 marca 2019 przez Ronie Użytkownik (780 p.)
mam podobnie i mieszcze sie w czasie mam 0,7 s :) w petli odliczas od i=b , ja mam tak zrobione ze  w petli odliczam od mniejszej z tych dwóch liczb, najpierw sprawdzam która jest mniejsza. to jest napewno szybsza metoda.
0 głosów
odpowiedź 7 lutego 2016 przez XPACK Początkujący (320 p.)
Skorzystałem z Algorytm Euklidesa i podziałało. Szkoda, że te normy czasowe są warunkiem koniecznym a nie dodatkowym.
–1 głos
odpowiedź 7 lutego 2016 przez XPACK Początkujący (320 p.)

Chciałbym się też zapytać, którą wersję C++ wybierać w SPOJu:

  • C++(clang 3.7) 
  • C++g++(4.3.2) 
  • C++g++(5.1) 
  • C++14(g++5.1) 

?

Podobne pytania

0 głosów
1 odpowiedź 1,064 wizyt
pytanie zadane 19 października 2016 w C i C++ przez Paq_93 Początkujący (260 p.)
0 głosów
1 odpowiedź 3,140 wizyt
+1 głos
2 odpowiedzi 528 wizyt
pytanie zadane 1 marca 2016 w C i C++ przez cherubinek Nowicjusz (190 p.)

92,454 zapytań

141,263 odpowiedzi

319,099 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...