Что является самым быстрым способом проверки повторяющихся цифр номера?

Question

Предположим, я хочу проверить, имеет ли число n = 123 дубликаты цифр. Я пробовал:

#include <iostream> 

using namespace std; 

int main() { 
    int n = 123; 
    int d1 = n % 10; 
    int d2 = (n/10) % 10; 
    int d3 = (n/100) % 10; 
    if(d1 != d2 && d1 != d3 && d2 != d3) { 
     cout << n << " does not have duplicate digits.\n"; 
    } 
} 

Есть ли более быстрое решение этой проблемы?

Обновление
Извините, что не понимаете. Код выше был написан на C++ только для описания цели. Я должен решить эту проблему в TI-89 с числом 9 цифр. И поскольку ограничение памяти и скорости, я ищу быстрый способ.

TI-89 имеет только несколько ключевых слов условие:

• Если
• Если ...
• когда (
• Для ... ENDFOR
• Хотя ... EndWhile
• Loop ... EndLoop
• Custom ... EndCustom

Спасибо,
Чан

Answer 1

Быстрее, возможно, нет (но вы должны измерить в любом случае, на всякий случай - моя оптимизация мантра "measure, don't guess"). Но яснее в намерениях, я думаю, да, и способен обрабатывать целые числа произвольного размера.

int hasDupes (unsigned int n) { 
    // Flag to indicate digit has been used. 

    int i, used[10]; 

    // Must have dupes if more than ten digits. 

    if (n > 9999999999) 
     return 1; 

    // Initialise dupe flags to false. 

    for (i = 0; i < 10; i++) 
     used[i] = 0; 

    // Process all digits in number. 

    while (n != 0) { 
     // Already used? Return true. 

     if (used[n%10]) // you can cache n%10 if compiler not too smart. 
      return 1; 

     // Otherwise, mark used, go to next digit. 

     used[n%10] = 1; // and you would use cached value here. 
     n /= 10; 
    } 

    // No dupes, return false. 

    return 0; 
} 

---

Если у вас есть ограниченный набор возможностей, вы можете использовать освященное время подхода жертвуя пространства для времени.

Допустим, вы говорите чисел от 0 до 999:

const int *hasDupes = { 
// 0 1 2 3 4 5 6 7 8 9 
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // x 
    0, 1, 0, 0, 0, 0, 0, 0, 0, 0, // 1x 
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, // 2x 
    : 
    0, 0, 0, 0, 0, 0, 0, 1, 0, 1, // 97x 
    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, // 98x 
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 99x 
}; 

и просто сделать поиск в таблице в hasDupes[n].

---

На основании вашего редактирования, когда вам нужно обрабатывать девять цифр, миллиардов элементов массива а (второе решение выше), вероятно, не будет возможно на калькуляторе :-)

Я выбрал бы первое решение.

Answer 2

template<class T, int radix = 10> 
bool has_duplicate_digits(T n) { 
    int digits_mask = 0; 
    while (digits_mask |= (1 << (n % radix)), n /= radix) 
     if (digits_mask & (1 << (n % radix))) 
      return true; 
    return false; 
} 

Нечто подобное должно работать до тех пор, как n неотрицательна и int имеет по крайней мере radix бит.

---

digits_mask является BitSet (бит 0 представляет собой вхождение цифры 0, бит 1 представляет возникновение 1 цифры и т.д.).

Растровое изображение заполнено наименее значащей цифрой n, а остальная часть цифр сдвигается вниз.Если есть больше цифр, а новая наименее значащая цифра отмечена как имевшаяся ранее, верните true, в противном случае повторите.

Если цифр больше нет, верните значение false.

1 << x возвращает 1, 2, 4, 8 и т. Д .: маски, используемые для тестирования/установки бит в битете.

a |= z это сокращение для a = a | z, который устанавливает биты объединением a от z.

a & z является пересечением битов в a и z, и равна нулю (ложь), если ни один не установлены и не равен нулю (истина), если таковые установлены.

Answer 3

я сделал ускоренный курс TI-89 Basic ответить :)

Давайте посмотрим, если это работает (я не эмулятор, поэтому не может проверить).

Test() 
Prgm 
{0,0,0,0,0,0,0,0,0,0}->A 
Title "Request" 
Request "Enter a number",B 
EndDlog 
Expr(B)->B 
While B > 1 
MOD(10,B)->C 
if A[C+1] = 1 goto K 
1->A[C+1] 
B-C->B 
EndWhile 
Title "Done" 
Text "Numbers non repeating" 
Enddlog 
goto J 

Lbl K 
Title "Done" 
Text "Numbers repeating" 
Enddlog 

Lbl J 
EndPrgm