创新工场二面试题！数字拆解

码拜

10年 ago

创新工场二面的面试官，问了本人一个题目，本人直接就跪在那里了！题目如下：
4=1+1+1+1

=1+1+2

=1+3

=2+2
例如   数字4  可以被拆解成为如上的四种情况。那么本人现在给你一个vector< vector<int> >      你把全部的结果全部的保存到这个
vector<  vector<int>   >  中。
函数的函数体，应该是这个样子的       vector<  vector<int>  >  &    fun(int   n){    //函数体   }
让本人写出这个函数的代码，但是本人写不出来，甚至连算法本人都没有思路。
可能大家觉的4还是很容易的，但是本人给你100，那么：

100=59+41

=58+42

=57+43

。

=1+99

=1+1+98

=1+1+97
等等结果非常的多本人也不知道该怎么样拆分

有时间限制吧？面试的时候考这个确实挺难了，一小时才写出来，效率也比较低。

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
bool sort_by( const int &v1, const int &v2)
{  
	return v1 < v2;
} 
void invternal(vector<vector<int>> &vv, int n)
{
	vector<int> vs;
	if (n == 1)
	{
		vs.push_back(1);
		vv.push_back(vs);
		return;
	}
	else
	{
		vector<vector<int>> oo;
		invternal(oo, n - 1);
		if (n == 4)
		{
			int a = 1;
		}
		vector<vector<int>> os = oo;
		vector<vector<int>>::iterator us;
		vector<int>::iterator uv;
		for (us = oo.begin() ; us != oo.end() ; us++)
		{
			us->push_back(1);
			sort(us->begin(), us->end(), sort_by);
		}
		int ita = 0;
		int itb = 0;
		for (us = os.begin() ; us != os.end() ; us++, ita++)
		{
			vector<int> xs;
			set<int> mm;
			itb = 0;
			for (uv = us->begin() ; uv != us->end() ; uv++, itb++)
			{
				if (mm.find(*uv) == mm.end() && *uv < n - 1)
				{
					xs = *us;
					xs[itb]++;
					mm.insert(*uv);
					sort(xs.begin(), xs.end(), sort_by);
					vector<vector<int>>::iterator un;
					for (un = oo.begin() ; un != oo.end() ; un++)
					{
						if (*un == xs)
						{
							break;
						}
					}
					if (un == oo.end())
					{
						oo.push_back(xs);
					}
				}
			}
		}
		vv = oo;
	}
}
vector<vector<int>> &fun(int n)
{
	vector<vector<int>> *vv = new vector<vector<int>>;
	if (n <= 0)
	{
		return *vv;
	}
	invternal(*vv, n);
	return *vv;
}
int main()
{
	vector<vector<int>> &uu = fun(7);
	getchar();
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
void print(int res[], int num) {
    static int L=0;
    L++;
    printf("%8d:",L);
    for (int i=0;i<num;++i) {
        printf(" %d", res[i]);
    }
    printf("\n");
}
void split(int n, int m) {// n表示总数，m表示最大因子
    static int res[100];// 保存结果
    static int num=-1;// 当前因子下标
    if (n<m || n<0 || m<1) return;
    num++;
    if (0==n) {// 递归终止条件，为0不可再分，直接输出
        print(res,num+1);
        num--;
        return;
    } else {
        if (n==m) {// 不拆，直接输出
            res[num]=m;
            print(res,num+1);
            num--;
        } else {
            // 拆分出第一个
            res[num]=m;
            n=n-m;
            if (m>n) m = n; // 最大因子不可能大于总数
            for (int i=m;i>=1;--i) {// 循环，第二个因子可以继续拆分，而且按照最大因子不同可以拆分成多个
                split(n,i);
            }
            num--;
        }
    }
}
void Split(int n) {
    if (n<=0) return;
    if (100<n) {
        printf("Up to 100\n");
        return;
    }
    for (int i=n;i>=1;--i) {
        split(n, i);
    }
}
void main(int argc,char **argv) {
         if (argc<=1) Split(5);
    else if (argc>=3) split(atoi(argv[1]),atoi(argv[2]));
    else              Split(atoi(argv[1]));
}

#include <iostream>
#include <vector>
using namespace std;
vector< vector<int> > split(int number, int head)
{
    int begin = head, end = head;
    vector< vector<int> > vvint;
    while (begin + end <= number) {
        vector<int> vint;
        int temp = number - begin - end;
        vint.push_back(begin);
        for (int i = 0; i < temp; i++)
            vint.push_back(1);
        vint.push_back(end);
        vvint.push_back(vint);
        end++;
    }
    return vvint;
}
vector < vector<int> > totalSplit(int number)
{
    vector < vector<int> > totalVvint;
    vector < vector<int> > vvint;
    int head = 1;
    do {
        vvint = split(number, head++);
        for (unsigned int i = 0; i < vvint.size(); i++)
            totalVvint.push_back(vvint.at(i));
    } while(!vvint.empty());
    return totalVvint;
}
void printSplit(vector < vector<int> > totalVvint)
{
    for (unsigned int i = 0; i < totalVvint.size(); i++) {
        vector<int> vvint = totalVvint.at(i);
        for (unsigned int j = 0; j < vvint.size(); j++) {
            cout << vvint.at(j) << " ";
        }
        cout << endl;
    }
    cout << endl;
}
int main()
{
    cout << "number : " << 4 << endl;
    printSplit(totalSplit(4));
    cout << "number : " << 10 << endl;
    printSplit(totalSplit(10));
    return 0;
}

输出结果：