一、編程思想和語言基礎王振昊緒論為什么要學習編程Oier的尷尬地位怎樣學好編程課表時間段安排2月1號2月2號2月3號2月4號2月5號上午講解（8：30-10：30）了解學生需求

語言：（含結構體與

基本語言技巧）暴力（含BFS、DFS）動態規劃及相關應用語言貪心二分（以例題和較深的講解為主）Dp的講解

數學（擴歐、唯一分解，二項式定理、快速冪）練習（10：30-11：30）語言題、答疑暴力題目、答疑動態規劃習題、答疑語言題+貪心+二分數學+Dp習題下午講解（14：30-17：00）遞歸二分貪心圖論（并查集、生成樹、最短路）遞歸與遞推

Dp的一些講解圖論的理解練習（6：00-8：00）語言題、遞歸習題、答疑二分、貪心簡單習題圖論習題、答疑語言題+貪心+二分Dp的簡單習題圖論習題（較基礎）王振昊薛鑫磊一、編程思想和語言基礎1.1編程思想1.2Ｃ／Ｃ＋＋語言初步1.3結構體（記錄類型）1.4高精度計算1.1編程思想

程序（program）是為實現特定目標或解決特定問題而用計算機語言編寫的命令序列的集合。為進行某活動或過程所規定的途徑。編程就是讓計算機為解決某個問題而使用某種程序設計語言編寫程序代碼，并最終得到結果的過程。為了使計算機能夠理解人的意圖，人類就必須要將需解決的問題的思路、方法、和手段通過計算機能夠理解的形式告訴計算機，使得計算機能夠根據人的指令一步一步去工作，完成某種特定的任務。這種人和計算機之間交流的過程就是編程。因此，一個好的程序員必須學會從計算機的角度去思考問題1.1編程思想舉幾個例子：Swap冒泡排序和插入排序輾轉相除法計算幾何1.1編程思想著名計算機科學家沃思提出一個公式：數據結構+算法=程序。實際上，一個程序除了以上兩個主要的要素外，還應當采用程序設計方法進行設計，并且用一種計算機語言來表示。因此，算法、數據結構、程序設計方法和語言工具4個方面是一個程序員所應具備的知識。1.1編程思想推薦幾本經典的書1.2Ｃ／Ｃ＋＋語言初步C語言是一種計算機程序設計語言，它既具有高級語言的特點，又具有匯編語言的特點。隨著微型計算機的日益普及,出現了許多C語言版本。由于沒有統一的標準,使得這些C語言之間出現了一些不一致的地方。為了改變這種情況,美國國家標準研究所(ANSI)為C語言制定了一套ANSI標準，成為現行的C語言標準。C語言是世界上最流行、使用最廣泛的高級程序設計語言之一。1.2Ｃ／Ｃ＋＋語言初步先從簡單的入手： A+BProblem:

輸入格式:

兩個自然數a和b(0<=a,b<=32767)

輸出格式:

一個數，即a和b的和1.2Ｃ／Ｃ＋＋語言初步程序：#include<stdio.h>;intmain(){inta,b;scanf("%d%d",&a,&b);printf("%d",a+b);}1.2Ｃ／Ｃ＋＋語言初步用程序使計算機按照題目描述過程得出結果稱為模擬NOIP中第一道題往往是模擬題，也是常說的送分題，要做對這樣的題，要求熟練掌握編程語言和簡單基本的算法簡單基本算法主要指：排序、求最大（最小）值等下面看道簡單的模擬題明明的隨機數題目描述：明明想在學校中請一些同學一起做一項問卷調查，為了實驗的客觀性，他先用計算機生成了N個1到1000之間的隨機整數（N≤100），對于其中重復的數字，只保留一個，把其余相同的數去掉，不同的數對應著不同的學生的學號。然后再把這些數從小到大排序，按照排好的順序去找同學做調查。請你協助明明完成“去重”與“排序”的工作。輸入格式：輸入有2行，第1行為1個正整數，表示所生成的隨機數的個數：N第2行有N個用空格隔開的正整數，為所產生的隨機數。輸出格式：輸出也是2行，第1行為1個正整數M，表示不相同的隨機數的個數。第2行為M個用空格隔開的正整數，為從小到大排好序的不相同的隨機數。明明的隨機數本題的幾種思路快速排序？冒泡排序？注意題目數據大小桶排序明明的隨機數#include<stdio.h>intmain(){intser_num[1001]={0};intn,m=0,t,i,j;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&t);ser_num[t]++;//計一個數出現的次數}明明的隨機數 for(i=0;i<=1000;i++) for(j=1;j<=ser_num[i];j++) if(ser_num[i]>1) m++; printf("%d\n",n); for(i=0;i<=1000;i++) for(j=1;j<=ser_num[i];j++) if(ser_num[i]>1) printf("%d",i); printf(“\n”); return0;}1.2Ｃ／Ｃ＋＋語言初步C++是一種面向對象的計算機程序設計語言。它是一種使用非常廣泛的計算機編程語言。C++是一種靜態數據類型檢查的、支持多重編程范式的通用程序設計語言。它支持過程化程序設計、數據抽象、面向對象程序設計、泛型程序設計等多種程序設計風格。參考書籍：C++Primer1.3結構體（記錄類型）結構體（struct），也叫結構，是由一系列具有相同類型或不同類型的數據構成的數據集合。

1.結構說明和結構變量定義

在TurboC中,結構也是一種數據類型,可以使用結構變量,因此,

象其它

類型的變量一樣,在使用結構變量時要先對其定義。

定義結構變量的一般格式為:

struct結構名

{

類型

變量名;

類型

變量名;

...

}結構變量;

結構名是結構的標識符不是變量名。

1.3結構體（記錄類型）

下面舉一個例子來說明怎樣定義結構變量。

structstring

{

charname[8];

intage;

charsex[2];

chardepart[20];

floatwage1,wage2,wage3,wage4,wage5;

}person;

1.3結構體（記錄類型）其實沒有什么題是必須用結構體來做的（除了用指針構建鏈表時），多用幾個變量可以達到同樣的效果。但用結構體可以增強代碼的完整性和可懂性。下面看道例題：

誰拿了最多獎學金

題目描述某校的慣例是在每學期的期末考試之后發放獎學金。發放的獎學金共有五種，獲取的條件各自不同：

1)院士獎學金，每人8000元，期末平均成績高于80分（>80），并且在本學期內發表1篇或1篇以上論文的學生均可獲得；

2)五四獎學金，每人4000元，期末平均成績高于85分（>85），并且班級評議成績高于80分（>80）的學生均可獲得；

3)成績優秀獎，每人2000元，期末平均成績高于90分（>90）的學生均可獲得；

4)西部獎學金，每人1000元，期末平均成績高于85分（>85）的西部省份學生均可獲得；

5)班級貢獻獎，每人850元，班級評議成績高于80分（>80）的學生干部均可獲得；只要符合條件就可以得獎，每項獎學金的獲獎人數沒有限制，每名學生也可以同時獲得多項獎學金。例如姚林的期末平均成績是87分，班級評議成績82分，同時他還是一位學生干部，那么他可以同時獲得五四獎學金和班級貢獻獎，獎金總數是4850元。現在給出若干學生的相關數據，請計算哪些同學獲得的獎金總數最高（假設總有同學能滿足獲得獎學金的條件）。

誰拿了最多獎學金輸入格式輸入的第一行是一個整數N（1<=N<=100），表示學生的總數。接下來的N行每行是一位學生的數據，從左向右依次是姓名，期末平均成績，班級評議成績，是否是學生干部，是否是西部省份學生，以及發表的論文數。姓名是由大小寫英文字母組成的長度不超過20的字符串（不含空格）；期末平均成績和班級評議成績都是0到100之間的整數（包括0和100）；是否是學生干部和是否是西部省份學生分別用一個字符表示，Y表示是，N表示不是；發表的論文數是0到10的整數（包括0和10）。每兩個相鄰數據項之間用一個空格分隔。輸出格式輸出包括三行，第一行是獲得最多獎金的學生的姓名，第二行是這名學生獲得的獎金總數。如果有兩位或兩位以上的學生獲得的獎金最多，輸出他們之中在輸入文件中出現最早的學生的姓名。第三行是這N個學生獲得的獎學金的總數。

誰拿了最多獎學金#include<cstdio>intmain(){charname[101][30],ganbu[101][5],xibu[101][5];intqimo[101],banji[101],wen[101],money[101]={0};intn,i,j=0,k,l=0;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%s%d%d%s%s%d",&name[i],&qimo[i],&banji[i],&ganbu[i],&xibu[i],&wen[i]);if(qimo[i]>80&&wen[i]>=1)money[i]+=8000;if(qimo[i]>85&&banji[i]>80)money[i]+=4000;if(qimo[i]>90)money[i]+=2000;if(qimo[i]>85&&xibu[i][0]=='Y')money[i]+=1000;if(banji[i]>80&&ganbu[i][0]=='Y')money[i]+=850;if(money[i]>j){j=money[i];k=i;}l+=money[i];}printf("%s\n%d\n%d\n",name[k],money[k],l);return0;}1.4高精度計算利用計算機進行數值計算，有時會遇到這樣的問題：有些計算要求精度高，希望計算的數的位數可達幾十位甚至幾百位，雖然計算機的計算精度也算較高了，但因受到硬件的限制，往往達不到實際問題所要求的精度。我們可以利用程序設計的方法去實現這樣的高精度計算。介紹常用的幾種高精度計算的方法。 高精度計算中需要處理好以下幾個問題： (1)數據的接收方法和存貯方法 數據的接收和存貯：當輸入的數很長時，可采用字符串方式輸入，這樣可輸入數字很長的數，利用字符串函數和操作運算，將每一位數取出，存入數組中。另一種方法是直接用循環加數組方法輸入數據。 voidinit(inta[])//傳入一個數組 {strings; cin>>s;//讀入字符串s a[0]=s.length();//用a[0]計算字符串s的位數 for(i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0';//將數串s轉換為數組a，并倒序存儲 }另一種方法是直接用循環加數組方法輸入數據。1.4高精度計算2)高精度數位數的確定位數的確定：接收時往往是用字符串的，所以它的位數就等于字符串的長度。(3)進位,借位處理加法進位：c[i]=a[i]+b[i];if(c[i]>=10){c[i]%=10;++c[i+1];}減法借位：if(a[i]<b[i]){--a[i+1];a[i]+=10;}c[i]=a[i]-b[i];乘法進位：c[i+j-1]=a[i]*b[j]+x+c[i+j-1];x=c[i+j-1]/10;c[i+j-1]%=10;(4)商和余數的求法商和余數處理：視被除數和除數的位數情況進行處理.【例1】高精度加法。輸入兩個正整數，求它們的和。【分析】輸入兩個數到兩個變量中，然后用賦值語句求它們的和，輸出。但是，我們知道，在C++語言中任何數據類型都有一定的表示范圍。而當兩個被加數很大時，上述算法顯然不能求出精確解，因此我們需要尋求另外一種方法。在讀小學時，我們做加法都采用豎式方法，如圖1。這樣，我們方便寫出兩個整數相加的算法。856+2551111

圖1A3A2A1+B3B2B1

C4C3C2C1

圖2

如果我們用數組A、B分別存儲加數和被加數，用數組C存儲結果。則上例有A[1]=6，A[2]=5，A[3]=8，B[1]=5，B[2]=5，B[3]=2，C[4]=1，C[3]=1，C[2]=1，C[1]=1，兩數相加如圖2所示。因此，算法描述如下：intc[100];voidadd(inta[],intb[])//a,b,c都為數組，分別存儲被加數、加數、結果{inti=1,x=0;//x是進位while((i<=a數組長度)||(i<=b數組的長度)){c[i]=a[i]+b[i]+x; //第i位相加并加上次的進位x=c[i]/10; //向高位進位c[i]%=10;//存儲第i位的值i++;//位置下標變量}}

通常，讀入的兩個整數用可用字符串來存儲，程序設計如下：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){ chara1[100],b1[100]; inta[100],b[100],c[100],lena,lenb,lenc,i,x; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); gets(a1); gets(b1); //輸入加數與被加數 lena=strlen(a1); lenb=strlen(b1); for(i=0;i<=lena-1;i++)a[lena-i]=a1[i]-48; //加數放入a數組 for(i=0;i<=lenb-1;i++)b[lenb-i]=b1[i]-48;//加數放入b數組 lenc=1; x=0;

while(lenc<=lena||lenc<=lenb) { c[lenc]=a[lenc]+b[lenc]+x;//兩數相加 x=c[lenc]/10; c[lenc]%=10; lenc++; } c[lenc]=x; if(c[lenc]==0) lenc--;//處理最高進位 for(i=lenc;i>=1;i--) cout<<c[i];//輸出結果 cout<<endl; return0;}【例2】高精度減法。輸入兩個正整數，求它們的差。【算法分析】類似加法，可以用豎式求減法。在做減法運算時，需要注意的是：被減數必須比減數大，同時需要處理借位。高精度減法的參考程序：#include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){ inta[256],b[256],c[256],lena,lenb,lenc,i; charn[256],n1[256],n2[256]; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c));

printf("Inputminuend:");gets(n1);//輸入被減數 printf("Inputsubtrahend:");gets(n2);//輸入減數 if(strlen(n1)<strlen(n2)||(strlen(n1)==strlen(n2)&&strcmp(n1,n2)<0))//strcmp()為字符串比較函數，當n1==n2,返回0;//n1>n2時，返回正整數；n1<n2時，返回負整數 {//處理被減數和減數，交換被減數和減數 strcpy(n,n1);//將n1數組的值完全賦值給n數組 strcpy(n1,n2); strcpy(n2,n); cout<<"-";//交換了減數和被減數，結果為負數 }

lena=strlen(n1);lenb=strlen(n2); for(i=0;i<=lena-1;i++)a[lena-i]=int(n1[i]-'0');//被減數放入a數組 for(i=0;i<=lenb-1;i++)b[lenb-i]=int(n2[i]-'0');//減數放入b數組

i=1; while(i<=lena||i<=lenb) { if(a[i]<b[i]) { a[i]+=10;//不夠減，那么向高位借1當10 a[i+1]--; } c[i]=a[i]-b[i];//對應位相減 i++; } lenc=i; while((c[lenc]==0)&&(lenc>1))lenc--;//最高位的0不輸出 for(i=lenc;i>=1;i--)cout<<c[i];//輸出結果 cout<<endl; return0;}【例3】高精度乘法。輸入兩個正整數，求它們的積。【算法分析】

類似加法，可以用豎式求乘法。在做乘法運算時，同樣也有進位，同時對每一位進行乘法運算時，必須進行錯位相加，如圖3、圖4。分析c數組下標的變化規律，可以寫出如下關系式：ci=c’i+c”i+…由此可見，ci跟a[i]*b[j]乘積有關，跟上次的進位有關，還跟原ci的值有關，分析下標規律，有c[i+j-1]=a[i]*b[j]+x+c[i+j-1];x=c[i+j-1]/10;c[i+j-1]%=10;856×254280171221400

圖3A3A2A1

×B2B1

C’4C’3C’2C’1

C”5C”4C”3C”2

C6C5C4C3C2C1圖4高精度乘法的參考程序：#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){chara1[100],b1[100];inta[100],b[100],c[100],lena,lenb,lenc,i,j,x;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));gets(a1);gets(b1);lena=strlen(a1);lenb=strlen(b1);for(i=0;i<=lena-1;i++)a[lena-i]=a1[i]-48;for(i=0;i<=lenb-1;i++)b[lenb-i]=b1[i]-48;

for(i=1;i<=lena;i++) { x=0;//用于存放進位 for(j=1;j<=lenb;j++)//對乘數的每一位進行處理 { c[i+j-1]=a[i]*b[j]+x+c[i+j-1];//當前乘積+上次乘積進位+原數 x=c[i+j-1]/10; c[i+j-1]%=10; } c[i+lenb]=x;//進位 } lenc=lena+lenb; while(c[lenc]==0&&lenc>1)//刪除前導0 lenc--; for(i=lenc;i>=1;i--) cout<<c[i]; cout<<endl; return0;}【例4】高精度除法。輸入兩個正整數，求它們的商（做整除）。【算法分析】

做除法時，每一次上商的值都在０～９，每次求得的余數連接以后的若干位得到新的被除數，繼續做除法。因此，在做高精度除法時，要涉及到乘法運算和減法運算，還有移位處理。當然，為了程序簡潔，可以避免高精度除法，用0～9次循環減法取代得到商的值。這里，我們討論一下高精度數除以單精度數的結果，采取的方法是按位相除法。#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intmain(){ chara1[100],c1[100]; inta[100],c[100],lena,i,x=0,lenc,b; memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); gets(a1); cin>>b; lena=strlen(a1); for(i=0;i<=lena-1;i++) a[i+1]=a1[i]-48;

for(i=1;i<=lena;i++)//按位相除 { c[i]=(x*10+a[i])/b; x=(x*10+a[i])%b; } lenc=1; while(c[lenc]==0&&lenc<lena) lenc++;//刪除前導0 for(i=lenc;i<=lena;i++) cout<<c[i]; cout<<endl; return0;}

實質上，在做兩個高精度數運算時候，存儲高精度數的數組元素可以不僅僅只保留一個數字，而采取保留多位數（例如一個整型或長整型數據等），這樣，在做運算（特別是乘法運算）時，可以減少很多操作次數。例如圖5就是采用4位保存的除法運算，其他運算也類似。具體程序可以修改上述例題予以解決，程序請讀者完成。示例：123456789÷45=1’2345’6789÷45=274’3484∵1/45=0，1%45=1∴取12345/45=274∵12345%45=15∴取156789/45=3484∴答案為2743484,余數為156789%45=9圖5

【例5】高精除以高精，求它們的商和余數。 【算法分析】 高精除以低精是對被除數的每一位（這里的“一位”包含前面的余數，以下都是如此）都除以除數，而高精除以高精則是用減法模擬除法，對被除數的每一位都減去除數，一直減到當前位置的數字（包含前面的余數）小于除數（由于每一位的數字小于10，所以對于每一位最多進行10次計算）具體實現程序如下：

#include<iostream>#include<cstring>usingnamespacestd;inta[101],b[101],c[101],d,i;voidinit(inta[]){strings; cin>>s;//讀入字符串s a[0]=s.length();//用a[0]計算字符串s的位數 for(i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0';//將數串s轉換為數組a，并倒序存儲．}voidprint(inta[])//打印輸出{ if(a[0]==0){cout<<0<<endl;return;} for(inti=a[0];i>0;i--)cout<<a[i]; cout<<endl; return;}

intcompare(inta[],intb[]) //比較a和b的大小關系，若a>b則為1，a<b則為-1,a=b則為0{ if(a[0]>b[0])return1;//a的位數大于b則a比b大 if(a[0]<b[0])return-1;//a的位數小于b則a比b小 for(i=a[0];i>0;i--)//從高位到低位比較 { if(a[i]>b[i])return1; if(a[i]<b[i])return-1; } return0;//各位都相等則兩數相等。}voidnumcpy(intp[],intq[],intdet)//復制p數組到q數組從det開始的地方{ for(inti=1;i<=p[0];i++)q[i+det-1]=p[i]; q[0]=p[0]+det-1;}

voidjian(inta[],intb[])//計算a=a-b{ intflag,i; flag=compare(a,b);//調用比較函數判斷大小 if(flag==0){a[0]=0;return;}//相等 if(flag==1)//大于 { for(i=1;i<=a[0];i++) { if(a[i]<b[i]){a[i+1]--;a[i]+=10;}//若不夠減則向上借一位 a[i]-=b[i]; } while(a[0]>0&&a[a[0]]==0)a[0]--;//修正a的位數 return; }}

voidchugao(inta[],intb[],intc[]){ inttmp[101]; c[0]=a[0]-b[0]+1; for(inti=c[0];i>0;i--) { memset(tmp,0,sizeof(tmp));//數組清零 numcpy(b,tmp,i); while(compare(a,tmp)>=0){c[i]++;jian(a,tmp);}//用減法來模擬 } while(c[0]>0&&c[c[0]]==0)c[0]--; return;}

intmain(){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c)); init(a);init(b); chugao(a,b,c); print(c); print(a); return0;}

【例6】回文數【問題描述】 若一個數（首位不為零）從左向右讀與從右向左讀都是一樣，我們就將其稱之為回文數。例如：給定一個10進制數56，將56加65（即把56從右向左讀），得到121是一個回文數。又如，對于10進制數87，STEPl：87＋78=165STEP2：165＋561=726STEP3：726＋627＝1353STEP4：1353+3531=4884在這里的一步是指進行了一次N進制的加法，上例最少用了4步得到回文數4884。寫一個程序，給定一個N（2＜N＜＝10或N=16）進制數M．求最少經過幾步可以得到回文數。如果在30步以內（包含30步）不可能得到回文數，則輸出“Impossible”【輸入樣例】：987【輸出樣例】：6【算法分析】N進制運算1、當前位規范由%10改為%n2、進位處理由/10改為/n3、其他運算規則不變

【參考程序】#include<iostream>#include<cstring>usingnamespacestd;intn,a[101],b[101],ans,i;voidinit(inta[])//將數串s轉化為整數數組a{ strings; cin>>n>>s;//讀入字符串s memset(a,0,sizeof(a));//數組a清0 a[0]=s.length();//用a[0]計算字符串s的位數 for(i=1;i<=a[0];i++) if(s[a[0]-i]>='0'&&s[a[0]-i]<='9')a[i]=s[a[0]-i]-'0'; elsea[i]=s[a[0]-i]-'A'+10;}boolcheck(inta[])//判別整數數組a是否為回文數{ for(i=1;i<=a[0];i++) if(a[i]!=a[a[0]-i+1])returnfalse; returntrue;}

voidjia(inta[])//整數數組a與其反序數b進行n進制加法運算{ for(inti=1;i<=a[0];i++)b[i]=a[a[0]-i+1];//反序數b for(inti=1;i<=a[0];i++)a[i]+=b[i];//逐位相加 for(inti=1;i<=a[0];i++)//處理進位 {a[i+1]+=a[i]/n; a[i]%=n; } if(a[a[0]+1]>0)a[0]++;//修正新的a的位數（a+b最多只能的一個進位）}intmain(){ init(a); if(check(a)){cout<<0<<endl;return0;} ans=0;//步數初始化為0 while(ans++<=30) {jia(a); if(check(a)){cout<<ans<<endl;return0;} } cout<<"Impossible";//輸出無解信息 return0;}【上機練習】1、求N！的值【問題描述】

用高精度方法，求N！的精確值(N以一般整數輸入)。【輸入樣例】ni.in10【輸出樣例】ni.out36288002、求A/B高精度值【問題描述】

計算A/B的精確值，設A，B是以一般整數輸入，計算結果精確小數后20位。【輸入樣例】ab.in43【輸出樣例】ab.out4/3=1.33333333333333333333【輸入樣例】ab.in65【輸出樣例