程序員每日計算題

1. 程序員開發用到的十大基本演算法

演算法一：快速排序演算法
快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法（Divide and conquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。

演算法步驟：
1 從數列中挑出一個元素，稱為 「基準」（pivot），
2 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
3 遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

演算法二：堆排序演算法
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆排序的平均時間復雜度為Ο(nlogn) 。

演算法步驟：
1.創建一個堆H[0..n-1]
2.把堆首（最大值）和堆尾互換
3.把堆的尺寸縮小1，並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置
4.重復步驟2，直到堆的尺寸為1

演算法三：歸並排序
歸並排序（Merge sort，台灣譯作：合並排序）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

演算法步驟：

演算法四：二分查找演算法
二分查找演算法是一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜 素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組 為空，則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半，時間復雜度為Ο(logn) 。

演算法五：BFPRT(線性查找演算法)
BFPRT演算法解決的問題十分經典，即從某n個元素的序列中選出第k大（第k小）的元素，通過巧妙的分 析，BFPRT可以保證在最壞情況下仍為線性時間復雜度。該演算法的思想與快速排序思想相似，當然，為使得演算法在最壞情況下，依然能達到o(n)的時間復雜 度，五位演算法作者做了精妙的處理。

演算法步驟：

終止條件：n=1時，返回的即是i小元素。

演算法六：DFS（深度優先搜索）
深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。它沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分 支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發 現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。DFS屬於盲目搜索。

深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。

演算法步驟：

上述描述可能比較抽象，舉個實例：
DFS 在訪問圖中某一起始頂點 v 後，由 v 出發，訪問它的任一鄰接頂點 w1；再從 w1 出發，訪問與 w1鄰 接但還沒有訪問過的頂點 w2；然後再從 w2 出發，進行類似的訪問，… 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。

接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之後再從此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。

演算法七：BFS(廣度優先搜索)
廣度優先搜索演算法（Breadth-First-Search），是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。BFS同樣屬於盲目搜索。一般用隊列數據結構來輔助實現BFS演算法。

演算法步驟：

演算法八：Dijkstra演算法
戴克斯特拉演算法（Dijkstra』s algorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹演算法使用了廣度優先搜索解決非負權有向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。

該演算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 表示G中所有邊的集合，而邊的權重則由權重函數 w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知有 V 中有頂點 s 及 t，Dijkstra 演算法可以找到 s 到 t的最低權重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。對於不含負權的有向圖，Dijkstra演算法是目前已知的最快的單源最短路徑演算法。

演算法步驟：

重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

演算法九：動態規劃演算法
動態規劃（Dynamic programming）是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。 動態規劃常常適用於有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合並子問題的解以得出原問題的解。 通常許多 子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量： 一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個 子問題解之時直接查表。 這種做法在重復子問題的數目關於輸入的規模呈指數增長時特別有用。

關於動態規劃最經典的問題當屬背包問題。

演算法步驟：

演算法十：樸素貝葉斯分類演算法
樸素貝葉斯分類演算法是一種基於貝葉斯定理的簡單概率分類演算法。貝葉斯分類的基礎是概率推理，就是在各種條件的存在不確定，僅知其出現概率的情況下， 如何完成推理和決策任務。概率推理是與確定性推理相對應的。而樸素貝葉斯分類器是基於獨立假設的，即假設樣本每個特徵與其他特徵都不相關。

樸素貝葉斯分類器依靠精確的自然概率模型，在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，樸素貝葉斯模型參數估計使用最大似然估計方法，換言之樸素貝葉斯模型能工作並沒有用到貝葉斯概率或者任何貝葉斯模型。

盡管是帶著這些樸素思想和過於簡單化的假設，但樸素貝葉斯分類器在很多復雜的現實情形中仍能夠取得相當好的效果。

2. 程序員考試做題app哪個好(編程刷題app)

1、牛客

牛客是一款專為程序員筆試、面試而打造的找工作神器。在這里可以隨時隨地免費刷題，各種名企校招真題應有盡有，是數百萬大學生都在使用的免費在線學習平台，通過刷題提高筆試通過的機率，幫助程序員們喚配順利拿到OFFER。

2、程序員雜志

程序員雜志是一款程序員資訊工具閱讀軟體，每月不可錯過的前沿技術、工具盡在其中。這是針對開發人員的專業技術刊物，是程序員學習與提高的重要。

3、程序媛

女程序員是不是很酷？而程序媛是一款學習教育信息，是專為女性打造的線上編程學習平台。界面簡潔，提供有趣的會話式學習模式，且擁有活躍的社區讓用戶們在辯閉這可快速解決各式各樣的疑難。

程序員考試屬於全國計算機技術與軟體專業技術資格考試（簡稱計算機軟體資格考試）中的一個初級考試。程序員考試分為上午科目和下午科目，上午考基礎知識；下攜鏈裂午題是程序設計。我用的APP上學吧的程序員題庫你可以試試

3. 編程題c++：從鍵盤輸入10個學生的成績，計算平均成績，統計及格人數，計算高於平均分的學生的分數

#include <stdio.h>

int main()

{

int i;

float a[10],min,max,avg; //max表示最高分，min表示最低分，avg表示平均分

printf("請輸入10位學生的分數 ");

printf("******************************** ");

for(i=0;i<=9;i++)

{

printf("請輸入一位學生的分數：");

scanf("%f",&a[i]);

}

max=min=avg=a[0];

int jige=0;

for(i=1;i<=9;i++)

{

if(min>a[i])

{min=a[i];}

if(a[i]>=60)

jige=jige+1;

if(max<a[i])

{max=a[i];}

avg=avg+a[i];

}

avg=avg/10;

printf("max=%f ",max);

printf("min=%f ",min);

printf("avg=%f ",avg);

printf("及格人數：%d ",jige);

printf("******************************** ");

}

(3)程序員每日計算題擴展閱讀：

C++是C語言的繼承，它是一種使用非常廣泛的計算機編程語言，C++作為一種靜態數據類型檢查的、支持多范型的通用程序設計語言，能夠支持過程化程序設計、數據抽象化、面向對象程序設計、泛型程序設計、基於原則設計等多種程序設計風格。

C++的編程領域眾廣，常用於系統開發，引擎開發等應用領域，深受廣大程序員的喜愛。

C++不僅擁有計算機高效運行的實用性特徵，同時還致力於提高大規模程序的編程質量與程序設計語言的問題描述能力。

網路-C++

4. c語言編程題，計算平均數

#include "stdio.h"
int main()
{
int a,b,c,sum;
float average;
scanf("%d%d%d",&a,&b,&c);
sum=a+b+c;
average = (float)sum/3;
printf("%d ",sum);
printf("%.2f ",average);
return 0;
}

5. 計算機二進制計算題

11
19.625

135 10000111

85.375 1010101.011
303 100101111

463.625

111001111.1010

6. 急需程序員筆試題，附帶答案

一、選擇題(每題1分，共20分)
1． 下列那種語言是面向對象的（C）
A. C B. PASCAL C. C++ D. FORTRAN77
2．在 Windows9x 下，可以進入 MS-D0S 方式。當在 DOS 提示符下鍵入 (B ) 命令後，
系統將退出 MS-DOS方式，返回到 WIndows 方式。
A. CLOSE B. EXIT C. QUIT D. RETURN
3．下面哪些是面向對象的基本特性：(A,B,C )
A 多態 B 繼承 C 封裝 D 介面
4．在C++中經常要進行異常處理，下面哪些是異常處理常用到的關鍵詞：(A,B,C)
A try B catch C throw D break E contiue
5．資料庫技術中的「臟數據',是指（D）的數據。
A.錯誤 B.回返 C.未提交 D.未提交的隨後又被撤消
6．TCP/IP是一種（A,B）
A.標准 B.協議 C.語言 D.演算法
7． 下面有關計算機操作系統的敘述中，不正確的是( )
A 操作系統屬於系統軟體
B 操作系統只負責管理內存儲器，而不管理外存儲器
C UNIX 是一種操作系統
D 計算機的處理器、內存等硬體資源也由操作系統管理
8．微機上操作系統的作用是( D)
A 解釋執行源程序 B 編譯源程序
C 進行編碼轉換 D 控制和管理系統資源
9．下列存儲器中存取速度最快的是(A )
A 內存 B 硬碟 C 光碟 D 軟盤
10．在計算機中，—個位元組是由多少個二進制位組成的( )
A. 4 B. 8 C. 16 D. 24
11. 存儲16×16點陣的一個漢字信息，需要的位元組數為( )
A 32 B 64 C 128 D 256
12. 以下選項中合法的字元常量是（C）
A."B" B. '\010' C. 68 D. D
13. 假定x和y為double型，則表達式x=2,y=x+3/2的值是（）
A. 3.500000 B. 3 C. 2.000000 D. 3.000000
14. 以下合法的賦值語句是（）
A. x=y=100 B. d--; C. x+y; D. c=int(a+b);
15. 設正x、y均為整型變數，且x=10 y=3，則以下語句
pprintf("%d,%d\n",x--,--y); 的輸出結果是（）
A.10,3 B. 9,3 C. 9,2 D.10,2
16. x、y、z被定義為int型變數，若從鍵盤給x、y、z輸入數據，正確的輸入語句是（）
A .INPUT x、y、z; B. scanf("%d%d%d",&x,&y,&z);
C. scanf("%d%d%d",x,y,z); D. read("%d%d%d",&x,&y,&z);
17.以下數組定義中不正確的是（）
A) int a[2][3]; B) int b[][3]={0,1,2,3};
C) int c[100][100]={0}; D) int d[3][]={{1,2},{1,2,3},{1,2,3,4}};
18. 以下程序的輸出結果是（）
main()
{
int a[4][4]={{1,3,5},{2,4,6},{3,5,7}};
printf("%d%d%d%d\n",a[0][3],a[1][2],a[2][1],a[3][0];
}
A) 0650 B) 1470 C) 5430 D) 輸出值不定
19 以下程序的輸出結果是（）
main()
{
char st[20]= "hello\0\t\\\";
printf(%d %d \n",strlen(st),sizeof(st));
}
A) 9 9 B) 5 20 C) 13 20 D) 20 20
20. 當調用Windows API函數InvalidateRect,將會產生什麼消息（）
A:WM_PAINT B:WM_CREATE
C:WM_NCHITTEST D:WM_SETFOCUS

二、填空題(每題3分，共30分)
1．請列舉當前一些當前流行的資料庫引擎__________
2． 為了將當前盤當前目錄中的所有文本文件（擴展名為.TXT）的內容列印輸出，正確
的單條DOS命令為______。
3． 計算機網路分為區域網和廣域網，網際網路屬於 廣域網。
4. 設y是int型變數，請寫出判斷y為奇效的關系表達_______。
5. 設有以下程序:
main()
{ int n1,n2;
scanf("%d",&n2);
while(n2!=0)
{ n1=n2%10;
n2=n2/10;
printf("%d",n1);
}
}
程序運行後，如果從鍵盤上輸入1298；則輸出結果為____。
6．以下程序運行後的輸出結果是______。
main()
{ char s[ ]="9876",*p;
for ( p=s ; pbr>}
7．以下函數的功能是：求x的y次方，請填空。
double fun( double x, int y)
{ int i;
double z;
for(i=1, z=x; ibr>return z;
}
8．以下程序段打開文件後，先利用fseek函數將文件位置指針定位在文件末尾，然後調
用ftell函數返回當前文件位置指針的具體位置，從而確定文件長度，請填空。
FILE *myf; ling f1;
myf= ______("test.t","rb");
fseek(myf,0,SEEK_END); f1=ftel(myf);
fclose(myf);
printf("%d\n",f1);
9. 以下程序輸出的最後一個值是______。
int ff(int n)
{ static int f=l;
f=f*n;
return f;
}
main()
{ int i;
for(I=1;I<=5;I++ printf("%d\n",ff(i));
)
10. 以下程序運行後的輸出結果是_____。
main()
{ int i=10, j=0;
do
{ j=j+i; i-;
while(i>2);
printf("%d\n",j);
}

三、判斷題(每題2分，共20分)
1：動態鏈結庫不能靜態調用。
2：UDP是面向無連接的網路連接
3：ASP是一種資料庫引擎
4：隊列是先進後出。
5：Weblogic是分布式應用伺服器。
6：TCP,UDP都是傳輸層的協議。
7: 兩個線程不能共存於同一地址空間
8: JAVA是一種跨平台的開發工具
9．在WINDOWS操作系統中對外設是以文件的方式進行管理
10. 虛擬內存實際是創建在硬碟上的

四、問答題(每題10分，共30分)
1． 寫出從資料庫表Custom中查詢No、Name、Num1、Num2並將Name以姓名顯示、計算出
的和以總和顯示的SQL。
Select No、Name、Num1、Num2 from custom;
2. 何為「事務處理」，談談你對它的理解。
3. 常用的數據結構有哪些？請枚舉一些。（不少於5個）
4. 什麼是OOP？什麼是類？請對比類和對象實例之間的關系。
5. 有一組數字（3，10，6，8，98，22），請編程排序（升降序皆可），語言不限，演算法不限，但須註明是何種演算法。
[email protected]

7. 程序員演算法實現-買賣股票的最佳時機系列問題

主要思路：因為只有一股可以交易，所以我們可以枚舉 必須以i位置作為賣出時機的情況下，得到的最大收益是多少。如果我們得到每個i位置的最大收益，那麼最大收益必是所有位置的最大收益的最大值 。

使用兩個變數：

min變數：表示遍歷到的位置之前的最小值是什麼。

max變數：表示當前收集到必須以i位置賣出的最大收益是多少。

遍歷數組一遍，在遍歷到i位置的時候，min和max的更新邏輯如下：

遍歷完數組，返回max的值就是最終答案。完整代碼見：

主要思路：由於可以進行任意次的交易，但是任何時候最多隻能持有一股股票，所以我們可以把股票曲線的所有 上升段 都抓取到，累加收益就是最大收益。遍歷數組，遍歷到的位置減去前一個位置的值，如果是正數，就收集，如果是負數，就把本次收益置為0（就等於沒有做這次交易），這樣遍歷一遍數組，就不會錯過所有的收益。

設置一個變數max，初始為0，用於收集最大收益值，來到i位置，max更新邏輯如下：

完整代碼如下：

由本題可以簡單得出一個結論： 如果數組元素個數為N，則最多執行N/2次交易就可以抓取所有的上升段的值（極端情況下，當前時刻買，下一個時刻賣，保持這樣的交易一直到最後，執行的交易次數就是N/2） 。

主要思路：

在第2種情況下，我們定義

其中dp[i][j]表示[0...i]范圍內交易j次獲得的最大收益是多少。如果可以把dp這個二維表填好，那麼返回dp[N-1][k]的值就是題目要的答案。

dp這個二維矩陣中，

第一行的值表示數組[0..0]范圍內，交易若干次的最大收益，顯然，都是0。

第一列的值表示數組[0...i]范圍內，交易0次獲得的最大收益，顯然，也都是0。

針對任何一個普遍位置dp[i][j]的值，

我們可以枚舉i位置是否參與交易，如果i位置不參與交易，那麼dp[i][j] = dp[i-1][j]，如果i位置參與交易，那麼i位置一定是最後一次的賣出時機。

那最後一次買入的時機，可以是如下情況：

最後一次買入的時機在i位置，那麼dp[i][j] = dp[i][j-1] - arr[i] + arr[i]

最後一次買入的時機在i-1位置，那麼dp[i][j] = dp[i-1][j-1] - arr[i-1] + arr[i]

最後一次買入的時機在i-2位置，那麼dp[i][j] = dp[i-2][j-1] - arr[i-2] + arr[i]

...

最後一次買入的時機在0位置，那麼dp[i][j] = dp[0][j-1] - arr[0] + arr[i]

完整代碼如下：

上述代碼中包含一個枚舉行為

增加了時間復雜度，我們可以優化這個枚舉。

我們可以舉一個具體的例子來說明如何優化，

比如，

當我們求dp[5][3]這個值，我們可以枚舉5位置是否參與交易，假設5位置不參與交易，那麼dp[5][3] = dp[4][3]，假設5位置參與交易，那麼5位置一定是最後一次的賣出時機。那最後一次買入的時機，可以是如下情況：

最後一次買入的時機在5位置，那麼dp[5][3] = dp[5][2] - arr[5] + arr[5]

最後一次買入的時機在4位置，那麼dp[5][3] = dp[4][2] - arr[4] + arr[5]

最後一次買入的時機在3位置，那麼dp[5][3] = dp[3][2] - arr[3] + arr[5]

最後一次買入的時機在2位置，那麼dp[5][3] = dp[2][2] - arr[2] + arr[5]

最後一次買入的時機在1位置，那麼dp[5][3] = dp[1][2] - arr[1] + arr[5]

最後一次買入的時機在0位置，那麼dp[5][3] = dp[0][2] - arr[0] + arr[5]

我們求dp[4][3]這個值，我們可以枚舉4位置是否參與交易，假設4位置不參與交易，那麼dp[4][3] = dp[3][3]，假設4位置參與交易，那麼4位置一定是最後一次的賣出時機。那最後一次買入的時機，可以是如下情況：

最後一次買入的時機在4位置，那麼dp[4][3] = dp[4][2] - arr[4] + arr[4]

最後一次買入的時機在3位置，那麼dp[4][3] = dp[3][2] - arr[3] + arr[4]

最後一次買入的時機在2位置，那麼dp[4][3] = dp[2][2] - arr[2] + arr[4]

最後一次買入的時機在1位置，那麼dp[4][3] = dp[1][2] - arr[1] + arr[4]

最後一次買入的時機在0位置，那麼dp[4][3] = dp[0][2] - arr[0] + arr[4]

比較dp[5][3]和dp[4][3]的依賴關系，可以得到如下結論：

假設在求dp[4][3]的過程中，以下遞推式的最大值我們可以得到

dp[4][2] - arr[4]

dp[3][2] - arr[3]

dp[2][2] - arr[2]

dp[1][2] - arr[1]

dp[0][2] - arr[0]

我們把以上式子的最大值定義為best，那麼

dp[5][3] = Math.max(dp[4][3],Math.max(dp[5][2] - arr[5] + arr[5], best + arr[5]))

所以dp[5][3]可以由dp[4][3]加速得到，

同理，

dp[4][3]可以通過dp[3][3]加速得到，

dp[3][3]可以通過dp[2][3]加速得到，

dp[2][3]可以通過dp[1][3]加速得到，

dp[1][3]可以很簡單得出，dp[1][3]有如下幾種可能性:

可能性1，1位置完全不參與，則

可能性2，1位置作為最後一次的賣出時機，買入時機是1位置

可能性3，1位置作為最後一次的賣出時機，買入時機是0位置

此時，best的值為

然後通過dp[1][3]加速dp[2][3]，通過dp[2][3]加速dp[3][3]......，所以二維dp的填寫方式是按列填，

先填dp[1][0]，dp[1][2]一直到dp[1][k]，填好第一列；

然後填dp[2][0],dp[2][1]一直到dp[2][k]，填好第二列；

...

依次填好每一列，直到填完第N-1列。

枚舉行為被優化，優化枚舉後的完整代碼如下：

主要思路：上一個問題中，令k=2就是本題的答案。

主要思路：因為有了冷凍期，所以每個位置的狀態有如下三種：

定義三個數組，分別表示i位置這三種情況下的最大值是多少

顯然有如下結論：

針對一個普遍位置i

最大收益就是如上三種方式的最大值。完整代碼見：

由於三個數組有遞推關系，所以可以用三個變數替換三個數組，做空間壓縮，優化後的代碼如下：

主要思路：由於沒有冷凍期，所以在i位置的時候，狀態只有兩種

針對0位置

針對普遍位置i

完整代碼如下：

同樣的，兩個數組都有遞推關系，可以做空間壓縮，簡化後的代碼如下：

原文鏈接：買賣股票的最佳時機系列問題 - Grey Zeng - 博客園