NWW wielu liczb

[blost]

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?

[Szemek]

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.

[argv]

Szemek mnie ubiegl ale jak juz wklepalem to wkleje

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;
}

swoją drogą ciekawe czy to spełnia ramy czasowe jak nie to się bedzie optymalizować

[blost]

Hej.
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;
/////////////////////////////////////////////////////
}
}

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

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);   
}
}

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

[matshadow]

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

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]

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]

Powiem Ci, że wersja rekurencyjna NWD to zły pomysł, dla dużych danych może się stos przepełnić

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 gotowa

[Kajot]

Powiem Ci, że wersja rekurencyjna NWD to zły pomysł, dla dużych danych może się stos przepełnić

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 gotowa

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 takiego

oczywiscie to taka dygresja na boku jesli chodzi o wydajnosc NWD