搜狗:
1,有n*n个正方形格子,每个格子里有正数或者0,从最左上角往最右下角走,只能向下和向右走。一共走两次,把所有经过的格子的数加起来,求最大值。且两次如果经过同一个格子,则该格子的数只加一次。
思路:
搜索:一共搜(2n-2)步,每一步有四种走法。考虑不相交等条件可以剪去很多枝。
复杂度为O(4^n)
动态规划:
by:绿色夹克衫
详细算法思路:http://www.51nod.com/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)
- #include <iostream>
- #define MAX(a,b) (a)>(b)?(a):(b)
- using namespace std;
-
- #define N 5
- int map[5][5]={
- {2,0,8,0,2},
- {0,0,0,0,0},
- {0,3,2,0,0},
- {0,10,0,0,0},
- {2,0,8,0,2}};
- int sumMax=0;
- int p1x=0;
- int p1y=0;
- int p2x=0;
- int p2y=0;
- int curMax=0;
-
- /*
- 编号系统为:
- 00000
- 11111
- 22222
- 33333
- 44444
- 走1次:编号有:0,1
- 走2次:编号有:0,1,2
- 走5次:编号有:1,2,3,4
- 走k次:编号有:l,l+1,l+2...,h-1 //low,high 的计算见code
- 编号到map坐标的转换为:
- 编号i,则对应map[i][k-i].
-
- dp方程为:
- 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];
- */
- int dp(void){
- int s[2*N-1][N][N];
- s[0][0][0]=map[0][0];
-
- for(int k=1;k<2*N-1;k++){
- int h = k<N?k+1:N; //走k次后编号上限
- int l = k<N?0:k-N+1; //走k次后编号下限
- for( int i=l;i<h;i++){
- for( int j=i+1; j<h; j++){
- int t=0;
- if( k==1||i<j-1)
- t= MAX(t,s[k-1][i][j-1]);
- if( i-1>=0)
- t= MAX(t, s[k-1][i-1][j-1]);
- if( j<h)
- t= MAX(t, s[k-1][i][j]);
- if( i-1>=0&&j<h)
- t= MAX(t, s[k-1][i-1][j]);
- s[k][i][j]=t+map[i][k-i]+map[j][k-j];
- }
- }
- }
- return s[2*N-3][N-2][N-1]+map[N-1][N-1];
- }
-
- void dfs( int index){
- if( index == 2*N-2){
- if( curMax>sumMax)
- sumMax = curMax;
- return;
- }
-
- if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))
- {
- if( p1x>= p2x && p1y >= p2y )
- return;
- }
-
- //right right
- if( p1x+1<N && p2x+1<N ){
- p1x++;p2x++;
- int sum = map[p1x][p1y]+map[p2x][p2y];
- curMax += sum;
- dfs(index+1);
- curMax -= sum;
- p1x--;p2x--;
- }
-
- //down down
- if( p1y+1<N && p2y+1<N ){
- p1y++;p2y++;
- int sum = map[p1x][p1y]+map[p2x][p2y];
- curMax += sum;
- dfs(index+1);
- curMax -= sum;
- p1y--;p2y--;
- }
-
- //rd
- if( p1x+1<N && p2y+1<N ) {
- p1x++;p2y++;
- int sum = map[p1x][p1y]+map[p2x][p2y];
- curMax += sum;
- dfs(index+1);
- curMax -= sum;
- p1x--;p2y--;
- }
-
- //dr
- if( p1y+1<N && p2x+1<N ) {
- p1y++;p2x++;
- int sum = map[p1x][p1y]+map[p2x][p2y];
- curMax += sum;
- dfs(index+1);
- curMax -= sum;
- p1y--;p2x--;
- }
- }
-
- int main()
- {
- curMax = map[0][0];
- dfs(0);
- cout <<"搜索结果:"<<sumMax-map[N-1][N-1]<<endl;
- cout <<"动态规划结果:"<<dp()<<endl;
- return 0;
- }
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
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。