Как проверить, что число имеет повторяющийся ди git с помощью рекурсии?

Question

Мне нужно знать, есть ли у числа повторяющийся ди git с использованием рекурсии и возвращать «да» или «нет». Мне не разрешено использовать циклы или массивы. Это то, что я делал до сих пор с 10 глобальными переменными, и это работает, но я думаю, что есть лучший способ.

#include <iostream>

using namespace std;


int counter0 = 0;
int counter1 = 0;
int counter2 = 0;
int counter3 = 0;
int counter4 = 0;
int counter5 = 0;
int counter6 = 0;
int counter7 = 0;
int counter8 = 0;
int counter9 = 0;
bool check(int k) {
    int p = k % 10;;
    if (k < 10) {
        return false;
    } else {
        if (p == 0) {
            counter0++;
        } else if (p == 1) {
            counter1++;
        } else if (p == 2) {
            counter2++;
        } else if (p == 3) {
            counter3++;
        } else if (p == 4) {
            counter4++;
        } else if (p == 5) {
            counter5++;
        } else if (p == 6) {
            counter6++;
        } else if (p == 7) {
            counter7++;
        } else if (p == 8) {
            counter8++;
        } else if (p == 9) {
            counter9++;
        }
        if(counter1>1 || counter2>1 || counter3>1 || counter4>1 || counter5>1 || counter6>1 || counter7>1 || counter8>1 || counter9>1)
        {
            return true;
        }
        k=k/10;
        check(k);
    }

}

int main() {
    //cout << "Hello, World!" << std::endl;
    int n;
    cin >> n;
   cout << (check(n) ? "yes" : "no") << endl;
    //cout << n/10;
    return 0;
}

Answer 1

#include <iostream>

using namespace std;

bool hasRepeatingDigit(int n, int mask)
{
    // base case: if we have checked all the digits and didn't find any duplicates, return false
    if (n == 0)
        return false;

    /*
        p is the place of the last digit in n (n%10).
        A digit can range from 0 to 9.
        The place of 0 will be 1 << 0 which is 1.
        The place of 1 will be 1 << 1 which is 2.
        The place of 2 will be 1 << 2 which is 4.
        ...
        ...
        The place of 9 will be 1 << 9 which is 512.
    */
    int p = 1 << (n % 10);

    // if place of p has already been marked then it's a duplicate
    if (mask&p)
        return true;

    // otherwise scrap the last digit (n/10), mark place p and recurse on the remaining digits
    return hasRepeatingDigit(n / 10, mask|p);
}

int main()
{
    int n;
    cin >> n;

    cout << hasRepeatingDigit(n, 0) << endl;
}

Answer 2

сначала код неверный ... если вы введете n = 11, он говорит «нет», но 1 повторяется дважды. вы можете исправить это, изменив оператор if с if(k < 10) на if(k == 0), вы можете перейти на уровень битов, но я не могу понять, насколько это полезно ... в заключение, это лучшее, что вы можете сделать без массивов ...

НО : если вам нужно найти, повторяется ли di git дважды или более в строке , другой ответ идеально подходит

Answer 3

У проблем рекурсии всегда есть базовый регистр и рекурсивный регистр .

Базовый случай прост: k <11 не имеет повторяющихся цифр. <br>Для рекурсивного случая k имеет повторяющиеся цифры, если либо:

• две нижние цифры k равны, либо
• k / 10 имеет повторяющиеся цифры.

Итак:

bool check(int k) {
  if (k < 11)
    return false;
  int digit = k % 10;
  int next = k / 10;
  int digit2 = next % 10;
  if (digit == digit2)
    return true;
  else
    return check(next);
  // Or in one expression:
  // return (digit == digit2) || check(next);
}