Rekurencja - operacje na liczbach

Question

Byłbym wdzięczny za wytłumaczenie dlaczego ten kod nie działa, ewentualnie zaproponowanie swojego rozwiązania.

Mam zadanie:

Dane są trzy operacje na liczbach:
A) Jeżeli dana liczba jest co najmniej dwucyfrowa, zamieniamy jej dwie ostatnie cyfry miejscami
B) Mnożymy liczbę przez 3
C) Jeżeli dana liczba jest co najmniej dwucyfrowa, usuwamy pierwszą cyfrę (od lewej)

Mamy dane liczby x,y i musimy napisać funkcję szukającą sekwencję operacji przekształcającą x na y. Sekwencja ta ma być max.7 operacyjna oraz zakładamy, że x != y na początku.

Przykład: x = 6 y = 3
Sekwencja BACB
Bo: B: 6*3 = 18   A:81 C:1 B: 1*3=1

I tutaj to co udało mi się naklepać:

Funkcje pomocnicze realizujące działania A,B,C:

int dzialanie_A(int x)
{
    int a,b;
    a = x % 10;
    b = (x / 10) % 10;
    x /= 100;
    x *= 100;
    x += b + 10 * a;
    return x;
}

int dzialanie_B(int x)
{
    x*=3;
    return x;
}

int dzialanie_C(int x)
{
    int xc = x;
    int dl = 0;
    while(xc > 0)
    {
        xc /= 10;
        dl++;
    }

    int k = 1;
    for(int i=1; i<dl; i++)
        k *= 10;

    x %= k;
    return x;
}

Funkcja rekurencyjna szukająca sekwencji:

bool czyA = false;

bool przeksztalcenia(int x, int y, int & ile, string & wynik)
{
    if(x == y)   return true;
    if(ile == 0)
    {
        ile++;
        return false;
    }

    ile--;


    if(x % 100 > 9 and czyA == false)
    {
        czyA = true;

        if(przeksztalcenia(dzialanie_A(x),y,ile,wynik))
        {
            wynik = 'A' + wynik;
            return true;
        }
    }
    czyA = false;


     if(x % 100 > 9)
    {
        if(przeksztalcenia(dzialanie_C(x),y,ile,wynik))
        {
            wynik = 'C' + wynik;
            return true;
        }
    }


    if(przeksztalcenia(dzialanie_B(x),y,ile,wynik))
    {
        wynik = 'B' + wynik;
        return true;
    }
}

 

 

Cały program w jednym kawałku:

#include <iostream>

using namespace std;

int dzialanie_A(int x)
{
    int a,b;
    a = x % 10;
    b = (x / 10) % 10;
    x /= 100;
    x *= 100;
    x += b + 10 * a;
    return x;
}

int dzialanie_B(int x)
{
    x*=3;
    return x;
}

int dzialanie_C(int x)
{
    int xc = x;
    int dl = 0;
    while(xc > 0)
    {
        xc /= 10;
        dl++;
    }

    int k = 1;
    for(int i=1; i<dl; i++)
        k *= 10;

    x %= k;
    return x;
}



bool czyA = false;

bool przeksztalcenia(int x, int y, int & ile, string & wynik)
{
    if(x == y)   return true;
    if(ile == 0)
    {
        ile++;
        return false;
    }

    ile--;


    if(x % 100 > 9 and czyA == false)
    {
        czyA = true;

        if(przeksztalcenia(dzialanie_A(x),y,ile,wynik))
        {
            wynik = 'A' + wynik;
            return true;
        }
    }
    czyA = false;


     if(x % 100 > 9)
    {
        if(przeksztalcenia(dzialanie_C(x),y,ile,wynik))
        {
            wynik = 'C' + wynik;
            return true;
        }
    }


    if(przeksztalcenia(dzialanie_B(x),y,ile,wynik))
    {
        wynik = 'B' + wynik;
        return true;
    }
}



int main()
{
    int x,y;
    int ile = 7;
    string w = "";

    cin>>x>>y;

    przeksztalcenia(x,y,ile,w);

    cout<<w;


    return 0;
}

 

Comments

Problem najprawdopodobniej wynika z tego, że mimo ograniczenia ilości działań przez zmienną ile program wykonuje się sporo więcej razy i to ograniczenie jakoś spaprałem, byłbym dalej wdzięczny za wskazówki jak to zrobić żeby jak dojdzie do 7 to żeby program się cofnął

Answer 1

Dla twoich przykładów aplikacja wyrzuca tą sekwencję, którą podałeś. Jedyne co musiałem zmienić to and na && i dodać bibliotekę string'ów.