搜狗笔试题--2012

搜狗：
1，有n*n个正方形格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右走。一共走两次，把所有经过的格子的数加起来，求最大值。且两次如果经过同一个格子，则该格子的数只加一次。

思路：

搜索：一共搜（2n-2）步，每一步有四种走法。考虑不相交等条件可以剪去很多枝。

复杂度为O(4^n）

动态规划：

by:绿色夹克衫

详细算法思路：http://www./question/index.html#!questionId=657

s[k][i][j] = max(s[k-1][i-1][j-1],s[k-1][i-1][j],s[k-1][i][j-1],s[k-1][j][i])+map[i][k-i]+map[j][k-j];

复杂度为O(n^3)

[cpp] view plaincopyprint?

1. #include <iostream>  
2. #define MAX(a,b) (a)>(b)?(a):(b)  
3. using namespace std;  
4.   
5. #define N 5  
6. int map[5][5]={  
7.     {2,0,8,0,2},  
8.     {0,0,0,0,0},  
9.     {0,3,2,0,0},  
10.     {0,10,0,0,0},  
11.     {2,0,8,0,2}};  
12. int sumMax=0;  
13. int p1x=0;  
14. int p1y=0;  
15. int p2x=0;  
16. int p2y=0;  
17. int curMax=0;  
18.   
19. /* 
20. 编号系统为： 
21. 00000 
22. 11111 
23. 22222 
24. 33333 
25. 44444 
26. 走1次：编号有：0,1 
27. 走2次：编号有：0,1,2 
28. 走5次：编号有：1,2,3,4 
29. 走k次：编号有：l,l+1,l+2...,h-1 //low,high 的计算见code 
30. 编号到map坐标的转换为： 
31. 编号i，则对应map[i][k-i]. 
32.  
33. dp方程为： 
34. s[k][i][j] = max(s[k-1][i-1][j-1],s[k-1][i-1][j],s[k-1][i][j-1],s[k-1][j][i])+map[i][k-i]+map[j][k-j]; 
35. */  
36. int dp(void){  
37.     int s[2*N-1][N][N];  
38.     s[0][0][0]=map[0][0];  
39.       
40.     for(int k=1;k<2*N-1;k++){  
41.         int h = k<N?k+1:N;     //走k次后编号上限  
42.         int l = k<N?0:k-N+1;   //走k次后编号下限  
43.         for( int i=l;i<h;i++){  
44.             for( int j=i+1; j<h; j++){  
45.                     int t=0;  
46.                     if( k==1||i<j-1)  
47.                         t= MAX(t,s[k-1][i][j-1]);  
48.                     if( i-1>=0)  
49.                         t= MAX(t, s[k-1][i-1][j-1]);  
50.                     if( j<h)  
51.                         t= MAX(t, s[k-1][i][j]);  
52.                     if( i-1>=0&&j<h)  
53.                         t= MAX(t, s[k-1][i-1][j]);  
54.                     s[k][i][j]=t+map[i][k-i]+map[j][k-j];  
55.             }  
56.         }  
57.     }  
58.     return s[2*N-3][N-2][N-1]+map[N-1][N-1];  
59. }  
60.   
61. void dfs( int index){  
62.     if( index == 2*N-2){  
63.         if( curMax>sumMax)  
64.             sumMax = curMax;  
65.         return;  
66.     }  
67.   
68.     if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))  
69.     {  
70.         if( p1x>= p2x && p1y >= p2y )  
71.             return;  
72.     }  
73.   
74.     //right right  
75.     if( p1x+1<N && p2x+1<N ){  
76.         p1x++;p2x++;  
77.         int sum = map[p1x][p1y]+map[p2x][p2y];  
78.         curMax += sum;  
79.         dfs(index+1);  
80.         curMax -= sum;  
81.         p1x--;p2x--;  
82.     }  
83.   
84.     //down down  
85.     if( p1y+1<N && p2y+1<N ){  
86.         p1y++;p2y++;  
87.         int sum = map[p1x][p1y]+map[p2x][p2y];  
88.         curMax += sum;  
89.         dfs(index+1);  
90.         curMax -= sum;  
91.         p1y--;p2y--;  
92.     }  
93.   
94.     //rd  
95.     if( p1x+1<N && p2y+1<N ) {  
96.         p1x++;p2y++;  
97.         int sum = map[p1x][p1y]+map[p2x][p2y];  
98.         curMax += sum;  
99.         dfs(index+1);  
100.         curMax -= sum;  
101.         p1x--;p2y--;  
102.     }  
103.   
104.     //dr  
105.     if( p1y+1<N && p2x+1<N ) {  
106.         p1y++;p2x++;  
107.         int sum = map[p1x][p1y]+map[p2x][p2y];  
108.         curMax += sum;  
109.         dfs(index+1);  
110.         curMax -= sum;  
111.         p1y--;p2x--;  
112.     }  
113. }  
114.   
115. int main()  
116. {  
117.     curMax = map[0][0];  
118.     dfs(0);  
119.     cout <<"搜索结果："<<sumMax-map[N-1][N-1]<<endl;  
120.     cout <<"动态规划结果:"<<dp()<<endl;  
121.     return 0;  
122. }  

2，有N个整数（数的大小为0-255）的有序序列，设计加密算法，把它们加密为K个整数（数的大小为0-255），再将K个整数顺序随机打乱，使得可以从这乱序的K个整数中解码出原序列。设计加密解密算法。
有三个子问题：
1，N<=16,要求K<=16*N.
2，N<=16,要求K<=10*N.
3，N<=64,要求K<=15*N.

-------------------------------------------------------

一个长度为n的数组a[0],a[1],...,a[n-1]。现在更新数组的名个元素，即a[0]变为a[1]到a[n-1]的积

a[1]变为a[0]和a[2]到a[n-1]的积，...，a[n-1]为a[0]到a[n-2]的积。
程序要求：
要求具有线性复杂度。
不能使用除法运算符。

算法思想:

设共有N个数(N=7), 建立一个数组backToFront,从数组最后开始分别保存a[6], a[6]*a[5], a[6]*a[5]*a[4],.......a[6]*a[5]*a[4]*a[3]*a[2]*a[1].

然后再设一个变量 frontToBack用来保存,从前到后的乘积.

#include <iostream>
using namespace std;

void print(long a[], int len)
{
    int i;
    for (i = 0; i < len; i++)
        cout << a[i] << " ";
    cout << endl;
}
void change(long a[], int len)
{
    long *backToFront = new long(len);
    long frontToBack;
    int i;
    
    backToFront[len - 1] = 1;
    for(i = len - 2; i >= 0; i--)
        backToFront[i] = backToFront[i + 1] * a[i + 1];
    
    frontToBack = 1;
        
    for(i = 0; i < len; i++)
    {
        int tmp;
        tmp = a[i];
        a[i] = frontToBack * backToFront[i];
        frontToBack *= tmp;
    }
    delete [] backToFront;
    
}
int main()
{
    long a[MAX];
    int i;
    for (i = 0; i < MAX; i++)
        a[i] = i + 1;
    
    print(a, MAX);    
    change(a, MAX);    
    print(a, MAX);
    
    system("PAUSE");
    return 0;
}

----------------------------------------------------

1. 选出程序输出的结果
#include <iostream>

using namespace  std;

int main()

{
    short input[10]={'A','B','C','D','E'};
    unsigned char *p=(unsigned char*)&input;
    int s=0;
    int temp=sizeof(input);
    for(int i=0; i<temp; ++i)
    {
        char v=p[i];
        if(v>0)
        s+=v-'A'+i;
    }
    printf("%d\n",s);
}

答案 ：A：10    B：15    C：25  D：30  E：35  F：得到不确定的结果或程序崩溃

这个题目要考虑大小端存储，因为x86平台下是小端模式所以对于input而言，内存如下：A0B0C0D0E0 0000000000当强制将内存按照char的方式读取的时候，i 分别在0 2 4 6 8 的位置是 非零，然后加上各自对应的值0 1 2 3 4 所以最后结果是 20 + 10 = 30对于在大端模式的平台下：0A0B0C0D0E 0000000000这样组后的结果就是 1 3 5 7 90 1 2 3 4是 25 + 10 = 35但是题目没有给出是大端还是小端模式，所以选F2. 写出程序的输出
char *c[] = { "ENTER", "NEW", "POINT", "FIRST" }; 
char **cp[] = { c+3, c+2, c+1, c }; 
char ***cpp = cp;

int main(void)
{ 
 printf("%s", **++cpp); 
 printf("%s", *--*++cpp+3); 
 printf("%s", *cpp[-2]+3); 
 printf("%s\n", cpp[-1][-1]+1); 
 return 0;
}
指针比较繁琐，仔细点应该不会有问题，分析如下：第一个输出如下：

第二个输出如下：

第三个输出如下：

第四个输出如下：

最后结果：Pointerstew