C: Поиск ближайшего номера к первому без повторения цифр со второго номера?

Question

Я прочитал два номера, оба int.

Что мне нужно сделать, это сделать печать числа выше, но ближе к первому числу, например 378, но не содержать любого из цифр от второго числа, например, 78.

Вход: 378 78, выход: 390, потому что это самый низкий показатель выше 378, который не содержит какой-либо из цифр 78.

Входной сигнал: 3454 54, выход: 3600 потому, что 3600 является первым ближе всего, что не содержит 5 или 4, цифр 54.

Я пытаюсь сделать это, получив последние цифры модуля первого номера, начиная с длины второго. Например:

378 mod 100 == 78, а затем сравнить 78 и 78 цифры, и если есть такая же цифра шаг на 379, а затем проверить 379 mod 100 == 79. При сравнении 79 и 78, 7 такая же цифра.

И так далее, пока мы не получим 390 например. Это должно работать для всех номеров N-размера.

Вот что я сделал до сих пор ... и это почти ничего.

#include <stdio.h> 

int main() 
{ 
    int number1, number2; 
    int closest = number1 + 1; 
    scanf("%d %d",&number1,&number2); 

    int count_modulus = 1; 

    while(number2) 
    { 
     count_modulus = count_modulus * 10; 
     number2 = number2/10; 
    } 
    int mod = count_modulus; 
    int n2 = number2; 
    while(number1) 
    { 
     int remain = number1 % mod; 
     while(remain) 
     { 
      if((remain % 10 == number2 % 10)) 
      { 

      } 
      else 
      { 

      } 
     } 
    } 
    printf("%d",closest); 
    return 0; 
} 

Answer 1

Я не полностью убежден, что ваш метод по модулю будет работать так, если вы начинаете с 7823 и 78, то 7823 mod 100 дает 23, который не имеет не цифры общего с 78 несмотря на то, 7823...

Но, даже если я неправильно понял спецификацию, и это действительно сработало, я думаю, что есть лучший способ. Прежде всего, как оценка номер, основанный на том, какие цифры он содержит.

Если ваши целые числа имеют не менее десяти бит (и они будут, поскольку стандарт задает диапазон, который требует шестнадцати), вы можете просто использовать битовую маску с каждым битом, представляющим, содержит ли число цифру. Мы можем использовать обычный int для этого, так как десять бит нас не найдут около знака, который может вызвать у нас проблемы.

Код для озвучивания номера является:

// Return a bitmask with the bottom ten bits populated, 
// based on whether the input number has a given digit. 
// So, 64096 as input will give you the binary value 
//  000000 0000111010 
// <-unused^^^^
//(digits) 

int getMask (int val) { 
    int mask = 0;      // All start at 0 
    while (val > 0) {     // While more digits 
     mask = mask | (1 << (val % 10)); // Set bit of digit 
     val = val/10;     // Move to next digit 
    } 
    return mask; 
} 

«хитрые» немного есть утверждение:

mask = mask | (1 << (val % 10)); 

Что она делает это получить последнюю цифру номера, с val % 10 давая вам остаток при делении val на десять. Таким образом 123 % 10 дает 3, 314159 % 10 дает 9 и так далее.

Следующим шагом является сдвиг двоичного файла 1 на то, что много бит влево, с 1 << (val % 10). Смещение 1-битного четырех оставшихся мест даст вам двоичное значение 10000, так что это просто способ получить 1-бит в правильном положении.

Наконец, вы побитовое ИЛИ маска с вычисленным значением, эффективно устанавливая эквивалентную бит в маске, имея в виду, что биты a | b дает 1 если либо или обаa и b являются 1.

Или вы можете проверить один из моих других ответов here для более подробной информации.

Итак, я слышал, вы спрашиваете, как эта битовая маска помогает нам найти числа без обычных цифр. Ну, что там, где входит бит побитового оператора & - это только дает вам бит 1, если как входные биты: 1 (опять же, см. Ссылку, предоставленную ранее для более подробной информации о побитовых операторах).

После того как вы битовая маска для ваших двух номеров, вы можете использовать & с ними на следующий пример, где нет общих цифр:

Number Bitmask 

------ ---------------- 
314159 000000 1000111010 
    720 000000 0010000101 
     ----------------- AND(&) 
     000000 0000000000 

Вы можете видеть, что, если бит позиция имеет 1 для как номеров, результирующий бит будет 0. Если какая-либо цифра в общем на всех, это будет некоторое ненулевое значение:

Number Bitmask  v 

------ ----------------- 
314159 000000 1000111010 
    320 000000 0000001101 
     ----------------- AND(&) 
     000000 0000001000 
        ^
        The bit representing the common digit 3. 

И это приводит нас к реальному коду проверки, что-то относительно легко построить на вершине функции выигрыша:

#include <stdio.h> 

int main (int argc, char *argv[]) { 
    // Default input numbers to both zero, then try 
    // to get them from arguments. 

    int check = 0, exclude = 0, excludeMask; 
    if (argc > 1) 
     check = atoi(argv[1]); 
    if (argc > 2) 
     exclude = atoi(argv[2]); 

    // Get the mask for the exclusion number, only done once. 

    excludeMask = getMask (exclude); 

    // Then we loop, looking for a mask that has no 
    // common bits. 

    printf ("%d -> ", check); 
    //check++; 
    while ((excludeMask & getMask (check)) != 0) 
     check++; 
    printf ("%d\n", check); 

    return 0; 
} 

Поток в основном, чтобы получить числа из аргументов, выработайте битовую маску для номера исключения (тот, у которого есть цифры , не нужно), затем начните смотреть с номера чека , пока не найдете его.

Я закомментировал первоначальный check++, так как я не уверен, действительно ли вы хотели высшее числа, чем один данный, или должны ли 123 с исключением 98 дать вам реальное отправное количество 123. Если нет, просто раскомментируйте строку.

И там вы имеете его, как показано в следующем транскрипта, который включает в себя тестовые данные, среди прочего:

$ ./myprog 378 78 
378 -> 390 

$ ./myprog 3454 54 
3454 -> 3600 

$ ./myprog 123 98 # would give 124 if 'count++' uncommented 
123 -> 123 

$ ./myprog 314159 6413 
314159 -> 500000 

У него есть один потенциально фатальный недостаток, но тот, который достаточно легко исправить, если вы проверяете битмакс исключения, прежде чем начинаете искать. Я оставлю это в качестве упражнения для читателя, а просто думать о том, что может произойти с помощью следующей команды:

$ ./myprog 1 154862397 

И, конечно же, если вы хотите пойти на другой путь (нижние числа) , это вопрос , декременяющийcheck, а затем увеличивая его. Вам также может понадобиться, чтобы получить немного умнее, о том, что вы хотите, если вы идете отрицательный, например, с:

$ ./myprog 1 102 

Код, как это в настоящее время стоит не может справиться с этим так хорошо.