国内某一著名IT公司面试题,集思广益！！！

Question

正整数10000能够被看作是若干个正整数相加之和，比如10000=1+9999，10000=3+67+25+9905，...，10000=6+52+41+69+30+21+98+2535+7148。某一个等式被看作是一种“结果”，问题：利用递归法求出能得出10000的所有“结果”的总个数。（说实在的这道题我不会，看看有没有高手能拿下此题。）

Answer 1

f（1）＝1；
f(2)=f(1)+1;
f(3)=f(2)+1;
.....
f(10000)=f(9999)+1
用递归就可以啦

Answer 2

f(1)=1;
f(2)=f(1)*1
f(3)=f(1)*f(2);
f(4)=f(1)*f(3)+f(2)*f(2);
f(5)=f(1)*f(4)+f(2)*f(3);
...
f(n)=f(1)*f(n-1)+....f(k)*f(k+1);//n=2k+1
f(n)=f(1)*f(n-1)+....f(k)*f(k);//n＝2k

Answer 3

classjava(原始野人)    
  f(1)=1;
f(2)=f(1)*1
f(3)=f(1)*f(2);
f(4)=f(1)*f(3)+f(2)*f(2);
f(5)=f(1)*f(4)+f(2)*f(3);
...
f(n)=f(1)*f(n-1)+....f(k)*f(k+1);//n=2k+1
f(n)=f(1)*f(n-1)+....f(k)*f(k);//n＝2k
个人感觉解法中有重复的：
   如f(1)*f(n-1)＝1＋1＋1＋..............+1
     f(k)*f(k)=1+1+1+..............+1

Answer 4

f(1)=1;
f(2)=f(1)*1
f(3)=f(1)*f(2);这三个解出来可能不对哦
1=1
2=1+1
3=1+2
3=1+1+1 
是不是结果就不对了？

Answer 5

int count(int sum,int floor){
    if(sum==floor)return 1;
    else if(sum<floor) return 0;
    else return count(sum-floor,floor)+count(sum,floor+1);
}
count(10000,1)就是结果
虽然是递归，但是强烈不建议这么写，效率太低，只是表示下递归的思想。

Answer 6

加一句，上面是允许重复的情况。
如果是不允许重复的话，改写一下：nt count(int sum,int floor){
    if(sum==floor)return 1;
    else if(sum<floor) return 0;
    else return count(sum-floor,floor+1)+count(sum,floor+1);
}

Answer 7

f(1)=1;
f(2)=f(1)+1;
f(3)=f(2)+f(1);
f(4)=f(3)+f(2)+f(1);
....
f(n)=f(n-1)+..+f(1);

Answer 8

//还是有重复^_^
danjiewu(阿丹) 请把那个思路写出来^_^

Answer 9

这是一个比较简单的组合问题，这样想（就拿100举例子）。
1。100是由一百个1相加而成
2。所要求的解是100可以分解成任意个数字的和的表达式的个数有多少。
3。这样的表达式的类型有多少个，所谓的类型就是由多少个加数组成，很自然的想到有2个加数的，3个加数的，4个加数的，--- ---,98个加数的，99个加数的，100个加数的
4。求每一类表达式存在的个数的多少。比如说求2个加数的表达式的个数，也就是100个一分两组有多少中分发，很显然有99种，就是C99一（组合的表达式，这里写不出 C在左边99在右下，1在右上，想起来了吧）（你这样想象有100个人站成一排，要分两组，那么就是在其中的某两个人中间的断开，100个人有多少个缝隙呢，显然是100-1 = 99个）。同样求3个加数的表达式的个数就是C99二，4个的就是C99三，--- ---， 98个的就是C99九十七，99个的就是C99九十八，100个加的就是C99九十九。

Answer 10

5。 所以 100可以分解成任意个数字的和的表达式的个数 = 
         C99一 + C99二 + C99三 + ... ... + C99九十七 + C99九十八 + C99九十九6。 对上面的这个等式进行推导，得出一个更简洁的公式。7。 既然100会求了，那么对于任意整数n也应该会求了吧， 最后得出的公式肯定是一个关于n的表达式f(n)，题目要求用递归，我们直接的表达式都有了，还怕递归吗？ 递归不就是求f(n)和f(n-1)的关系嘛，通过上面步骤5我们知道这个表达式是一个和式，那么f(n) - f(n - 1)
不就求出来递归增量了嘛，问题不也就解决了嘛

Answer 11

^_^
由eulerLCS(阿童木)推出
f(4)=3+3+1=7;//这里不对

Answer 12

该method在3中选1中就明显的重复了
1*111  //(1)
11*11  //(2)
111*1  //(1)

Answer 13

to classjava(原始野人) OK
看可以重复的情况。
int count(int sum,int floor){
    if(sum==floor)return 1;
    else if(sum<floor) return 0;
    else return count(sum-floor,floor)+count(sum,floor+1);
}这是按照从小到大的顺序添加正整数，这样可以确保表达式不重复。sum表示各整数的和，floor表示从哪个数开始取。
如果floor==sum那么肯定只有1种表达式，如果floor>sum那么就不存在表达式。这应该容易理解吧？
对于floor<sum的情况，一共有2种可能：
1、取floor做为加数；
那么从sum里减去floor，然后仍然是从floor开始取（如果是不可以重复的情况那就要从floor+1开始取），表达式的个数就是count（sum-floor，floor）
2、不取floor做为加数。
那么sum不变，但是要从floor+1开始取（因为是从小到大的顺序），表达式的个数就是count（sum，floor+1）
两者相加就是总的表达书的个数。这就是递归。

Answer 14

http://community.csdn.net/Expert/topic/4678/4678835.xml?temp=.2455255
领分贴

Answer 15

f(n) = 
for int i = 0 ; i <= round(m/2)+1 i++
f(i)+f(n-i);f(i) 又可以转化，当时面试的时候做出来了，但是有重复的 哈哈

Answer 16

public class AddTo10000 {
    public static void main(String args[]){
        ToDo td = new ToDo();
        td.getCase("10000=",1,10000);
        System.out.println("Cases : " + td.x);
    }
}
public class ToDo{
    public int x = 0;
    public void getCase (String s, int b, int n) {
        int z = (int) Math.floor(n/2);
        for(int i = b; i < z; i++){
            int j = n-i;
            String t = s.substring(s.length()-1).equals("=") ? s : s + "+";
            System.out.println(t + i + "+" +j);
            x++;
            getCase(t + i, i + 1, j);
        }
    }    
}

Answer 17

danjiewu(阿丹) 提供的应该是对的
不过是无法用程序执行的
递归太深了,每次都是一分为二,知道最好才能退出
空间复杂度也是2^n次方 
2^100=10^30 = 10^21 G
简单是天文数字
和汉塔差不多!

Answer 18

to eulerLCS(阿童木)
说的好像和题目没什么关系

Answer 19

（纯属个人意见）
f(1) = 1;
f(2) = 1;
f(3) = 2 * 1;
f(4) = 2 * (1 + 2);
f(5) = 2 * (1 + 2 + 3);
.
.
.
.
f(n) = 2 * (1 + 2+ 3 + ... + (n-2) );

Answer 20

to treeroot(旗鲁特) ( ) 信誉：106 已经说过递归效率比较低，而且10000的话应该会溢出了。
可以看作是二叉树的DFS，时间复杂度不到O（2~n），空间复杂度是O（n）。题目应该只要个思路，否则要求用递归就没有意义了。

Answer 21

to classjava(原始野人) 
对于f(4)来说，我的方法认为  1 + 3 和 3 + 1 是不同的表达式
在这个前提下，那么 f(4) = 3 + 3 + 1 是正确的
1 + 3          2 + 2          3 + 1
1 + 1 + 2      1 + 2 + 1      2 + 1 + 1
1 + 1 + 1 + 1

Answer 22

f(n) = f(n-1) + [n/2]注:[n] = 不大于n的最大整数

Answer 23

T0 classjava(原始野人)  我揭你的榜，请验证上面的答案是否正确
---------------------------数学是思维的体操，我们一起来做体操~！

Answer 24

f(1) = 0
f(2) = f(1) + [2/2] = 0 + 1 = 1
            2 = 1 + 1
f(3) = f(2) + [3/2] = 1 + 1 = 2
            3 = 1 + 2
            3 = 1 + 1 + 1
f(4) = f(3) + [4/2] = 2 + 2 = 4
            4 = 1 + 3
            4 = 2 + 2
            4 = 1 + 1 + 2
            4 = 1 + 1 + 1 + 1
f(5) = f(4) + [5/2] = 4 + 2 = 6
            5 = 1 + 4
            5 = 2 + 3
            5 = 1 + 1 + 3
            5 = 1 + 2 + 2
            5 = 1 + 1 + 1 + 2
            5 = 1 + 1 + 1 + 1 + 1

Answer 25

eulerLCS(阿童木) f(n) = f(n-1) + [n/2] 应该是对的 这里f(1) = 0

Answer 26

谢谢，jiayodo(爱上一只猪) 帮我顶贴，要不然我三连就不能发贴了，他是我同学对上面的表达式做一下解释
1.    首先  n = 1 + (n - 1)   也就是说f(n-1)有x个和式(比如其中一个是 x + y + z)，那么f(n)一定有这样一个和式 1 + x + y + z，同时加数的个数增加了一个，所以n-1的f(n-1)个和式在前面添上 1 这个加数 就变成了n的 f(n-1)个和式。这是表达式的第一项的来源解释。
2.    那么 [n/2]是怎么得来的呢？ 步骤1.的表达式是由3个和3个以上的加数构成的，那么由两个加数构成的有多少个呢，很显然是[n/2]个（为什么是[n/2]个我就不解释了，想不出来也就别看这道题了 *^_^*）

Answer 27

eulerLCS(阿童木) 的推导是正确的，本贴可以揭贴了呵呵。祝贺

Answer 28

f(5) = f(5) + [6/2] = 6 + 3 = 9
            6 = 1 + 5
            6 = 2 + 4
            6 = 3 + 3
            6 = 1 + 1 + 4
            6 = 1 + 2 + 3
            6 = 1 + 1 + 1 + 3
            6 = 1 + 1 + 2 + 2
            6 = 1 + 1 + 1 + 1 + 2
            6 = 1 + 1 + 1 + 1 + 1 + 1这里是9种，那么6 = 2 + 2 + 2哪里去了？
推理不严密。谁说f(n-1)就是3个和3个以上加数的表达式个数？

Answer 29

ft
是f(6) = f(5) + [6/2] = 6 + 3 = 9

Answer 30

这道题很简单：下面采用C#语言编写的：
直接调用F(n)就可以了，得到答案：例如F(1)=1，F(2)=2
注：1＝1，2＝2象这样的也算一个结果。
static void F(int n)
{
int t=0;
for(int i=1;i<=n;i++)
{
//t+=F(n,i);
int ti=f(0,n,i);
t+=ti;
}
Console.WriteLine(t.ToString());
}static int f(int an,int n,int ai)
{
int t=0;
if(n==ai)
{
//return 1;
if(an>1)
{
return 0;
}
else
{
return 1;
}
}
if(ai==1)
{
if(an>n)
{
return 0;
}
else
{
return 1;
}
}
for(int i=1;i<=n-ai+1;i++)
{
if(an>i)
{
continue;
}
int fi=f(i,n-i,ai-1);
t+=fi;
}
return t;
}

Answer 31

大家可以看我的程序，呵呵，这道题也太简单了。我给大家出一个题吧，谁做出来我把我所有的分都给他：呵呵
已知一种飞机：加满油可飞行距离为L，这种飞机可以相互加油，相互加油的时候时间忽略不计，假设在一个星球上，有一个飞机场，星球的周长为S，（S>L），请问，飞机场上至少有多少加这样的飞机才可以保证至少有一加飞机能够绕这个星球飞行一周？（注：飞机不能有损失，不能因为给其他飞机加油，而导致其自身不能到达飞机场而坠毁）这道题谁能用算法解决，我把自己的所有分都给他。

Answer 32

f(n) += f(n-1) ＋1
i = [n/2];
j = 2;
while( n/j > i){
f(n) += f([n/j]);
j++;
}
大家算算看对不对。
例如：f（6）＝ f(5) + 1 + f(6/2) + f(6/3)
                   
            
            6 = 3 + 3
            6 = 2 + 2 + 2
            6 = 2 + 4
            6 = 1 + 5
            6 = 1 + 1 + 4
            6 = 1 + 2 + 3
            6 = 1 + 1 + 1 + 3
            6 = 1 + 1 + 2 + 2
            6 = 1 + 1 + 1 + 1 + 2
            6 = 1 + 1 + 1 + 1 + 1 + 1

Answer 33

写错了。
f(n ) += f(n-1) +1 
while( j > n/2){
f(n) += f([n/j]);
j++;
}

Answer 34

其实这道题用数学表达式列出来，也就2个式子而已：
F(n)= Σ(i=1～n) F（0,n,i)
F(an,n,i)= Σ （Ki＝1～n-i+1)F(Ki,n-Ki,i-1)

Answer 35

原理很简单package cxz.math;public class whyget10000 {
    static long ncount = 20;    public static void main(String[] args) {
        long result = 0;
        for (long i = 1; i <= ncount; i++) {
            long s = get(i);
            System.out.println("" + i + "个数相加，种类共:" + s + "");
            result += s;
        }
        System.out.println("合计:" + result);
    }    private static long getZuHeCount(long n, long m) {
        return (m == 0) ? 1 : (getPaiLie(n, m) / getPaiLie(m, m));
    }    private static long getPaiLie(long n, long m) {
        long ret = 1;
        for (long i = n; i > n - m; i--)
            ret *= i;
        return ret;
    }    private static long get(long np) {
        return getZuHeCount(ncount - 1, np - 1);
    }
}

Answer 36

设n=10000
 则总个数=C(n-1,0)+C(n-1,1)+C(n-1,2)+......+C(n-1,n-2)+C(n-1,n-1)
 其中C(n,m)表示从n个元素中取出m个元素的组合个数
根据高中数学的有关定理
 则总个数=C(n-1,0)+C(n-1,1)+C(n-1,2)+......+C(n-1,n-2)+C(n-1,n-1) = 2的n-1次方就是2的9999次方  实在太大了用对数法计算，得到9.97531558440478*(10^3009)

Answer 37

f(1)=1
f(2)=2
f(3)=3
f(4)=5
f(5)=7
f(6)=11
f(7)=15
f(8)=22
f(9)=30
f(10)=42
f(11)=56
f(12)=77
f(13)=101
f(14)=135
f(15)=176
f(16)=231
f(17)=297
f(18)=385
f(19)=490
f(20)=627
f(21)=792
f(22)=1002
f(23)=1255
f(24)=1575
f(25)=1958
f(26)=2436
f(27)=3010
f(28)=3718
f(29)=4565
f(30)=5604
f(31)=6842
f(32)=8349
f(33)=10143
f(34)=12310
f(35)=14883
f(36)=17977
f(37)=21637
f(38)=26015
f(39)=31185
f(40)=37338
f(41)=44583
f(42)=53174
f(43)=63261
f(44)=75175
f(45)=89134
f(46)=105558
f(47)=124754
f(48)=147273
f(49)=173525
f(50)=204226这里像10=10这样也算一个等式，不是这个结果的考虑好再发。

Answer 38

原来没有想到还可以用BigInteger来做，代码很简单：
        int n = 10000;
        BigInteger s = new BigInteger("2");
        BigInteger t = s.pow(n - 1);
        System.out.println("合计:" + t.toString());
结果如下（有点长，三千多位）：
9975315584403791924418710813417925419117484159430962274260044749264719415110973315959980842018097298949665564711604562135778245674706890558796892966048161978927865023396897263382623275633029947760275043459096655771254304230309052342754537433044812444045244947419004626970816628925310784154736951278456194032612548321937220523379935813492726611434269080847157887814820381418440380366114267545820738091978190729484731949705420480268133910532310713666697018262782824765301571340117484700167967158325729648886639832887803086291015703997099089803689122841881140018651442743625950417232290727325278964800707416960807867294069628547689884559638900413478867837222061531009378918162751364161894635355186901433196515714066620700812097835845287030709827171162319400624428073652603715996129805898125065496430120854170403802966160080634246144248127920656422030768369475743557128157555544872757101656910101465820478798232378005202922920783036022481433508257530960315502093211137954335450287303208928475955728027534125625203003759921130949029618559027222394036453197621274169610991353702236581188380423306516889353019901706598566746827311350281584968727754120890486405491645657201785938762384254928638468963216610799699938443330404184418919013821641387586136828786372392056147194866905430803711626645987406560098802089140982848737949082265629217067979931392065064092703141738324544345260523790441307911980992885061203522165291537934519659802301702486578291604336052956650451876411707769872697198857628727645255106155473660805376737412870387636993174149249170378468977823319310937284749639508286051850682216567908607155895699111491922923667220135482091425502536463874182275289317250550426493906194736964349770417173079403521979559492907572889588571809849364065729741891601040737491085929005694535614125452913408718110288737960708826857843862807452291452496230514315040767791654065050993837928117171769477704587811700422443763081321784324416759731860188646620047228123461627175200339013636918877688203363449318120518745705483359278525379549050123394940089135962976690641210977014151379704224477507338334194848998443120818156688196951686727900703818370938855527692112869749555093234109848290825742565247111184973857381534577734108841438100181388628861890682665805598405640396334740943600649321830384275819930267301148935778758973692623184723461543947132974108504025560161182748144084517869560684169196795878209366925255485135806957719795495799077327208668155828468015561124968984999613390866179011555931322287649567879087504099919618142307624940544480116122181086885809043178507734242029311164896426937811743278220268481311009481785514406180783756271669151635014548834325284278578752758363759449597064855668845074958090657585772003864325286594778725460165092652423556909157703662026659519231042018210881851955775319894500371426836098140451738987266660234184397934290118976109314560040371409775658974078812224149259230754852444013637360787344065797375204866057540249095227901708413474893570658031605343195755840887152396298354688

Answer 39

不考虑对称性的话，上面的结果是正确的，答案就是2^(n-1)
如果考虑对称性，即1＋3和3＋1算一个，如下计算。数值太大的时候，取消中间结果输出，速度快些。
package cxz.math;import java.util.Vector;public class ua {
    static int ncount = 10;
    private static int count = 0;
    static int[] arr = new int[ncount];
    static int L = -1;
    static int nW = -1;    public static void main(String[] args) {
        for (int i = 1; i <= ncount; i++) {
            L = i;
            nW = 0;
            get(i, ncount);
        }
        System.out.println("_______________\n总数" + count + ":");
    }    private static void get(int n, int nc) {
        if (n == 1) {
            arr[nW] = nc;
            nW++;
            show();
            nW--;
            return;
        }
        for (int i = 1; i <= nc - n + 1; i++) {
            arr[nW] = i;
            nW++;
            get(n - 1, nc - i);
            if (nW > 0)
                nW--;
        }
    }    private static void show() {
        String ret = "";
        for (int i = 0; i < L - 1; i++) {
            for (int j = i + 1; j < L; j++) {
                if (arr[i] > arr[j]) {
                    return;
                }
            }
        }
        for (int k = 0; k < L; k++) {
            ret += arr[k] + " ";
            if (k != L - 1)
                ret += "+";
        }
        count++;
        System.out.println(count + ":" + ret);
    }
}
//------------------------
结果
1:10 
2:1 +9 
3:2 +8 
4:3 +7 
5:4 +6 
6:5 +5 
7:1 +1 +8 
8:1 +2 +7 
9:1 +3 +6 
10:1 +4 +5 
11:2 +2 +6 
12:2 +3 +5 
13:2 +4 +4 
14:3 +3 +4 
15:1 +1 +1 +7 
16:1 +1 +2 +6 
17:1 +1 +3 +5 
18:1 +1 +4 +4 
19:1 +2 +2 +5 
20:1 +2 +3 +4 
21:1 +3 +3 +3 
22:2 +2 +2 +4 
23:2 +2 +3 +3 
24:1 +1 +1 +1 +6 
25:1 +1 +1 +2 +5 
26:1 +1 +1 +3 +4 
27:1 +1 +2 +2 +4 
28:1 +1 +2 +3 +3 
29:1 +2 +2 +2 +3 
30:2 +2 +2 +2 +2 
31:1 +1 +1 +1 +1 +5 
32:1 +1 +1 +1 +2 +4 
33:1 +1 +1 +1 +3 +3 
34:1 +1 +1 +2 +2 +3 
35:1 +1 +2 +2 +2 +2 
36:1 +1 +1 +1 +1 +1 +4 
37:1 +1 +1 +1 +1 +2 +3 
38:1 +1 +1 +1 +2 +2 +2 
39:1 +1 +1 +1 +1 +1 +1 +3 
40:1 +1 +1 +1 +1 +1 +2 +2 
41:1 +1 +1 +1 +1 +1 +1 +1 +2 
42:1 +1 +1 +1 +1 +1 +1 +1 +1 +1 
_______________
总数42:

Answer 40

对算法做了些改进。取消中间结果输出的话，求出 f(50)=204226只要0.547秒。但n>500以后还是很慢，看哪位有没有更好的算法？package cxz.math;import java.util.Calendar;public class whyget10000b {
    static int n = 50;
    private static int count = 0;
    static int[] arr = new int[n];
    static int L = -1;
    static int nW = -1;    public static void main(String[] args) {
        Calendar cstart = Calendar.getInstance();
        for (int i = 1; i <= n; i++) {
            L = i;
            nW = 0;
            get(i, n);
        }
        Calendar cend = Calendar.getInstance();
        System.out.println("花费时间" + (cend.getTimeInMillis() - cstart.getTimeInMillis()) / 1000.0 + "秒");
        System.out.println("_______________\n f(" + n + ")=" + count + ":");
    }    private static void get(int n, int nc) {
        if (n == 1) {
            if (nW > 0 && nc > arr[nW - 1])
                return;
            arr[nW] = nc;
            nW++;
         //   showRecord();
            count++;
            nW--;
            return;
        }
        for (int i = 1; i <= nc - n + 1; i++) {
            if (nW > 0 && i > arr[nW - 1])
                continue;
            arr[nW] = i;
            nW++;
            get(n - 1, nc - i);
            if (nW > 0)
                nW--;
        }
    }    private static void showRecord() {
        StringBuffer ret = new StringBuffer();
        for (int k = 0; k < L; k++) {
            ret.append(arr[k] + " ");
            if (k != L - 1)
                ret.append("+");
        }
        System.out.println(count + ":" + ret.toString());
    }
}

Answer 41

0 -> 0+0
1 -> 1+0 :0=0+0
2 -> 1+1 :1=1+0
3 -> 1+2 :2=1+1:1=1+0:0=0+0