c面试算法题
第一题:
#include<stdio.h>
longfun(intn){//计算1到n所有数的乘积1*2*3*...n
longfac=1;
inti;
for(i=1;i<=n;i++){
fac*=i;
}
returnfac;
}
intmain(void){
inti;
longsum=0;
for(i=1;i<4;i+=2){//循环2次i=13
sum=sum+fun(i);
}
printf("sum=%ld ",sum);
return0;
}
第二题:
#include<stdio.h>
//元素首位交换位置
voidfun(intx[],intn){
inti,j,temp;
i=0;j=n-1;
while(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
i++;
j--;
}
}
intmain(void){
intx[]={1,2,3,4,5,6};
fun(x,6);
for(inti=0;i<6;i++){
printf("%2d",x[i]);
}
//运行结果654321
return0;
}
第三题:
#include<stdio.h>
doublefun(doublex[3][4]){
inti,j;
doublesum=0;
for(i=0;i<3;i++){
for(j=0;j<4;j++){
sum=sum+x[i][j];
}
}
returnsum/12;
}
intmain(void){
doublex[3][4]={{1.2,3.1},{6.5},{2.6,8.9}},ave;
ave=fun(x);
printf("ave=%lf ",ave);
return0;
}
② c语言问题.
Dijkstra算法可描述如下:
1初始化： S ← { v0 };
dist[j] ← Edge[0][j], j = 1, 2, …, n-1;
// n为图中顶点个数
2求出最短路径的长度：
dist[k] ← min{ dist[i] }, i V- S ;
S ← S U { k };
3修改：
dist[i] ← min{ dist[i], dist[k] + Edge[k][i] },
对于每一个 i V- S ;
4判断： 若S = V, 则算法结束，否则转2。
用于计算最短路径的图邻接矩阵类的定义
const int NumVertices = 6; //图中最大顶点个数
class Graph { //图的类定义
private:
int Edge[NumVertices][NumVertices]; //邻接矩阵
int dist[NumVertices]; //最短路径长度数组
int path[NumVertices]; //最短路径数组
int S[NumVertices]; //最短路径顶点集
public:
void ShortestPath ( const int, const int );
int choose ( const int );
};
计算从单个顶点到其它各个顶点的最短路径
void Graph::ShortestPath ( const int n, const int v ){
//Graph是一个具有n个顶点的带权有向图, 各边上
//的权值由Edge[i][j]给出。本算法建立起一个数
//组: dist[j], 0 j < n, 是当前求到的从顶点v到顶点
//j的最短路径长度, 同时用数组path[j], 0 j < n, 存
//放求到的最短路径。
for ( int i = 0; i < n; i++) {
dist[i] = Edge[v][i]; //dist数组初始化
S[i] = 0;
if ( i != v && dist[i] < MAXINT ) path[i] = v;
else path[i] = -1; //path数组初始化
}
S[v] = 1; dist[v] = 0; //顶点v加入顶点集合
//选择当前不在集合S中具有最短路径的顶点u
for ( i = 0; i < n-1; i++ ) {
int min = MAXINT; int u = v;
for ( int j = 0; j < n; j++ )
if ( !S[j] && dist[j] < min )
{ u = j; min = dist[j]; }
S[u] = 1; //将顶点u加入集合S
for ( int w = 0; w < n; w++ ) //修改
if ( !S[w] && Edge[u][w] < MAXINT &&
dist[u] + Edge[u][w] < dist[w] ) {
dist[w] = dist[u] + Edge[u][w];
path[w] = u;
}
Floyd算法的基本思想：
定义一个n阶方阵序列：
A(-1), A(0), …, A(n-1).
其中 A(-1) [i][j] = Edge[i][j]；
A(k) [i][j] = min { A(k-1)[i][j]，
A(k-1)[i][k] + A(k-1)[k][j] }, k = 0,1,…, n-1
A(0) [i][j]是从顶点vi 到vj , 中间顶点是v0的最短路径的长度, A(k) [i][j]是从顶点vi 到vj , 中间顶点的序号不大于k的最短路径的长度, A(n-1)[i][j]是从顶点vi 到vj 的最短路径长度。
所有各对顶点之间的最短路径
void Graph::AllLengths ( const int n ) {
//Edge[n][n]是一个具有n个顶点的图的邻接矩阵。//a[i][j]是顶点 i 和 j 之间的最短路径长度。path[i][j]
//是相应路径上顶点 j 的前一顶点的顶点号, 在求
//最短路径时图的类定义中要修改path为
//path[NumVertices][NumVertices]。
for ( int i = 0; i < n; i++ ) //矩阵a与path初始化
for ( int j = 0; j < n; j++ ) {
a[i][j] = Edge[i][j];
if ( i <> j && a[i][j] < MAXINT )
path[i][j] = i; // i 到 j 有路径
else path[i][j] = 0; // i 到 j 无路径
}
for ( int k = 0; k < n; k++ ) //产生a(k)及path(k)
for ( i = 0; i < n; i++ )
for ( j = 0; j < n; j++ )
if ( a[i][k] + a[k][j] < a[i][j] ) {
a[i][j] = a[i][k] + a[k][j];
path[i][j] = path[k][j];
} //缩短路径长度, 绕过 k 到 j
}
③ 一道面试题，找出1-100中没有插入的两个数
恩 将下我的思路吧： （算法自己实现，不会再联系我）：
假设这连个数是a和b：
1. 对数组中的98个元素，进行求和为c， a+b = 5050-c
2. 1到100求平方在求和，数组中98个元素求平方在求和，求差 a2+b2=...
3. 这就类似一个一元二次方程，在解方程就可以了