Loading...
melda.h avatar 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);
    
}

Тагове:
0
C++ Programming
ThePSXHive avatar 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. 

0
11/12/2016 15:56:57
melda.h avatar melda.h 4 Точки

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

0
melda.h avatar melda.h 4 Точки

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

0
ThePSXHive avatar 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, когато а притежава две или повече цифри, няма никакви попадения.

0
11/12/2016 18:49:06
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.