驗證性實驗

求1~n的連續整數和

說明

對于給定的正整數n，求$1+2+\dots +n$，采用逐個累加和$\frac{n(n＋1)}{2}$（高斯法）兩種解法。

對于相同的n，給出這兩種解法的求和結果和求解時間，并用相關數據進行測試。

• clock_t類型、clock()函數和CLOCKS_PER_SEC常量均在time.h頭文件中聲明。
• clock_t是時鐘數據類型（長整型數）
• clock()函數返回CPU時鐘計時單元數（以毫秒為單位）
• CLOCKSPER_SEC是一個常量，表示1秒包含的毫秒數。
• 表達式((float) t)/CLOCKS_PER_SEC返回t轉換成的秒數;

放碼

//文件名：exp1-1.cpp//求1+2+...+n
#include <stdio.h>
#include <time.h>       // clock_t, clock, CLOCKS_PER_SEC
#include <math.h>//方法1：老實累加
long add1(long n)     
{long i, sum = 0;for (i = 1; i <= n; i++)sum += i;return(sum);
}void AddTime1(long n)  /* 采用方法1的耗時統計 */
{clock_t t = clock();long sum = add1(n);t = clock() - t;printf("方法1:\n");printf("  結果:1～%d之和:%ld\n", n, sum);printf("  用時:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}//方法2：用公式
long add2(long n)     /* 方法2：求1+2+...+n */
{return(n * (n + 1) / 2);
}void AddTime2(long n) /* 采用方法2的耗時統計 */
{clock_t t = clock();long sum = add2(n);t = clock() - t;printf("方法2:\n");printf("  結果:1～%d之和:%ld\n", n, sum);printf("  用時:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}int main()
{int n;printf("n(大于1000000):");scanf("%d", &n);if (n < 1000000)return(0);AddTime1(n);AddTime2(n);return(1);
}

結果

n(大于1000000):99999999
方法1:結果:1～99999999之和:887459712用時:0.222000秒
方法2:結果:1～99999999之和:887459712用時:0.000000秒
請按任意鍵繼續. . .

常見算法時間函數的增長趨勢分析

說明

理解常見算法時間函數的增長情況。

對于1~n的每個整數n，輸${\log }_{2}n$ 、$\sqrt{n}$、$n$、$n{\log }_{2}n$、$n^2$、$n^3$、$2^n$ 和$n!$。

放碼

//文件名：exp1-2.cpp
#include <stdio.h>
#include <math.h>double log2(double x)	//求log2(x)
{return log10(x)/log10((double)2);
}long exponent(int n)	//求2^n
{long s=1;for (int i=1;i<=n;i++)s*=2;return s;
}long factorial(int n)	//求n!
{long s=1;for (int i=1;i<=n;i++)s*=i;return s;
}void fun(int n)
{printf("log2(n) sqrt(n)  n       nlog2(n)   n^2	    n^3	     2^n		n!\n");printf("===========================================================================\n");for (int i=1;i<=n;i++){printf("%5.2f\t",log2(double(i)));printf("%5.2f\t",sqrt((double)i));printf("%2d\t",i);printf("%7.2f\t",i*log2(double(i)));printf("%5d\t",i*i);printf("%7d\t",i*i*i);printf("%8d\t",exponent(i));printf("%10d\n",factorial(i));}
}int main()
{int n=10;fun(n);return 1;
}

結果

log2(n) sqrt(n)  n       nlog2(n)   n^2     n^3      2^n                n!
===========================================================================0.00    1.00    1         0.00     1         1        2                 11.00    1.41    2         2.00     4         8        4                 21.58    1.73    3         4.75     9        27        8                 62.00    2.00    4         8.00    16        64       16                242.32    2.24    5        11.61    25       125       32               1202.58    2.45    6        15.51    36       216       64               7202.81    2.65    7        19.65    49       343      128              50403.00    2.83    8        24.00    64       512      256             403203.17    3.00    9        28.53    81       729      512            3628803.32    3.16   10        33.22   100      1000     1024           3628800
請按任意鍵繼續. . .

設計性實驗

求素數個數

說明

通過對比同一問題不同解法的絕對執行時間 ，體會如何設計“好”的算法。

求1~n的素數個數。對于相同的n，給出這兩種解法的結果和求解時間，并用相關數據進行測試。

放碼

//文件名：exp1-3.cpp
#include <stdio.h>
#include <stdlib.h>
#include <time.h>		 	//clock_t, clock, CLOCKS_PER_SEC
#include <math.h>//------方法1-----------------------------------------------
bool prime1(long n) //方法1：判斷正整數n是否為素數
{long i;for (i = 2; i < n; i++)if (n % i == 0)return false; //若n不是素數,則退出并返回falsereturn true;
}void PrimeTime1(long n) //采用方法1的耗時統計
{long sum = 0, i;clock_t t = clock();for (i = 2; i <= n; i++)if (prime1(i))sum++;t = clock() - t;printf("方法1:\n");printf("  結果:2～%d的素數個數:%d\n", n, sum);printf("  用時:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}//------方法2-----------------------------------------------
bool prime2(long n) //方法2：判斷正整數n是否為素數
{long i;for (i = 2; i <= (int)sqrt((double)n); i++)//對n開方進行優化if (n % i == 0)return false; //若n不是素數,則退出并返回falsereturn true;
}
void PrimeTime2(long n) //采用方法2的耗時統計
{long sum = 0, i;clock_t t = clock();for (i = 2; i <= n; i++)if (prime2(i))sum++;t = clock() - t;printf("方法2:\n");printf("  結果:2～%d的素數個數:%d\n", n, sum);printf("  用時:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}//------方法3-----------------------------------------------
int countPrimes(long n) //方法3：埃拉托色尼篩選法，空間換時間，n不能過大，否則程序報錯
{bool *flag = (bool *)malloc(n * sizeof(bool));for (long i = 0; i < n; i++)//這步不能省略，否則得不到正確值flag[i] = 0;int count = 0;for (long i = 2; i < n; i++){if (flag[i] == 0){count++;for (long j = i; i * j < n; j++) {flag[i * j] = 1;}}}free(flag);return count;
}
void PrimeTime3(long n) //采用方法3的耗時統計
{long sum = 0;clock_t t = clock();sum = countPrimes(n);t = clock() - t;printf("方法3:\n");printf("  結果:2～%d的素數個數:%d\n", n, sum);printf("  用時:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}//------------------------------------------------------------
int main() {long n;printf("n（取值范圍[10000, 40000]）:");scanf("%d", &n);if (!(10000 <= n && n <= 40000)) return 0;PrimeTime1(n);PrimeTime2(n);PrimeTime3(n);return 1;
}

結果

n（取值范圍[10000, 40000]）:40000
方法1:結果:2～40000的素數個數:4203用時:0.236000秒
方法2:結果:2～40000的素數個數:4203用時:0.009000秒
方法3:結果:2～40000的素數個數:4203用時:0.001000秒
請按任意鍵繼續. . .

求連續整數階乘的和

說明

對于給定的正整數n，求1!+2!+3!+…+n !。給出一種時間復雜度為O(n)的解法。

放碼

//文件名：exp1-4.cpp
#include <stdio.h>//循環版
long Sum(int n) {long sum = 0, fact = 1;for (int i = 1; i <= n; i++) {fact *= i;sum += fact;}return sum;
}//TODO:遞歸版//------------------------------------------------------------
int main() {int n;printf("n(3-20):");scanf("%d", &n);if (n < 3 || n > 20) return 0;printf("1!+2!+…+%d!=%ld\n", n, Sum(n));return 1;
}

結果

n(3-20):15
1!+2!+…+15!=1443297817
請按任意鍵繼續. . .