Как изменить цифры числа в рекурсивной функции? Переполнение стека
Я должен ввести номер n, a цифра и b цифра и вывод числа n со всеми a цифры в нем заменены на b один. Например:
Input:
n = 1561525
a = 5
b = 9
Output:
n = 1961929
Должен быть рекурсивным! Я не публиковал какой-либо код, так как делал это нерекурсивно, но, видимо, он даже близко не соответствует тому, что мне нужно.
Спасибо за помощь !
Решение
Проверьте это, это работает, но, возможно, это слишком много C
int convert(int num, int a, int b)
{
if( num )
{
int res = convert(num/10,a,b);
int t = num%10;
res *=10;
t = t == a ? b:t;
res = res + t;
return res;
}
return 0;
}
Разделите на 10 начальное число, пока от него ничего не останется, и затем построите его снова, заменив a на b.
Другие решения
Чтобы упростить задачу, вы можете преобразовать число в строку ( char[] в C ++). Затем достаточно просто выполнить итерацию и на каждом шаге проверять, найдено ли число, которое мы хотим заменить, в текущей позиции. Для возможного решения, вот реализация алгоритма в Python — одна из приятных особенностей языка в том, что он читается почти как псевдокод, и его должно быть относительно просто портировать на C ++:
def aux(n, a, b, i):
if i == len(n):
return ''
elif n[i] == a:
return b + aux(n, a, b, i+1)
else:
return n[i] + aux(n, a, b, i+1)
def change(n, a, b):
return int(aux(str(n), str(a), str(b), 0))
Работает как положено:
change(1561525, 5, 9)
=> 1961929
Так что самый простой и безопасный способ, который я могу себе представить, это использование std::replace:
int replace(int num, int d1, int d2) {
string s = std::to_string(num); // convert to string
std::replace( s.begin(), s.end(), d1+'0', d2+'0'); // call std::replace
return atoi( s.c_str() ); // return the int
}
Теперь, если вы действительно необходимо использовать рекурсию (здесь нет необходимости), вот одно из возможных решений:
using std::string;
// recursive function, accepts a string, current index, c2 replaces c1
string replace_rec (string s, unsigned index, char c1, char c2) {
// check if the it's still a valid index
if (index < s.size()) {
// if this is a char to be converted, do so
if (s[index] == c1)
s[index] = c2;
// call itself but with an updated string and incremented index
replace_rec(s, index+1, c1, c2);
}
// the last call will result in the string with all chars checked. return it
return s;
}
// call this function with input, the num to be replaced and what with
int replace(int num, int d1, int d2) {
string s = std::to_string(num); // convert to string
// convert the result back to int and return it.
return atoi( replace_rec(s, 0, d1+'0', d2+'0').c_str() );
}
В любом случае вы можете позвонить replace() функционировать так:
int main(){
cout << replace (4578, 4, 9); // output: 9578
cin.get();
}
detector