Autor Wątek: algorytm na najwiekszy wspolny dzielnik  (Przeczytany 1639 razy)

Offline _user

  • Użytkownik

# Maj 08, 2015, 12:01:49
Witam, od wczoraj ukladam na to algorytmy ale zaden sie nie sprawdza, mysle ze nie do konca wiem jak wyglada szukanie najwyzszego wspolnego mianownika dla 2 liczb, czytalem na wikipedii ale nie widze tam systemu niestety, wiec niezbyt wiem jak napisac algorytm, podam nizej swoje algorytmy i bede wdzieczny za korekte:
int tab[200];
  int x,z,c=2;
  for(int i=0;i<x;++i){
    x=l1;
    l1=l1/c;
    ++c;
    tab[i]=l1;
    ++i;
    l1=l1/2;
    tab[i]=l1;
    printf("%i\n", l1);
  }
  printf("\n\n");
  for(int i=0;i<z;++i){
    z=l2;
    l2=l2/2;
    printf("%i", l2);
    if(l2==tab[i])
      printf("%i", l2);
  }
/*int fspr2(int l1, int l2){

  if(l1>l2){
    do{
      l1=l1/2;
      int l=l2%l1;
      if(l==0){
printf("%i\n", l1);
return 0;
      }
    }while(1);
  }

  if(l1<l2){
    do{
      l2=l2/2;
      int l=l1%l2;
      if(l==0){
printf("%i\n", l2);
return 0;
      }
    }while(1);
  }
  return 0;
}
int fspr2(int l1,int l2){
  int x=l1;
  int z=l2;
  if(l1>l2){
    do{
      l1=l1/2;
      int l=l2%l1;
      if(l==0){
l2=l2/2;
int k=x%l2;
if(k==0){
  printf("%i\n", l2);
  return 0;
}
      }
    }while(1);
   
    if(l1<l2){
      do{
l2=l2/2;
int l=l1%l2;
if(l==0){
  l1=l1/2;
  int k=z%l1;
  if(k==0){
    printf("%i\n", l1);
    return 0;
  }
}
      }while(1);
    }
  }
  return 0;
}
  //  if(l1>l2){
  int tab[200];
  int x,x1,x2,z,c=2;
  for(int i=0;i<x;++i){
    x=l1;
    x1=l1/2;
    tab[i]=x1;
    printf("%i\n", x1);
    ++i;
    x2=x1/2;
    tab[i]=x2;
    printf("%i\n", x2);
    ++c;
    ++i;
    l1=l1/c;   
    tab[i]=l1;
    printf("%i\n", l1);
  }
@EDIT,przepraszam nie wiedzialem ze w c jest funkcja gcd... spojrzalem na jej kod i juz ok, dziala
int gcd(int a, int b)
{
    while (b != 0)
    {
        a %= b;
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return a;
}
« Ostatnia zmiana: Maj 08, 2015, 12:27:29 wysłana przez _user »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Kos

  • Użytkownik
    • kos.gd

# Maj 08, 2015, 12:54:47
Cytuj
        a ^= b;
        b ^= a;
        a ^= b;

Powaga? Xor-swap? Jak chcesz zaciemniać kod to napisz po prostu while (b ^= a ^= b ^= a %= b);
:P.

Offline _user

  • Użytkownik

# Maj 08, 2015, 13:50:41
Nie chce zaciemniac kodu, pierwszy raz slysze o czyms takim jak xor-swap wgl ;p chcialem napisac program ktory liczby najwiekszy wspolny dzielnik 2 liczb i znalazlem taka funkcje w internecie, ale dalej nie rozumiem jak to dziala, jesli wprowadzam np a=24, b=54, to po pierwszym a ^= b , moje a=46, dlaczego ? jak ten operator ^ liczy ? Czytalem o tym XOR'ze na wikipedii i tam bylo napisane ze zwraca albo 1 albo 0 zaleznie od tego czy 2 wyrazenia sa takie same czy nie, ale tutaj zwraca mi jakies inne liczby, np to 46 z 24 ^= 54, jakby ktos mogl wytlumaczyc mi dzialanie tego bylbym wdzieczny.
« Ostatnia zmiana: Maj 08, 2015, 14:07:16 wysłana przez _user »


Offline mawpa

  • Użytkownik

  • +1
# Maj 08, 2015, 14:11:21
Xor jest operatorem bitowym. To znaczy, że nie operuje na "rzeczywistych" wartościach, takich jak 24 czy 54, tylko na ich reprezentacjach binarnych i porównuje wartości poszczególnych bitów.

Przykład dla Twoich a = 24, b = 54:

24 jako liczba binarna to 011000
54 jako liczba binarna to 110110

Czyli zamiast 24 xor 54 mamy 011000 xor 110110
Porównujemy po kolei bity obu liczb, zaczynając od lewej:

0 xor 1 = 1
1 xor 1 = 0
1 xor 0 = 1
0 xor 1 = 1
0 xor 1 = 1
0 xor 0 = 0

Czytając od góry wyniki wszystkich działań, wychodzi nam 101110, co po zamianie na system dziesiętny daje nam 46 - dalej postępujemy analogicznie.
« Ostatnia zmiana: Maj 08, 2015, 16:44:02 wysłana przez mawpa »

Offline _user

  • Użytkownik

# Maj 08, 2015, 19:49:05
okej dziekuje