基礎算法(二)
主要內容：
1.迭代法
2.蠻力法
3.分治法
4.貪心法
5.動態規劃
1.迭代法
迭代法也稱“輾轉法”，是一種不斷用變量的舊值遞推出新值得解決問題的方法，一般用于數學計算。它是我們早已熟悉的算法策略，累加、累乘都的迭代算法的基礎應用。利用迭代算法策略解決問題，設計工作主要有3步：
1.確定迭代模型：根據問題描述，分析得出前一個（或幾個）值與其下一個值的迭代關系數學模型。
2.建立迭代關系式：遞推數學模型一般是帶下標的字母，算法設計中要將其轉化為"循環不變式"——迭代關系式。迭代關系式就是一個直接或間接地不斷由舊值遞推出新值得表達式，存儲新值得變量稱為迭代變量。
3.對迭代過程進行控制：確定在什么時候結束迭代過程。迭代過程的控制通常可分為兩種情況：一種是已知或可以計算出所需的迭代次數，通過構建一個固定次數的循環來實現對迭代過程的控制。另一種是所需的迭代次數無法確定，需要分析出迭代過程的結束條件，有時還需考慮得不到目標解的情況，避免出現迭代過程的死循環。
穿越沙漠問題：
一輛吉普車穿越1000km的沙漠。吉普車的總裝油量為500加侖，耗油率為1加侖/km,由于沙漠中沒有油庫，必須先用這輛車在沙漠中建立臨時油庫。若吉普車用最少的耗油量穿越沙漠，應該在哪些地方建立油庫，以及各處存儲的油量。
對于這個問題，我們從終點開始倒著推解儲油點的位置及儲油量。根據耗油量最少的目標進行分析，從后（終點）向前（起點）分段討論：
第一段長度為500km且第一個加油點儲油量為500加侖。
第二段中，為了儲備油，吉普車在這段行程中必須有往返。這段一共走3次：第一、二次來回耗油量為裝載量的2/3，儲油量則為裝載量的1/3，第三次單向行駛耗油量為裝載量的1/3，儲油量為裝載量的2/3，這樣第二個加油點的儲油量為1000加侖，長度為500/3km
第三段與第二段思路相同。這一段共走5次：第一、二次來回耗油量為裝載量的2/5，儲油量為裝載量的3/5，第三、四次來回耗油量為裝載量的2/5，儲油量為裝載量的3/5，第五次單向行駛耗油量為裝載量的1/5，儲油量為裝載量的4/5，這樣第三個加油點儲油量為1500加侖，長度為500/5km
..........
綜上分析，從終點開始分別間隔500，500/3，500/5 ...(km)設立儲油點，每個儲油點的油量為500，1000，1500...
#include<stdio.h>
int main()
{
int dis, k, oil,i;
int distances[10], oilquantities[10];
dis = 500; k = 1; oil = 500;
do
{
distances[k] = 1000 - dis;
oilquantities[k] = oil;
k = k + 1;
dis = dis + 500 / (2 * k - 1);
oil = 500 * k;
} while (dis<1000);
oil = 500 * (k - 1) + (1000 - dis)*(2 * k - 1);
distances[k] = 0;
oilquantities[k] = oil;
for (i = k; i>=1; i--)
{
printf("storepoint: %d, distance: %d, oilquantity: %d\n", k+1-i, distances[i],oilquantities[i]);
}
return 0;
} 牛頓迭代法：
牛頓迭代公式：Xn+1=Xn-f(Xn)/f'(Xn)
下面給出求形如a*x^3+b*x^2+c*x+d=0方程根的算法，求x在1附近的一個實根。
#include<stdio.h>
#include<math.h>
float f(float a, float b, float c, float d)
{
float x1 = 1, x0, f0, f1;
do
{
x0 = x1;
f0 = ((a*x0 + b)*x0 + c)*x0 + d;
f1 = (3 * a*x0 + 2 * b)*x0 + c;
x1 = x0 - f0 / f1;
} while (fabs(x1-x0)>=exp(-4));
return x1;
}
int main()
{
float a, b, c, d, fx;
printf("輸入系數a,b,c,d:");
scanf("%f%f%f%f", &a, &b, &c, &d);
fx = f(a, b, c, d);
printf("方程的根為:%f\n", fx);
} 2.蠻力法
蠻力法是基于計算機運算速度快的特點，在解決問題時采用的一種“懶惰”策略，它幾乎不經過思考，把問題的所有情況交給計算機去嘗試，從中找出問題的解。蠻力策略的應用范圍很廣，比如選擇排序，冒泡排序，插入排序，順序查找、樸素的字符串匹配等等。在這里我們簡單了解一下蠻力策略中的枚舉法。
枚舉法就是根據問題中的條件將可能的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解，有時候還需要進一步考慮，排除一些明顯不合理的情況，盡量減少問題可能解的列舉數目。用枚舉法解決問題：
1.找出枚舉范圍：分析問題所涉及的各種情況
2.找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達式表示
百錢百雞問題：
雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何？
#include<stdio.h>
int main()
{
int x, y, z;
for (x = 1; x <= 20; x++)
{
for (y = 1; y <= 33; y++)
{
z = 100 - x - y;
if (z % 3 == 0 && 5 * x + 3 * y + z / 3 == 100)
printf("the cock number is %d,the hen number is %d,the chick number is %d\n",x,y,z);
}
}
} 數字謎：
ABCAB*A=DDDDDD
#include<stdio.h>
int main()
{
int A, B, C, D;
long E, F;
for (A = 3; A <= 9; A++)
for (D = 1; D <= 9; D++)
{
E = D * 100000 + D * 10000 + D * 1000 + D * 100 + D * 10 + D;
if (E%A == 0)
{
F = E / A;
if (F / 10000 == A && (F % 100) / 10 == A)
if ((F / 1000) % 10 == F % 10)
printf("%ld*%d=%ld\n", F, A, E);
}
}
} 3 .分治法
分治法求解問題的過程是，將整個問題分成若干個小問題后分而治之。如果分解得到的子問題相對來說還太大，則可反復使用分治策略將這些子問題分成更小的同類型子問題，直至方便求解的子問題，必要時逐步合并這些子問題的解，從而得到問題的解。
下面是分治法求解的三個步驟：
1.分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題
2.解決：若子問題規模較小而容易被解決則直接解，否則再繼續分解為更小的子問題，直到容易解決。
3.合并：將已求解的各子問題的解，逐步合并為原問題的解。
適合用分治法策略的問題：
1.能將n個數據分解成k個不同子集合，且得到k個子集合是可以獨立求解的子問題。（1<k<=n）
2.分解得到的子問題與原問題具有相似的結構，便于利用遞歸或循環機制
3.在求出這些子問題的解之后，就可以推解出原問題的解。
下面給出殘缺棋盤和金塊問題的問題描述與具體算法，比較經典的分治法解決的問題還有大整數乘法問題，可以自己研究一下。
殘缺棋盤
殘缺棋盤是一個有2^k*2^k(k>=1)個方格的棋盤，其中恰有一個殘缺。用k=1時各種可能的殘缺棋盤（三格板）去覆蓋更大的殘缺棋盤，要求：1.三格板不能重疊2.三格板不能覆蓋殘缺方格，但必須覆蓋其他所有的方格。
#include<stdio.h>
int amount = 0, Board[100][100];
void Cover(int tr, int tc, int dr, int dc, int size)
{
int s, t;
if (size < 2) return;
amount = amount + 1;
t = amount;
s = size / 2;
if (dr < tr + s&&dc < tc + s)
{
Cover(tr, tc, dr, dc, s);
Board[tr + s - 1][tc + s] = t;
Board[tr + s][tc + s - 1] = t;
Board[tr + s][tc + s] = t;
Cover(tr, tc + s, tr + s - 1, tc + s, s);
Cover(tr + s, tc, tr + s, tc + s - 1, s);
Cover(tr + s, tc + s, tr + s, tc + s, s);
}
else if (dr<tr + s&&dc >= tc + s)
{
Cover(tr, tc + s, dr, dc, s);
Board[tr + s - 1][tc + s - 1] = t;
Board[tr + s][tc + s - 1] = t;
Board[tr + s][tc + s] = t;
Cover(tr, tc, tr + s - 1, tc + s - 1, s);
Cover(tr + s, tc, tr + s, tc + s - 1, s);
Cover(tr + s, tc + s, tr + s, tc + s, s);
}
else if (dr >= tr + s&&dc<tc + s)
{
Cover(tr + s, tc, dr, dc, s);
Board[tr + s - 1][tc + s - 1] = t;
Board[tr + s - 1][tc + s] = t;
Board[tr + s][tc + s] = t;
Cover(tr, tc, tr + s - 1, tc + s - 1, s);
Cover(tr, tc + s, tr + s - 1, tc + s, s);
Cover(tr + s, tc + s, tr + s, tc + s, s);
}
else if (dr >= tr + s&&dc>=tc + s)
{
Cover(tr + s, tc + s, dr, dc, s);
Board[tr + s - 1][tc + s - 1] = t;
Board[tr + s - 1][tc + s] = t;
Board[tr + s][tc + s - 1] = t;
Cover(tr, tc, tr + s - 1, tc + s - 1, s);
Cover(tr, tc + s, tr + s - 1, tc + s, s);
Cover(tr + s, tc, tr + s, tc + s - 1, s);
}
}
void OutputBoard(int size)
{
for (int i = 0; i < size; i++)
{
for (int j = 0; j <size; j++)
{
printf("%6d", Board[i][j]);
}
printf("\n");
}
}
int main()
{
int size = 1, x, y, i, j, k;
scanf("%d", &k);
for (i =1; i <= k; i++)
size = size * 2;
printf("input incomplete pane\n ");
scanf("%d %d", &x, &y);
Cover(0, 0, x, y, size);
OutputBoard(size);
return 0;
} 金塊問題
老板有一袋金塊（共n塊，n是2的冪，n>=2），最優秀的雇員得到其中最重的一塊，最差的雇員得到其中最輕的一塊。用最少的比較次數找出最重和最輕的金塊。
#include<stdio.h>
#define N 8
float a[N] = {4.5,2.3,3.4,1.2,6.7,9.8,5,6};
void maxmin(float &fmax, float &fmin, int i, int j)
{
int mid;
float lmax, lmin, rmax, rmin;
if (i == j)
{
fmax = a[i];
fmin = a[i];
}
else if(i==j-1)
{
if (a[i] < a[j])
{
fmax = a[j];
fmin = a[i];
}
else
{
fmax = a[i];
fmin = a[j];
}
}
else
{
mid = (i + j) / 2;
maxmin(lmax, lmin,i, mid);
maxmin(rmax, rmin,mid + 1, j);
if (lmax > rmax)
fmax = lmax;
else
fmax = rmax;
if (lmin > rmin)
fmin = rmin;
else
fmin = lmin;
}
}
int main()
{
float max, min;
maxmin(max, min, 0, N - 1);
printf("Max=%.1f\nMin=%.1f\n", max, min);
return 0;
} 4.貪心法
貪心法是逐步獲得最優解，解決最優化問題時的一種簡單但適用范圍有限的策略。它沒有固定的算法框架，算法設計的關鍵是貪婪策略的選擇，選擇的貪婪策略要具有無后向性。貪婪策略面對問題僅考慮當前局部信息便做出決策，也就是使用貪婪算法的前提是局部最優策略能導致產生全局最優解。
鍵盤輸入一個高精度的正整數n,去掉其中任意s個數字后剩下的數字按原來左右次序將組成一個新的正整數。編程對給定的n和s，尋找一種方案使得剩下的數字組成的新數最小。
#include<stdio.h>
int length(const char s[])
{
int i = 0;
if (s == NULL)
{
return 0;
}
while (s[i] != '\0')
{
++i;
}
return i;
}
void deleteNum(char* n, int b, int k)
{
int i;
for (i = b;i < length(n) - k;i++)
n[i] = n[i + k];
n[i] = '\0';
}
int main()
{
char n[100];
int s, i, j, j1, c, data[100], len;
scanf("%s", n);
scanf("%d", &s);
len = length(n);
if (s > len)
{
printf("data error");
return 0;
}
j1 = 0;
for (i = 1;i <= s;i++)
{
for (j = 0; j < length(n); j++)
{
if (n[j] >n[j+1])
{
deleteNum(n, j, 1);
if (j >= j1)
data[i] = j + i;
else
data[i] = data[i - 1] - 1;
j1 = j;
break;
}
if (j > length(n))
break;
}
}
for (i = i; i <=s; i++)
{
j = len - i + 1;
deleteNum(n, j, 1);
data[i] = j;
}
while (n[0]=='0'&≤ngth(n)>1)
{
deleteNum(n, 0, 1);
}
printf("\n%s\n", n);
for (i = 1; i <=s; i++)
{
printf("%d ", data[i]);
}
printf("\n");
} 幣種統計問題
某單位給每個職工發工資（精確到元）。為了保證避免臨時兌換零錢，且取款的張數最少，發工資前要統計出所有職工的工資所需各種幣值（100，50，20，10，5，2，1共7種）的張數。
#include<stdio.h>
int main()
{
int i, j, n, GZ, A, B[8] = { 0,100,50,20,10,5,2,1 }, S[8] = { 0,0,0,0,0,0,0,0 };
scanf("%d", &n);
for (i = 1; i <=n;i++)
{
scanf("%d", &GZ);
for (j = 1; j <=7; j++)
{
A = GZ / B[j];
S[j] = S[j] + A;
GZ = GZ - A*B[j];
}
}
for (i = 1; i <=7; i++)
{
printf("%d----%d\n", B[i], S[i]);
}
printf("\n");
} 埃及分數
設計一個算法，把一個真分數表示為埃及分數之和的形式。所謂埃及分數，是指分子為1的分數。如7/8=1/2+1/3+1/24
#include<stdio.h>
int main()
{
int a, b, c,i=0;
printf("input a element:");
scanf("%d", &a);
printf("input denominator:");
scanf("%d", &b);
if (a >= b)
{
printf("input error");
}
else
{
if (a == 1 || b%a == 0)
{
printf("%d/%d=%d/%d\n", a, b, 1, b / a);
}
else
{
while (a!=1)
{
c = b / a + 1;
a = a*c - b;
b = b*c;
printf("1/%d+", c);
if (b%a == 0 || a == 1)
{
printf("1/%d", b / a);
a = 1;
}
}
printf("\n");
}
}
} 5.動態規劃
動態規劃主要針對最優化問題，它的決策不是線性而是全面考慮各種不同的情況分別進行決策，最后通過多階段的決策逐步找出問題的最終解。
適用條件：
最優化原理（最優子結構）
無后向性（某狀態以后過程不會影響以前）
子問題重疊（子問題不獨立，一個子問題在下一階段決策時可能被多次使用到）
基本思想：
把求解的問題分成許多階段或多個子問題，然后按順序求解各子問題。
步驟：
劃分階段（劃分為無后向性若干子階段）
選擇狀態（羅列所出現狀態，要滿足無后效性）
確定決策并寫出狀態轉移方程
0-1背包問題
給定N個物品和一個背包。物品i的重量是Wi ,其價值為Vi ，背包的容量為C。問應該如何選擇裝入背包的物品，使得裝入背包的物品的總價值為最大？（在選擇物品的時候，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品i裝入多次，也不能只裝入物品的一部分。因此，該問題被稱為0-1背包問題。）
#include<stdio.h>
int V[200][200];//前i個物品裝入容量為j的背包中獲得的最大價值
int max(int a, int b)
{
if (a >= b) return a; else return b;
}
int KnapSack(int n, int w[], int v[], int x[], int C)
{
int i, j;
for (i = 0; i <= n; i++) V[i][0] = 0;
for (j = 0; j <= C; j++) V[0][j] = 0;
for (i = 0; i <= n - 1; i++)
for (j = 0; j <= C; j++)
if (j<w[i]) V[i][j] = V[i - 1][j];
else V[i][j] = max(V[i - 1][j], V[i - 1][j - w[i]] + v[i]);
j = C;
for (i = n - 1; i >= 0; i--)
{
if (V[i][j]>V[i - 1][j])
{
x[i] = 1; j = j - w[i];
}
else
x[i] = 0;
}
printf("選中的物品是:\n");
for (i = 0; i < n; i++)
if (x[i])
printf("%d ", i + 1);
printf("\n");
return V[n - 1][C];
}
int main()
{
int n, i, v[200], w[200], x[200], c;
printf("請輸入背包的容量:");
scanf("%d", &c);
printf("請輸入物品的個數:");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d%d", &v[i], &w[i]);
x[i] = 0;
}
KnapSack(n, w, v, x, c);
return 0;
}