undefined
изчисляване на факториел чрез итерация и рекурсия
факториел чрез итерация
факториел чрез рекурсия
редица с факториел
двоен факториел n!!
Ще наричаме факториел от N произведението на всички естествени от интервала [1..N].
С факториел са свързани ред практически задачи. Примерно по колко различни начина могат да бъдат подредени N предмета.
Математическата функция факториел връща стойност 1, ако въведеното число N е 0 или 1.
Алгоритъм:
Инициализираме началната стойност на променливата факториел = 1.
В цикъл от 2 до N умножаваме получената до момента стойност с поредното число от цикъла.
След като цикъла приключи се извежда стойността на тази променлива - стойност на вече изчисления факториел от това число.
Една примерна задача за изчисляване на факториел би имала следното условие:
Да се състави програма за изчисляване на факториел по въведено число n: n*(n-1)*(n-2)*..*2*1.
Входни данни: естествено число от интервала [2 - 15].
Пример: 5 Изход: 120
Ще разгледаме задачата за изчисляване на факториел в два варианта: чрез итерация и чрез рекурсия.
Следващите две програми дават решена задача за изчисляване на факториел.
факториел чрез итерация
#include <iostream>
using namespace std;
long int have_fak_I( int chis ) //!!! long - mnogo byrzo narastwa stojnostta
{long fak=1;//nachalna inicializaciq
int i;
cout<<"Presmqtam s chislo : "<<chis<<endl;
for (i=1;i<=chis;i++)
{ fak*=i;
cout<<"Chislo : "<<i<<"! = "<<fak<<endl;
}
return fak;
}//kraj na funkciq factoriel
int main ()
{ int n;
cout<<"Da se systawi programa, izpolzwasha rekursiwna funkciq, koqto\n";
cout<<"izwevda faktoriel na wywedeno chislo n! = n*(n-1)*(n-2)*..*2*1.\n";
cout<<"Whodni danni: estestweno chislo ot interwala [3..15].\n";
cout<<"Primer: 5 Izhod 120.\n";
cout<<"Wywedete estestweno chislo ot interwala [3..15]: "; cin>>n;
cout<<"Poluchenata chislo za factoriel "<<n<<"! e: "<<have_fak_I(n)<<endl;
system("pause");
return 0;
}//kraj na programa factoriel
Начало на страницата
факториел чрез рекурсия
#include <iostream>
using namespace std;
long int have_fak_R( int chis ) //!!! long - mnogo byrzo narastwa stojnostta
{//tqlo na rekursiwnata funkciq - stojnostta na faktoriela raste byrzo
cout<<"Presmqtam s chislo : "<<chis<<endl;
if ( chis > 1 )
{return have_fak_R( chis-1 )*chis; }
//rekursiwno izwikwane, no s chislo s 1 po-malko ot tekushoto
else { return 1; } // dyno na rekursiata factoriel 0 = 1
}//kraj na rekursiwnata funkciq factoriel
int main ()
{ int n;
cout<<"Da se systawi programa, izpolzwasha rekursiwna funkciq, koqto\n";
cout<<"izwevda faktoriela na wywedeno chislo n! = n*(n-1)*(n-2)*..*2*1.\n";
cout<<"Whodni danni: estestweno chislo ot interwala [3..15].\n";
cout<<"Primer: 5 Izhod 120.\n";
cout<<"Wywedete estestweno chislo ot interwala [3..15]: "; cin>>n;
cout<<"Poluchenata chislo za factoriel "<<n<<"! e: "<<have_fak_R(n)<<endl;
system("pause");
return 0;
}//kraj na programa factoriel
редица с факториел
Да направим съпоставка между аритметична прогресия с разлика 1 и факториел - при изчисляване на факториел всеки следващ член от редицата е с 1 по-голям от предходния - аналогично на артметична прогресия с разлика 1.
Нека разгледаме примерна задача с факториел, в който всеки следващ член придобива стойност кратна на предходния - аналогично на геометрична прогресия с въведена стойност за частно.
Да се състави програма, чрез която се изчислява произведение от вида: 1*(1+k)*(1+2*k)...*(1+n*k), където n и k са естествени числа.
Алгоритъм:
Произведение, в който един от множителите е 0 е също 0.
При функцията с цикъл инициализираме началната стойност на произведението с 1 и на всяка стъпка изчисляваме новия член на редицата - множители на функция факториел.
При рекурсивната функция стигаме до първия член от редицата, на който присвояваме стойност 1 и в обратния ход изчисляваме новия член на редицата.
Следващата примерна програма съдържа итеративна и рекурсивна функция за изчисляване членове на редица с факториел:
#include <iostream>
using namespace std;
long int faktoriel_rekursiq( int chis, int koef )
{//tqlo na rekursiwna funkciq - stojnostta na faktoriela raste byrzo
if ( chis > 1)
{return faktoriel_rekursiq( chis-1,koef )*(1+(chis-1)*koef);
//rekursiwno izwikwane, no s chislo s 1 po-malko ot tekushoto
} else return 1; //dyno na rekursiq
}//kraj rekursiq faktoriel
long int faktoriel_iteraciq( int chis, int koef )
{int i;//iteratiwna funkciq
long k=1;
for (i=1;i<chis;i++) k*=(1 + (chis-i)*koef);
return k;}//iteraciq faktoriel
int main ()
{ int n,k;
cout<<"Da se systawi programa, izpolzwasha rekursiwna funkciq, koqto\n";
cout<<"izwevda stojnost na izraza 1*(1+k)*(1+2*k)...*(1+n*k).\n";
cout<<"Whodni danni: estestweno chislo ot interwala [3..10].\n";
cout<<"Primer: n=4, k=2 Izhod 945.\n";
cout<<"Wywedete estestweno chislo n ot interwala [3..10]: "; cin>>n;
cout<<"Wywedete estestweno chislo k ot interwala [1..2]: "; cin>>k;
cout<<"Poluchena stojnost s rekursiq za "<<n<<" e: "<<faktoriel_rekursiq(n,k)<<endl;
cout<<"Poluchena stojnost s iteraciq za "<<n<<" e: "<<faktoriel_iteraciq(n,k)<<endl;
system("pause");
return 0;
}//kraj na programa faktoriel
двоен факториел n!!
При изчисляване на факториел от естествено число N се взема произведението от N и всички естествени числа <N.
Аналогично при двоен факториел се взема произведението от N и всички естесвени числа през 1.
Ако N е нечетно число, то N!!=1*3*5*7...*(N-4)*(N-2)*N.
Ако N е четно число, то N!!=2*4*6*8...*(N-4)*(N-2)*N.
Да се състави програма, чрез която се въвежда естествено число N и се извежда N!!
Алгоритъм
Произвeдение, в който един от множителите е 0 е също 0.
Число умножено или разделено с 1 не променя стойността си
И при двете функции началната стойност на факториел се инициализира с 1.
Изчисляването на всеки отделен множител на функцията факториел се извършва аналогично на прогресия с разлика 2.
Следващата примерна програма съдържа итеративна и рекурсивна функция за изчисляване на двоен факториел:
#include <iostream>
using namespace std;
long int faktoriel_iteraciq( int chis )
{ long k=1;
while(chis>1)
{ k*=chis;
chis-=2;}
return k; }//kraj dwoen faktoriel n!!
long int faktoriel_rekursiq( int chis )
{//tqlo na rekursiwna funkciq - stojnostta na faktoriela raste byrzo
if ( chis > 1 )
{return faktoriel_rekursiq( chis-2 )*chis;
//rekursiwno izwikwane, no s chislo s 2 po-malko ot tekushoto
} else return 1; //dyno na rekursiq
}//kraj rekursiq faktoriel
int main ()
{ int n;
cout<<"Da se systawi programa, izpolzwasha rekursiwna funkciq, koqto\n";
cout<<"izwevda stojnost na dwoen faktoriel 2*4*...(n-2)*n\n";
cout<<"Whodni danni: estestweno chislo ot interwala [3..20].\n";
cout<<"Primer: n=8 Izhod 384.\n";
cout<<"Wywedete estestweno chislo n ot interwala [3..20]: "; cin>>n;
cout<<"Poluchenata stojnost s rekursiq za "<<n<<" e: "<<faktoriel_rekursiq(n)<<endl;
cout<<"Poluchenata stojnost s iteraciq za "<<n<<" e: "<<faktoriel_iteraciq(n)<<endl;
system("pause");
return 0;
}//kraj na programa faktoriel rekursiq
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.
Начало на страницата
