一篇文章帶你瞭解論C語言中算法的重要性

Posted on by

一、問題一（打印階乘）

問題描述：

打印出數字一到數字20的階乘

一開始，我總會多打印出一個1，這令我十分苦惱，並且從n等於13開始，數據就開始溢出

問題分析：

讓我們分析一下問題，這裡面存在著兩個問題：

1.多打印出一個1

2.數據溢出

解決方案：

1.讓我們檢查一下結果，發現問題很有可能是循環的時候沒有循環本身

for (i = 1; i < num; i++)//這句話明顯錯瞭

改成

for (i = 1; i <= num; i++) {//i的值要乘以它本身！
			n = n * i;
		}

2.這裡要引入C++中STL庫的一個知識點

常規的32位整數隻能夠處理40億以下的數。

如果遇到比40億要大的數，就要用到C++的64位擴展。不同的編譯器對64位整數的擴展有所不同。這個我也是聽別人科普的，大傢可以站內搜索一下。

優化後的代碼如下：

#include <stdio.h>
void main() {
	__int64 fac(int num);
	int n = 1;
	int num;
	for (num = 0; num <= 20; ++num) {
		printf("%3d! = %I64d\n", num, fac(num));
	}
}
__int64 fac(int num) {
	register __int64 n = 1, i;     //寄存器變量
		for (i = 1; i <= num; i++) {//i的值要乘以它本身！
			n = n * i;
		}
		return n;
}

二、問題二（比較多項式計算時間）

問題描述：

這裡先科普幾個測試代碼中的知識點：

這個表示本程序開始計時：

start = clock();

本程序結束計時：

stop = clock();

clock tick :時鐘打點

CLK_TCK：機器時鐘每秒所走的時鐘打點數

問題分析：

首先這個問題有兩種算法：

直接算

p1 += (pow(x, i)/i);

把x當成公因式提出計算（秦九韶法）

p2 = 1.0/(a[i – 1])+ (x*p2);

然後我發現瞭三個問題：

1.測量不出時間

2.程序重復性高

3.第一種結果和第二種結果不一致

解決方案：

1.讓被測函數重復運行多次，使得測出的總時鐘打點間隔充分長，最後計算被測函數除以運行次數即可得出平均每次的運行時間

duration = ((double)(stop - start)) / CLK_TCK / MAXK;

2.可以通過多設置幾個函數，並調用函數解決問題

3.這是算法的問題

這個地方真的特別容易出錯，我改瞭不知道多少遍。。。。。。

double f2(int n, double a[], double x) {
	int i;
	double p2 = 1.0/a[n];
	for (i = n; i > 0; i--) {
		p2 = 1.0/(a[i - 1])+ (x*p2);//算法思路出毛病瞭（數學）
	}
	return p2;
}

總體的代碼：

#include <stdio.h>
#include <math.h>
#include <time.h>
clock_t start, stop;
double duration;
#define MAXN 101//數組裡元素個數（多項式的系數），如果看n值需要減一，因為有a0
#define MAXK 1000//重復調用的次數
double f1(int n, double a[], double x)
{
	double p1 = a[0];//a[0]都已經算出來瞭,循環從1開始
	for (int i = 1; i <= n; i++) {
		p1 += (pow(x, i)/i);
	}
	return p1;	
}
double f2(int n, double a[], double x) {
	int i;
	double p2 = 1.0/a[n];
	for (i = n; i > 0; i--) {
		p2 = 1.0/(a[i - 1])+ (x*p2);//算法思路出毛病瞭（數學）
	}
	return p2;
}
double ceshijian()
{
	stop = clock();//停止計時
	duration = ((double)(stop - start)) / CLK_TCK / MAXK;//計算單次運行時間
	printf("ticks=%f\n", (double)(stop - start));
	printf("duration=%6.2e\n", duration);
	return 0;
}
int main()
{
	int i;
	double a[MAXN];
	for (i = 0; i < MAXN; i++) {
		a[i] = (double)i;
	}//輸入的早就是i值瞭
	a[0] = 1;
	//不在測試范圍內的準備工作寫在clock()調用之前
	start = clock();//開始計時
	for (int i = 0; i < MAXK; i++)//重復調用
		f1(MAXN - 1, a, 1.1);//被測函數,這裡如果寫數組的話就越界瞭，而且要調用某個值是不確定的,隻能寫a,因為要定義的就是a值
	printf("第一種結果為%f\n", f1(MAXN - 1, a, 1.1));
	ceshijian();

	start = clock();//開始計時
	for (i = 0; i < MAXK; i++)
		f2(MAXN - 1, a, 1.1);//被測函數,這裡如果寫數組的話就越界瞭，而且要調用某個值是不確定的
	printf("第二種結果為%f\n", f2(MAXN - 1, a, 1.1));
	ceshijian();
	return 0;
}

結果如下

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：