Кадндидат-студентски изпит по информатика на C++

С++ решаваня на задачи по информатика, от кандидатстудентски изпити

Нмиране на най-голям общ делител

leave a comment »

Намиране на най-голям делител – алгоритми на С++

  • Алгоритъм на Евклид с изваждане
  • Алгоритъм на Евклид с остатък от деление

Алгоритъм на Евклид с изваждане

Алгоритъмът е следния: От по-голямото се вади по-малкото число и присвоява получения резултат. Това се изпълнява докато числата са различни. Когато се изравнят двете числа, то това е НОД(a,b).

Пример: NOD(16,12) = NOD(16-12,12)=NOD(4,12)
NOD(4,12) = NOD(4,12-4)=NOD(4,8)
NOD(4,8) = NOD(4,8-4)=NOD(4,4)
NOD(4,4) => 4

Забележете, че задачата винаги има решение и не може да се получи безкраен цикъл!

Итеративно решение на C++:

/**
 * Функцията за най-голям общ делител
 */
unsigned int NOD(unsigned int a, unsigned int b)
{
    while(a!=b){
        if(a>b) a = a-b;
        else b = b-a;
    }
    return a;
}

Рекурсивно решение на C++:

/**
 * Функцията за най-голям общ делител
 */
unsigned int NOD(unsigned int a, unsigned int b)
{
    if(a>b) return NOD(a-b,b);
    else if(b>a) return NOD(a,b-a);
    else return a;
}

Алгоритъм на Евклид с остатък от деление

Алгоритъмът е следния: Ако имаме 2 естествени числа a и b(a>b), то може да запишем a=b.q+r, където r е остатъкът от делението на a на b. НОД се намира като всеки път се дели по-голямото число на по-малкото, като същото се повтаря като се вземе по-малкото число и остатъкът. Това се повтаря докато се намери остатък който е 0, то тогава търсеното число е делителят.

Пример: NOD(16,12) = NOD(12,16%12)=NOD(12,4)
NOD(12,4) = NOD(4,12%4)=NOD(4,0)
NOD(4,0) => 4

Задачата винаги има решение и тук не може да се получи безкраен цикъл!

Итеративно решение на C++:

/**
 * Функцията за най-голям общ делител
 */
unsigned int NOD(unsigned int a, unsigned int b)
{
    int r;
    if(a>b) swap(a,b);
    while(r=a%b){
        a=b;
        b=r;
    }
    return b;
}

Рекурсивно решение на C++:

/**
 * Функцията за най-голям общ делител
 */
unsigned int NOD(unsigned int a, unsigned int b)
{
    if(a<b) swap(a,b);
    if(b==0) return a;
    return NOD(b,a%b);
}

Written by Stoyanoff

20/04/2014 в 22:41

Вашият коментар

Попълнете полетата по-долу или кликнете върху икона, за да влезете:

WordPress.com лого

В момента коментирате, използвайки вашия профил WordPress.com. Излизане /  Промяна )

Google photo

В момента коментирате, използвайки вашия профил Google. Излизане /  Промяна )

Twitter picture

В момента коментирате, използвайки вашия профил Twitter. Излизане /  Промяна )

Facebook photo

В момента коментирате, използвайки вашия профил Facebook. Излизане /  Промяна )

Connecting to %s

%d блогъра харесват това: