2. Рекурсия и итерация - 14.10.03

Алгоритъм на Евклид [1.2.3]
/* Два варианта на алгоритъма на Евклид за пресмятане на най-голям общ делител [1.2.3] */
// gcd.c
#include <stdio.h>
const unsigned n=6;

unsigned gcd1(unsigned a, unsigned b)
{ unsigned swap;
while (b>0) { swap=b; b=a%b; a=swap; }
return a;
}

unsigned gcd2(unsigned a, unsigned b)
{ return (0==b)? a : gcd2(b, a%b); }

int main(void)
{ const unsigned a=1, b=125;
printf("%u \n", gcd1(a, b));
printf("%u \n", gcd2(a, b));
return 0;
}
-- Реализация с изваждане
-- Съкращаване на дроби

/* Рекурсивно отпечатване на цифрите на число [1.2.5] */
// digit2.c
#include <stdio.h>

void printN(unsigned n)
{ if (n>=10) printN(n/10);
printf("%u ", n%10);
}
int main(void)
{ unsigned m=1234;
printN(m);
return 0;
}

/* Два варианта за пресмятане на n! [1.2.5] */
// fact.c
#include <stdio.h>
const unsigned n=6;
unsigned long fact1(unsigned i)
{ if (1==i) return 1;
return i*fact1(i-1);
}
unsigned i;
unsigned long fact2()
{ if (1==i) return 1;
return i-- *fact2(); // --i*fact();
}
int main(void)
{ i=n; // i=n+1;
printf("fact1: %u! = %lu \n", n, fact1(n));
printf("fact2: %u! = %lu \n", n, fact2());
return 0;
}

/* Три варианта за рекурсия и използване на глобални променливи [1.2.5] */
// print0.c
#include <stdio.h>
const unsigned n=6;
void printRed1(unsigned k, unsigned long res)
{ printf("%lu ", res);
if (k<n) printRed1(k+1,res*10);
printf("%lu ", res);
}

unsigned k=0;
void printRed2(unsigned long res)
{
k++;
printf("%lu ", res);
if (k<n) printRed2(res*10);
printf("%lu ", res);
}

unsigned long res = 1;
void printRed3()
{
k++;
res*=10;
printf("%lu ", res);
if (k<n) printRed3();
printf("%lu ", res);
res/=10;
}
int main(void)
{
printRed1(1,10);
printf("\n");
printRed2(10);
printf("\n");
k=0;
printRed3();
printf("\n");
return 0;
}

Стандартен вход и изход; пренасочване на входа и изхода.
1. Стандартен вход за езика C
scanf("<форматиращ спецификатор>",<адрес на променлива>);
Пример:
int ik;
unsigned uk;
long lk;
unsigned long ulk;
double dk;
scanf("%d %u %ld %lu %lf", &ik, &uk, &lk, &ulk, &dk);

2. Стандартен изход за езика C
printf("<форматиращ спецификатор>", <променлива>);
Пример:
int ik=-10;
unsigned uk=10;
long lk=-1000000;
unsigned long ulk=1000000;
double dk=2.52;
printf("%d %u %ld %lu %lf\n", ik, uk, lk, ulk, dk);

3. Стандартен вход за езика C++
cin >> <име на променлива>;
Пример:
int k;
cin >> k;

4. Стандартен изход за езика C++
cout << <име на променлива>;
Пример:
int ik=-10;
unsigned int uk=10;
long lk=-1000000;
unsigned long ulk=1000000;
double dk=2.52;
cout << ik << " " << uk << " " << lk << " "
<< ulk << " " << dk << "\n";

5. Пренасочване на стандартни вход и изход със средствата на ОС - DOS и всеки Unix-like.
Файл с програма на C или C++ със стандартни вход и изход: prog.exe
Текстов файл с входните данни за програмата:test1.inp
Изпълнение на програмата:
prog <test1.inp >test1.out
Текстов файл, произведен от програмата при това изпълнение: test1.out

Задача: Да се напише програма за намиране на НОД на n естествени числа.

Хипотеза: За естественото число a дефинираме редицата a₀= a, a_k+₁= a_k/2, ако a_k е четно или a_k+₁= 3a_k+1, ако a_k е нечетно. Ако някое a_k = 1, то тази стойност се счита за край на редицата. Всяко естествено число a генерира крайна редица.

Хипотези на Голдбах [1.1.3]
1. Всяко цяло четно число може да се представи като сума на две прости числа.
2. Всяко цяло число > 17 може да се представи като сума на 3 различни прости числа.
8849+8861+9769=27479
9973+2+3=9978