線性搜索的計算方法

『壹』 C語言編程：輸入一個整數，輸出這幾個數的和，例如1987，1+9+8+7=25

第一題：
#include<stdio.h>
void
main()
{
int
a;
int
sum=0;
scanf("%d",&a);
while(a!=0)
{
sum=sum+a%10;
a=a/10;
}
printf("%d\n",sum);
}
第二題：
#include<stdio.h>
void
main()
{
int
a[10],i;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<10;i++)
if(a[i]%3==0&&a[i]%5!=0)
printf("%d\t",a[i]);
}
第三題：
方法一：線性查找法是最簡單的查找方法。若在一個一維數組中查找給定的值x，過程是：先從第一個元素查起，看它是否等於x，若等於x，即找到了，否則，接著查第二個元素……線配旅飢性查找法不要求被操作的數組已排序。
#include<stdio.h>
void
main()
{
int
a[10]={12,4,23,56,34,2,15,68,56,1};
int
x,i,flag=0;
scanf("%d",&x);
for(i=0;i<10;i++)
if(a[i]==x)
{
flag=1;
break;
}
if(flag==0)printf("not
found.\n");
else
printf("a[%d]=%d\n",i,a[i]);
}
方法二：.二分法：­
當數據量很大適宜採用該方法。採用二分法查找時，數據需是排好序的。­
基本思想：假設數據是按升序排序的，對於給定值x，從序列的中間位置開始比較，如果當前位置值等於x，則查找成功；若x小於當前位置值，則在數列的前半段中查找；若x大於當前位置值則在數列的後半段中繼續查找­，直到找到為止。­
假如有一組數為3，12，24，36，55，68，75，88要查給定的值24.可設三個變數front，mid，end分別指向數據的上界，中間和下界鎮旅，mid=（front+end）/2.­
1.開始令front=0（指向3），end=7（指向88），則mid=3（指向36）。因為mid>x，故應在前半段中查找。­
2.另新的end=mid-1=2，而front=0不變，則新的mid=1。此時x>mid，故確定應在後半段中查找。­
3.令新的front=mid+1=2，而end=2不變，則新的mid=2，此時a[mid]=x，查找成功。­
如果要查找的數不是數列中的數，例如x=25，當第三次判斷時，x>a[mid]，按以上規律，令front=mid+1，即front=3，出現front>end的情況，表示查找不成功。­
例：在有序的有N個元素的數組中查找用戶輸進去的數據x。­
演算法如下：­
1.確定查找范圍front=0，end=N-1，計算中項培返mid（front+end）/2。­
2.若a[mid]=x或front>=end,則結束查找；否則，向下繼續。­
3.若a[mid]<x,說明待查找的元素值只可能在比中項元素大的范圍內，則把mid+1的值賦給front，並重新計算mid，轉去執行步驟2；若a[mid]>x，說明待查找的元素值只可能在比中項元素小的范圍內，則把mid-1的值賦給front，並重新計算mid，轉去執行步驟2。­
#include<stdio.h>
#define
N
8
void
main()
{
int
a[N];
int
front,end,mid,x,i;
printf("請輸入已排好序的a數組元素\n");
for(i=0;i<N;i++)
scanf("%d",&a[
i
]);
printf("請輸入待查找的數x\n");
scanf("%d",&x);
front=0;end=N-1;
mid=(front+end)/2;
while(front<end&&a[mid]!=x)
{
if(a[mid]<x)front=mid+1;
if(a[mid]>x)end=mid-1;
mid=(front+end)/2;
}
if(a[mid]!=x)printf("沒找到。\n");
else
printf("找到了，在第%d項里。\n",mid+1);
}

『貳』 梯度下降中的線性搜索計算學習率是怎麼理解

梯度下降法是一個最優化演算法，通常也稱為最速下降法。最速下降法是求解無約束優化問題最簡單和最古老的方法之一，雖然現在已經不具有實用性，但是許多有效演算法都是以它為基礎進行改進和修正而得到的。最速下降法是用負梯度方向為搜索方向的，最速下降法越接近目標值，步長越小，前進越慢。
梯度下降法可以用於求解非線性方程組。
顧名思義，梯度下降法的計算過程就是沿梯度下降的方向求解極小值（也可以沿梯度上升方向求解極大值）。

表示梯度方向上的中首槐搜索步長。梯度方向我們可以通過對函數求導得到，步長的確定比較麻煩，太大了的話可能會發散，太小收斂速度又太慢。一般確定步長的方法是由線性搜索演算法來確定，即把下一個點的坐標看做是ak+1的函數，然後求滿足f(ak+1)的最小值即可。
因為一般情況下，梯度向量為0的話說明是到了一個極值點，此時梯度的幅值也為0.而採用梯度下降演算法進行最優化求解時，演算法迭代的終止條件是梯度向量的幅芹笑值接近0即可，可以設置個非常小賣友的常數閾值。

『叄』 線性搜索的演算法步驟

procerelinearsearch(x:整數,a1,a2,...,an:不罩賀猛同整數)
i:=1
while(i<=n&&x=/(不等於)ai)
i:=i+1
ifi<=nthenlocation:=i
elselocation:=0
{location是等於拍戚x的下標,或是0(找不到)}
最物橋壞情況下使用O(n)次比較,2分搜索演算法最壞情形復雜度O(logn)次比較,2分搜索演算法比之線性搜索最壞情況下要好.

『肆』 數學優化問題(最優化問題)

  數學優化（Mathematical Optimization）問題，也叫最優化問題，是指在一定約束條件下，求解一個目標函數的最大值（或最小值）問題。
  數學優化問題的定義為：給定一個目標函數（也叫代價函數） f : A → R ，尋找一個變數（也叫參數） x ^∗ ∈ D ，使得對於所有 D 中的 x ， f(x ^∗ ) ≤ f(x) （最小化）；或者 f(x ^∗ ) ≥ f(x) （最大化），其中 D 為變數 x 的約束集，也叫可行域； D 中的變數被稱為是可行解。

  根據輸入變數 x 的值域是否為實數域，數學優化問題可以分為離散優化問題和連續優化問題。

  離散優化（Discrete Optimization）問題是目標函數的輸入變數為離散變數，比如為整數或有限集合中的元素。連續優化（Continuous Optimization）問題是目標函數的輸入變數為連續變數 x ∈ R ^d ，即目標函數為實函數。離散優化問題主要有兩個分支：

  離散優化問題的求解一般都比較困難，優化演算法的復雜度都比較高。後面的內容主要以連續優化為主。

  在連續優化問題中，根據是否有變數的約束條件，可以將優化問題分為無約束優化問題和約束優化問題。
   無約束優化問題（Unconstrained Optimization） 的可行域為整個實數域 D = R ^d ，可以寫為
其中 x ∈ R ^d 為輸入變數， f : R ^d → R 為目標函數。
   約束優化問題（Constrained Optimization） 中變數 x 需要滿足一些等式或不等式的約束。約束優化問題通常使用拉格朗日乘數法來進行求解。

  如果目標函數和所有的約束函數都為線性函數，則該問題為 線性規劃問題（Linear Programming） 。相反，如果目標函數或任何一個約束函數為非線性函數，則該問題為 非線性規劃問題（Nonlinear Programming） 。
  在非線性優化問題中，有一類比較特殊的問題是 凸優化問題（Convex Programming） 。在凸優化問題中，變數 x 的可行域為凸集，即對於集合中任意兩點，它們的連線全部位於在集合內部。目標函數 f 也必須為凸函數，即滿足
  凸優化問題是一種特殊的約束優化問題，需滿足目標函數為凸函數，並且等式約束函數為線性函數，不等式約束函數為凹函數。

   優化問題 一般都是通過 迭代 的方式來求解：通過猜測一個初始的估計 x ₀ ，然後不斷迭代產生新的估計 x ₁ , x ₂ , · · · x _t ，希望 x _t 最終收斂到期望的最優解 x ^∗旅散納 。一個好的優化演算法應該是在 一定的時間或空間復雜度下能夠快速准確地找到最優解。同時，好的優化演算法受初始掘培猜測點的影響較小，通過迭代能穩定地找到最優解 x ^∗ 的鄰域，然後迅速收斂於 x ^∗ 。
  優化演算法中常用的迭代方法有 線性搜索和置信域方法 等。線性搜索的策略是尋找方向和步長，具體演算法有梯度下降法、牛頓拆沒法、共軛梯度法等。

  對於很多非線性優化問題，會存在若干個局部的極小值。局部最小值，或局部最優解 x ^∗ 定義為：存在一個δ > 0，對於所有的滿足|| x − x∗|| ≤ δ 的 x ，公式 f(x ^∗ ) ≤ f(x) 成立。也就是說，在 x ^∗ 的附近區域內，所有的函數值都大於或者等於 f(x ^∗ ) 。對於所有的 x ∈ A ，都有 f(x∗) ≤ f(x) 成立，則 x ^∗ 為全局最小值，或全局最優解。一般的，求局部最優解是容易的，但很難保證其為全局最優解。 對於線性規劃或凸優化問題，局部最優解就是全局最優解 。

『伍』 牛頓法、黃金分割法、二次插值法實驗（最優化1）

在生產過程、科學實驗以及日常生活中，人們總希望用最少的人力、物力、財力和時間去辦更多的事，獲得最大的效益，，所以最優化理論和方法日益受到重視。

無約束最優化計算方法是數隱森值計算領域中十分活躍的研究課題之一，快速的求解無約束最優化問題，除了自身的重要性以外，還體現在它也構成一些約束最優化問題的子問題。因此，對於無約束最優化問題，如何快速高精度的求解一直是優化工作者十分關心的事。本文驗證求解 一維無約束最優化問題 的三種線性搜索方法，分別是牛頓法、黃金分割法，二次插值法。

min ⁡f(x)=3x ⁴ - 4x ³ -12x ²

牛頓迭代法（Newton』s method）又稱為牛頓-拉夫遜方法（Newton-Raphson method）,它是牛頓在17世紀提出的一種在實數域和復數域上近似求解方程的方法,其基本思想是利用目標函數的二次Taylor展開，並將其極小化。牛頓法使用函數 f(x)的泰勒級數的前面幾項來尋找方程 "f(x)=0" 的根。牛頓法是求方程根的重要方法之一，其困改最大優點是在方程 "f(x)=0" 的單根附近具有平方收斂，而且該法還可以用來求方程的重根、復根，此時非線性收斂，但是可通過一些方法變成線性收斂。

方程 f(x)=0 的根 x ^* 可解釋為曲線y=f(x)軸的焦點的橫坐標。如下圖：

設 x[k]是根 x ^* 的某個近似值，過曲線 y=f(x)上橫坐標為 x[k]的點P[k]引切線，並將該切線與 x軸的交點 的橫坐標 x_{k+1}_作為 x ^* 的新的近似值。鑒於這種幾何背景，牛頓法亦稱為切線法。

將f(x ^k+1 )在x=x ^k 處一階泰勒展開：

公式不打了
令函數趨於0，求與x軸交點：

分別取-1.5,0.4,1.0,1.6,2.8

在凸函數很初始點選取好的情況下，收斂快。

Ø 計算二階導數，計算量大

Ø 要求函數二階可微

Ø 收斂性與初始點選取有關

黃金分割法適用於[a,b]區間上的任何單股函數求極小值問題，對函數除要求「單峰」外不做其他要求，甚至可以不連續。因此，這種方法的適應面非常廣。黃金分割法也是建立在區間消去法原理基礎上的試探方法，即在搜索區間 ？內適當插入兩點 ？，並計算其函數值。 ？將區間分成三段，應用函數的單峰性汪攜判質，通過函數值大小的比較，刪去其中一段，是搜索區間得以縮小。然後再在保留下來的區間上作同樣的處理，如此迭代下去，是搜索區間無限縮小，從而得到極小點的數值近似解。

一 維搜索是解函數極小值的方法之一，其解法思想為沿某一已知方向求目標函數的極小值點。一維搜索的解法很多，這里主要採用黃金分割法（0.618法）。如圖所示

黃金分割法是用於一元函數 ？在給定初始區間 ？內搜索極小點？的一種方法。其基本原理是：依照「去劣存優」原則、對稱原則、以及等比收縮原則來逐步縮小搜索區間。

具體步驟是：在區間 ？內取點： ？分為三段。如果 ？,令？；如果 ？，令 <？,如果 ？都大於收斂精度？重新開始。因為 ？為單峰區間，這樣每次可將搜索區間縮小0.618倍或0.382倍，處理後的區間都將包含極小點的區間縮小，然後在保留下來的區間上作同樣的處理，如此迭代下去，將使搜索區 ？逐步縮小，滿足預先給定的精度時，即獲得一維優化問題的近似最優解。

[-2,0],[1,3]

很巧妙地使每次分割點都為上次的黃金分割點，可以復用上次運算的結果，簡化計算。它是優化計算中的經典演算法，以演算法簡單、收斂速度均勻、效果較好而著稱，是許多優化演算法的基礎，但它只適用於一維區間上的凸函數，即只在單峰區間內才能進行一維尋優，其收斂效率較低。

在求解一元函數?的極小點時，在搜索區間中用低次（通常不超過三次）插值多項式?來近似目標函數，後求該多項式的極小點（比較容易計算），並以此作為目標函數?的近似極小點。如果其近似的程度尚未達到所要求的精度時，反復使用此法，逐次擬合，直到滿足給定的精度時為止。

考慮二次多項式

則

令 ，得 。這意味著我們要求a，b。
今考慮在包含 的極小點 的搜索區間 中，給定三個點 ， ， ，滿足
< <
> <
利用三點處的函數值 ， ， 構造二次函數，並要求插值條件滿足

令 ，i=1,2,3。解上述方程組得

於是，二次函數 的極小點為

設 。求得 和 以後，如果
≤ ，當 > 時，
或者如果
≤ ，當 < 時。
則我們認為收斂准則滿足。如果 < ,則極小點估計為 ，否則為 。
若終止准則不滿足，則利用 提供的信息，從 ， ， 和 中選出相鄰的三個點，將原來的搜索區間縮小，然後重復上述過程，直到終止准則滿足為止。

初始步 給出?，?，?，滿足上述設計步驟。
步1 由上述設計步驟計算?。
步2 比較?和?的大小，如果?>?，則轉步3；否則轉步4。
步3 如果?≤?，則
?，?，?，?，
轉步5；否則?，?，轉步5。
步4 若?，則
?，?，?，?，
轉步5；否則?，?，轉步5。
步5 如果收斂准則滿足，停止迭代；否則轉步1，在新的搜索區間[?,?]上按公式計算二次插值函數的極小點?。

-2.5,-1.4,-0.3
-0.3,1.5,3.3.

插值法僅需計算函數值，不涉及導數、Hesse矩陣等的計算，計算起來相對比較簡單，能夠適用於非光滑和導數表達式復雜或表達式寫不出等種種情形。

當迭代步數較多時，計算過程比較復雜，計算量較大，計算起來比較麻煩。當迭代點離目標函數的最優解較遠時，追求線性搜索的精度反而會降低整個演算法的效率。

用符號推導畫圖

picture.py

Gold_ratio.py

Newton.py

Polynomial_interpolation.py