TYPO3: добавить специальное меню CE и добавить class = «active»

Однако для итеративного алгоритма мы имеем:

int iterativeEGCD(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a % n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

. С парами Фибоначчи нет разницы между iterativeEGCD() и iterativeEGCDForWorstCase(), где последнее выглядит следующим образом:

int iterativeEGCDForWorstCase(long long n, long long m) {
    long long a;
    int numberOfIterations = 0;
    while ( n != 0 ) {
         a = m;
         m = n;
         n = a - n;
        numberOfIterations ++;
    }
    printf("\nIterative GCD iterated %d times.", numberOfIterations);
    return m;
}

Да, с парами Фибоначчи, n = a % n и n = a - n, это точно одно и то же.

Мы также знаем, что в более раннем ответе на тот же вопрос является преобладающим убывающим фактором: factor = m / (n % m).

Поэтому, чтобы сформировать итеративную версию евклидова GCD в определенном виде, мы можем изобразить как «симулятор» следующим образом:

void iterativeGCDSimulator(long long x, long long y) {
    long long i;
    double factor = x / (double)(x % y);
    int numberOfIterations = 0;
    for ( i = x * y ; i >= 1 ; i = i / factor) {
        numberOfIterations ++;
    }
    printf("\nIterative GCD Simulator iterated %d times.", numberOfIterations);
}

Основываясь на работе (последний слайд) д-ра Jauhar Ali, вышеописанный цикл является логарифмическим.

[/g1]

Да, малый О, потому что симулятор сообщает больше итераций. Партии, не связанные с Фибоначчи, занимали меньшее количество итераций, чем Фибоначчи, если они были исследованы на евклидовом GCD.