Определение минимального числа в целых числах

Question

С учетом n-значного числа и числа 'k'. Вам нужно удалить цифры «k» из числа и указать кратчайшее число из оставшихся цифр «n-k», чтобы последовательность цифр оставалась одинаковой. Например, если число равно 637824 и k = 3. Поэтому вам нужно удалить 3 цифры из данного номера. Число, сформированное из оставшихся цифр, должно быть минимальным, а последовательность цифр не должна изменяться. Таким образом, выходной сигнал должен быть 324.

подход, который я использовал такой же, как включение исключения логики:

Input 63119 и К = 2:

Выберите 9 + минимум (6311) = 19 или дон 't выберите 9, выберите 1 + минимум (631) = 11 и , наконец, возьмите минимум.

Для входа 4567813 и к = 3:

Выберите 3 и 1 вместе с минимумом (45678) = 413

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

#define min(a, b) ((a)>(b)?(b):(a)); 

    int minimum(char *s, int i, int j) 
    { 
      if (i == j) 
        return s[i] - '0'; 
      return min(s[j]-'0', minimum(s, i, j-1)); 
    } 

    int add_up(char *s, int i, int j) 
    { 
      int sum = 0, mul = 1; 
      while(i < j) { 
        sum = sum + (s[j] - '0')*mul; 
        j--;mul *= 10; 
      } 
      return sum; 
    } 

    int foo(char *s, int size, int j, int k) 
    { 
      int sum = 0, i, mul = 1; 
      if (k < 0 || j > size || j < 0) 
        return 0; 
      if ((k == 0) && (j != 0)) 
        return add_up(s, 0, j); 
      if ((k == 1) && (j != 0)) 
        return minimum(s, 0, j); 
      if (k-1 == j) 
        return add_up(s, 0, j); 
      for (i=k;i>=0;i--) { 
        sum += min((s[j]-'0')+10*foo(s, size, j-1, k-1), foo(s, size, j-1, k)); 
      } 
      return sum; 
    } 

    int main() 
    { 
      char s[] = {"4567813"}; 
      printf("%d\n", foo(s, strlen(s)-1, strlen(s)-1, 2)); 
      return 0; 
    } 

Answer 1

Вы сказали наконец принять минимум всех, но вы взяли минимум все, а затем добавляют их. Вы должны взять минимум за каждые i и сохранить минимум за все i в sum. См. Код для разъяснения. Также есть ошибка в вашей функции add_up, она должна добавляться до i<=j.

int add_up(char *s, int i, int j) 
{ 
    int sum=0, mul=1; 
    while(i <= j) { // modification here 
     sum=sum + (s[j] - '0')*mul; 
     j--; mul*=10; 
    } 
    return sum; 
} 

int foo(char *s, int size, int j, int k) 
{ 
    int sum=INT_MAX, i, mul=1; 
    if(k < 0 || j > size || j < 0) 
     return 0; 
    if((k == 0) && (j != 0)) 
     return add_up(s, 0, j); 
    if((k == 1) && (j != 0)) 
     return minimum(s, 0, j); 
    if(k-1 == j) 
     return add_up(s, 0, j); 
    for(i=k; i>=0; i--) { 
     int res=min((s[j]-'0')+10*foo(s, size, j-1, k-1), foo(s, size, j-1, k)); 
     sum=min(sum,res); // minimum over all possible i 
    } 
    return sum; 
}