创新工场2017年校园招聘笔试试题

概要：①，四层循环②，使用回溯法在空间中搜索代码为思路2：[cpp] view plaincopyprint?// chuangxingongchan.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include#includeusing namespace std;int count=0;int Target=0;int coin[4]={1,2,5,10};int total=0;vector solution;void dfs(int index){if( total == Target ){count++;cout << count <<":" ;for( int i=0; i<(int)solution.size(); i++){cout << solution[i]<<" ";}cout << endl;return;}if( total > Target )return;for( int i

创新工场2017年校园招聘笔试试题,标签：笔试大全,http://www.88haoxue.com
　　①，四层循环

　　②，使用回溯法在空间中搜索

　　代码为思路2：

　　[cpp] view plaincopyprint?

　　// chuangxingongchan.cpp : 定义控制台应用程序的入口点。

　　//

　　#include "stdafx.h"

　　#include

　　#include

　　using namespace std;

　　int count=0;

　　int Target=0;

　　int coin[4]={1,2,5,10};

　　int total=0;

　　vector solution;

　　void dfs(int index)

　　{

　　if( total == Target )

　　{

　　count++;

　　cout << count <<":" ;

　　for( int i=0; i<(int)solution.size(); i++)

　　{

　　cout << solution[i]<<" ";

　　}

　　cout << endl;

　　return;

　　}

　　if( total > Target )

　　return;

　　for( int i=index; i<4; i++)

　　{

　　total += coin[i];

　　solution.push_back( coin[i] );

　　dfs(i);

　　solution.pop_back();

　　total -=coin[i];

　　}

　　}

　　int _tmain(int argc, _TCHAR* argv[])

　　{

　　while(1)

　　{

　　count=0;

　　cin >> Target;

　　dfs(0);

　　cout << count <

　　}

　　return 0;

　　}

　　// chuangxingongchan.cpp : 定义控制台应用程序的入口点。

　　//

　　#include "stdafx.h"

　　#include

　　#include

　　using namespace std;

　　int count=0;

　　int Target=0;

　　int coin[4]={1,2,5,10};

　　int total=0;

　　vector solution;

　　void dfs(int index)

　　{

　　if( total == Target )

　　{

　　count++;

　　cout << count <<":" ;

　　for( int i=0; i<(int)solution.size(); i++)

　　{

　　cout << solution[i]<<" ";

　　}

　　cout << endl;

　　return;

　　}

　　if( total > Target )

　　return;

　　for( int i=index; i<4; i++)

　　{

　　total += coin[i];

　　solution.push_back( coin[i] );

　　dfs(i);

　　solution.pop_back();

　　total -=coin[i];

　　}

　　}

　　int _tmain(int argc, _TCHAR* argv[])

　　{

　　while(1)

　　{

　　count=0;

　　cin >> Target;

　　dfs(0);

　　cout << count <

　　}

　　return 0;

　　}

　　2，马戏团里有个叠罗汉的表演，为了便于美观，下面的人身高和体重都要大于上面的人。现在知道n个演员的身高和体重，请问最多能叠多少层?

　　解答：

　　思路：

　　首先生成一个有向图，用连接矩阵的方式来表示。

　　map[i][j]==1表示第i个人上面可以放第j个人。

　　然后开始对每个人进行深度搜索，这个图中不可能有环。

　　所以对于每个人来说就是一棵树，搜索树的高度。

　　再找出最高的高度即是答案。

　　[cpp] view plaincopyprint?

　　#include "stdafx.h"

　　#include

　　#include

　　#include

　　#include

　　using namespace std;

　　int N=0;

　　double *weight;

　　double *height;

　　int **map;

　　int maxDepth=0;

　　vector bestPath;

　　int dfs( int index, vector &path )

　　{

　　int flag=0;

　　int depth = 0;

　　vector bestPath;

　　for( int i=0; i

　　{

　　if( map[index][i] != 0)

　　{

　　flag = 1;

　　vector tPath;

　　int t = dfs(i, tPath);

　　if( t > depth )

　　{

　　path = tPath;

　　depth = t;

　　}

　　}

　　}

　　if( flag==0 )

　　{

　　path.clear();

　　path.push_back(index);

　　return 1;

　　}

　　else

　　{

　　// path = bestPath;

　　path.push_back(index);

　　return depth+1;

　　}

　　}

　　void CreateMap()

　　{

　　map = new int*[N];

　　for( int i=0; i

　　{

　　map[i] = new int [N];

　　memset( map[i], 0, N*sizeof(int) );

　　}

　　for( int i=0; i

　　{

　　for( int j=0; j

　　{

　　if( weight[j]

　　map[i][j]=1;

　　}

　　}

　　}

　　void CreateData()

　　{

　　ofstream out( "in.txt" );

　　int N = 30;

　　out << N <

　　for( int i=0; i

　　out << rand() << " ";

　　out << endl;

　　for( int i=0; i

　　out << rand() << " ";

　　}

　　int main()

　　{

　　CreateData();

　　freopen( "in.txt", "r", stdin );

　　cout << "Please input N:" <

　　cin >> N;

　　height = new double[N];

　　weight = new double[N];

　　for( int i=0; i

　　cin >> height[i];

　　for( int i=0; i

　　cin >> weight[i];

上一页  [1] [2] [3]  下一页