Задача с рекурсия

melda.h 4 Точки

Задача с рекурсия

Да се намери броя на срещанията на а я записа на б? Пример: 4 85454 - 2, 123 984512 - 0, 65 321659 - 1
Не мога да разбера къде бъркам!!!

#include <iostream>
using namespace std;

void FindNumber(unsigned int b,unsigned int a, int count) {

   if (b%10==a) {
       count++;

   }

   else if(b/10>0) {
       FindNumber(b/10, a, count);
   }

   cout << count << "\n";

}
int main() {
   unsigned int a, b;
   int count = 0;
   cin >> b >> a;
   FindNumber(b,a, count);

}

Тагове:

11/12/2016 11:26:36 C++ Programming

ThePSXHive 436 Точки

Тази програма установява броя на a в b само когато a е цифра. Ще сработи за първият пример, но не и за останалите два. Но проблемът в случая e, че се използва конструкция else-if вместо 2 if-a; нека вземем за пример b = 1223 и a = 2. Това означава, че най-напред ще бъде проверено първото условие, и понеже то е неистинно (1 != 2), изпълнението на ф-та преминава към else-if, и извикваме ф-та отново. Сега, тъй като (2 == 2), то броячът отчита едно попадение, но и проверката е вярна, а когато имаш else-if конструкция, след вярна проверка не се изпълнява else-if блокът, и рекурсията се прекратява. Всичко това се случва докато стойността на counter-a се показва за всяко извикване на ф-та. Предполагам, че това също не е желателно. Бих пренаписал ф-та по следния начин, запазвайки общата й структура:

void FindNumber(unsigned int b, unsigned int a, unsigned int count)
{
    if (b % 10 == a) count++;
    if (b == 0) cout << count;
    else FindNumber(b / 10, a, count);
}

Забележи разположението на моя base case (условие за прекратяване на рекурсивната верига на извиквания). Освен това, count също е неотрицателно число, и затова типът му трябва да бъде unsigned.

11/12/2016 15:43:48 11/12/2016 15:56:57

melda.h 4 Точки

Благодаря ти много! Просто не разбирах защо ми се прекратява проверката и номера с count++ къде точно да е.

11/12/2016 18:12:37

melda.h 4 Точки

A какъв е проблемът, че не е валиден този код за другите два примера?

11/12/2016 18:21:30

ThePSXHive 436 Точки

Променливата count служи по-скоро като променлива, която изброява цялото съвпадение на a с b. Ако вземем за пример първите данни - b = 85454 и a = 4 - имаме следната поредица от операции:

8545|4 == 4 -> counter = 1
854|5 != 4 -> ----
85|4 == 4 -> counter = 2
8|5 != 4 -> ----
|8 != 4 -> ----

Дотук добре. Понеже a e цифра, всяко попадение с b се отчита. Но ето какво се получава ако а има повече от една цифра:

32165|9 != 65 <-> ---- 
3216|5 != 65 <-> ---- 
321|6 != 65 <-> ---- 
32|1 != 65 <-> ---- 
3|2 != 65 <-> ---- 
|3 != 65 <-> ----

Понеже този алгоритъм рекурсивно "разбива" b на по-малка стойност, като само последната цифра бива сравнявана със стойността на a, когато а притежава две или повече цифри, няма никакви попадения.

11/12/2016 18:46:24 11/12/2016 18:49:06