C: Najmanji zajednički sadržilac N brojeva - rekurzija

Teme vezane za console/GUI programiranje u C/C++ jeziku
4 post(ov)a • Stranica: 1/1.

C: Najmanji zajednički sadržilac N brojeva - rekurzija

PostPostao/la displayerror » 13 lis 2015, 15:35

Kako prevesti sljedeću iterativnu implementaciju u rekurzivnu:

Kod: Označi sve
int nzd(int a,int b)
{
   if(b == 0)
      return a;
   else return nzd(b,a%b);    
}

int nzs(int niz[],int n)
{
      int rezultat=1;
   for(int i=0;i<n;i++)
      rezultat=rezultat*niz[i]/nzd(rezultat,niz[i]);
   return rezultat;    
}

Re: C: Najmanji zajednički sadržilac N brojeva - rekurzija

PostPostao/la displayerror » 13 lis 2015, 16:27

Evo sad radi:
Kod: Označi sve
int nzd(int a, int b)
{
  if (b == 0)
    return a;
  return gcd(b, a%b);
}
int nzs(int niz[], int n) {
  int rezultat = 1, i=0;
  start:
  if(i<n) {
    rezultat = rezultat*niz[i]/gcd(rezultat, niz[i]);
    i++;
    goto start;
  }
  return rezultat;
}

int main()
{
   int niz[100];
   int n,i;

   do
   {
       printf("n=");
       scanf("%d",&n);
   }
   while(n<1);
   for(i=0;i<n;i++)
   {
       printf("%d. broj:",i+1);
       scanf("%d",niz+i);
   }
   printf("%d",nzs(niz,n));
   return 0;
}

Re: C: Najmanji zajednički sadržilac N brojeva - rekurzija

PostPostao/la displayerror » 13 lis 2015, 16:49

Moj prethodni kod ponovo nije rekurzvan (goto je ekvivalentan petlji).
Kako ovo riješiti rekurzivno?

Re: C: Najmanji zajednički sadržilac N brojeva - rekurzija

PostPostao/la Jasko » 14 lis 2015, 09:27

Evo jedno moguce rjesenje:

cpp code
#include <stdio.h>

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

int nzs(int niz[], int n, int rezultat) {

if(n==0) return rezultat;
return nzs(niz,n,(rezultat*niz[--n]/(gcd(rezultat, niz[n]))));
}

int main()
{
int niz[100];
int n,i;

do
{
printf("n=");
scanf("%d",&n);
}
while(n<1);
for(i=0;i<n;i++)
{
printf("%d. broj:",i+1);
scanf("%d",niz+i);
}
printf("%d\n",nzs(niz,n,1));
return 0;
}
Postoji 10 vrsta ljudi na zemlji. Oni koji razumiju binarni sistem i oni koji ga ne razumiju!
Posjetite moj YouTube kanal za gledanje za programiranje i druge teme oko računara.


4 post(ov)a • Stranica: 1/1.

Na mreži

Trenutno korisnika/ca: / i 1 gost.