Nejmenší společný dělitel a "hloupá" holka v nesnázích – C / C++ – Fórum – Programujte.com

Zdravím lidi,

potřebovala bych poradit do školy s úlohou "Hledání nejmenšího společného dělitele". Ve škole mi bohužel utekl celý úvod do C++ a doučuji se jen tady pomocí "Kurzu C++" (tímto mockrát děkuji autorovi za krásně napsaný kurz i pro dementy jako já, protože přávě čtu 2. lekci a zatím jsem v obraze). Ale zpět k věci, prostě jsem uplně v pasti, matematicky bych to dala, ale nevím jak to přenést do C++. Poradí please nějaký borec, který se zrovna nudí :-)

Pokud jo, předem velice děkuji.

Lara

Jeastli to "matematicky" uděláš tak není problém to v Cčku udělat. Přemýšlej nad vzorcem výpočtu a pak to zakomponuj do kódu.

Najmensi spolocny delitel ? Ved to je pre vsetky cisla z R 1 ;). Tak predpokladam, ze hladas najvacsi spolocny delitel.

int D(int x1, int x2)

{

   int tmpx = x1 > x2 ? x2 : x1;

   for(;tmpx > 1; tmpx--) {

      if( ((x1%tmpx) || (x2%tmpx)) == 0)

         return tmpx;

        }

   return 1;

}

DeathHumanCZ píše:#
# Jeastli to "matematicky" uděláš tak není problém to v Cčku udělat. Přemýšlej nad vzorcem výpočtu a pak to zakomponuj do kódu.

k píše:#
# Najmensi spolocny delitel ? Ved to je pre vsetky cisla z R 1 ;). Tak predpokladam, ze hladas najvacsi spolocny delitel.#
##
#

#
#int D(int x1, int x2)#
#{#
#   int tmpx = x1 > x2 ? x2 : x1;#
#   for(;tmpx > 1; tmpx--) {#
#      if( ((x1%tmpx) || (x2%tmpx)) == 0)#
#         return tmpx;#
#        }#
#   return 1;#
#}#
#

#
#

Ještě doplním, úloha má jít řešit 2 způsoby. Potřebovala bych to vysvětlit i kamarádce (ještě větší lama než já). Zítra todle budem řešit ve škole a potřebovaly bychom zaperlit každá s jiným způsobem :-D takový divadýlko pro učitele ;-)

nesluzi na toto prave euklidov algoritmus? (teda ked predpokladam ze sa jedna o najvecsi delitel)

int nsd(int a, int b){



  do{



    if(a > b) a -= b;

    else if(b > a) b -= a;



  }while(a != b);



  return a;

}

Dovolim si olga trosicku opravit ;-)
Pro hledání největšího společného dělitele (NSD, Greatest Comon Divisor, GCD) dvou čísel se používá euklidovský algoritmus.

int nsd(int ta, int tb){



  int A, B, C;



  // zjistime, ktere z cisel je vetsi

  if(ta > tb){

    A = ta;

    B = tb;

  } else if(ta < tb){

    A = tb;

    B = ta;

  } else{ // pokud jsou stejna, jsou obe NSD

    return ta;

  }



  do{



    C = A%B; // % je operator modulo



    A = B;

    B = C;

  } while(B != 0); // dokud neni zbytek (tedy C) roven "0".. Protoze jsme to ale pred chvily cele posunuli, budeme porovnavat B



  return A;



}

A          B          C



250        32         26

32         26         6

26         6          2

6          2          0

To olgo: jj, Euklidův algoritmus je pro největšího, já ale potřebuju pořešit nejmenšího společného dělitele :-]

To Zelenáč: Byl jsi rychlejší :-) Každopádně díky i za toho největšího společ. dělitele. ;-) Můj problém ale zůstává

Lara

NEJMENŠÍ SPOLEČNÝ DĚLITEL NEEXISTUJE!!!
z toho důvodu, že neexistuje ani nejmenší číslo... Ať vezmu jakékoli číslo, vždy najdu ještě nějaké číslo měnší (to samozřejmě platí pro obor reálných čísel).
V oboru celých čísel je nejmenší společný dělitel vždy 1, takže nemá cenu ho počítat..

To Zelenáč: Ty jo, dohodneme se na tom, že na celý tento topic zapomeneme a nebudeme o něm nikomu říkat? :-D Řeším to už několik hodin a až teď mi došlo, že jsem celou dobu řešila uplnou hloupost :-D

Díky moc za pomoc, jdu si posypat hlavu popelem.

Lara

To Zelenáč: a ako je to pri zrovnani tych algoritmov? imho je rychlejsie to odcitane ale asi to bude hodne zavisiet od vstupu

Asi urcite to bude zaviset na vstupu.. Deleni je sice AFAIK daleko narocnejsi nez odecitani, ovsem rekneme, ze bychom meli spocitat NSD 10 000 000 000 a 2.. Moje verze by tohle zvladla za jedinou iteraci, zatimco tvoje by na to potrebovala 9 999 999 998 iteraci..

To Zelenáč: Už jsem přišel na vzorec pro nejmenšího společného dělitele "a:a" :-D

omg nikto neuviedol funkciu na vypočet najmenšieho delitela tak ja to napravim:

int spolocnyDelitel(int a,int b)

{

     int ret;



     ret = (a+b) / (b+a);

     ret *= ret;

     for (int i=0;i<(sqrt(a*a+b*b);i++)

           ret = (-1)*(-1)*ret;

     return ret;

}

To mephi: :-D