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. 這就類似一個一元二次方程，在解方程就可以了