Определяне на цифри в естествено число - рекурсия и итерация

Следващите програми илюстрират идеята, че рекурсия и итерация са алтернативни подходи при решаване на широк кръг задачи. Изборът рекурсия или итерация трябва да бъде обвързан с конкретния проблем, а не да бъде самоцел. В много от случаите при циклична обработка се ползва масив. При използване на рекурсия се препоръчва масивът да не се предава като параметър. Итерацията изглежда по-разбираема, рекурсията е по-бърза, но и изисква повече памет. Когато казваме, че една програма е рекурсивна се разбира, че тя съдържа в себе си поне една рекурсивна функция.

Под естествено число ще разбираме цяло положително число (1,2,3,...,n). Цифрите в 10-ична бройна система са 0,1,2,3,4,5,6,7,8,9 и също са числа. Алгоритъм за определяне броя и вида цифри в естествено число: въвежда се естествено число; това число се дели целочислено на основата на бройната система - в случая 10; последната (най-дясната) цифра може да бъде определена чрез операцията %, следващата стъпка е целочислено делене на 10 - премахваме последната цифра. Алгоритъмът продължава докато редуцираното число е по-голямо от 0. Всяка програма съдържаща цикличен алгоритъм може да се реализира, както с итерация, така и с рекурсия.

Тук целта е да се представят успоредно двата варианта - с рекурсия и итерация.
Задачата е следната:
От клавиатурата се въвежда естествено число N от интервала [1..10001].
Програмата трябва да изведе сумата на всички единици, участващи в изписването на числата от интервала [1..N] при представянето им в 2-ична бройна система.
Пример: 4 Изход: 5
1 – 1
2 - 10
3 – 11
4 – 100
Общият брой на 1-ците е 5.
Кратко описание на алгоритъма брой и вид цифри в двоично число.
Въвежда се естествено число.
Създадени са 2 вложени цикъла. Външният обхожда всички числа от интервала. Вътрешният брой всички единици на поредното число, чрез проверка на най-дясната цифра. След като е проверена тази цифра се изтрива.
В езика C/C++ има възможност да се работи директно с разрядите на въведеното число:
а) i & 1;//операция AND
дали въведеното число е четно или нечетно, дали последна цифра на това число в 2-ично представяне е 0 или 1
б) i=i>>1;//всички разряди се премества с 1 позиция надясно, т.е. маха се най-десния разряд, най-дясната цифра на въведеното число.
Същият резултат може да се постигне и чрез целочислено делене на 2 и проверка на целочисления остатък. Този подход е приложен във функцията redica2.
Реализацията на алгоритъма е в 3 варианта: чрез вложен цикъл (redica2), чрез 2 отделни цикъла (redica и chislo) и чрез съставна рекурсия (redica1 и chislo1).
За по-голяма яснота при съпоставяне рекурсия итерация освен една функция с вложен цикъл са реализирани две отделни функции.

Следващата примерна програма реализира решена задача за извеждане на всички цифри в естествено число чрез итерация.

#include <iostream>
using namespace std;

long chislo(long i)//wytreshen cikyl
 {long j;
  // iteratiwen wariant za prowerka broj cifri 1 w dwoichnoto predstawqne
  j=0;//inicializirane na suma ot 1 w dwoichnoto predstawqne
    while (i>0)
   {j +=i & 1;//operaciq AND dali chisloto e chetno ili ne, dali poslednata cifra e 0 ili 1
     i=i>>1;//izmestwane s 1 razrqd nadqsno
    }//while
   return j;
} // iteraciq broj cifri 1 w chisla

long redica(long m)//wynshen cikyl
{ long j,k,n;
   //wariant iteraciq za obhovdane na wsichki chisla ot interwala
   j=0;//inicializirane na obshata suma
  for (k=1; k<=m;k++)
    {n=chislo(k);//broj 1-ci w porednoto estestweno chislo
     j+=n;    // broj edinici w porednoto chislo
     //sledwashiq red e samo za iliustraciq - movete da go ostawite kato komentar
     //cout<<"Chisloto "<<k<<" w 2-ichna brojna sistema ima "<<n<<" broq 1-ci\n";
   }//for
    return j;
 }// iteraciq cifri w chislo

long chislo1(long i)//wlovena rekursia
   { long m;
   // wariant rekursia za prowerka broj 1-ci w dwoichnoto predstawqne
    m= i & 1;//dali poslednata mu cifra e 1
     if (i>0) {i=i>>1; return chislo(i)+m;}
    else return 0;
}// rekursia cifri 1 pri dwoichno predstawqne na chislo

 long redica1(long m)
 {// wariant rekursia za obhovdane na wsichki chisla ot interwala
      if (m>0) {return redica1(m-1)+chislo(m);}
      else return 0;
    }// rekursia obhovdane na chisla

   long redica2 (long m) //funkciq s wloven cikyl
   // wariant iteraciq s wloven cikyl za prowerka broj 1 w dwoichnoto predstawqne
  {long i,j,N,sum=0;
     for (i=1;i<=m;i++)//obhovdane na wsichki chisla ot interwala
   { N=i;//porednoto chislo ot interwala
    while (N>0)//broj 1-ci w chsiloto, predstaweno w 2-ichna brojna sistema
        { sum+=N%2;//dali chisloto e chetno - celochislen ostatyk
          N/=2; //namalqwame 2-pyti chisloto - celochisleno delene
     }//while
    }//for
   return sum;
}// iteraciq broj cifri 1 w chisla

int main ()
{ long m,n; 
  char ose;
  cout<<"Imate wywedeno estestweno chislo M ot interwala [5..50005].\n";
  cout<<"Da se systawi programa,  chrez koqto se izchislqwa obshiq broj\n";
  cout<<"na 1-cite pri predstawqne na wsichki estestweni chisla ot 1\n";
  cout<<"do wywedenoto wkluichitelno w 2-ichna brojna sistema.\n";
  cout<<"Primer: 10 Izhod 17\n";
   do { cout<<"Wywedete chislo [5..1005]: ";cin>>m;
        n=redica(m);
        cout<<"Pri iteratiwniq wariant obsh broj 1-ci w redicata: "<<n<<endl; 
        n=redica1(m);//wsichki chisla ot interwala 1..m wkluichitelno
        cout<<"Pri wariant s rekursia obsh broj 1-ci w redicata: "<<n<<endl;
        n=redica2(m);
        cout<<"Pri wariant s wloven cikyl obsh broj 1-ci w redicata: "<<n<<endl;
        cout<<"She wywevdate li drugi chisla <y/n>: ";cin>>ose;
    } while (ose=='y');
    system("pause");
    return 0;
}//kraj na programa rekursia

Начало на страницата

рекурсия - монотонна редица

Имаме редица състояща се от предварително въведени N броя естествени числа. Трябва да се провери дали редицата е монотонно намаляваща, т.е. дали всяко число от редицата е по-голямо или равно на следващото. Да се използва рекурсия.

Алгоритъм:
За да се въведат елементите в редицата се използва масив, който е деклариран като глобален.
Чрез рекурсия се обхожда масива започвайки от неговия последен член с индекс n-1.
В рекурсивното извикване се проверява условието if (mas[n-2]>=mas[n-1]).
Следващата примерна програма реализира проверка за монотонност чрез рекурсия:

#include <iostream>
using namespace std;

const int broi=9;//razmer na redica
int mas[broi]={33,23,21,12,12,8,6,3,2};//gllobalno definiran masiw

int monoton(int n)
{int b;
 if (n==1) return 1;//dyno rekursia
 if (mas[n-2]>=mas[n-1]) b=1; else b=0;
 return b && monoton(n-1);
}//kraj rekursia  

int main () //nachalo na programata
{int br;
 cout<<"Da se systawi programa, chrez koqto se wywevdat 9 estestweni\n";
 cout<<"chisla ot interwala [1..99]. Izpolzwajte rekursiwna funkciq,\n";
 cout<<"za da prowerite dali wywedenata redica e monotonno namalqwasha.\n";
 for (br=0;br<broi;br++)  { cout<<mas[br]<<"; "; }
 cout<<"\n Redicata ";
 if (monoton(broi)) {cout<<"e ";} else {cout<<"ne e ";}//1 da ili 0-ne
 cout<<"monotonno namalqwasha. "<<endl;
system("pause");
return 0;
}//kraj na programa rekursia

Начало на страницата

рекурсия - елемент в редица

Имаме редица от предварително въведени N броя естествени числа. Трябва да се провери дали в редицата се съдържа елемент с определена стойност. Да се използва рекурсия.

Алгоритъм:
Използва се масив, който е деклариран като глобален – при всяко рекурсивно извикване фунцията зарежда отново в оперативната памет кода и данните си.
Чрез рекурсия се обхожда масива започвайки от неговия последен член.
Резултатът от проверката mas[0] == x е от булев тип и е дъно на рекурсия.
Условието за равенство се проверява в рекурсивното извикване чрез логически OR x == mas[n-1] || tursi (x,n-1).
Следващата примерна програма реализира проверка наличие на определена стойност в редица чрез рекурсия:

#include <iostream>
using namespace std;

const int broi=9;//zadawa razmer na redica
int mas[broi]={2,5,7,8,9,11,13,1,6};

int tursi (int x, int n)
{ if (n<1) return mas[0]==x;// dyno na rekursia
return x==mas[n-1] || tursi (x,n-1);//dali e rawno na 1 ot dwete
}//kraj rekursia

int main ()
{int br, chis;
 cout<<"Da se systawi programa, chrez koqto se wywevdat 9 estestweni \n";
 cout<<"chisla ot interwala [1..99]. Izpolzwajte rekursia, za da \n";
 cout<<"prowerite dali wyw wywedenata redica ima opredeleno chislo.\n";
 for (br=0;br<broi;br++)  cout<<mas[br]<<"; ";
 cout<<endl;
 cout<<"Wywedete tyrsenoto chislo: ";cin>>chis;
 cout<<"Chisloto "<<chis;
 if (tursi (chis,broi)) {cout<<" e ";} else {cout<<" ne e ";}//rezultat ot erkursiq 0,1
 cout<<"wyw wywedenata redica."<<endl;
system("pause");
return 0;
}//kraj na programa rekursia

Начало на страницата

рекурсия - сума от елементи в редица

Имаме редица съставена от предварително въведени N броя естествени числа. Трябва да се изчисли сумата на всички елементи в редицата. Да се използва рекурсия.

Алгоритъм:
Използва се масив, който е деклариран като глобален.
Чрез рекурсия се обхожда масива започвайки от неговия последен член.
В рекурсивното извикване се натрупва сумата return have_sum( chis-1 )+ mas[chis]. Началната стойност на сумата е 1-вия елемент от редицата return mas[0] - дъно на рекурсия.
Разликата на подхода при рекурсия и итерация се вижда от приложената блок схема:

рекурсия - итерация

Следващата примерна програма реализира сума на елементи от редица чрез рекурсия:

#include <iostream>
#include <stdlib.h>//rand;
using namespace std;

const int n=10;
int mas[n];

int  have_sum( int chis ) 
{ if ( chis >0 )  return have_sum( chis-1 )+ mas[chis];
  else return mas[0];//dyno na rekursia 
}//kraj na rekursia

int main()
{ int c;
 cout<<"Da se systawi programa, izpolzwasha rekursiwna funkciq, koqto\n";
 cout<<"izwevda sumata na wsichki elementi ot dadena redica.\n";
 cout<<"Nachalni stojnosti na masiwa:\n";
 for (c=0;c<n;c++) 
 {mas[c]=rand() %50;//mas[c]=c+1;
 cout<<mas[c]<<" ";}
 cout<<"\n Suma: ";
 cout<<have_sum(n)<<endl;;//rekursiwna funkcia  
system("pause");
return 0;
}//kraj na programa rekursia

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

Начало на страницата

Размер на шрифта

Търсене в сайта:

Спонсори

Изпълними приложения за

Определяне на цифри в естествено число - рекурсия и итерация

рекурсия - монотонна редица

рекурсия - елемент в редица

рекурсия - сума от елементи в редица