Prośba o pomoc - NWD z tabeli liczb naturalnych.

0

Witam.
Od razu uprzedzam, że jestem początkujący i przepraszam za wszelkie uchybienia oraz błędy w terminologii, jakie mogę popełnić.
To mój pierwszy post na forum. Piszę z prośbą o pomoc...

Moim zadaniem było napisanie prostego programu wyznaczającego NWD z tablicy liczb wprowadzonych przez użytkownika.
Oto, co napisałem:

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

int main()
{
  int o=0;
  int s=0;
  int n=0;
  int dzielnik[n];
  int tab[19];
  
  cout<<"\n\tFprowadz 20 liczb naturalnych...";
    
    for (int i=0; i<19; i++)
    {
    cin>>tab[i];  
	cout<<"\n\t";      
                }
                
    int min=tab[0];
    int max=tab[0];

 for (int j=0; j=19; j++)
    {
        if (tab[j]>max)
        {max=tab[j];}
        if (tab[j]>min)
        {min=tab[j];}
        }
        

for(int i=1;i<=sqrt(min);i++)
    {
         if ((min%i)==0)
            {
               dzielnik[n]=i;
               n++;
            }
    }


for(;n>=0;n--)
             {
             while(o=0)
                                  {
                                  o=tab[s]%dzielnik[n];
                                  s++;                                  
                                  }
             
             }
cout<<"\n\tNajwiekszy wspolny dzielnik dla wczytanych liczb: "<<dzielnik[n]<<"\n\n\t";
cin.ignore ();
getchar ();

return 0;
}

Po wpisaniu wszystkich liczb program staje w miejscu. Podejrzewam, że po prostu któraś z pętli wykonuje się w nieskończoność z powodu błędu w warunkach jej wykonania, ale nie potrafię sam tego błędu znaleźć.
Z góry dziękuję za pomoc.

0

tak na pierwszy rzut oka:

  int n=0;
  int dzielnik[n];

po pierwsze z tego co wiem nie mozna tak robic tablicy (n musialobybyc stalą, lub tablica dynamiczną), po drugie jest to bez sensu - tworzysz tablice zero-elemntowa

 for (int j=0; j=19; j++)
    {
        if (tab[j]>max)
        {max=tab[j];}
        if (tab[j]>min)
        {min=tab[j];}
        }

niby bledu w tym nie ma ale latwo mozna poprawic wydajnosc robiac:

 for (int j=0; j=19; j++)
    {
        if (tab[j]>max)
        {max=tab[j];}
        else if (tab[j]>min)
        {min=tab[j];}
        }

bo jesli j-ty element jest dotychczas najwiekszy to nie jest najmniejszy - jedno porownanie mniej;)

for(int i=1;i<=sqrt(min);i++)
    {
         if ((min%i)==0)
            {
               dzielnik[n]=i;
               n++;
            }
    }

chyba nie zrozumialem - skad tu n? nie wiem czy to blad, czy ja nie rozumiem... poza tym jesli n deklarujesz na zer (na poczatku) to teraz wychodzisz poza zakres

for(;n>=0;n--)
             {
             while(o=0)
                                  {
                                  o=tab[s]%dzielnik[n];
                                  s++;                                  
                                  }
 
             }

while(o=0) != while(o==0) ;)
a w tej wersji ktora tutaj jest - while(o=0) - ani razu, bo wartoscia operatora przypisania jest przypisywana wartosc. w tym przypadku 0 a wiec warunek na starcie jest niespelniony. taka dygresja ale mysle ze troche wyjasniajaca;)

nad algorytmem sie nie zastanawialem, tylko analizowalem kod pod katem skladni. jesli chodzi o sam algorytm to wydaje mi sie troche zagmatwany, jak bede mial dluzsza chwile to nad nim posiedze;)

0

ajajaj jeszcze zapomnialem dodac:

    for (int i=0; i<19; i++)
    {
    cin>>tab[i];  
        cout<<"\n\t";      
                }
 
    int min=tab[0];
    int max=tab[0];
 
 for (int j=0; j=19; j++)
    {
        if (tab[j]>max)
        {max=tab[j];}
        if (tab[j]>min)
        {min=tab[j];}
        }

nie dajesz petlom warunku tylko ustawiasz j na 19 i wychodzisz poza zakres;)

0

@kpusmo
Dzięki za pomoc i przepraszam za głupie błędy.
Pozmieniałem te parę rzeczy, o których pisałeś. Teraz kod wygląda tak:

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

int main()
{
  int a=0;
  int o=0;
  int s=0;
  int n=0;
  int dzielnik[100];
  int tab[4];
  
  cout<<"\n\tWprowadz 5 liczb naturalnych...";
    
    for (int i=0; i<4+1; i++) //wprowadzanie liczb do tablicy
    {
    cin>>tab[i];  
	cout<<"\n\t";      
                }
                
    int min=tab[0]; //deklaracja zmiennych max i min; max właściwie jest niepotrzebne, ale niech już zostanie
    int max=tab[0];

  for (int j=0; j<4+1; j++)
    {
        if (tab[j]>max)
        {max=tab[j];}
        else if (tab[j]>min)
        {min=tab[j];}
        }
        

for(int i=1;i<=sqrt(min);i++)
//wpisanie do tablicy wszystkich dzielników liczby minimalnej; musiałem założyć jakąś ich maksymalną ilość, dałem 100, po to było 'n', ale jeżeli tak nie można to nie można
    {
         if ((min%i)==0)
            {
               dzielnik[n]=i;
               n++;
            }
    }

//sprawdzenie każdej liczby z tabeli przez maksymalny dzielnik liczby minimalnej; jeżeli się nie dzieli, wczytanie kolejnego czynnika i ponowne sprawdzenie
for(;n>=0;n--) //pętla zmieniająca kolejne dzielniki minimalnej liczby
             {
              a=0
             while(o==0) //pętla zmieniająca kolejne liczby sprawdzane
                                  {

                                  o=tab[s]%dzielnik[n];
                                  s++;
                                  a++;
                                  if (a==4)
                                  {goto koniec;}
                                  
                                  }
             
             }

koniec:

cout<<"\n\tNajwiekszy wspolny dzielnik dla wczytanych liczb: "<<dzielnik[n]<<"\n\n\t";
cin.ignore ();
getchar ();

return 0;
}

Po wykonaniu program działa, ale wywala jako winik jakieś wartości z kosmosu, np. po wpisaniu pięciu piątek jest to: "1961269466".
Co do algorytmu, to nie robiłem z jakiegoś konkretnego, zastosowałem się do luźnych wskazówek mojego nauczyciela.

0

Algorytm ktory wymysliles troche ciezko napisac, ale pomecze sie z tym jutro. dzis juz troche nie mam czasu ale jutro chetnie sie tym zajme;) najtrudniejsze jest sprawdzenie czy wszystkie liczby sie dziela przez ten dzielnik (tablica bool ale to moze ciezko zamulic program). Jutro albo dzisiaj pozniej przesle Ci rozwiazanie. Jesli sam chcesz to zrobic to zwroc uwage na ilosc dzielnikow - musisz zalozyc jakies maksymalne dane wejsciowe. jezeli nie, to nie bedzie ich wiecej niz dwa pierwiastki z najmniejszej liczby tablicy. pozniej w ostatniej petli musisz sprawdzac czy dana liczba jest dzielnikiem wszystkich w tablicy.

0

ten kod jest tak błędny, że nawet ciężko wszystko wypisać
zresztą nad czym wy się tak trudzicie? jest prosty (najbardziej podstawowy) algorytm do obliczania NWD...
http://pl.wikipedia.org/wiki/Algorytm_Euklidesa

0

i skorzystaj z tej własności
nwd(x0, x1, x2, ...)=nwd(x0, nwd(x1, x2, ...))

0

Dziękuję wszystkim za pomoc. Chciałem to zrobić tym swoim sposobem, ale chyba się poddam i skorzystam ze sposobu, który podał adf88... @kpusmo, skoro sam nie potrafię ogarnąć tego algorytmu to chyba nie ma sensu żebyś Ty pisał ten kod za mnie ;P w każdym razie dzięki za uświadomienie mi tego.

0

Teraz kod wygląda tak:

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

int main()
{
  int a=0;
  int b=0;
  int tab[4];
  
  cout<<"\n\tWprowadz 5 liczb naturalnych...\n\t";
    
    for (int i=0; i<4+1; i++) //wprowadzanie liczb do tablicy
    {
    cin>>tab[i];  
	cout<<"\n\t";      
                }
                
                while (b<=4)
                {
					while (tab[b]=!tab[b+1])
					{
						if (a<b)
						tab[b]=tab[b]-tab[a];
						else
						tab[a]=tab[a]-tab[b];
									}			
					
					b++;
					
					
					
					}
					cout<<"\n\t\n\tNWD z liczb to:"<<tab[b];
					cin.ignore();
					getchar();
					return 0;
				}

...i program działa. Dziękuję za pomoc!

0

Po pierwsze, użyj funkcji jak sugerował @adf88.
Po drugie, użyj algorytmu z liczeniem reszty, a nie z odejmowaniem. Zastanów się ile razy wykona się odejmowanie dla liczb 1 oraz 2147483647.

0
bogdans napisał(a):

Po pierwsze, użyj funkcji jak sugerował @adf88.
Po drugie, użyj algorytmu z liczeniem reszty, a nie z odejmowaniem. Zastanów się ile razy wykona się odejmowanie dla liczb 1 oraz 2147483647.

Jak ma działać algorytm z obliczniem reszty..? A w ogóle to zmienna "int" ma chyba zakres do 64000? Program który wstawiłem ma jednak błąd :/ próbuję go naprawić.

0
  1. int ma większy zakres niż 64000, liczba którą podałem jest typu int.
  2. Na stronie do której dostałeś link jest opisany algorytm z wykorzystaniem reszty,
  NWD(liczba całkowita a, liczba całkowita b)
       dopóki b != 0
           c := reszta z dzielenia a przez b
           a := b
           b := c
       zwróć a
  1. Napisz funkcję, która liczy NWD dwóch liczb, a potem zrób pętle:
int wynik = NWD(tab[0],tab[1]);
for(int i=2;i<rozmiar_tablicy,i++)
{
    wynik = NWD(wynik,tab[i]);
}
0

<quote="884464">1. int ma większy zakres niż 64000, liczba którą podałem jest typu int.
2. Na stronie do której dostałeś link jest opisany algorytm z wykorzystaniem reszty,

  NWD(liczba całkowita a, liczba całkowita b)
       dopóki b != 0
           c := reszta z dzielenia a przez b
           a := b
           b := c
       zwróć a
  1. Napisz funkcję, która liczy NWD dwóch liczb, a potem zrób pętle:
int wynik = NWD(tab[0],tab[1]);
for(int i=2;i<rozmiar_tablicy,i++)
{
    wynik = NWD(wynik,tab[i]);
}</quote>

To jest najlepszy sposób, dziękuję za podanie jego, ja głupi bym się z tym trudził jeszcze parę godzin zanim bym na to wpadł.

Kod:
```csharp
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

int NWD (int z, int y)
{
int c;
while (y!=0)
{			
c=z%y;
z=y;
y=c;		
}
return z;		
}


int main()
{
int a=0;
int wynik;
int b=0;
int c=0;
int tab[4];
  
cout<<"\n\tWprowadz 5 liczb naturalnych...\n\t";
    
for (int i=0; i<4+1; i++)
{
cin>>tab[i];  
cout<<"\n\t";      
}

wynik = NWD(tab[0],tab[1]);
for(int i=2;i<4;i++)
{
wynik = NWD(wynik,tab[i]);
}		
												
cout<<"\n\t\n\tNWD z liczb to:"<<wynik;
cin.ignore();
getchar();
return 0;
}

Teraz działa tak jak powinno. Jeszcze raz dzięki.

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