快捷導(dǎo)航

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

更新時(shí)間：2021年08月13日 17:00:46 作者：風(fēng)起FQ

最近一直在學(xué)數(shù)據(jù)結(jié)構(gòu)與算法，深深的感受到我們學(xué)習(xí)語言，永遠(yuǎn)都只是一項(xiàng)工具，方法才是其中最重要的部分。這篇文章我將會(huì)通過幾個(gè)例子來說明算法，也就是寫程序的思路在程序中的重要意義

一、問題一（打印階乘）

問題描述：

打印出數(shù)字一到數(shù)字20的階乘

一開始，我總會(huì)多打印出一個(gè)1，這令我十分苦惱，并且從n等于13開始，數(shù)據(jù)就開始溢出

問題分析：

讓我們分析一下問題，這里面存在著兩個(gè)問題：

1.多打印出一個(gè)1

2.數(shù)據(jù)溢出

解決方案：

1.讓我們檢查一下結(jié)果，發(fā)現(xiàn)問題很有可能是循環(huán)的時(shí)候沒有循環(huán)本身

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

改成

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

2.這里要引入C++中STL庫的一個(gè)知識(shí)點(diǎn)

常規(guī)的32位整數(shù)只能夠處理40億以下的數(shù)。

如果遇到比40億要大的數(shù)，就要用到C++的64位擴(kuò)展。不同的編譯器對(duì)64位整數(shù)的擴(kuò)展有所不同。這個(gè)我也是聽別人科普的，大家可以站內(nèi)搜索一下。

優(yōu)化后的代碼如下：

#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;
}

二、問題二（比較多項(xiàng)式計(jì)算時(shí)間）

問題描述：

這里先科普幾個(gè)測(cè)試代碼中的知識(shí)點(diǎn)：

這個(gè)表示本程序開始計(jì)時(shí)：

start = clock();

本程序結(jié)束計(jì)時(shí)：

stop = clock();

clock tick :時(shí)鐘打點(diǎn)

CLK_TCK：機(jī)器時(shí)鐘每秒所走的時(shí)鐘打點(diǎn)數(shù)

問題分析：

首先這個(gè)問題有兩種算法：

直接算

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

把x當(dāng)成公因式提出計(jì)算（秦九韶法）

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

然后我發(fā)現(xiàn)了三個(gè)問題：

1.測(cè)量不出時(shí)間

2.程序重復(fù)性高

3.第一種結(jié)果和第二種結(jié)果不一致

解決方案：

1.讓被測(cè)函數(shù)重復(fù)運(yùn)行多次，使得測(cè)出的總時(shí)鐘打點(diǎn)間隔充分長(zhǎng)，最后計(jì)算被測(cè)函數(shù)除以運(yùn)行次數(shù)即可得出平均每次的運(yùn)行時(shí)間

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

2.可以通過多設(shè)置幾個(gè)函數(shù)，并調(diào)用函數(shù)解決問題

3.這是算法的問題

這個(gè)地方真的特別容易出錯(cuò)，我改了不知道多少遍。。。。。。

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);//算法思路出毛病了（數(shù)學(xué)）
	}
	return p2;
}

總體的代碼：

#include <stdio.h>
#include <math.h>
#include <time.h>
clock_t start, stop;
double duration;
#define MAXN 101//數(shù)組里元素個(gè)數(shù)（多項(xiàng)式的系數(shù)），如果看n值需要減一，因?yàn)橛衋0
#define MAXK 1000//重復(fù)調(diào)用的次數(shù)
double f1(int n, double a[], double x)
{
	double p1 = a[0];//a[0]都已經(jīng)算出來了,循環(huán)從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);//算法思路出毛病了（數(shù)學(xué)）
	}
	return p2;
}
double ceshijian()
{
	stop = clock();//停止計(jì)時(shí)
	duration = ((double)(stop - start)) / CLK_TCK / MAXK;//計(jì)算單次運(yùn)行時(shí)間
	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;
	//不在測(cè)試范圍內(nèi)的準(zhǔn)備工作寫在clock()調(diào)用之前
	start = clock();//開始計(jì)時(shí)
	for (int i = 0; i < MAXK; i++)//重復(fù)調(diào)用
		f1(MAXN - 1, a, 1.1);//被測(cè)函數(shù),這里如果寫數(shù)組的話就越界了，而且要調(diào)用某個(gè)值是不確定的,只能寫a,因?yàn)橐x的就是a值
	printf("第一種結(jié)果為%f\n", f1(MAXN - 1, a, 1.1));
	ceshijian();

	start = clock();//開始計(jì)時(shí)
	for (i = 0; i < MAXK; i++)
		f2(MAXN - 1, a, 1.1);//被測(cè)函數(shù),這里如果寫數(shù)組的話就越界了，而且要調(diào)用某個(gè)值是不確定的
	printf("第二種結(jié)果為%f\n", f2(MAXN - 1, a, 1.1));
	ceshijian();
	return 0;
}

結(jié)果如下