求一道面试题答案

哈哈，最简单的就是写十次循环，累加在一起，输入 sum=90的，
好像还有用递归实现的，google一下，很多的

int nums = 0; //nums为计数器，初始化为0；
void GetPlbNums(int n, int m)  //n = 10*10 - 90 = 10 , m = 现在打第几枪 = 1初始化为1
{
if(m>11)
return;
if(m<11 && n == 0)
    nums++;
else
{
    for(int i = 0 ; i<=n; i++)
    GetPlbNums(n-i, m+1);
}
}

变量范围：0<=A1，A2，A3...A10<=10
方程式：A1+A2+A3+...+A10=90解这个多元方程，有多少组解，就是多少种情况

表面上看是10层for循环，在最内层判断方程等于90是否成立，成立了就计数器加一，最后计数器的值就是所有的情况数。要下班了，不想别的方法了

刚凭印象写了一下，自己看看，有不对的在改改。但是思路应当就是这个思路了public class ShootTest {
public static void shoot(int score,int num,int s[]){
if(score<0 || score>(num+1)*10){
return;
}
if(num == 0){
s[num]=score;
System.out.println("This method is avaliable:");
int total = 0;
for(int i =0;i<10;i++){
System.out.print(s[i] + ",");
total += s[i];
}
System.out.print("total score is" + total);
return;
}
for(int i = 0;i <= 10 ;i++){
s[num] = i;
shoot(score-i,num-1,s);
}
}
public static void main(String args[]){
ShootTest t = new ShootTest();
int s[] = new int[10];
t.shoot(90, 9, s);
}
}

搞了两天
终于出了结果
                92378#include <iostream>
using namespace std;
int main()
{
    int i0,i1,i2,i3,i4,m,n=0,q=0,p=0,k=0,sum,sum8,sum7,sum6,sum5,sum4,sum3,sum2,sum1,yi,er,san,si,wu;

    /*八个10*/
    { for(i0=0;i0<=10;i0++)
      for(i1=0;i1<=10;i1++)

    {m=i0+i1;
     if(m==10)

     {if(i0!=10&&i1!=10)
     {cout<<i0<<"  "<<i1<<endl;
       n++;
     if(i0==i1)
     p++;
     }
     }
    }
    k=(n-p)/2;
    sum8=k*10*9+p*(9+8+7+6+5+4+3+2+1);
    cout<<"  n="<<n<<"    p="<<p<<"     k="<<k<<"    sum8="<<sum8<<endl;
    n=0;p=0;k=0;
    }
    /*七个10*/
    {
     for(i0=0;i0<=10;i0++)
      for(i1=0;i1<=10;i1++)
       for(i2=0;i2<=10;i2++)

    {m=i0+i1+i2;
     if(m==20)
     {



        if(i0!=10&&i1!=10&&i2!=10)
       { cout<<i0<<"  "<<i1<<"  "<<i2<<endl;
        n++;
        if(i0==i1||i0==i2||i1==i2)
          p++;
        }
     }
    }
    k=(n-p)/6;
    sum7=k*10*9*8+(p/3)*10*(8+7+6+5+4+3+2+1);
    cout<<"       n= "<<n<<"   p="<<p<<"    k="<<k<<"   sum7="<<sum7<<endl;
     n=0;p=0;k=0;
    }
    /*六个10*/
    {
     for(i0=0;i0<=10;i0++)
      for(i1=0;i1<=10;i1++)
       for(i2=0;i2<=10;i2++)
        for(i3=0;i3<=10;i3++)

    {m=i0+i1+i2+i3;
     if(m==30)
     {if(i0!=10&&i1!=10&&i2!=10&&i3!=10)
     {
       n++;
        if(i0==i1||i0==i2||i1==i2||i0==i3||i1==i3||i2==i3)
          {p++;

          cout<<i0<<"  "<<i1<<"  "<<i2<<"  "<<i3<<endl;
          }
       }
     }
    }
    k=(n-p)/24;
    san=3*10*((7+6+5+4+3+2+1)+(6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1);
    er=3*10*9*
(7+6+5+4+3+2+1)+2*(9+8+7+6+5+4+3+2+1)*
(7+6+5+4+3+2+1);
    sum6=k*10*9*8*7+san+er;
    cout<<"       n= "<<n<<"   p="<<p<<"    k="<<k<<"   sum6="<<sum6<<endl;
     n=0;p=0;k=0;
    }
   /*五个10*/
   {
     for(i0=0;i0<=10;i0++)
      for(i1=0;i1<=10;i1++)
       for(i2=0;i2<=10;i2++)
        for(i3=0;i3<=10;i3++)
         for(i4=0;i4<=10;i4++)

    {m=i0+i1+i2+i3+i4;
     if(m==40)
     {

       if(i0!=10&&i1!=10&&i2!=10&&i3!=10&&i4!=10)
     {   n++;
     cout<<i0<<"  "<<i1<<"  "<<i2<<"  "<<i3<<"  "<<i4<<endl;
       if(i0==i1||i0==i2||i1==i2||i0==i3||i1==i3||i2==i3)
          {p++;
           }

     }
     }
    }
    k=(n-p)/120;
    er=2*10*((8+7+6+5+4+3+2+1)*(6+5+4+3+2+1));
    san=3*10*9*((6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1);
    si=10*(((6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
    ((5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
((4+3+2+1)+(3+2+1)+(2+1)+1)+
((3+2+1)+(2+1)+1)+
((2+1)+1)+1);
    wu=
(((6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
((5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
((4+3+2+1)+(3+2+1)+(2+1)+1)+
((3+2+1)+(2+1)+1)+
((2+1)+1)+1)+
(((5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
((4+3+2+1)+(3+2+1)+(2+1)+1)+
((3+2+1)+(2+1)+1)+
((2+1)+1)+1)+
(((4+3+2+1)+(3+2+1)+(2+1)+1)+
((3+2+1)+(2+1)+1)+
((2+1)+1)+1)+
(((3+2+1)+(2+1)+1)+
((2+1)+1)+1)+
(((2+1)+1)+1)+
1;
    sum5=k*10*9*8*7*6+er+san+si+wu;
    cout<<"       n= "<<n<<"   p="<<p<<"    k="<<k<<"   sum5="<<sum5<<endl;
    n=0;p=0;k=0;
   }

    /*四个10,,必有二个9*/
    {
     for(i0=0;i0<=10;i0++)
      for(i1=0;i1<=10;i1++)
       for(i2=0;i2<=10;i2++)
        for(i3=0;i3<=10;i3++)

    {m=i0+i1+i2+i3;
     if(m==32)
     {if(i0!=10&&i1!=10&&i2!=10&&i3!=10)
     {
       n++;

          cout<<i0<<"  "<<i1<<"  "<<i2<<"  "<<i3<<endl;

       }
     }
    }
    si=(9+8+7+6+5+4+3+2+1)*
     (((5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
((4+3+2+1)+(3+2+1)+(2+1)+1)+
((3+2+1)+(2+1)+1)+
((2+1)+1)+1);
    san=10*(((6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
    ((5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
((4+3+2+1)+(3+2+1)+(2+1)+1)+
((3+2+1)+(2+1)+1)+
((2+1)+1)+1);
    er=10*
(8+7+6+5+4+3+2+1)*((5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
((9+8+7+6+5+4+3+2+1)+10*9)*
     (((5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)+
((4+3+2+1)+(3+2+1)+(2+1)+1)+
((3+2+1)+(2+1)+1)+
((2+1)+1)+1);
    sum4=si+san+er;
    cout<<"       n= "<<n<<"   p="<<p<<"   sum4="<<sum4<<endl;
     n=0;p=0;k=0;
    }
    /*三个10,,必有四个9*/
    {
      for(i0=0;i0<=10;i0++)
      for(i1=0;i1<=10;i1++)
       for(i2=0;i2<=10;i2++)

    {m=i0+i1+i2;
     if(m==(24))
     {



        if(i0!=10&&i1!=10&&i2!=10)
       { cout<<i0<<"  "<<i1<<"  "<<i2<<endl;
        n++;
        if(i0==i1||i0==i2||i1==i2)
          p++;
        }
     }
    }
    san=((8+7+6+5+4+3+2+1)+(7+6+5+4+3+2+1)+(6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1)*
    ((5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1);

    er=10*((7+6+5+4+3+2+1)+(6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1);
    yi=10*9*((6+5+4+3+2+1)+(5+4+3+2+1)+(4+3+2+1)+(3+2+1)+(2+1)+1);
    sum3=san+er+yi;
    cout<<"       n= "<<n<<"   p="<<p<<"    k="<<k<<"   sum3="<<sum3<<endl;
    n=0;p=0;k=0;
    }

    /*二个10,必有六个9*/
    {
     for(i0=0;i0<=10;i0++)
      for(i1=0;i1<=10;i1++)

    {m=i0+i1;
     if(m==16)

     {if(i0!=10&&i1!=10)
     {cout<<i0<<"  "<<i1<<endl;
       n++;}


     }
    }
    er=(9+8+7+6+5+4+3+2+1)*(7+6+5+4+3+2+1);
    yi=10*(8+7+6+5+4+3+2+1);
    sum2=er+yi;
    cout<<"  n="<<n<<"    p="<<p<<"     k="<<k<<"    sum2="<<sum2<<endl;

    }
    /*一个10,八个9,一个8*/
    {sum1=10*9;
    cout<<"  sum1="<<sum1<<endl;
    }

    /*SUM中:"1"代表十个9时,"10"代表九个10时*/
    sum=1+10+sum1+sum2+sum3+sum4+sum5+sum6+sum7+sum8;
    cout<<"    sum="<<sum;
       return 0;
}

的确是 92378 种，
next 函数主要是产生10个数有多少种不同的加法计算，
因为加法满足交换律，比如 1+2 + .. = 2+1 +...
所以，产生了 1,2 这些，就不产生 2,1... 这些，
规律就是后面的数要大于等于前面的数， n 函数计算那10个数可以排列成多少个不同的数，因为
有重复，所以，需要用 10! / 那些有重复的这道题的确有些难度阿，如果面试，估计当时真还算不出。public class Shoot90 { static final int MAX=10;

/**
* 0 <= numbers[i] <=10
* @param numbers
*/
public boolean next(int[] numbers) {
int idx=-1;
for(int i=numbers.length-1;i>=0;i--) {
if (numbers[i]<MAX) {
idx=i;
break;
}
}
if (idx!=-1) {
numbers[idx] = numbers[idx]+1;

for(int i=idx+1;i<numbers.length;i++) {
numbers[i]=numbers[idx];
}
return true;
}
return false;
}

/**
* return n!
* @param n
* @return
*/
static long factorial(int n) {
long ret=1;
for(int i=2;i<=n;i++) {
ret = ret * i;
}
return ret;
}

private int[] dup = new int[11];
public long n(int[] numbers) {
for(int i=0;i<dup.length;i++) {
dup[i] = 0;
}
for(int i=0;i<numbers.length;i++) {
dup[numbers[i]] ++;
}

long ret = 10*9*8*7*6*5*4*3*2; // 10!
for(int i=0;i<dup.length;i++) {
if (dup[i]!=0) {
ret = ret / factorial(dup[i]);
}
}
return ret;
}

public static void main(String[] args) {
Shoot90 s90 = new Shoot90();
int[] shoot = new int[]{0,0,0,0,0,0,0,0,0,0};
long cnt = 0;
int sum;
while(s90.next(shoot)) {
sum = 0;
for(int i=0;i<shoot.length;i++) {
sum = sum + shoot[i];
}
if (sum==98) {
for(int i=0;i<shoot.length;i++) {
System.out.print(shoot[i] + ",");
}
System.out.println();

cnt = cnt + s90.n(shoot);
}
}
System.out.println("cnt: " + cnt);
}}

考虑下题目本身的算法。变量范围：0<=A1，A2，A3...A10<=10
方程式：A1+A2+A3+...+A10=90==》（10-A1) + (10-A2) + .. +(10 -A3) = 10;
let : B1 = 10-A1; B2 = 10-A2 ... ==> 0 <= B(i) <= 10
==> 原题变为求解： B1+B2+...+B10 = 10;
==》可用插板法：往10个1 中间×（两头也可插入）插入9块板，则9快板分割出的10个数字就是一组解。
==》共有11个空隙，多个板可重复插入一个空隙。
==》分类讨论：没有0时。 == 只有一种可能性
==》继续：至少有一个0，
==》注意：一个空隙中的两个板意味着有一个数为0
==》可再考虑递归， B1 + B2 + .. + B9 = 10;...抛砖引玉

调试易

求一道面试题答案

解决方案 »