printf("%lu\n", sizeof(int));開胃菜1：? ? 求小于1000的自然數(shù)中所有3或5的倍數(shù)之和。

方法一：遍歷1~1000中能被3或5整除的數(shù)并相加

參考程序如下所示

int ans = 0;

for(int i = 1; i < 1000; i++){

????if(i % 3 == 0 || i % 5 == 0){

????????ans += i;

????}

}

printf("%d\n",ans);//233168

方法二：尋找規(guī)律，3、5的倍數(shù)即等差數(shù)列，重復(fù)的部分是15的倍數(shù)，如下所示：

?1? 2? 3? 4? 5

?6? 7? 8? 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

26 27 28 29 30

?等差數(shù)列求和公式=（首項+末項）*數(shù)量/2，可得1000以內(nèi)自然數(shù)中3的倍數(shù)之和=（3+999）*333/2

參考程序如下所示

int t3 = (3 + 999) * 333 / 2;

int t5 = (5?+ 995) * 199?/ 2;

int t15?= (15?+ 990) *?66?/ 2;

printf("%d\n", t3 + t5 - t15);//233168

知識點1：時間復(fù)雜度——不是執(zhí)行時間，在數(shù)據(jù)規(guī)模發(fā)生變化時，執(zhí)行時間如何變化

表示方式——O（n）

? ? ? ? ? ? ? ? n=1000? ? ? ? n=4000? ? ? ? ??

方法一? ? ?1000? ? ? ? ? ? ?4000? ? ? ? ? ?O(n)線性級

方法二? ? ?4? ? ? ? ? ? ? ? ? ? 4? ? ? ? ? ? ? ? O(1)常數(shù)級

代碼——>執(zhí)行時間——>復(fù)雜度

????例如下程序：

int?n;

//scanf

for(int i = 0; i < n / 2; i++){

????//printf

}

for(int i = 0; i < n; i++){

????//printf

}

for(int i = 0; i < n; i++){

????for(int j?= 0; j < n;?j++){

????????//printf

????}

}

n/2+n+n*n=n*n+n*2/3

刪常數(shù)n*n+n——>保留最大項n*n——>時間復(fù)雜度為O(n^2)

常見時間復(fù)雜度：

????O(1)?常數(shù)級?幾條語句

? ? O(logn)?對數(shù)級?二分查找

? ? O(n)?線性級?循環(huán)

? ? O(nlogn)?線性對數(shù)?歸并排序

? ? O(n^2)?平方?冒泡排序

? ? O(n^3)? ??O(n!)? ?O(2^n)......

練習程序：

int x = 0, s = 0, n;

scanf("%d", &n);

while(s < n){

????x++;

????s += x;

}

printf("%d\n", x);//n=100，x=14? ?n=400，x=20 ?n=4000，x約等于280

上面程序的分析：s為x的累加，即s = 1+ 2......+x=(1+x)*x/2=(x^2+x)/2<n

——>x^2<n——>x=>時間復(fù)雜度

問題1：方法O(nlogn)執(zhí)行時間一定比O(n^2)快嗎？

????????????答：不一定（原因好好琢磨琢磨）

開胃菜2：斐波那契數(shù)列（1，2，3，5，8，13，21，34，55，89，......）中不超過四百萬的項，求其中偶數(shù)的項之和。

方法一：循環(huán)判斷數(shù)列中被2整除的數(shù)并累加求和

int num[4000005];//大數(shù)組保存在全局變量，存在棧區(qū)存在風險,+5防止數(shù)組越界

參考程序如下所示

int main(){

????num[1] = num[2] = 1;

????int ans = 0;

????for(int i = 3; 1; i++){

????????num[i] =?num[i - 1] + num[n - 2];

????????if(num[i] >= 4000000){

????????????break;

????????}

????????if(num[i]%2 == 0){

????????????ans += num[i];

????????}

????}

????printf("%d\n", ans);//4613732

????return 0;

}

方法二：找規(guī)律：a，b,a+b,a+2b,2a+3b,3a+5b......

1 1 2 3 5 8 13...

參考程序如下所示

int a = 1, b = 1, ans = 0;

while(b < 4000000){

????if?(b%2 == 0){

????????ans += b;

????}

????b += a;

????a = b - a;

}

printf("%d\n", ans);//4613732

知識點2：空間復(fù)雜度——不是內(nèi)存空間，在數(shù)據(jù)規(guī)模發(fā)生變化時，內(nèi)存空間如何變化

方法一空間復(fù)雜度O(n),方法二空間復(fù)雜度O(1)

常見的空間復(fù)雜度

????O(1)?常數(shù)?幾個變量

? ? O(n)?線性?一維數(shù)組

??? O(n^2)?線性?二維數(shù)組?

??? O(logn)?遞歸?深度? ?

復(fù)習C語言基礎(chǔ)

1、指針

int?a = 5;

printf("%lu\n", sizeof(int));//%lu無符號長整形格式輸出——>4

int *p = &a;

printf("%lu\n", sizeof(p));//8

printf("%p\n%p\n",?&a,p);//%p指針輸出相同

*p = 20;

printf("%d\n", a);//20

int num[10] = {1};//num[3]=0?

printf("%p\n%p\n", num, &num[0]);//數(shù)組名為數(shù)組首地址

int *q=num;//&num[0]

q[1] = 99;

printf("%d\n",?num[1]);//99

printf("num size ->%lu",sizeof(num));//40

printf("*q?size ->%lu",sizeof(q));//8

2、結(jié)構(gòu)體——>把幾個類型組合成一個類型

定義：

struct?類型名(node){

????類型1(int)?變量1(a)；

????類型2(double)?變量2(b)；

}；

使用結(jié)構(gòu)體：struct node x;

????類型（struct node）?類型名(x)——>定義

????類型名.a——>成員訪問

使用結(jié)構(gòu)體指針：struct?xxx *p = &x;

????類型（struct node *）?類型名(p)——>定義

????類型名->a——>成員訪問

typedef struct node{

????int a;

????double b;

}aaaa;//重定義結(jié)構(gòu)體

aaaa y;//定義結(jié)構(gòu)體變量

3、動態(tài)內(nèi)存管理

cpprerfence.com——C++、C參考手冊

手動內(nèi)存申請

1）malloc——僅申請

2）calloc——申請并清零

3）realloc——重新申請

4）free——釋放空間

#include <stdlib.h>//引用頭文件

int *num;

num = (int *)malloc(10000000*sizeof(int));//使用堆區(qū)空間

......

free(num);

總結(jié)：

時間復(fù)雜度、空間復(fù)雜度、C語言基礎(chǔ)復(fù)習指針、結(jié)構(gòu)體、動態(tài)內(nèi)存管理