google 笔试题-动态规划求解数字出现问题

   给定一个数组A，里面只出现0-9这10个数字，但不一定全部出现，然后给定一个K的值，求A中大于K的整数当中最小的一个，并输出。例如A={0，1}， k =12,则结果为100.    请编程实现。

   假设A={2,4,5,7,8}

  

   这里先说下大前提,我先用动态规划是从高位到低位,结果可想而知!!!!没搞出来,这个应该是由低位到高位.

   eg:

     input: 589

   

   589--处理9--得到12

   592--处理9--得到12

   622--处理6--7

 

   大致思路就是digit一位大于最大的A[N]了就返回10+A[0]，没有大于最大的话,就返回第一个>=的

5就返回5,6就返回7...

  

 

#include <stdio.h>
#include <stdlib.h>

#define N 5

int len;

void print_array(int A[], int n)
{
  int i;
  for(i=0;i<n;i++)
   printf("%d\t", A[i]);
   
  printf("\n");
}

int find_first_big(int A[], int n, int digit)
{
  int i;
  int B[10];

  
  for(i=0;i<10;i++)
    B[i] = 0;
    
  for(i=0;i<n;i++)
    B[A[i]] = 1;
    
  for(i=0;i<10-digit;i++)
   {
     if(B[digit+i]==1)
      {
        return digit+i;
      }
   }
}

int count_digit(int A[], int n, int digit)
{
  if(digit>A[n-1])
    return (10 + A[0]);
  else
     return find_first_big(A, n, digit);
}

int* count_dp(int A[], int n, int num)
{
  int i = 0;
  int j = 0;
  int tmp = 0;
  int* p = (int*)malloc(sizeof(int)*10);

  for(i=0;i<10;i++)
    p[i] = 0;
  
  while(num!=0)
   {
     p[len++] = num%10;
     num/=10;
     printf("p[%d]is %d\n", len-1, p[len-1]);
   }
  
    
  for(i=len-1;i>=0;i--)
    {
     tmp = count_digit(A, n, p[i]);
     if(tmp>p[i])
      {
        p[i] = tmp;
        for(j=i-1;j>=0;j--)
          p[j] = A[0];
         
        break;
      }
    }
   
   for(i=0;i<len;i++)
    printf("p[%d] is %d\n", i, p[i]);
    
   i = len;
   while(--i)
    {
      if(p[i]>9)
         break;
    }
    for(j=i;j<len;j++)
     {
       if(p[j]>9)
        {
         p[j+1]++;
         p[j+1] = count_digit(A, n, p[j+1]);
         p[j] %= 10;
        }
     }
      
   return p;
}

int main(int argc, char *argv[])
{
  int i;
  int num;
  int* ret;
  int A[N] = {2,4,5,7,8};

  printf("the array is:\n");
  print_array(A, N);
  
  while(1)
   {
    printf("Please input the num you want to count:\n");
    scanf("%d", &num);
    ret = count_dp(A,N,num);
   
    printf("Your input is:%d\t", num);
    printf("We count:");
    for(i=len;i>=0; i--)
     {
      printf("%d",ret[i]);
     }
    printf("\n");
    free(ret);
    ret = NULL;
    len = 0;
   }
   
  system("PAUSE");    
  return 0;
}