Google面试题 (转载)

[大花狗上树]

再次优化第一题，用递归算法求解。

代码：

/*******************************/
/*   Q:WWWDOT-GOOGLE=DOTCOM    */
/*   A:777589-188103=589486    */
/*     777589-188106=589483    */
/*******************************/
#include <stdio.h>

void getans(int num[], int n_tmp)    //通过递归调用对num_0_9数组进行组合排序
{
  int tmp;
  int w,d,o,t,g,l,e,c,m,wwwdot,google,dotcom;
  if(n_tmp == 1){
    w = num[0];
    d = num[1];
    o = num[2];
    t = num[3];
    g = num[4];
    l = num[5];
    e = num[6];
    c = num[7];
    m = num[8];
    wwwdot = w*111000 + d*100 + o*10 + t;
    google = g*100100 + o*11000 + l*10 + e;
    dotcom = d*100000 + o*10010 + t*1000 + c*100 + m;

    //其中的M和E的值可以互换，但不允许第一位是0。
    if(w!=0 && g!=0 && d!=0)    
        if((wwwdot-google==dotcom) || (wwwdot-(google-e+m) == (dotcom-m+e)))
            printf("%d - %d = %d\n",wwwdot,google,dotcom);
  }
  else{
    for(int i = 0; i < n_tmp; i++){
      tmp=num[i]; num[i]=num[n_tmp-1]; num[n_tmp-1]=tmp;
      getans(num, n_tmp-1);
      tmp=num[i]; num[i]=num[n_tmp-1]; num[n_tmp-1]=tmp;

    }
  }
}

void main()
{
  int n = 10;
  int num_0_9[]={0,1,2,3,4,5,6,7,8,9};

  getans(num_0_9, n);

}

[ Last edited by 大花狗上树 on 2005-11-22 at 00:16 ]