三、演算法舉例
（一）窮舉演算法
特點：對問題的所有可能狀態一一測驗，直到找到解或全部可能狀態測驗過為止，
典型問題：搬磚問題
百文百雞問題
百馬百擔問題
一元錢組合問題
大量資料錄入問題
1.某地需要搬運磚塊，已知男人一人搬3塊，女人一人搬2塊，小孩兩人搬一塊，
問用45人正好搬45塊磚，有多少種搬法？
for (men = 0; men <= 45; men++)
第一種方法：使用三重回圈，將男人、女人、小孩的可能狀態全部列舉出來，
for (women = 0; women <= 45; women++)
for (child = 0; child <= 45; child++)
if ((men+women+child45) && (men3+women2+child*0.545))
printf(“men=%d women=%d child=%d\n”, men, women, child);
第二種方法：使用兩重回圈，將男人、女人的可能狀態全部列舉出來，小孩的狀態由條件推導而出，
for (men = 0; men <= 15; men++)
for (women = 0; women <= 22; women++)
{
child = 45 – women – men;
if (men * 3 + women * 2 + child * 0.5 == 45)
printf(“men=%d women=%d child=%d\n”, men, women, child);
}
（二）迭代演算法特點：不斷用新值取代舊值（或舊值遞推出新值）的程序，
典型問題： 銀行利率計算問題
人口增長問題
兔子繁殖問題（Fibonacci數列）
一元方程的迭代解法
例如：1. 現有12億人，每年遞增2%，十年后將有多少人？
初值m=12
m=m*(1+2%) 第一年后人口
m=m*(1+2%) 第二年后人口
2. 一對新生兔子，從第三月開始它們每個月都生一對兔子，按此規律，假設沒有兔子死亡，一年后共有多少兔子？
x1=1,x2=1; 第一個月 第二個月
x=x1+x2 x為當前月，x2為上月， x1為上上月
x1=x2; 新值取代舊值
x2=x; 新值取代舊值
程式代碼：
#include<stdio.h>
int main()
{
long x1,x2,x,i;
x1=1;x2=1;
for(i=1;i<=12;i++)
{
if(i<3) x=1;
else
{
x=x1+x2;
x2=x1;
x1=x;
}
printf(" %5d",x);
}
}
3.二分法解方程
一元多次方程 f(x)=x3-2x2-3=0;
在函式f(x)上任取兩點，須保證f(x1)和f(x2)的值異號，
x=(x1+x2)/2;
若f(x)與f(x1)同號，則x1=x; 否則 x2=x；重復直到f(x)<= ε，
答案：x=2.485544
程式代碼：
#include<math.h>
#define EP 1.0e-5
int main()
{
double x1,x2,x;
double f(double x);
printf(“Please input x1,x2:”);
scanf("%lf%lf",&x1,&x2);
do
{
x=(x1+x2)/2;
if(f(x1)*f(x)>0)
x1=x;
else x2=x;
}while(fabs(f(x))>EP);
printf(" x=%f\n",x);
}
double f(double x)
{
double y;
y=xxx-2xx-3;
return y;
}
- 牛頓迭代法解方程
一元多次方程 f(x)=x3-2x2-3=0;
切線方程y= f(xk)+f’(xk).(x-xk)
與x軸交點 f(xk)+f’(xk).(x-xk)=0
解為x (k+1)=xk-f(xk)/f’(xk);
重復直到f(x)<=ε
答案：x=2.485544
程式代碼：
方程 f(x)=x3-2x2-3=0;
#include<math.h>
#define EP 1.0e-5
main()
{
double x;
double f(double x);
double f1(double x);
printf(“Please input x:”);
scanf("%lf",&x);
do
{
x=x-f(x)/f1(x);
}while(fabs(f(x))>EP);
printf(" x=%f\n",x);
}
double f(double x) /計算f(x)值的函式/
{
double y;
y=xxx-2xx-3;
return y;
double f1(double x) /計算f(x)導數值的函式/
{
double y;
y=3xx-4*x;
return y;
}
5.求兩個正整數的最大公約數（輾轉相除法）
兩個正整數u和v
輾轉相除 例
r=u%v r=10%4 r=4%2
u=v u=4; u=2;
v=r; v=2; v=0;
最后余數為0時，u的值即為兩個數的最大公約數.
程式代碼
#include<stdio.h>
main()
{
int a,b,u,v,r;
printf(“Please input a,b:”);
scanf("%d%d",&a,&b);
u=a;v=b;
do
{
r=u%v;
u=v;
v=r;
}while(r!=0);
printf(" %d and %d gcd is %d\n",a,b,u);
}
6.輸入一個正整數m，判斷它是否為素數，素數：只能被1和自身整除的正整數，1不是素數，2是素數，
演算法：除了1和m，不能被其它數整除，
設 i 取值 [2, m-1]
如果m不能被該區間上的任何一個數整除，即對每個i，m%i 都不為0，則m是素數
只要找到一個i，使m%i為0，則m肯定不是素數
m %2 %3 %4 %5 %(m-1)
不是素數 || =0 =0
是素數 && !=0 !=0
m不可能被大于 m/2 的數整除，故 i可取值 [2, m-1] 、 [2, m/2] 、 [2, sqrt(m)]
/* 判斷正整數m是否為素數 /
#include <stdio.h>
int main(void)
{
int i, m;
printf("Enter a number: "); / 輸入提示 /
scanf ("%d", &m);
for(i = 2; i <= m/2; i++) / 第9行 /
if(m % i == 0) break; / 若m能被某個i整除，則m不是素數，提前結束回圈 /
if(i > m/2)/ 如果回圈正常結束，說明m不能被任何一個i整除，則m是素數 /
printf("%d is a prime number! \n", m);
else
printf(“No!\n”); / 第15行 /
return 0;
}
8. 整數個位分解問題（從高位開始分解）
輸入一個整數，從高位開始逐個數字輸出，例如12345
Step 1: 12345 /10000 = 1
12345 %10000 =2345
Step 2: 2345 /1000 = 2
2345%1000 =345
Step 3: 345 /100 = 3
345%100 =45
Step 4: 45 /10 = 4
45%10 =5
Step 5: 5/1= 5
5%1=0
End
1） 如何得到10000
找輸入資料對應的冪
pow=1; temp = x;
while (x != 0) {
pow = pow * 10;
x =x /10;
}
pow = pow /10;
（2） 每次回圈pow縮小1/10
（3） 直到pow=0結束，
代碼：
#include “stdio.h”
int main()
{
long x,pow,temp;
scanf("%ld",&x);
if(x<0)x=-x;
pow=1;temp=x;
while(x!=0)
{
pow=pow10;
x=x/10;
}
pow=pow/10;
x=temp;
while(pow!=0)
{
printf("%5d",x/pow);
x=x%pow;
pow=pow/10;
}
printf("\n");
return 0;
}
9. 整數個位分解問題（從個位開始分解）
輸入一個整數，從個位開始逐個數字輸出，例如12345
Step 1: 12345 %10 = 5
12345 /10 =1234
Step 2: 1234 % 10 = 4
1234/10 =123
Step 3: 123 % 10 = 3
123/10 =12
Step 4: 12 % 10 = 2
12 /10 =1
Step 5: 1% 10= 1
1/10=0
End /* 統計一個整數的位數 /
程式代碼：
#include <stdio.h>
int main(void)
{
int count, number,m; / count 記錄整數number的位數 /
count = 0;
printf(“Enter a number:”); / 輸入提示 /
scanf ("%d", &number);
if(number < 0) number = -number; / 將輸入的負數轉換為正數 /
do{
m=number%10; / 整數求余得到個位數*/
number = number / 10; /* 整除后減少一位個位數，組成一個新數 /
count ++; / 位數加1 /
printf("%5d", m); / 輸出個位*/
}while(number != 0); /* 判斷回圈條件 */
printf("\nIt contains %d digits.\n", count);
return 0;
}
10. 使用格里高利公式求π的近似值，要求精確到最后一項的絕對值小于10–4，
代碼：
/* 用格里高利公式計算π的近似值，精度要求：最后一項的絕對值小于0.0001 /
#include <stdio.h>
#include <math.h> / 程式中呼叫絕對值函式 fabs，需包含 math.h /
int main( )
{
int i, flag;
double item, pi; / pi 用于存放累加和 /
/ 回圈初始化 /
flag = 1; / flag 表示第 i 項的符號，初始為正，每次回圈改變符號*/
i = 1; /* 表示第 i 項的分母，初始為1 /
item = 1.0; / item 中存放第 i 項的值，初值取 1 /
pi = 0; / 置累加和 pi 的初值為0 */
/* 當|item| ≥ 0.0001時，執行回圈 /
while(fabs(item) >= 0.0001)
{
item = flag * 1.0 /i; / 計算第 i 項的值 /
pi = pi + item; / 累加第 i 項的值 /
flag = -flag; / 改變符號，為下一次回圈做準備 /
i= i + 2; / 分母遞增2 ，為下一次回圈做準備 /
}
pi = pi * 4; / 回圈計算的結果是 pi/4 */
printf (“pi = %f\n”, pi);
return 0;
}
11.階乘計算
/* 使用函式計算 1! + 2! + 3! + … + 100! /
#include <stdio.h>
double fact (int n); / 函式宣告 /
int main(void)
{
int i;
double sum;
sum = 0;
for(i = 1; i <= 100; i++ )
sum = sum + fact (i); / 呼叫fact(i)求i!，共重復100次 /
printf(“1! + 2! + … + 100! = %e\n”, sum); / 用指數形式輸出結果 */
return 0;
}
/* 定義求 n! 的函式 /
double fact (int n)
{
int i;
double result; / 變數 result 中存放階乘的值 /
result = 1; / 置階乘 result 的初值為1 /
for(i = 1; i <= n; i++) / 回圈執行n次，計算n! /
result = result * i;
return result; / 把結果回送主函式 */
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260582.html
標籤：其他
上一篇：理解深度學習中的“卷積神經網路”