一道某知名公司的面试题

Question

有 1,2,5三个数字 每个数字可以有任意多问题:
求用这三个数字加法组合成10的方案 如 5+5 2+2+2+2+2给分原则: 程序效率最优的给的最多,其次是能回答上来的抛砖引玉给个不完整的答案版本(没有去重版)var nArr=[1,2,5];
var results=[];
function calc(num, arr)
{
    if(num==0)
    {
results[results.length]=arr.join(",");
return;
    }
    if(num<0)
    {
return;
    }
    for(var i=0;i<nArr.length;i++)
    {
arr.push(nArr[i]);
calc(num-nArr[i], arr);
arr.pop();
    }
}
calc(10,[]);
for(var i=0; i<results.length; i++)
{
alert(results[i]);
}

Answer 1

function calc()
{
    for(var i=0;i<=10;i++)
    {
 for(var j=0;j<=5;j++)
{
 for(var k=0;k<=2;k++)
{
if((i+2*j+5*k)==10)
{
alert(i+" , "+j+" , "+k);
}
}
}
    }
}
calc();

Answer 2

var nArr=[1,2,5];
var results=[];
function calc(num)
{
    for(var i=0;i<=parseInt(num/nArr[0]);i++)
    {
 for(var j=0;j<=parseInt(num/nArr[1]);j++)
{
 for(var k=0;k<=parseInt(num/nArr[2]);k++)
{
if((nArr[0]*i+nArr[1]*j+nArr[2]*k)==10)
{
results[results.length] = show(i,nArr[0])+show(j,nArr[1])+show(k,nArr[2]);
}
}
}
    }
}
calc(10);
function show(total,nArrValue){
var temStr = "";
for(var i=0;i<total;i++){
temStr = temStr + nArrValue+",";
}
return temStr;
}
for(var i=0; i<results.length; i++)
{
    alert(results[i]);
}

Answer 3

var nArr=[5,2,1];
var results=[];
function calc(num, arr)
{
    if(num==0)
    {
    results[results.length]=arr.join(",");
    return;
    }
    if(num<0)
    {
    return;
    }
    for(var i=0;i<nArr.length;i++)
    {
if(nArr[i] > arr[arr.length-1])continue;
        arr.push(nArr[i]);
        calc(num-nArr[i], arr);
        arr.pop();
    }
}
calc(10,[]);
for(var i=0; i<results.length; i++)
{
    alert(results[i]);
}

Answer 4

哈哈，两分钟想出，10分钟写出，行不行？$("#btntest").click(function() {
var strOut="";
for(var i=0;i<=10;i++)
{
for(var j=0;j<=5;j++)
{
for(var k=0;k<5;k++)
{
if(i+(2*j)+(5*k) == 10)
{
strOut+="(1*"+i.toString()+")+(2*"+j.toString()+")+(5*"+k.toString()+") == 10;\n";
}
}
}
}
alert(strOut);
});
结果是：

(1*0)+(2*0)+(5*2) == 10;
(1*0)+(2*5)+(5*0) == 10;
(1*1)+(2*2)+(5*1) == 10;
(1*2)+(2*4)+(5*0) == 10;
(1*3)+(2*1)+(5*1) == 10;
(1*4)+(2*3)+(5*0) == 10;
(1*5)+(2*0)+(5*1) == 10;
(1*6)+(2*2)+(5*0) == 10;
(1*8)+(2*1)+(5*0) == 10;
(1*10)+(2*0)+(5*0) == 10;？？行不行？

Answer 5

看不明，我解下；
i 表是 1 出现的个数；
j 表是 2 出现的个数；
K 表是 5出现的个数；

Answer 6

 for(var k=0;k<5;k++)
这个要改为
 for(var k=0;k<=5;k++)

Answer 7

修改一下26楼的代码var rs=[];
for(var i=0;i<=2;i++) // 5出现的次数
    {
        for(var j=0;j<=(10-5*i)/2;j++) // 2 出现的次数
        {
            for(var k=0;k<=(10-5*i - 2*j);k++)  // 1 出现的次数
            {
                if(k+(2*j)+(5*i) == 10)
                {
                    rs.push("(1*"+k+")+(2*"+j+")+(5*"+i+") == 10\n");
                }
            }
        }
    }
    alert(rs);

Answer 8

#30 楼：hch126163 (老胡)
高，效率高，去重复，可以说是（简单中的）最好的选择了！

Answer 9

另一种思路，java所写。10=5+5，5=2+2+1，2=1+1
public class Test {
public static int[] a={5,5};
public static int[] b={2,2,1};
public static int[] c={1,1};
public static void main(String[] args){
cal();
}
public static void cal(){
List<Integer> list=new ArrayList<Integer>();
list.add(a[0]);list.add(a[1]);
int i=0;
System.out.println(list);
while(i<list.size()){
if(list.get(i)!=1){
int tmp=list.get(i);
list.remove(i);
if(tmp==5){
list.add(i,b[0]);
list.add(i+1,b[1]);
list.add(i+2,b[2]);
}else if(tmp==2){
list.add(i,c[0]);
list.add(i+1,c[1]);
}
i--;
System.out.println(list);
}
i++;
}
}
}

Answer 10

动态规划 java用的不熟……public class test {    /**
     * 
     * @param args
     */
    public static void main(String[] args) {
        int[] num = { 1, 2, 5 };
        List<String>[] list = new ArrayList[11];
        int count[] = new int[11];
        for (int i = 0; i < 11; i++) {
            count[i] = 0;
        }
        for (int i = 0; i < 11; i++) {
            list[i] = new ArrayList<String>();
        }
        count[0] = 1;
        list[0].add("");
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 11; j++) {
                if (count[j] != 0 && j + num[i] < 11) {
                    count[j + num[i]] = count[j] + 1;
                    for (String str : list[j]) {
                        if (j == 0) {
                            list[j + num[i]].add((Integer.toString(num[i])));
                        } else {
                            list[j + num[i]].add(str + "+" + num[i]);
                        }
                    }
                }
            }
        }
        for (String ans : list[10]) {
            System.out.println(ans);
        }
    }}

Answer 11

  rs.push("(1*"+k+")+(2*"+j+")+(5*"+i+") == 10\n");
这个能解释下为什么不用  rs.push("(1*k)+(2*j)+(5*i) == 10\n");吗？初学者还望大侠多多指教！

Answer 12

for(int i=0;i<=10;i++){
   for(int j=0;j<=5;j++){
      for(int k=0;k<=2;k++){
if((1*i+2*j+5*k)==10){
   System.out.print("1*"+i);
   System.out.print("+2*"+j);
   System.out.println("+5*"+k);
}
      }
    }
}
我觉得这样挺好的，简单易懂。

Answer 13

<!DOCTYPE html>
<html>
<head>
</head>
<body>
<script>
function combination(resultNum, numArr){
var result = [];
(function(_sum, _len, assembly){
for(var i = _len; i >= 0; i--){
var _assembly = assembly.concat([]),
lastNum = numArr[i];
if(_sum +  lastNum < resultNum){
_assembly.push(lastNum);
arguments.callee(_sum + lastNum, i, _assembly);
}else if(_sum +  lastNum === resultNum){
_assembly.push(lastNum);
result.push(_assembly);
}
}
})(0, numArr.length - 1, []);
return result;
}
var nArr = [1, 2, 5];
var result = combination(10, nArr);
for(var i in result){
//console.log(i+": "+result[i]);
document.write(i+": "+result[i]+"<br/>");
}
</script>
</body>
</html>

Answer 14

中间偷懒了function doing(){
var k=[1,2,5];
var s=[];
var sum=0,i=0;
while(1){
if(i<k.length){
if(sum+k[i]<10){
s.push(k[i]);
sum=sum+k[i];
}
if(sum+k[i]>=10){
if(sum+k[i]==10)
document.write(s.join("+")+"+"+k[i]+"</br>");
i++;
}
}
else{
i=s.pop();
sum=sum-i;
if(i==5)
i=3;
}
if(s.length==0&&i==3)
return 0;
}
}

Answer 15

理论是这一类问题都可以解决，不过如果数据量大的话，效率不高，这时候要采用别的解决方案。 function combination(resultNum, numArr){
var result = [];
(function(_sum, len, assembly){
for(var i = len; i >= 0; i--){
var _assembly = assembly.concat([]),
lastNum = numArr[i];
if(_sum +  lastNum < resultNum){
_assembly.push(lastNum);
arguments.callee(_sum + lastNum, i, _assembly);
}else if(_sum +  lastNum === resultNum){
_assembly.push(lastNum);
result.push(_assembly);
}
}
})(0, numArr.length - 1, []);
return result;
}

document.write("<h3>1,2,5:</h3><br/>");
var arr1 = [1, 2, 5];
var result1 = combination(10, arr1);
for(var i in result1){
document.write(i+": "+result1[i]+"<br/>");
}

document.write("<h3>1,2,3,5:</h3><br/>");
var arr2 = [1, 2, 3, 5];
var result2 = combination(10, arr2);
for(var i in result2){
document.write(i+": "+result2[i]+"<br/>");
}

Answer 16

count = 0;
for (i5 = 2; i5 >= 0; i5--) {
    i2 = (10 - i5 * 5) / 2;
    while (i2 >= 0) {
        ++count;
    }
}

Answer 17

我的方法一点都不好，还是遍历的一边,求更高效
顺便恶搞一下，据说是效率最高的(function(){
strs=["1+1+1+1+1+1+1+1+1+1"
,"1+1+1+1+1+1+1+1+2"
,"1+1+1+1+1+1+2+2"
,"1+1+1+1+1+5"
,"1+1+1+1+2+2+2"
,"1+1+1+2+5"
,"1+1+2+2+2+2"
,"1+2+2+5"
,"2+2+2+2+2"
,"5+5"]
for(var i=0;i<10;i++)
document.write(strs[i]+"<br/>");
})();

Answer 18

// pData从大到小排序
bool Calc(int iSum, int *pData, int iDataCnt, const CString &StrPre)
{
ASSERT( iSum > 0 );
ASSERT( pData );
ASSERT( iDataCnt > 0 );
if ( iSum == 0 )
{
return true; // 已经计算完毕了
}
if ( iDataCnt == 0 )
{
return false; // 无法成立的和
}
for ( int i=0; i < iDataCnt ; ++i )
{
int iSub = iSum - pData[i];
ASSERT( pData[i] != 0 );
if ( pData[i] == 0 )
{
continue;
}
if ( iSub < 0 )
{
// 不能取这个值
}
else if ( iSub == 0 )
{
// 满足条件了
CString StrPre2;
if ( StrPre.IsEmpty() )
{
StrPre2.Format(_T("%d"), pData[i]);
}
else
{
StrPre2.Format(_T("%s+%d"), StrPre, pData[i]);
}
TRACE(_T("Probably: %s\n"), StrPre2);
}
else
{
// 需要继续计算
CString StrPre2;
if ( StrPre.IsEmpty() )
{
StrPre2.Format(_T("%d"), pData[i]);
}
else
{
StrPre2.Format(_T("%s+%d"), StrPre, pData[i]);
}
Calc(iSub, pData+i, iDataCnt-i, StrPre2);
}
}
return false;
}

Answer 19

不知道这个简不简单
    int sum=0;
    int i=0,j=0,z=0;
for(i=0;i<=2;i++)
{
sum = 0;
sum += 5*i;
for(j=0;j<= 5;j++)
{
sum += 2*j;
z = 10 -sum;
if(z >=0)
printf("5:%d  2:%d  1:%d\n",i,j,z);
}
}

Answer 20

有一点小问题 
应该在if（z>=0）里面加上 
if(z >=0)
{
   printf("5:%d 2:%d 1:%d\n",i,j,z);
   sum=sum-2*j;
}
如果不加sum=sum-2*j;
则对某一个固定的i，j产生的sum值会带到j+1中

Answer 21

#include <stdio.h>
main()
{
    for(int i = 0;i <= 2;i++)
    {
        for(int j = 0;j <= 5;j++)
        {
             for(int k = 0;k <= 10;k++)
             {
                 if((5*i+2*j+k) == 10)
                 {
                      for(int l = 0;l < i;l++)
                      printf("5");
                      for(int m = 0;m < j;m++)
                      printf("2");
                      for(int n = 0;n < k;n++)
                      printf("1");
                      printf("\n");
                      continue;    
                 }
             }    
        }
    }
}

Answer 22

 static void Main(string[] args)
        {
            Stack s = new Stack();
            for (int i = 0; i <= 2; i++)//5
            {
                for (int j = 0; j <= (10 - 5 * i) / 2;j++ )
                {
                    for(int k=0;k<=(10-5*i)-(2*j);k++)
                    {
                        if (i * 5 + j * 2 + k == 10)
                        {
                            s.Push("1*"+k+"+2*"+j+"+5*"+i+"=10"); 
                        }
                    }
                }
            }
            foreach (string result in s)
            {
                Console.WriteLine(result);
            }
            Console.ReadKey();         
        }
效率什么的没深究，见谅

Answer 23

var strs=new Array();
for(i=0;i<=10;i++){
   for(var j=0;j<=Math.ceil((10-i)/2);j++){         
  if((10-i-j*2)%5==0){
       str=i+"个1,"+j+"个2,"+((10-i-j*2)/5)+"个5";
       strs.push(str);
       //alert(str);
  }
   }
}

Answer 24

好贴留个名！
3个for循环嵌套是最容易想出来的方法，但是效率不高；
递归代码简单，思路清晰，效率也不高；
期待中

Answer 25

先上一个，后面在优化     function MM() {
         var sArr = [1, 2, 5];
         var scount = "";
 
         var s1 = 10;
         var s2 = 10 / 2;
         var s5 = 10 / 5;
         //1和2的组合
         for (var i = 0; i <= s2; i++) {
             var s = 10 - i * 2;
             for (var k = 1; k <= s; k++) {
                 scount += 1 + "+";
             }
             for (var t = 1; t <= i; t++) {
                 scount += "2+";
             }
             scount = scount.substr(0, scount.length - 1);
             scount += "=10<br/>";
         }
         //1和5的组合
         for (var i = 1; i <= s5; i++) {
             var s = 10 - i * 5;
             for (var k = 1; k <= s; k++) {
                 scount += 1 + "+";
             }
             for (var t = 1; t <= i; t++) {
                 scount += "5+";
             }
             scount = scount.substr(0, scount.length - 1);
             scount += "=10<br/>";
         }
         //1,5,2的组合
         var p = 10 - 5 - 2;
         for (var n = 1; n <= p; n++) {
             scount += 1 + "+";
         }
         scount += "5+2=10<br/>";         for (var n = 1; n <= p-2; n++) {
             scount += 1 + "+";
         }
         scount += "2+5+2=10<br/>";         es.innerHTML = scount;
     }
     window.onload = MM;1+1+1+1+1+1+1+1+1+1=10
1+1+1+1+1+1+1+1+2=10
1+1+1+1+1+1+2+2=10
1+1+1+1+2+2+2=10
1+1+2+2+2+2=10
2+2+2+2+2=10
1+1+1+1+1+5=10
5+5=10
1+1+1+5+2=10
1+2+5+2=10