前幾天去了創(chuàng)新工場的一個招聘筆試，剛剛收到的面試通知。給大家寫下這次創(chuàng)新工場招聘筆試大概的題目吧，我也記得不多呀~

1. 在A*B的棋盤上，左上角是(0,0)，右下角是(A-1，B-1)，你每一步只能從(x,y)到(x+1,y), (x,y+1), (x+2,y+1), (x+1,y+2) 4個位置中的一個。求從左上角到右下角走法的數(shù)目。(這個數(shù)目可能很大，結果只需要模10 000 007即可，1

int func(int row, int col)

{

if (row < 1 || col < 1)

{

if (0 == row && col > 0 || row > 0 && 0 == col)

{

return 1; // 當只有一行或者一列時，從(0,0)到(0,col)或者是(row,0)均有一種方法，故返回1，

}

else

{

return 0; // 不滿足條件

}

}

else if (1 == row && 1 == col)

{

return 2; // 當只有一行且一列時，從(0,0)到(row,col)有兩種方法，故返回2

}

else if (1 == row && 2 == col || 2 == row && 1 == col)

{

return 4; //當只有兩行一列或者一行兩列時，從(0,0)到(row,col)有四種方法，故返回4

}

else

{

return func(row - 1, col)

+ func(row, col - 1)

+ func(row - 2, col - 1)

+ func(row - 1, col - 2);

}

}

int main()

{

cout<

system("pause");

return 0;

}

上面的方法是按題意直接寫的，不難看出其中存在著 子問題重疊

#include "stdafx.h"

#include

using namespace std;

int func(int row, int col)

{

// 新建table用于存儲

int *table = new int[(row + 2) * (col + 2)];

int i, j;

int res;

memset(table, 0, sizeof(int) * (row + 2) * (col + 2));

// 初始化

for (i = 1; i < (row + 2); ++i)

{

table[i * (col + 2) + 1] = 1;

對大家有用么？

}

for (i = 1; i < (col + 2); ++i)

{

table[(col + 2) + i] = 1;

}

for (i = 2; i < (row + 2); i++)

{

for (j = 2; j < (col + 2); j++)

{

// 某個點的值等于能到達該點的四個點的值相加

table[i * (col + 2) + j] = table[i * (col + 2) + j - 1]

+ table[(i - 1) * (col + 2) + j]

+ table[(i - 1) * (col + 2) + j - 2]

+ table[(i - 2) * (col + 2) + j - 1];

table[i * (col + 2) + j] %= 1000000;//取模

}

}

res = table[(row + 2) * (col + 2) - 1];

delete[]table;

return res;

}

int main()

{

cout<

system("pause");

return 0;

}

2. 給出一個自然數(shù)n(1<=n<=500000)，計算這個自然數(shù)所有因子的和。因子是只小于一個n的數(shù)，并且能找到一個自然數(shù)，使其相乘的積等于n。