NWW wielu liczb
-
- Użytkownik
- Posty: 1994
- Rejestracja: 20 lis 2007, o 18:52
- Płeć: Mężczyzna
- Podziękował: 52 razy
- Pomógł: 271 razy
NWW wielu liczb
Hej
taki maly problem mam... mam napisac algorytm ktory oblicza n liczb
kod mam taki
#include <iostream.h>
using namespace std;
main()
{
int t,p,i=0;
cin>>t;
for (;i<t;i++)
{
cin>>p;
int tab[p];
int w=0;
for (;w<p;w++)
{
cin>>tab[w];
}
int b=0,x=0;
for (;x<p-1;x++)
{
int k,p;
k=tab[x+1]*tab;
while (tab!=tab[x+1])
{ if (tab[x+1]>tab)
{ tab[x+1]=tab[x+1]-tab; }
else
{ tab=tab-tab[x+1]; } }
p=k/tab;
tab=p;
}
cout<<tab<<endl;
}
}
w sumie dziala tylko przekracza mi limit czasu i musze go jakos usprawnic... ma ktos jakies pomysly?
taki maly problem mam... mam napisac algorytm ktory oblicza n liczb
kod mam taki
#include <iostream.h>
using namespace std;
main()
{
int t,p,i=0;
cin>>t;
for (;i<t;i++)
{
cin>>p;
int tab[p];
int w=0;
for (;w<p;w++)
{
cin>>tab[w];
}
int b=0,x=0;
for (;x<p-1;x++)
{
int k,p;
k=tab[x+1]*tab;
while (tab!=tab[x+1])
{ if (tab[x+1]>tab)
{ tab[x+1]=tab[x+1]-tab; }
else
{ tab=tab-tab[x+1]; } }
p=k/tab;
tab=p;
}
cout<<tab<<endl;
}
}
w sumie dziala tylko przekracza mi limit czasu i musze go jakos usprawnic... ma ktos jakies pomysly?
- Szemek
- Użytkownik
- Posty: 4819
- Rejestracja: 10 paź 2006, o 23:03
- Płeć: Mężczyzna
- Lokalizacja: Gdańsk
- Podziękował: 43 razy
- Pomógł: 1407 razy
NWW wielu liczb
blost, jeśli wrzucasz kod, to postaraj się go wcześniej odpowiednio sformatować, a później umieścić pomiędzy \(\displaystyle{ \text{[code][/code]}}\)
Co do Twojego kodu, to unikaj takich rzeczy:
int tab[p];
Kiedy korzystałem z Dev-C++ to takie rzeczy chodziły, ale od czasu kiedy pracuję z Visual Studio korzystam albo z dynamicznie alokowanej tablicy operatorem new, albo z kontenera <vector>
Robiłem kiedyś zadanie na SPOJu i problem rozwiązałem inaczej.
# Nie tablicuj liczb.
# Wykorzystaj własność \(\displaystyle{ NWW(a,b)=\frac{ab}{NWD(a,b)}}\)
# Skorzystaj z tego, że \(\displaystyle{ NWW(a,b,c) = NWW(a, NWW(b,c))}\)
# Skorzystaj z algorytmu Euklidesa - osobiście polecam wersję z dzieleniem modulo.
Co do Twojego kodu, to unikaj takich rzeczy:
int tab[p];
Kiedy korzystałem z Dev-C++ to takie rzeczy chodziły, ale od czasu kiedy pracuję z Visual Studio korzystam albo z dynamicznie alokowanej tablicy operatorem new, albo z kontenera <vector>
Robiłem kiedyś zadanie na SPOJu i problem rozwiązałem inaczej.
# Nie tablicuj liczb.
# Wykorzystaj własność \(\displaystyle{ NWW(a,b)=\frac{ab}{NWD(a,b)}}\)
# Skorzystaj z tego, że \(\displaystyle{ NWW(a,b,c) = NWW(a, NWW(b,c))}\)
# Skorzystaj z algorytmu Euklidesa - osobiście polecam wersję z dzieleniem modulo.
- argv
- Użytkownik
- Posty: 569
- Rejestracja: 27 maja 2009, o 01:27
- Płeć: Mężczyzna
- Podziękował: 51 razy
- Pomógł: 66 razy
NWW wielu liczb
Szemek mnie ubiegl ale jak juz wklepalem to wkleje
swoją drogą ciekawe czy to spełnia ramy czasowe jak nie to się bedzie optymalizować
Kod: Zaznacz cały
#include <stdio.h>
#include <stdlib.h>
int nwd(int a, int b)
{
return b == 0 ? a : nwd(b, a % b);
}
int nww(int a, int b)
{
return a * b / (nwd(a, b));
}
int main(void)
{
int tab[] = {24, 6, 4, 6, 7,8 , 3 };
int r = sizeof(tab) / sizeof(tab[0]);
/* nww zawsze ma min 2 liczby */
int wynik = nww(tab[0], tab[1]);
int i;
for(i = 2; i < r; i++) {
wynik = nww(wynik, tab[i]);
}
printf("%d
", wynik);
return 0;
}
-
- Użytkownik
- Posty: 1994
- Rejestracja: 20 lis 2007, o 18:52
- Płeć: Mężczyzna
- Podziękował: 52 razy
- Pomógł: 271 razy
NWW wielu liczb
Hej.
Kurcze siedze nad tym juz troszke i nadal nie wiem gdzie jest blad
to jest ten wczesniejszy kod. On jet wlasnie rozwiazany tak jak sugerowales Szemek... mialem caly czas zbyt duzy czas to wywalilem funkcje i wpisalem po prostu ten algorytm w srodek kodu zeby predkosc zwiekszyc, dlatego pewno takie nieczytelne... no ale niezbyt wystarczajaco zwiekszylem
argv zmodyfikowalem troszke Twoj algorytm na potrzeby zadania do postaci
ale nie wiem czemu caly czas mi sedzia wyswietla blad odpowiedzi. gdy sprawdzam na dev to wszystko ok wychodzi wiec nie mam pojecia gdzie lezy problem
bede wdzieczny za nakierowanie na ten problem...
ps. nie jestem jeszcze dosyc dobry w programowaniu (co widac) wiec kontenera czy dynamicznego alokowania nie wiem jak uzywac
Kurcze siedze nad tym juz troszke i nadal nie wiem gdzie jest blad
Kod: Zaznacz cały
#include <iostream.h>
using namespace std;
main()
{
int t,p,i=0;
cin>>t;
for (;i<t;i++)
{
cin>>p;
int tab[p];
int w=0;
/////////////////////////////////////////////////////
for (;w<p;w++)
{
cin>>tab[w];
}
int b=0,x=0;
for (;x<p-1;x++)
{
int k,p;
k=tab[x+1]*tab[b];
while (tab[b]!=tab[x+1])
{ if (tab[x+1]>tab[b])
{ tab[x+1]=tab[x+1]-tab[b]; }
else
{ tab[b]=tab[b]-tab[x+1]; } }
p=k/tab[b];
tab[b]=p;
}
cout<<tab[b]<<endl;
/////////////////////////////////////////////////////
}
}
argv zmodyfikowalem troszke Twoj algorytm na potrzeby zadania do postaci
Kod: Zaznacz cały
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
long nwd(long a, long b)
{
return b == 0 ? a : nwd(b, a % b);
}
long nww(long a, long b)
{
return a * b / (nwd(a, b));
}
main()
{
int t;
std::cin>>t;
for(int k=0;k<t;k++)
{
long p;
cin>>p;
long tab[p];
for ( int j=0; j<p;j++)
{
std::cin>>tab[j];
}
long wynik = nww(tab[0], tab[1]);
int i;
for(i = 2; i < p; i++) {
wynik = nww(wynik, tab[i]);
}
printf("%d
", wynik);
}
}
bede wdzieczny za nakierowanie na ten problem...
ps. nie jestem jeszcze dosyc dobry w programowaniu (co widac) wiec kontenera czy dynamicznego alokowania nie wiem jak uzywac
-
- Użytkownik
- Posty: 941
- Rejestracja: 17 gru 2007, o 21:48
- Płeć: Mężczyzna
- Lokalizacja: Kingdom Hearts
- Podziękował: 6 razy
- Pomógł: 222 razy
NWW wielu liczb
Powiem Ci, że wersja rekurencyjna NWD to zły pomysł, dla dużych danych może się stos przepełnić
Poza tym błąd tkwi w NWW, bo a*b może przekroczyć zakres long longa
Po 3cie, nie ma potrzeby deklaracji tablicy - tylko pamięć zżera. Lepiej 2 zmienne
Tutaj jest mój kod, w razie pytań pisz na PW
Poza tym błąd tkwi w NWW, bo a*b może przekroczyć zakres long longa
Po 3cie, nie ma potrzeby deklaracji tablicy - tylko pamięć zżera. Lepiej 2 zmienne
Tutaj jest mój kod, w razie pytań pisz na PW
Kod: Zaznacz cały
#include <iostream>
using namespace std;
unsigned long long nwd(unsigned long long a, unsigned long long b)
{
while (b!=0)
{
unsigned long long c=a%b;
a=b;
b=c;
}
return a;
}
unsigned long long nww(unsigned long long a, unsigned long long b)
{
b /= nwd(a,b);
return b*a;
}
int main()
{
ios_base::sync_with_stdio(0);
unsigned long long s,t,n,d;
cin>>t;
while(t--)
{
s=1;
cin>>n;
while(n--)
{
cin>>d;
s=nww(s,d);
}
cout<<s<<endl;
}
return 0;
}
- argv
- Użytkownik
- Posty: 569
- Rejestracja: 27 maja 2009, o 01:27
- Płeć: Mężczyzna
- Podziękował: 51 razy
- Pomógł: 66 razy
NWW wielu liczb
Pisałem że ciekawe czy przechodzi i "jak nie to bedziemy optymalizowac" bo napisałem z palca dla przykładu A tablicowanie bylo tez dla przykladu czy nww i nwd dzialaja
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
NWW wielu liczb
Czyżby? Wywołań rekurencyjnych NWD będzie (bardzo grubo szacując) 128, nawet dla największych long longów - z każdym wywołaniem jedna z liczb zmniejsza się dwukrotnie. Jak ktoś ma 2kb pamięci w komputerze, to faktycznie katastrofa gotowamatshadow pisze:Powiem Ci, że wersja rekurencyjna NWD to zły pomysł, dla dużych danych może się stos przepełnić
-
- Użytkownik
- Posty: 87
- Rejestracja: 16 mar 2007, o 18:34
- Płeć: Mężczyzna
- Lokalizacja: Ostrowiec Św.
- Pomógł: 18 razy
NWW wielu liczb
w tym danym przypadku zdaje sie ze faktycznie bedzie to wystarczajace, niemniej dla "bignumów" (wlasna arytmetyka, długaaaśne liczby) Euklides jest już algorytmem mało wydajnym, więcej do poczytania w niebieskich książeczkach, o ile pamiętam zadanie "Łańcuchy choinkowe" albo cos takiegopaladin pisze:Czyżby? Wywołań rekurencyjnych NWD będzie (bardzo grubo szacując) 128, nawet dla największych long longów - z każdym wywołaniem jedna z liczb zmniejsza się dwukrotnie. Jak ktoś ma 2kb pamięci w komputerze, to faktycznie katastrofa gotowamatshadow pisze:Powiem Ci, że wersja rekurencyjna NWD to zły pomysł, dla dużych danych może się stos przepełnić
oczywiscie to taka dygresja na boku jesli chodzi o wydajnosc NWD