五大演算法基本思想舉例

1. 希爾排序的詳解

希爾排序基本思想：先取一個小於n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序；然後，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。

舉例說明：

對於這樣一個無序的數組5932611817410，想把它變成順序遞增的數組1234567891011。先隔3個元素取一次：把5284取了出來，往後搓一位，把96110取出來，再往後搓一位，又把3117取出來。分別對這三個小組排序成為遞增的序列，再插回去，如圖：

於是得到了第一趟排序的結果：2134675911810.現在再以2為間隔重復以上步驟（這次得到的是兩個小組）得到了2134576811910。最後再以1為間隔再搞一次（實際上這一步就是從左到右兩兩比較，調整位置），就得到了想要的結果。

這就是希爾排序，其要義就是先進行宏觀調整，再進行微觀調整。

2. 兩個數最大公因數怎麼找

找兩個數的最大公因數可以通過歐幾里得演算法（輾轉相除法）實現。

本文將從演算法流程、應用舉例等角度進行介紹，並提供拓展知識，幫助讀者全面了解最大公因數的概念和計算方法。

一、歐幾里得演算法流程

1.輾轉相除法

歐幾里得演算法，也稱為輾轉相除法，是一種計算兩個整數的最大公約數的演算法。其基本思想是：假設兩個整數為a和b，如果a>b，則a和b的最大公因數等於b和a%b（a除以b取余）的最大公因數。

如果b>a，則a和b的最大公因數等於a和b%a（b除以a取余）的最大公因數。不斷重復這個過程，直到其中一個數為0時停止，此時另一個非零數即為這兩個數的最大公因數。

三、拓展知識

1.最大公約數的性質

最大公因數有以下幾個基本性質：

（1）互質性：兩個數a、b的最大公約數為1時，稱a和b互質。

（2）倍數性：設p是正整數，a、b為整數，則(a*p,b*p)的最大公約數等於p*(a,b)。

（3）整除性：若a整除b，則(a,b)=a。

2.歐幾里得演算法適用范圍

歐幾里得演算法適用於計算整數之間的最大公約數。

3. 用窮舉法求解問題的基本過程

1．If語句和For語句

If語句在窮舉演算法中一般用塊結構居多，形式為：If條件Then

Else語句可以沒有

End If

For語句結構形式為：

For循環變數＝初值To終值Step步長

循環體語句

Next循環變數

3．窮舉演算法的應用

(1)使用窮舉演算法時，可能解的范圍是非常明確的，可能解的個數也是有限的，否則無法用此演算法。

(2)窮舉演算法應用舉例：猜密碼、尋找有特定要求的數字、最優方案等。

4. 5.貪心演算法的核心思想。6.什麼是遞歸什麼是迭代兩者的區別，舉例說明。7.回溯的含義是什麼舉例

1、貪心演算法主要是把問題分成很多局部問題，用局部最優解合成整體最優解。因此使用這種演算法需要此問題滿足兩個條件，一個是能夠分成多個能夠求解的局部問題，第二個就是局部問題的解能夠合成最優解。和動態規劃、回溯等相比差別就是再不回溯的前提下找出整體最優解或者接近最優解，速度快但應用有比較大的限制。

2、迭代也叫遞推，通過重復執行某一步驟或者函數來求得計算結果
遞歸是指函數中直接或者間接調用自身
舉例：
求a乘以2的10次方等於幾
迭代：
for (i=0;i<10;i++)
a *= 2;

遞歸：
int db(int a,int num)
{
if (num<10)
return 2 * db(a,num+1);
else
return 1;
}

db(a,0);

3、回溯的含義就是在搜索問題的狀態過程中，如果不能繼續前進，再向後回到岔口，換一條路繼續搜索，直到搜索完所有狀態或者查找到需要的狀態。
舉例：（最典型的就是樹的深度搜索，下面舉一個簡單的例子）
int a[10]={5,3,7,9,3,2,5,6,9,1};//從3開始查找1
int read[10]=(0);//是否查找過
int readNum = 0;//查找過的個數
int forward = 1;//1為左，2為右
int tmp = 0,index = 5;

tmp = a[index];
read[index] = 1;
readNum++;
while (tmp != 1 || readNum != 10)
{
if (forward == 1)
index --;
else
index++;
if (!read[index])
{
tmp = a[index];
read[index] = 1;
readNum++;
}

if (index <=0 || index>=9)
forward = 3 - forward;
}

5. 舉例說明演算法的應用

舉例說明演算法的應用如下：

1、遞推演算法（常用級數、數列求和、二分法、梯形積分法、窮舉法等）。

2、排序演算法（選擇法、冒泡法）。

3、查找演算法（順序查找、折半查找）。

4、有序數列的插入、刪除操作。

5、初等數論問題求解的有關演算法（最大數、最小數、最大公約數、最小公倍數、素數等）。

6、矩陣的處理（生成、交換及基本運算）。

演算法雹盯虛中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機則御化演算法在內的一些演算法，包含了一些隨機輸入。